Nim is Easy, Chess is Hard — But Why?? ∗

The game of chess appears to be hard. According to authoritative sources, this is due to the extremely large number of possible chess moves. We refute this argumentation by showing that simple games of moderate size — as an example we consider nim — have a larger number of moves than chess, yet possess a very easy winning strategy. So perhaps chess has also an easy strategy which remains elusive? We argue that this is rather unlikely, in view of several high-complexity aspects of chess, notably the proven Exptime-completeness of n × n chess. 1 Why is Nim Easy? In nim, a finite number of piles of finitely many marbles is given. Two players alternate in selecting a pile and removing from it any positive number of marbles, possibly the entire pile. The player first unable to move loses and the opponent wins. Nim is easy. Why? Because it has an easy perfect strategy: write the number of marbles in each pile in binary, and “add ” them without carry, an addition also known as XOR (Exclusive Or), denoted by ⊕. If the sum is 0, you better be a gentle(wo)man and offer your opponent to move first, because you can win as player II. If the sum is nonzero you can move first and make it 0, thus winning. Example. Consider 3 piles of sizes 1,2,3. Player I, say, moves 3 → 1, to the position (1, 2, 1). Now player II removes the entire pile of size 2, landing in the position (1, 1). Then player I is forced to take one of the piles of size 1, player II takes the other, winning. In fact, since 1 ⊕ 2 ⊕ 3 = 0, player II can win for every beginning move of player I