Sprague–Grundy theorem

The Sprague-Grundy theorem says that many simple games are mathematically equivalent to the stone-taking game of Nim (pictured).

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to. In the case of a game whose positions (or summands of positions) are indexed by the natural numbers (for example the possible heap sizes in nim-like games), the sequence of nimbers for successive heap sizes is called the nim-sequence of the game.

The theorem and its proof encapsulate the main results of a theory discovered independently by R. P. Sprague (1935) and P. M. Grundy (1939).^[1]

Definitions

For the purposes of the Sprague–Grundy theorem, a game is a two-player game of perfect information satisfying the ending condition (all games come to an end: there are no infinite lines of play) and the normal play condition (a player who cannot move loses).

An impartial game is one such as nim, in which each player has exactly the same available moves as the other player in any position. Note that games such as tic-tac-toe, checkers, and chess are not impartial games. In the case of checkers and chess, for example, players can only move their own pieces, not their opponent's pieces. And in tic-tac-toe, one player puts down X's, while the other puts down O's. Positions in impartial games fall into two outcome classes: either the next player (the one whose turn it is) wins (an N-position) or the previous player wins (a P-position).

In this proof, a position is identified with the set of positions that can be reached in one move (these positions are called options). For example, the position $\{\}$ is a P-position under normal play, because the current player has no moves and therefore loses. The position $\{\{\}\}$, in contrast, is an N-position; the current player has only one option, and that option is a losing position for their opponent.

A nimber is a special position denoted $*n$ for some ordinal $n$. $*0$ is $\{\}$, the P-position given as an example earlier. The other nimbers are defined inductively by $*(n+1) = *n \cup \{*n\}$; in particular, $*1 = \{*0\}$ (the example N-position from above), $*2 = \{*0, *1\}$ (a choice between the two example positions), etc. $*n$ therefore corresponds to a heap of $n$ counters in the game of nim, hence the name.

Two positions $G$ and $H$ can be added to make a new position $G+H$ in a combined game where the current player can choose either to move in $G$ or in $H$. Explicit computation of the set $G+H$ is by repeated application of the rule $G+H=\{G+h\mid h\in H\}\cup\{g+H\mid g\in G\}$, which incidentally indicates that position addition is both commutative and associative as expected.

Two positions $G$ and $G'$ are defined to be equivalent if for every position $H$, the position $G+H$ is in the same outcome class as $G'+H$. Such an equivalence is written $G\approx G'$.

First Lemma

As an intermediate step to proving the main theorem, we show that, for every position $G$ and every P-position $A$, the equivalence $G\approx A+G$ holds. By the above definition of equivalence, this amounts to showing that $G+H$ and $A+G+H$ share an outcome class for all $H$.

Suppose that $G+H$ is a P-position. Then the previous player has a winning strategy for $A+G+H$: respond to moves in $A$ according to their winning strategy for $A$ (which exists by virtue of $A$ being a P-position), and respond to moves in $G+H$ according to their winning strategy for $G+H$ (which exists for analogous reason). So $A+G+H$ must also be a P-position.

On the other hand, if $G+H$ is an N-position, then the next player has a winning strategy: choose a P-position from among the $G+H$ options, putting their opponent in the case above. Thus, in this case, $A+G+H$ must be a N-position, just like $G+H$.

As these are the only two cases, the lemma holds.

Second Lemma

As a further step, we show that $G\approx G'$ if and only if $G+G'$ is a P-position.

In the forward direction, suppose that $G\approx G'$. Applying the definition of equivalence with $H=G$, we find that $G'+G$ (which is equal to $G+G'$ by commutativity of addition) is in the same outcome class as $G+G$. But $G+G$ must be a P-position: for every move made in one copy of $G$, the previous player can respond with the same move in the other copy, and so always make the last move.

In the reverse direction, since $A=G+G'$ is a P-postion by hypothesis, it follows from the the first lemma, $G\approx G+A$, that $G\approx G+(G+G')$. Similarly, since $A=G+G$ is also a P-position, it follows from the first lemma in the form $G'\approx G'+A$ that $G'\approx G'+(G+G)$. By associativity and commutativity, the right-hand sides of these results are equal. Furthermore, $\approx$ is an equivalence relation because equality is an equivalence relation on outcome classes. Via the transitivity of $\approx$, we can conclude that $G\approx G'$.

Proof

We prove that all positions are equivalent to a nimber by structural induction. The more specific result, that the given game's initial position must be equivalent to a nimber, shows that the game is itself equivalent to a nimber.

Consider a position $G = \{G_1, G_2, \ldots, G_k\}$. By the induction hypothesis, all of the options are equivalent to nimbers, say $G_i \approx *n_i$. So let $G'=\{*n_1, *n_2, \ldots, *n_k\}$. We will show that $G \approx *m$, where $m$ is the mex (minimum exclusion) of the numbers $n_1, n_2, \ldots, n_k$, that is, the smallest non-negative integer not equal to some $n_i$.

The first thing we need to note is that $G \approx G'$, by way of the second lemma. If $k$ is zero, the claim is trivially true. Otherwise, consider $G+G'$. If the next player makes a move to $G_i$ in $G$, then the previous player can move to $*n_i$ in $G'$, and conversely if the next player makes a move in $G'$. After this, the position is a P-position by the lemma's forward implication. Therefore, $G+G'$ is a P-position, and, citing the lemma's reverse implication, $G \approx G'$.

Now let us show that $G'+*m$ is a P-position, which, using the second lemma once again, means that $G'\approx *m$. We do so by giving an explicit strategy for the previous player.

Suppose that $G'$ and $*m$ are empty. Then $G'+*m$ is the null set, clearly a P-position.

Or consider the case that the next player moves in the component $*m$ to the option $*m'$ where $m'<m$. Because $m$ was the minimum excluded number, the previous player can move in $G'$ to $*m'$. And, as shown before, any position plus itself is a P-position.

Finally, suppose instead that the next player moves in the component $G'$ to the option $*n_i$. If $n_i < m$ then the previous player moves in $*m$ to $*n_i$; otherwise, if $n_i > m$, the previous player moves in $*n_i$ to $*m$; in either case the result is a position plus itself. (It is not possible that $n_i = m$ because $m$ was defined to be different from all the $n_i$.)

In summary, we have $G\approx G'$ and $G'\approx *m$. By transitivity, we conclude that $G \approx *m$, as desired.

Development

If $G$ is a position of an impartial game, the unique integer $m$ such that $G \approx *m$ is called its Grundy value, or Grundy number, and the function which assigns this value to each such position is called the Sprague–Grundy function. R.L.Sprague and P.M.Grundy independently gave an explicit definition of this function, not based on any concept of equivalence to nim positions, and showed that it had the following properties:

• The Grundy value of a single nim pile of size $m$ (i.e. of the position $*m$) is $m$;
• A position is a loss for the next player to move (i.e. a P-position) if and only if its Grundy value is zero; and
• The Grundy value of the sum of a finite set of positions is just the nim-sum of the Grundy values of its summands.

It follows straightforwardly from these results that if a position $G$ has a Grundy value of $m$, then $G + H$ has the same Grundy value as $*m + H$, and therefore belongs to the same outcome class, for any position $H$. Thus, although Sprague and Grundy never explicitly stated the theorem described in this article, it is nevertheless an almost trivial consequence of their results. These results have subsequently been developed into the field of combinatorial game theory, notably by Richard Guy, Elwyn Berlekamp, John Horton Conway and others, where they are now encapsulated in the Sprague–Grundy theorem and its proof in the form described here. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.

See also

• Genus theory
• Indistinguishability quotient

References

• Reprinted, 1964, 27: 9–11.

External links

• Grundy's game at cut-the-knot
• Easily readable, introductory account from the UCLA Math Department
• The Game of Nim at sputsoft.com