Nim

Nim looks like a game of nerve: a few heaps of matchsticks, two players, and a vague sense that you should leave your opponent “something awkward”. It isn’t. Nim is completely solved, and the solution fits on the back of a matchbox: write the heap sizes in binary, add them up without carrying, and try to leave zero.

That makes it the rare game where learning the theory turns you from coin-flip to unbeatable in a single sitting. The Hard computer already knows it.

How to play

The board starts with several heaps. The classic setup, and the default here, is three heaps of 3, 4 and 5.

• Players alternate turns. On your turn you pick one heap and remove any number of objects from it: one, several, or the whole heap.
• You must take at least one object. You may not pass, and you may not split a take across two heaps.
• The game ends when every heap is empty.
• Under the normal rule, the player who takes the last object wins. Under the misère rule, the player who takes the last object loses.

Because every turn removes at least one object, the game always ends, and it can never be a draw. Someone takes the last one.

A worked example

Start from 3-4-5 under the normal rule. Write each heap in binary, one column for 4s, 2s and 1s:

The nim-sum row marks each column 1 if it holds an odd number of 1s, and 0 if even. Here only the 2s column is odd, so the nim-sum is 2. It is not zero, so the player to move can win. The job is to make every column even with a single move.

1. Only heap A has a 1 in the 2s column. Changing A from 3 (011) to 1 (001) fixes that column and leaves the others alone. Take 2 from heap A. Now the heaps are 1-4-5: 001, 100, 101. Every column is even; the nim-sum is 0.
2. Your opponent takes 3 from C, leaving 1-4-2. In binary that is 001, 100, 010: all three columns are odd, nim-sum 7. Find the heap with a 1 in the highest odd column (the 4s): that is B. Change B to 4 XOR 7 = 3. Take 1 from heap B, leaving 1-3-2 (001, 011, 010), nim-sum 0 again.
3. They empty heap B, leaving 1-0-2. Nim-sum is 3. Reduce C to 2 XOR 3 = 1: take 1 from heap C, leaving 1-0-1.
4. Two single objects. They take one, you take the other, and you took the last object. You win.

Notice the rhythm: they hand you an odd column, you make it even. They can never hand it back, because it is already even when it reaches them.

Strategy

Beginner: count the small endings

Learn the positions you can see at a glance. One heap alone: take all of it. Two equal heaps: you are in trouble, because whatever your opponent does to one, you can do to the other. Two unequal heaps: make them equal. The pair rule is the whole game in miniature.

Intermediate: pair up the powers of two

Split each heap into powers of two: 5 is 4 + 1, 3 is 2 + 1. Any power of two that appears an even number of times cancels out. If everything cancels, the position is lost for the player to move. If something is left over, the leftover is the nim-sum, and your move should cancel it.

Advanced: finding the move quickly

Compute the nim-sum s. Look at its highest 1 bit and pick any heap that has a 1 in that column. Reduce that heap to (heap XOR s). That new value is always smaller than the heap, so the move is legal, and it flips exactly the odd columns to even. There can be more than one heap that works; any of them wins.

Misère: the one-line adjustment

Misère Nim is played exactly like normal Nim until the moment your move would leave no heap bigger than 1. At that moment, leave an odd number of single-object heaps instead of an even one, so your opponent is forced to take the last. In practice: when only one heap has two or more objects left, either empty it or cut it to 1, whichever leaves an odd count of 1s. The worked example in misère goes the same way until 1-0-2, where you take the whole heap of 2 and leave a single object for your opponent.

The idea underneath

The nim-sum is the binary XOR of the heap sizes: add in binary but drop every carry, so each column is 1 if it holds an odd number of 1s. Charles Bouton proved in 1901 what is now called Bouton’s theorem: in normal-play Nim, the player to move loses with best play exactly when the nim-sum is zero.

The proof is three short facts:

• The empty board has nim-sum zero, and the player facing it has lost, because the opponent just took the last object.
• From zero, every move leads to non-zero. A move changes one heap, so it changes at least one bit of that heap, which makes that column’s count odd.
• From non-zero, some move leads to zero. Take the heap described in the advanced strategy; reducing it to heap XOR s is legal and zeroes every column.

So a player who hands over zero can keep doing it until the board is empty on the opponent’s turn. Zero positions are losses for the mover and non-zero positions are wins, which is why the Hard computer can tell who is winning from any position the moment you tick “Show the binary”.

For misère, the losing positions for the mover are: nim-sum zero while some heap still has two or more objects, or, once every heap is 0 or 1, an odd number of single objects.

The idea travels further than matchsticks. The Sprague–Grundy theorem shows that every finite impartial game, where both players have the same moves available, behaves like a single Nim heap of some size.

Common mistakes

• Taking a lot because it feels strong. Size is irrelevant; only the binary pattern matters. Often the right move takes one object.
• Forgetting the misère switch. Playing pure nim-sum to the end in misère hands your opponent the win at the last step.