Nim - Mathematical Theory

Mathematical Theory

Nim has been mathematically solved for any number of initial heaps and objects; that is, there is an easily calculated way to determine which player will win and what winning moves are open to that player. In a game that starts with heaps of three, four, and five, the first player will win with optimal play, whether the misère or normal play convention is followed.

The key to the theory of the game is the binary digital sum of the heap sizes, that is, the sum (in binary) neglecting all carries from one digit to another. This operation is also known as "exclusive or" (xor) or "vector addition over GF(2)". Within combinatorial game theory it is usually called the nim-sum, as will be done here. The nim-sum of x and y is written x ⊕ y to distinguish it from the ordinary sum, x + y. An example of the calculation with heaps of size 3, 4, and 5 is as follows:

Binary Decimal 011₂ 3₁₀ Heap A 100₂ 4₁₀ Heap B 101₂ 5₁₀ Heap C --- 010₂ 2₁₀ The nim-sum of heaps A, B, and C, 3 ⊕ 4 ⊕ 5 = 2

An equivalent procedure, which is often easier to perform mentally, is to express the heap sizes as sums of distinct powers of 2, cancel pairs of equal powers, and then add what's left:

3 = 0 + 2 + 1 = 2 1 Heap A 4 = 4 + 0 + 0 = 4 Heap B 5 = 4 + 0 + 1 = 4 1 Heap C --- 2 = 2 What's left after canceling 1s and 4s

In normal play, the winning strategy is to finish every move with a Nim-sum of 0. This is always possible if the Nim-sum is not zero before the move. If the Nim-sum is zero, then the next player will lose if the other player does not make a mistake. To find out which move to make, let X be the Nim-sum of all the heap sizes. Take the Nim-sum of each of the heap sizes with X, and find a heap whose size decreases. The winning strategy is to play in such a heap, reducing that heap to the Nim-sum of its original size with X. In the example above, taking the Nim-sum of the sizes is X = 3 ⊕ 4 ⊕ 5 = 2. The Nim-sums of the heap sizes A=3, B=4, and C=5 with X=2 are

A ⊕ X = 3 ⊕ 2 = 1

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

The only heap that is reduced is heap A, so the winning move is to reduce the size of heap A to 1 (by removing two objects).

As a particular simple case, if there are only two heaps left, the strategy is to reduce the number of objects in the bigger heap to make the heaps equal. After that, no matter what move your opponent makes, you can make the same move on the other heap, guaranteeing that you take the last object.

When played as a misère game, Nim strategy is different only when the normal play move would leave no heap of size two or larger. In that case, the correct move is to leave an odd number of heaps of size one (in normal play, the correct move would be to leave an even number of such heaps).

In a misère game with heaps of sizes three, four and five, the strategy would be applied like this:

A B C Nim-sum 3 4 5 010₂=2₁₀ I take 2 from A, leaving a sum of 000, so I will win. 1 4 5 000₂=0₁₀ You take 2 from C 1 4 3 110₂=6₁₀ I take 2 from B 1 2 3 000₂=0₁₀ You take 1 from C 1 2 2 001₂=1₁₀ I take 1 from A 0 2 2 000₂=0₁₀ You take 1 from C 0 2 1 011₂=3₁₀ The normal play strategy would be to take 1 from B, leaving an even number (2) heaps of size 1. For misère play, I take the entire B heap, to leave an odd number (1) of heaps of size 1. 0 0 1 001₂=1₁₀ You take 1 from C, and lose.

The previous strategy for a misère game can be easily implemented (for example in Python, below).

def nim(heaps, misere=True): """Computes next move for Nim in a normal or misère (default) game, returns tuple (chosen_heap, nb_remove)""" X = reduce(lambda x,y: x^y, heaps) if X == 0: # Will lose unless all non-empty heaps have size one if max(heaps) > 1: print "You will lose :(" for i, heap in enumerate(heaps): if heap > 0: # Empty any (non-empty) heap chosen_heap, nb_remove = i, heap break else: sums = chosen_heap = sums.index(True) nb_remove = heaps - (heaps^X) heaps_twomore = 0 for i, heap in enumerate(heaps): n = heap-nb_remove if chosen_heap == i else heap if n>1: heaps_twomore += 1 # If move leaves no heap of size 2 or larger, leave an odd (misère) or even (normal) number of heaps of size 1 if heaps_twomore == 0: chosen_heap = heaps.index(max(heaps)) heaps_one = sum(t==1 for t in heaps) # misère (resp. normal) strategy: if it is even (resp. odd) make it odd (resp. even), else do not change nb_remove = heaps-1 if heaps_one%2!=misere else heaps return chosen_heap, nb_remove