How to use the nim game solver
- Choose the game: Nim, last wins, Nim, last loses (misere) or a subtraction game.
- Type the heap sizes separated by spaces or commas. For a subtraction game, also type the amounts a player may take.
- Read whether the player to move wins or loses with best play.
- See every winning move, the nim-sum and the binary table, or the Grundy values for a subtraction game.
Formula
Nim-sum = XOR (binary addition without carrying) of all the heap sizes
Normal play: the player to move wins exactly when the nim-sum is not 0
Winning move: reduce a heap of size s to s XOR nim-sum when that is smaller than s
Subtraction game: Grundy value g(n) = smallest whole number not among g(n - m) for allowed m; XOR the heaps' Grundy values
In misere Nim the last player to take loses. It is played like normal Nim until every heap has at most 1 object. Then the player to move loses if the number of heaps of size 1 is odd.
Three positions
Heaps 3, 4 and 5 have a nim-sum of 3 XOR 4 XOR 5 = 2, so the player to move wins. The only winning move is to take 2 from the heap of 3, leaving 1, 4 and 5 with a nim-sum of 0. The heaps 1, 2 and 3 have a nim-sum of 0, so the player to move loses, whatever they do. In the misere game 1, 2 and 3 is also lost for the player to move.
In a subtraction game where a player may take 1, 3 or 4, the Grundy values of heap sizes 0 to 6 are 0, 1, 0, 1, 2, 3, 2 and then repeat every 7. For heaps of 10, 15 and 22 the values are 1, 1 and 1 with an XOR of 1, so the player to move wins, with four winning moves: take 1 or 3 from the 10, take 1 from the 15, or take 1 from the 22.
Why the nim-sum works
A position with nim-sum 0 has the property that every move changes the nim-sum to something other than 0, and from any position with nonzero nim-sum there is a move back to 0. The player who can always move back to nim-sum 0 eventually takes the last object. So positions with nim-sum 0 are lost for the player to move, and all others are won. The page checks its answers against a full search of the game tree for small positions.
Binary tools that help are the bitwise calculator and the binary translator. For another recursive puzzle see the Tower of Hanoi move generator, and for counting see the combinations and permutations calculator.
Subtraction games and Grundy values
A subtraction game lets a player remove only certain amounts from a single heap. Each heap size gets a Grundy value, the smallest whole number that none of its reachable positions has. Several heaps then combine by XOR, exactly as in Nim, because every heap behaves like a Nim heap of that size. This idea, the Sprague-Grundy theorem, applies to any game where the last player to move wins.
Assumptions and limits
- In Nim a move removes one or more objects from a single heap. Up to 20 heaps of up to a billion objects are allowed.
- Normal play means the player who cannot move loses. Misere play means the player who takes the last object loses.
- In subtraction games each heap is up to 5,000 and the allowed amounts are whole numbers from 1 to 5,000, normal play only.
- Both players are assumed to play perfectly.
Frequently asked questions
How do you win at Nim?
Make the nim-sum of the heaps equal to 0 on every move. Compute the XOR of all heap sizes, and if it is not zero, reduce one heap to its size XOR the nim-sum.
What is the nim-sum?
It is the XOR of the heap sizes: write each in binary and add the columns without carrying. For 3, 4 and 5 it is 011 XOR 100 XOR 101 = 010, which is 2.
How is misere Nim different?
The player who takes the last object loses. The strategy is the same as in normal Nim until a move would leave only heaps of size 1, where you leave an odd number of them for the opponent.
Does this work for games other than Nim?
Any game that is a sum of independent heaps, where the last mover wins, can be solved by XORing Grundy values. The subtraction game option shows how.