The Reveal
No luck, no lookahead search. Just one binary trick discovered in 1901 — and now that you're reading this, you can use it too.
Nim is simple: there are several piles of stones. On your turn, you remove any number of stones (at least one) from a single pile — you can never touch two piles in the same turn. Whoever removes the last stone on the board wins.
That's the entire rulebook. The depth is all hidden in the strategy.
The trick starts by looking at each pile size as a binary number instead of a decimal one. Take the piles 3, 4, 5:
| Pile | 4s place | 2s place | 1s place |
|---|---|---|---|
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 5 | 1 | 0 | 1 |
| XOR → | 0 | 1 | 0 |
Line the binary digits up in columns, and XOR straight down each column — each column's result is 1 if an odd number of piles have a 1 there, and 0 if an even number do (including zero). Here, the columns give 010, which is 2 in decimal.
This number — the column-by-column XOR of every pile — is called the nim-sum.
If the nim-sum is 0, the player about to move is losing — no matter how good their next move is. If the nim-sum is anything other than 0, the player about to move can force a win, no matter what their opponent does afterward.
That's the whole theorem, discovered by the mathematician Charles Bouton in 1901. It sounds almost too simple, so here's the same piles with one number changed:
| Pile | 4s place | 2s place | 1s place |
|---|---|---|---|
| 3 | 0 | 1 | 1 |
| 4 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 |
| XOR → | 0 | 0 | 0 |
Piles of 3, 4, 5 give a nim-sum of 2 (not 0) — good news for whoever moves next. Piles of 3, 4, 7 give a nim-sum of 0 — bad news for whoever moves next. One pile changed by 2 stones, and the entire outcome of the game flipped. That fragility is exactly what the winning strategy exploits.
If it's your turn and the nim-sum isn't 0, there is always at least one legal move that brings it back down to exactly 0 — take enough stones from the right pile, and the columns cancel out again. If the nim-sum is 0 when it's your turn, every move you make is guaranteed to push it away from 0, handing your opponent the exact position they need to do the same thing back to you.
So the strategy is only one sentence long: whenever it's your turn, make a move that brings the nim-sum back to 0. Do that every single time, and your opponent can never do it back to you.
Here's the part that matters when you're the one playing: who goes first alternates every game - the computer doesn't get to pick based on the piles. That means sometimes YOU move first into a position with a nonzero nim-sum, which is exactly the position a player can force a win from.
So the strategy for beating it is:
Do that consistently, and the computer - even playing perfectly - has no way back in. The theorem doesn't care who's human and who's code; it only cares who leaves the board at nim-sum 0 on the other player's turn.
If the computer happens to go first into a position where the nim-sum is already 0, it's already lost the moment the game started - even though it will still play every remaining move correctly. That's not a bug in the computer's strategy; it's the same theorem working against it instead of for it. Perfect play can't fix a position that was already lost before your first move.
Type in any pile sizes and see the nim-sum calculated live, column by column.