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.

The zero case is worth drawing before any other, because it is the one a reader can check without believing anything. A heap of seven in the subtraction game taking one, three or four counters reaches heaps of six, four and three, worth two, two and one; nought is missing from that list, so the mex is nought, and the Nim heap the position equals has no counters in it at all.

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.

The argument can also be replaced by a search, and replacing it is the honest thing to do, because a strategy described in prose is a strategy nobody has run. Take every heap of the game up to twelve, play each one beside every Nim heap up to twelve, and settle each of those sums by an ordinary win-or-lose recursion that has never heard of a Grundy value. Then compare each verdict with what the nim-sum of the two numbers predicts.

A hundred and sixty-nine agreements do not prove the theorem and are not offered as a proof; the induction above is the proof. What they establish is that the machinery on this page is the object the induction is about, which is the part of a claim a picture can carry and an argument cannot.

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.

The comparison that makes that concrete is the theorem applied to Nim itself, where it is guaranteed to say nothing new. A Nim heap of five can move to heaps of four, three, two, one and nought, worth four, three, two, one and nought, and the mex of those is five. Every row comes out that way, so the whole table is the identity.

Set the two tables beside each other and the subtraction game’s is nothing like the identity: its values run 0, 1, 0, 1, 2, 3, 2 and then repeat, so a heap of twelve is worth as much as a heap of five and a heap of seven is worth nothing whatever. Both tables came out of the same recursion, and only one of them could have been guessed from the rules.

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. The subtraction rule is implemented 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, the site’s evaluator 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 in advance rather than checked by eye.

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.

What the theorem is a statement about #

The theorem is easy to state and easy to under-read, and the under-reading is the reason it looks like a computational convenience rather than the foundation it is.

The weak reading is that a Grundy value summarises a position: a number that captures enough about it to decide the outcome. That would be useful and it would be a fact about single positions.

The strong reading — and the actual content — is that the value replaces it. A position with Grundy value five may be swapped for a Nim heap of five counters anywhere it appears, in any sum, alongside any other games, and no outcome anywhere changes. Not the winner of the sum, not the set of winning moves in the other components, nothing.

That is a claim quantified over every sum there is, which is why it is a theorem rather than an observation, and why it is worth so much more than an outcome rule. A summary answers one question about one position; a substitution licence turns a board of components into a board of heaps, and the board of heaps has a formula.

It also says exactly where the theorem’s usefulness lives, which is not in the number. A per-component number is worth having only because the numbers combine, and they combine because the substitution is exact. A value that decided outcomes and did not compose would be a curiosity — and several games on this site produce one, which is what the class of games outside this theorem looks like from inside.

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.

Where the ladder goes next #

sprague-grundy opens here with the theorem: every impartial position is a Nim heap, and the mex computes which one.

Turning Turtles is the theorem doing work nobody would predict from its statement — a coin-turning game whose positions are already sums, whose Grundy values come from a table of single coins, and whose losing positions turn out to be a linear code.

Two people, four years apart asks why the theorem was found twice and answers with a census of the alternatives: five plausible substitutes for the mex, each killed at a small heap, so the requirement was tight enough that there was nothing else to find. It also sets out what the requirements do and do not force — they pin the value down only up to a relabelling of the nimbers, and the shared numeral is a normalisation rather than a consequence.

Where the impartial theory stops is the boundary, and it is abrupt. Remove the hypothesis that both players have the same moves and the theorem is not weakened but destroyed: a partizan position does not have a Grundy value that is harder to compute, it has none, and no number behaves as one. That collapse is why the partizan theory had to be built from nothing thirty years later.

Read in order they are a theorem, a use of it nobody expected, an argument that it was forced, and the wall it runs into — which is a fair description of what the impartial theory is.