Every impartial game is a Nim heap

An impartial game is one where both players have exactly the same moves available from every position. Nim is impartial. So are the subtraction games, Kayles, Dawson’s chess, Wythoff’s game, and hundreds of others with their own rules, their own boards and their own literature.

The theorem is that there is only one of them.

The statement #

Every position in every finite impartial game is equal to $\ast n$ for exactly one non-negative integer $n$. That integer is called the Grundy value of the position, and it is computed by the rule below.

“Equal” here carries the full weight it has everywhere on this site: $G = \ast n$ means $G + \ast n$ is a second-player win, and it means $G$ can replace $\ast n$ inside any sum whatsoever without changing the outcome of the sum. It is not a statement that the two positions feel similar or that the same strategy works for both. It is a statement of interchangeability, and it is the strongest kind of statement the subject makes.

So Kayles is Nim. Dawson’s chess is Nim. Any impartial game anybody invents tomorrow is Nim, and the only work is finding out which heap each position corresponds to.

The mex rule #

The computation is a recursion, and it has one ingredient: the minimum excludant, universally abbreviated mex. The mex of a set of non-negative integers is the smallest non-negative integer not in it.

$$\operatorname{mex}\{0, 1, 3, 4\} = 2, \qquad \operatorname{mex}\{1, 2\} = 0, \qquad \operatorname{mex}\{\,\} = 0$$

The Grundy value of a position is the mex of the Grundy values of its options:

$$\mathcal{G}(G) = \operatorname{mex}\{\, \mathcal{G}(G') : G' \text{ an option of } G \,\}$$

The empty position has no options, so its Grundy value is $\operatorname{mex}\{\} = 0$, which is right: it is a loss for the player to move.

A position has Grundy value zero exactly when none of its options has Grundy value zero — that is, exactly when it is a previous-player win. So the theorem contains the outcome as its zero case, and everything above zero is extra information about how the position behaves in sums.

Why mex and not something else #

The mex rule looks arbitrary until the two things it has to do are separated.

It must never repeat an option’s value. If $\mathcal{G}(G) = k$, the position must not have an option with Grundy value $k$, because $\ast k$ has no move to $\ast k$ — a Nim heap cannot move to itself. Mex guarantees this: the excluded value is by definition not among the options.

It must reach every smaller value. If $\mathcal{G}(G) = k$, the position must have options with Grundy values $0, 1, \ldots, k-1$, because $\ast k$ can move to any of $\ast 0, \ldots, \ast(k-1)$. Mex guarantees this too: if any value below $k$ were missing from the options, the mex would be that value, not $k$.

Those two properties are exactly what “behaves like a heap of size $k$” means, and mex is precisely the operation that produces a number with both. It is the unique such rule, which is why it turns up in every treatment and why no alternative has ever been proposed.

One more thing is needed and is easy to miss: the position may have options with values greater than $k$, which $\ast k$ cannot reach. That is fine, and the reason is the first half of the Nim proof — a move to a larger value can always be answered by a move back down to $k$, so the extra options are harmless. This is the same phenomenon as dominated options in the partizan theory: options that cannot help are not merely tolerable, they are invisible to the value.

The proof of the equivalence #

The claim is that $G + \ast n$ is a second-player win when $n = \mathcal{G}(G)$. The strategy is a restore-the-balance argument, and it is the same shape as the two-heap Nim mirror.

The second player maintains the invariant that after each of their moves, the Grundy value of the game component equals the size of the heap component. Suppose the first player moves.

If they move in the heap, from $\ast n$ to $\ast m$ with $m < n$, the second player replies in the game, moving to an option with Grundy value $m$ — which exists, by the “reaches every smaller value” property. Balance restored.

If they move in the game, to an option with Grundy value $m$, there are two cases. If $m < n$, the second player takes the heap down to $\ast m$. If $m > n$, the second player moves in the game again, from that option down to a position of value $n$ — possible because a position of value $m > n$ has an option of value $n$. Either way, balance restored. And $m = n$ is impossible, by the “never repeats” property.

The invariant holds, the game is finite, so the second player makes the last move.

That argument is worth reading twice, because the awkward case — the opponent moves up in Grundy value and the reply is in the same component — is the part that makes the theorem work and the part that is usually skipped.

A worked mex, slowly #

The recursion is easy to state and easy to get wrong by hand, so one full computation is worth doing at the pace it actually takes.

Take the subtraction game with set $\{1, 3, 4\}$ and find the Grundy value of a heap of ten.

$\mathcal{G}(0) = \operatorname{mex}\{\} = 0$. $\mathcal{G}(1) = \operatorname{mex}\{\mathcal{G}(0)\} = \operatorname{mex}\{0\} = 1$. $\mathcal{G}(2) = \operatorname{mex}\{\mathcal{G}(1)\} = \operatorname{mex}\{1\} = 0$. $\mathcal{G}(3) = \operatorname{mex}\{\mathcal{G}(2), \mathcal{G}(0)\} = \operatorname{mex}\{0, 0\} = 1$. $\mathcal{G}(4) = \operatorname{mex}\{\mathcal{G}(3), \mathcal{G}(1), \mathcal{G}(0)\} = \operatorname{mex}\{1, 1, 0\} = 2$. $\mathcal{G}(5) = \operatorname{mex}\{\mathcal{G}(4), \mathcal{G}(2), \mathcal{G}(1)\} = \operatorname{mex}\{2, 0, 1\} = 3$. $\mathcal{G}(6) = \operatorname{mex}\{\mathcal{G}(5), \mathcal{G}(3), \mathcal{G}(2)\} = \operatorname{mex}\{3, 1, 0\} = 2$. $\mathcal{G}(7) = \operatorname{mex}\{\mathcal{G}(6), \mathcal{G}(4), \mathcal{G}(3)\} = \operatorname{mex}\{2, 2, 1\} = 0$.

At seven the sequence returns to zero and the pattern $0,1,0,1,2,3,2$ starts again. Nothing forced that; it is a fact about this subtraction set, discovered by computing.

Continuing, $\mathcal{G}(10) = \mathcal{G}(3) = 1$. So a heap of ten in this game is a Nim heap of one — a single counter — and the winning move from it must be a move to a position of Grundy value zero, which means a move to a heap of seven, that is, taking three.

The thing to notice is how little the answer resembles the position. A heap of ten counters, from which three different moves are legal, is worth exactly as much as a single counter that can only be taken. Every difference between them is invisible to every sum they might appear in.

Sums, and where the theorem earns its keep #

The equivalence would be a curiosity if it did not survive addition, and the point is that it does.

If $G = \ast a$ and $H = \ast b$, then $G + H = \ast a + \ast b = \ast(a \oplus b)$. So the Grundy value of a sum is the nim-sum of the Grundy values, and a position made of many independent components collapses to a single number by exclusive-or.

This is what makes the theorem useful rather than merely true. Real impartial positions are almost always sums — a Kayles row splits into two rows when a pin is knocked out of the middle, a subtraction-game position is several heaps, a Dawson’s chess position is a set of independent strips. Grundy values turn each component into a number, and exclusive-or combines them.

Without additivity, a game with three components would need its whole product space analysed. With it, three mex lookups and an exclusive-or suffice, and the analysis of a game reduces to computing one sequence.

The theorem applied to something that is not Nim #

An abstract statement of interchangeability is easier to believe when watched happening to a game with different rules and a different board.

Take the subtraction game with set $\{1, 3, 4\}$: a move removes one, three or four counters from a heap. Nothing about this looks like Nim — most moves are illegal, and the reachable positions from a heap of ten are heaps of nine, seven and six only.

Run the mex recursion. A heap of zero has no options, so $\mathcal{G}(0) = 0$. A heap of one can reach zero only, so $\mathcal{G}(1) = \operatorname{mex}\{0\} = 1$. A heap of two can reach one only, so $\mathcal{G}(2) = \operatorname{mex}\{1\} = 0$. A heap of three reaches two and zero, so $\mathcal{G}(3) = \operatorname{mex}\{0, 0\} = 1$. A heap of four reaches three, one and zero: $\operatorname{mex}\{1, 1, 0\} = 2$. A heap of five reaches four, two and one: $\operatorname{mex}\{2, 0, 1\} = 3$.

So a heap of five in this game is worth $\ast 3$, and the theorem says a heap of five here can be exchanged for a Nim heap of three counters anywhere at all, with no effect on any outcome. That claim is checkable and the build checks it.

The exchange is genuinely startling the first time. The two positions have different rule sets, different numbers of moves available, different game lengths. What they share is the shape of their option structure after mex has extracted it, and the theorem says that is the only thing that ever mattered.

Sums of different games #

The additivity has a consequence worth stating separately, because it is where the theorem stops being about one game.

Since every impartial position is a nimber, and nimbers add by exclusive-or regardless of where they came from, positions from different games can be added and the result computed the same way.

A heap of five in the $\{1,3,4\}$ subtraction game, worth $\ast 3$; a row of seven pins in Kayles, worth $\ast 2$; and a Nim heap of one, worth $\ast 1$. The whole thing is worth $\ast(3 \oplus 2 \oplus 1) = \ast 0$, a previous-player win, and the analysis took one exclusive-or.

Nothing in the proof cared that the components obeyed the same rules. The invariant is maintained component by component, and each component only ever needs the two mex properties. So the theorem does not merely reduce each impartial game to Nim — it makes all impartial games commensurable, so they can be mixed freely.

That is the sense in which there is only one impartial game.

The cost of the reduction #

It should be said what is lost, because “every impartial game is a Nim heap” is often quoted as though it ended the subject.

The theorem is an existence and computation result, not a shortcut. It says a Grundy value exists and gives a recursion. The recursion visits every reachable position, and for a game with an exponential state space that is an exponential computation. Kayles took real effort to work out, and its sequence is periodic only after a long irregular prefix.

Worse, for many games the sequence is not known to be periodic at all, which means there is no known way to answer questions about large heaps without computing every smaller one. Grundy sequences is where that difficulty lives, and it contains open problems that have resisted since the 1950s.

So the theorem converts “who wins this position” into “what is this sequence”, which is enormous progress and is not the same as an answer.

What the solver computed #

The strip above is not a table transcribed from a reference. lib/games.js implements the subtraction rule directly, subtractionGrundy runs the mex recursion over heap sizes, and findPeriod searches the resulting sequence for a repeat.

The check that matters is the cross-check. For each position drawn, lib/cgt.js also builds the game as a partizan position — options listed explicitly, both players given the same list — reduces it to canonical form, and reports the value independently. For every position in these figures the canonical form comes back as a nimber, and the nimber index matches the mex computation. Two independent routes, same answer, asserted at build time.

For the subtraction set $\{1, 3, 4\}$ the sequence begins $0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, \ldots$ and repeats with period seven from the start. So a heap of ten has Grundy value $\mathcal{G}(10) = \mathcal{G}(3) = 1$, and heaps of ten and three together have nim-sum $1 \oplus 1 = 0$ — a second-player win, which the recursion confirms independently.

Who found it, and when #

Roland Percival Sprague published the theorem in 1935 in the Tôhoku Mathematical Journal, in German, under a title that translates as On mathematical fighting games. Patrick Michael Grundy published the same result in 1939 in the Proceedings of the Cambridge Philosophical Society, apparently without knowing of Sprague’s paper.

Neither seems to have regarded it as the foundation of a subject. Grundy’s paper is four pages. It was Richard Guy and Cedric Smith who developed the machinery for computing the sequences in the 1950s, and Conway who, in 1976, placed the theorem where it belongs — as the impartial special case of a much larger partizan theory, in which nimbers are the values of games that happen to be confused with zero in a particularly simple way.

The independence of the two discoveries is a mild embarrassment for the naming, which is why the theorem carries both names and why the numbers are usually called Grundy values while the theorem is usually called Sprague–Grundy.

Where the model stops #

Impartial only. This is the load-bearing hypothesis and it is severe. As soon as the two players have different options, a single number is not enough — values become a much richer structure, and nimbers are only one small family within it. Domineering, Hackenbush and Go are all partizan and none of them reduces to Nim.

Normal play only. Under the misère convention the theorem fails, and it fails badly rather than needing an adjustment: two impartial games with the same Grundy value can behave differently in misère sums. The replacement machinery, misère quotients, is enormously more complicated and was not available until the 2000s.

Finite and loop-free. The recursion needs every line of play to terminate. Loopy games require an extended theory with an extra value for positions that draw.

Computability is not tractability. The theorem says the Grundy value exists and gives a recursion for it. It does not say the recursion finishes in reasonable time, and for many natural games it does not. Knowing every impartial game is a Nim heap does not mean knowing which one.

The ladder from here #

The immediate next rung is Grundy sequences — what these sequences actually look like, why so many are eventually periodic, and the games where nobody knows whether the periodicity ever starts.

Beyond that: octal games and the notation for describing them; Wythoff’s game, which is impartial and whose losing positions are governed by the golden ratio rather than by binary; and the question of what the sum operation looks like once partizan values are allowed, where the clean collapse to a single integer is the first thing to go.