Nim and Grundy Numbers, Explained

After reading this you will be able to look at any Nim position, compute its nim-sum in your head, and know whether you can force a win and exactly which move does it.

What Nim is and one position that gives the trick away

Nim is played with several heaps of stones. Two players alternate. On your turn you pick one heap and remove any number of stones from it, from a single stone up to the whole heap. You must remove at least one. In the normal version, the player who takes the last stone wins.

Here is the whole game in one example. Suppose the heaps are 3, 4, 5. It is your move. There are dozens of legal moves. Most of them lose. Exactly one class of move wins, and you can find it with a single bitwise operation.

Write each heap in binary and add the columns without carrying (that is XOR, the exclusive-or):

The result 2 is called the nim-sum. Because it is not zero, this position is a win for the player to move. If it were zero, you would be losing against anyone who knows the trick. That single number decides the entire game, and the rest of this article explains why.

When the XOR rule applies, and when it does not

The theorem below is exact, not approximate. But it depends on rules that are easy to break by accident, so check them before you trust the nim-sum.

First, the game must be impartial: both players have the same moves available from any position. Chess is not impartial, because you move only your own pieces. Nim is impartial, because either player may take from any heap. Second, this is the normal-play convention: last stone wins. The misère version, where taking the last stone loses, has a different (though closely related) rule. Third, the game must be finite and end, which Nim always does because the total stone count strictly drops every turn.

The nim-sum and why zero means loss

The rule is compact. Let the heaps be h_1, h_2, \dots, h_n and define the nim-sum as their bitwise XOR:

Here \oplus is XOR: add the binary digits column by column, and in each column keep 1 if the number of ones is odd, 0 if it is even. So 1 \oplus 1 = 0 and 1 \oplus 0 = 1. A position with S = 0 is called a P-position (Previous player wins, meaning the player who just moved). A position with S \ne 0 is an N-position (Next player to move wins).

Three facts prove the whole theorem, and each is short.

1. The empty position (all heaps zero) has S = 0, and the player facing it has already lost, since the previous player took the last stone.
2. From any S = 0 position, every legal move produces S \ne 0. Changing one heap changes at least one bit of the XOR, so the sum cannot stay zero.
3. From any S \ne 0 position, some legal move produces S = 0. Find the highest set bit of S, pick a heap that also has that bit set, and XOR that heap with S. The result is smaller than the original heap, so the move is legal, and it drives the sum to zero.

Put those together. A player on a zero-sum position must hand a nonzero sum to the opponent (fact 2). The opponent can always hand zero back (fact 3). So zero sums are forced on the loser forever, until the losing player is staring at the empty board (fact 1). That is a complete proof.

The winning move, computed step by step

Fact 3 tells you not just that you can win but how. The recipe is: for each heap h_i, compute h_i \oplus S. If that value is smaller than h_i, reducing heap i to h_i \oplus S is a winning move. There is always at least one such heap.

Reading the binary analysis panel

The analysis panel stacks the heaps in binary and shows the XOR beneath them. Read it column by column. A column with an even number of ones contributes 0 to the sum; an odd column contributes 1.

For 3, 4, 5 the columns are the value-4 bit, the value-2 bit, and the value-1 bit:

The 2s column is the only odd one, so S = 010_2 = 2. When you reach a P-position, every column is even and the whole XOR row is zeros. That row of zeros is the visual signature of a lost position (for the player about to move).

The Sprague-Grundy theorem: why Nim is the whole story

Nim is not just one puzzle. Every finite impartial game under normal play is equivalent to a single Nim heap. That is the Sprague-Grundy theorem. To each position you assign a Grundy number (also called the nimber), computed from the positions you can move to:

Here p \to q means q is reachable from p in one move, and \operatorname{mex} is the minimum excludant: the smallest non-negative integer not in the set. So if the moves lead to positions with Grundy numbers {0, 1, 3}, then \operatorname{mex} = 2, because 2 is the smallest whole number missing.

A single Nim heap of size k has Grundy number k: from a heap of k you can reach every heap from 0 to k-1, so \operatorname{mex}\{0,1,\dots,k-1\} = k. For several independent games played at once, the Grundy number of the whole is the XOR of the parts. That is exactly the nim-sum rule, now applied to arbitrary games, not just piles of stones. A position loses precisely when its Grundy number is 0.

Common mistakes

The math is airtight, but players trip on the same few things.

Confusing nim-sum with ordinary sum

The ordinary total of 3, 4, 5 is 12. The nim-sum is 2. Only the XOR predicts the winner. A heap total of 12 tells you nothing about who wins.

Thinking every heap has a winning move

From 3, 4, 5 only the heap of 3 can be reduced to force the win. Trying to fix heap 4 or 5 would require adding stones, which is illegal. Always test h \oplus S \lt h before committing.

Playing misère by the normal rule

If the last stone loses, the endgame flips. Keep the normal XOR strategy until only single-stone heaps remain, then leave your opponent an odd count of them.

Assuming a win is guaranteed

If you start from a P-position (S = 0), no strategy saves you against a perfect opponent. Your only hope is that the opponent errs, at which point the sum goes nonzero and you pounce.

Related tools

Nim sits among other exact combinatorial and puzzle machines on this site. The Tower of Hanoi is another game with a clean closed-form structure, solved in 2^n - 1 moves. The Fifteen Puzzle hinges on a parity argument much like the odd-column parity that drives the nim-sum. For search-based solving rather than a formula, see the N-Queens Visualizer and the Knight's Tour. If you would rather estimate optimal moves from random samples than derive them, the Monte Carlo Playground shows how noise converges on the right answer. And for a taste of how simple rules produce rich structure, try Langton's Ant or Conway's Game of Life.

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.