The Number That Wins Every Game

A game with nothing left to discover

Here is a game you can learn in one sentence. There are a few rows of tokens. On your turn you take as many as you like from a single row — one, or all of them, your choice — but only from one row. Players alternate. Take the last token on the board and you win.

That's the whole thing. It has no dice, no cards, no hidden information. Two players, perfect knowledge, no luck. And it is completely solved — not "hard for computers" like chess, not "usually solvable" like most puzzles, but solved in the strongest sense mathematics allows: from any position, there is a formula that instantly tells you whether the player about to move will win or lose, and if they can win, precisely how. The machine above is running that formula. It is not searching. It is not thinking ahead. It just knows.

The formula is one line, and it is built out of the most primitive operation a computer owns: the exclusive-or of a handful of small numbers. Play a round first — try to beat it from The Classic, where you can — then come back and watch it give up its secret.

Two observations that flatten the whole game

Nim looks like it should be complicated. A position is a list of row sizes, moves branch into more moves, and the tree of possibilities explodes. Two small observations quietly demolish all of that.

Order doesn't matter. Your moves and your opponent's don't interact across rows — taking from row A never touches row B. So a position is fully described by its multiset of row sizes. {3, 5, 7} is the same game whether you list it forwards or backwards. The branching is an illusion; there are far fewer genuinely different positions than there are sequences of moves.

The end is unambiguous. The board empties, someone took the last token, and the rules say who won. There is no draw, no repetition, no stalemate. Every game is a finite walk from the start down to zero.

Put those together and every position is, in principle, tagged W (the player to move can force a win) or L (they can't). The empty board is an L for the person facing it — they have no move, so the previous player just took the last token and won. From there the tags propagate: a position is W if some move leads to an L, and L if every move leads to a W. That's a clean recursive definition — but computing it by hand for {3, 5, 7} still means walking a tree. The miracle is that you never have to.

The nim-sum

Write each row's size in binary and stack them up. Now, for each column, ask a single question: is the number of 1s in this column even or odd? Combine the column answers back into one number — a 1 wherever the column was odd, a 0 wherever it was even. That number is the nim-sum: the bitwise XOR of all the row sizes.

For {3, 5, 7}:

  3  =  0 1 1
  5  =  1 0 1
  7  =  1 1 1
 XOR = 0 0 1  = 1

The theorem — Charles Bouton proved it in 1901, giving Nim the distinction of being the first game ever mathematically solved — is breathtakingly compact:

A position is a loss for the player about to move exactly when its nim-sum is 0. Otherwise it's a win.

Nim-sum 0 is a balanced position: every column has an even number of 1s. Nim-sum non-zero is unbalanced. So the entire game reduces to a parity check you can do in your head. {3, 5, 7} has nim-sum 1 — unbalanced — so whoever moves first (you) is already winning. {1, 3, 5, 7} XORs to 0 — balanced — so the first mover has already lost, before a single token is taken. The reasoning table under the board shows this column by column, live, updating on every move.

Why one XOR is enough

The theorem rests on two facts, and once you see them the strategy is forced.

From an unbalanced position, you can always rebalance. Suppose the nim-sum is some non-zero number x. Look at its highest 1-bit. At least one row has a 1 in that same place (otherwise the column would have been even). XOR that row's size with x: the result is smaller than the row (you just turned its top bit off), so it's a legal cut — and it makes the total nim-sum zero. There is always such a move, and finding it is the one line of arithmetic the machine runs. That's the "show me the winning move" button: it's not a lookup, it's row XOR nim-sum, computed on the spot.

From a balanced position, every move unbalances it. If the nim-sum is already 0 and you change a single row, exactly the columns where that row differs will flip parity — and since you changed something, at least one column flips from even to odd. You cannot help but hand your opponent a non-zero nim-sum.

Chain them together and the win is mechanical. Hand your opponent balance. They're forced to break it. You restore it. They break it again. Because every move strictly shrinks the pile total, this can't go on forever — and the position you keep handing back, all-zeros, is balanced, so the person who finally faces the empty board is them. You took the last token. This is why, from Marienbad, the machine is a wall: it starts balanced, the machine always hands you balance, and there is literally no move you can make that doesn't lose. That's not the machine playing well. That's the position being lost from the first token.

The twist under every other game

Here's the part that turns a card trick into a theory. The XOR isn't a quirk of Nim — it's the universal currency of a whole class of games. The Sprague–Grundy theorem (1930s) says every "impartial" game — any two-player, perfect-information game where both players have the same moves available and the last move wins — is secretly a single Nim pile in disguise. Each position has a number, its Grundy value, and to play a game that's several sub-games at once (this pile here, that puzzle there), you compute each part's Grundy value and XOR them together, exactly as if they were rows in Nim. The nim-sum you just learned is the addition law for all of combinatorial game theory. Learn to win at Nim and you've learned the skeleton of a hundred other games.

The one exception: playing to lose

Flip the switch above to take last = lose (this is misère Nim), and the famous story attaches: in the 1961 film Last Year at Marienbad, a character wins this version again and again with rows of 1, 3, 5, 7 — the position the game loads under "Marienbad."

The strategy is almost identical, which is the elegant part. You play ordinary balanced Nim right up until the endgame — specifically, until at most one row still holds two or more tokens. Only then does the goal invert: instead of leaving balance, you leave an odd number of single-token rows, forcing your opponent to pick up the poisoned last one. One line of exception, bolted onto the same engine. The machine switches rules at exactly that boundary; the reasoning panel notes when it's about to.

The honest part

Because a game that ships a losing "puzzle" would be a broken toy, the strategy was checked before it was written about. The machine's move — for both variants — was compared against a full minimax search over every position (a genuine, exhaustive W/L labeling of the game tree, not the formula it's meant to justify). Across thousands of positions the nim-sum verdict and the brute-force truth agreed every single time: zero mismatches. The formula isn't asserted here; it's the thing that was tested.

Which sets up the one thing worth being honest about. From a balanced starting position — Marienbad, or the small Endgame — you cannot beat the machine, ever. Not because it's clever, but because the position is lost the instant you're the one to move, and the machine never once gives it back. If you do win from there, it's only because a fallible opponent handed you an unbalanced board by mistake — which is exactly what the machine will never do. The unsettling lesson of Nim isn't that the computer is strong. It's that in a game this transparent, the winner was decided before anyone touched a token — and a single XOR could have told you who.