Nim, and the nim-sum

Counters are laid out in heaps. A move is to pick one heap and remove any positive number of counters from it, up to all of them. Play alternates, and under the normal-play convention the player who takes the last counter wins, because the opponent is then left with nothing to move in.

That is Nim. It is old enough that nobody knows where it came from, and it has been completely solved since 1901.

The rule, stated first #

Write each heap size in binary. Add the columns without carrying — equivalently, take the bitwise exclusive-or. Call the result the nim-sum.

$$3 \oplus 5 \oplus 7 = 011 \oplus 101 \oplus 111 = 001 = 1$$

If the nim-sum is zero the position is a loss for the player to move. If it is anything else, the player to move wins, and there is a move that makes it zero.

That is the entire theory of Nim. There is no case analysis, no lookup table, and no dependence on how many heaps there are or how large. The nim-sum of $3, 5, 7$ is $1$, so the first player wins — and the winning move is to take two counters from the heap of three, leaving $1, 5, 7$, whose nim-sum is $1 \oplus 5 \oplus 7 = 3 \oplus \ldots$ — no: leaving $1,5,7$ gives $1 \oplus 5 \oplus 7 = 3$, which is not zero. The correct move is to reduce the heap of seven to six, since $3 \oplus 5 = 6$.

That correction is worth leaving visible, because it is the ordinary experience of using this rule: the arithmetic is trivial and the intuition is useless. The nim-sum has to be computed, not guessed at.

Balanced and unbalanced #

A position with nim-sum zero is called balanced. The word is apt: in binary, every column has an even number of ones.

$$1 \oplus 2 \oplus 3 = 01 \oplus 10 \oplus 11 = 00$$

Heaps of $1, 2, 3$ are balanced, so whoever moves first from them loses against correct play. That is the smallest genuinely interesting Nim position, and it is the one the interactive figure below uses, because it is small enough for a reader to hold in mind and still surprising enough that most first attempts lose.

Everything else is unbalanced, and from an unbalanced position there is always a move to a balanced one. That pairing — every unbalanced position has a move to a balanced one, and no balanced position has a move to another balanced one — is the whole proof.

The proof, in two halves #

From balanced, every move unbalances. A move changes exactly one heap, from $a$ to $b$ with $b < a$. The nim-sum changes from $0$ to $a \oplus b$, and since $a \neq b$ that is not zero. So a player handed a balanced position hands back an unbalanced one, every time, with no choice in the matter.

From unbalanced, some move balances. Let the nim-sum be $s \neq 0$, and let the leading bit of $s$ be at position $k$ — the highest column with an odd number of ones. Some heap $a$ must have a one in column $k$, since otherwise the column would be empty. For that heap, $a \oplus s < a$: the operation clears bit $k$ (turning a one into a zero, which decreases the value by $2^k$) and can only change lower bits (which together are worth less than $2^k$). So $b = a \oplus s$ is a legal target, and replacing $a$ by $b$ changes the nim-sum to $s \oplus a \oplus b = s \oplus a \oplus a \oplus s = 0$.

The second half is where the exclusive-or earns its place. Any other way of combining the heaps would leave the existence of the balancing move as something to be checked; here it is a one-line computation, and it produces the move rather than merely asserting one exists.

The two halves combine by induction. From balanced, every move leads to unbalanced; from unbalanced, some move leads to balanced; and the all-empty position is balanced and is a loss for the player to move. So balanced positions are exactly the previous-player wins.

Why exclusive-or, of all things #

The natural first guess is that some simpler statistic should work — the total number of counters, the number of heaps, the parity of something. None of them do, and it is instructive to see them fail.

The total fails immediately: $1, 2, 3$ and $6$ both total six, and the first is a second-player win while the second is a first-player win in one move. The number of heaps fails: $1, 1$ is balanced and $1, 2$ is not. Parity of the total fails on the same example.

What is actually going on is that Nim is a sum of independent components — each heap is its own little game, and a move touches exactly one of them. The disjunctive sum is the central operation of the whole subject, and the nim-sum is what that operation does to heaps. Exclusive-or is not a trick that happens to work; it is the group structure of the game, and the fact that it coincides with binary addition without carrying is the coincidence, not the rule.

Concretely: a single heap of size $n$ has value $\ast n$, the nimber $n$, and the theorem is

$$\ast a + \ast b = \ast (a \oplus b).$$

Nimbers under addition form the group $(\mathbb{Z}/2)^\infty$ — every element is its own negative, since $\ast a + \ast a = \ast 0 = 0$. That self-inverse property is why the mirroring strategy works so cleanly on paired heaps, and it is the reason a position of two equal heaps is always a loss for the player to move.

What the solver computed #

The values on the figures above are not quoted from Bouton. lib/cgt.js builds each heap as a game — a heap of size $n$ has options to every smaller heap — reduces to canonical form, and computes the nim-sum of a position by the game recursion. A separate function computes the bitwise exclusive-or directly. The build compares the two and refuses to render if they disagree.

For heaps up to size seven, that comparison covers every position: $8^3 = 512$ three-heap positions, all checked, all agreeing. The recursion does not know about binary; it knows about options and the mex rule. That the two answers coincide is the theorem, and having the code check it on every build is more convincing than having it in a footnote.

Two heaps of size three has nim-sum zero, so the game recursion should report it a previous-player win, and it does. A single heap of size three has nim-sum three, so it should be a next-player win with a winning move to zero, and it is.

Two heaps, and why the mirror works #

The two-heap case is worth isolating because it is the one every player rediscovers.

With heaps $a$ and $b$, the nim-sum is zero exactly when $a = b$. So equal heaps lose for the player to move, and unequal heaps win by evening them up.

The strategy that implements this needs no arithmetic at all: copy. Whatever the opponent takes from one heap, take the same from the other. The position after each of the copier’s moves is a pair of equal heaps, which is balanced, and the copier is never the one who runs out.

This is the same mirroring argument that defines equality of games: $G - G$ is always a second-player win, because the second player copies across components. In Nim, negation does nothing — a heap is its own negative — so $G - G$ and $G + G$ are the same position, and two equal heaps is literally the statement that $\ast n + \ast n = 0$.

Most people who play Nim casually discover the two-heap mirror and stop there. The step from two heaps to three is where the exclusive-or becomes necessary, because there is no longer anything to copy.

Playing it badly on purpose #

There is a useful exercise that the interactive figures make possible and a book cannot: lose deliberately, and watch what the correct reply does.

From heaps of $1, 2, 3$, take the whole heap of one. The position is $2, 3$, nim-sum $1$, so it is now a win for whoever moves — and the reply is to take one from the three, leaving $2, 2$. From $2, 2$ the mirror runs and there is nothing to be done.

Take instead one counter from the three, leaving $1, 2, 2$. Nim-sum $1$, and the reply takes the heap of one, leaving $2, 2$. Same destination.

Take two from the three, leaving $1, 2, 1$. Nim-sum $2$, and the reply takes the whole heap of two, leaving $1, 1$. Different destination, same principle.

Every first move from a balanced position leads somewhere the opponent can rebalance, and the rebalanced positions are not all the same — which is the point. There is no single “safe shape” to steer towards. There is only the invariant, and the invariant is arithmetic.

Nim is not a good game #

This is worth saying plainly, because it explains why the subject did not stop in 1901.

A game with a known complete strategy is not worth playing. Nim’s interest is entirely mathematical, and its role in the theory is structural rather than recreational: it is the game everything else is measured against. The reason to care about heaps of counters is that the values of every impartial position turn out to be heap sizes, so understanding heaps completely is understanding a great deal.

The same is true of Hackenbush strings and of the tiny Domineering boards elsewhere on this site. These are not games anybody plays for pleasure. They are the positions small enough that a complete answer is available, which makes them the positions from which general statements can be extracted.

The games people actually play — Go, chess, Hex, Amazons — are interesting precisely because they are not solved and probably not solvable. The theory reaches into them through their endgames, where a large position splits into small independent components and the small-position analysis suddenly applies.

The heap that is a value #

One reframing makes the next essay inevitable.

A heap of size $n$ is not merely a position with a known winner. It is a position with a value, written $\ast n$ and called a nimber, and the value obeys an arithmetic:

$$\ast a + \ast b = \ast(a \oplus b), \qquad \ast a + \ast a = 0.$$

The second identity says every nimber is its own negative, which is a strong statement — in the partizan world the negative of a game is the game with the players’ roles swapped, and for an impartial game that swap changes nothing, because the options were the same to begin with. So $-G = G$, and $G + G = 0$ follows.

That means the nimbers form a group of exponent two, and it means the whole of Nim is the statement that a position of several heaps is the group element that is their sum. Bouton found the group operation before anybody was looking for a group.

Misère Nim, and a warning #

Change the convention so that the player who takes the last counter loses, and Nim is still solvable — which makes it thoroughly misleading.

The misère rule: play as in normal Nim until all heaps but one have size one; then take the whole of the last big heap, or all but one of it, whichever leaves an odd number of size-one heaps. If every heap is already of size one, win by leaving an odd number.

The temptation is to conclude that misère play is a small modification. It is not. Nim is essentially the only interesting game whose misère version is easy, and the general theory of misère play is vastly harder than the normal-play theory — the equivalence that makes normal play tractable simply fails, and positions that are interchangeable under normal play stop being interchangeable. Nim’s misère solution is a special case with no useful generalisation, and quoting it as evidence that misère play is manageable is the most common error in this area.

Who found it, and when #

Charles Leonard Bouton published Nim, a game with a complete mathematical theory in the Annals of Mathematics in 1901, while at Harvard. He gave the name, the binary criterion and the proof, essentially in the form above.

The paper is short and remarkably modern in tone. Bouton describes the position with nim-sum zero as “safe” and works entirely in binary, which was an unusual choice in 1901 and is the reason the result reads as though it were written for computers three decades before there were any.

What Bouton did not have was any reason to think Nim was more than a curiosity. That came in 1935, when Roland Sprague showed that every impartial game is equivalent to a single Nim heap, and independently in 1939 when Patrick Michael Grundy proved the same thing. At that point Bouton’s paper stopped being about a parlour game and became the base case of a general theory.

Where the model stops #

Impartial only. Nim is impartial: both players have exactly the same moves available. That is what makes a single number suffice. As soon as the players have different options — as in Hackenbush or Domineering — nimbers are not enough and the full partizan theory is needed.

Normal play only, as above.

Finite heaps, finitely many. Both are needed for the induction. Infinite heaps and transfinite Nim exist and are consistent, but nothing in the proof above survives unchanged.

The figures show at most three heaps. Three is enough for every phenomenon in the proof and small enough to draw. Nothing about the argument depends on the number of heaps, and the code checks positions the figures do not show.

The ladder from here #

The obvious next rung is Sprague–Grundy: the theorem that says Nim was not one game among many but the only impartial game, up to equivalence. Then Grundy sequences, where the values of a game are computed heap by heap and turn out to be eventually periodic surprisingly often — and where the open problems start.

Further along: Wythoff’s game, whose losing positions involve the golden ratio; octal games and the periodicity conjecture; and the point where impartial theory meets complexity and stops being able to answer questions it can pose.