Definitions

# Sprague–Grundy theorem

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game is equivalent to a nimber. The 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 was discovered independently by R. P. Sprague (1935) and P. M. Grundy (1939).

## 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 the same available moves in every position. Impartial games fall into two outcome classes: either the next player wins (an N-position) or the previous player wins (a P-position).

An impartial game can be identified with the set of positions that can be reached in one move (these are called the options of the game). Thus the game with options A, B, or C is the set {A, B, C}.

A nimber is a special game denoted *n for some ordinal n. We define *0 = {} (the empty set), then *1 = {*0}, *2 = {*0, *1}, and *(n+1) = *n ∪ {*n}. When n is an integer, the nimber *n = {*0, *1, ..., *(n−1)}. This corresponds to a heap of n counters in the game of nim, hence the name.

Two games G and H can be added to make a new game G+H in which a player can chose either to move in G or in H. In set notation, G+H means {G+h for h in H} ∪ {g+H for g in G}, and thus game addition is commutative and associative.

Two games G and G' are equivalent if for every game H, the game G+H is in the same outcome class as G'+H. We write GG'.

## Lemma

For impartial games, GG' if and only if G+G' is a P-position.

Firstly, we note that ≈ is an Equivalence relation since equality of outcome classes is.

We now show that for every game G, and P-position game A, A+GG. By the definition of ≈, we need to show that G+H is in the same outcome-class as A+G+H for all games H. If G+H is P-position, than the previous player has a winning strategy in A+G+H - to every move in G+H he responds according to his winning strategy in G+H, and to every move in A he responds with his winning strategy there. If G+H is N-position, than the next player in A+G+H makes a winning move in G+H, and then reverts to responding to his opponent in the manner described above.

Also, G+G is P-position for any game G. For every move made in one copy of G, the previous player can respond with the same move in the other copy, which means he always makes the last move.

Now, we can prove the lemma.

If GG', then G+G' is of the same outcome-class as G+G, which is P-position.

On the other hand, if G+G' is P-position, then since G+G is also P-position, GG+(G+G') ≈ (G+G)+G'G', thus GG'.

## Proof

We prove the theorem by structural induction on the set representing the game.

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

Let $G\text{'}=\left\{*n_1, *n_2, ldots *n_k\right\}$. The first thing we need to note is that $G approx G\text{'}$. Consider $G+G\text{'}$. If the first player makes a move in $G$, then the second player can move to the equivalent $*n_i$ in $G\text{'}$. After this the game is a P-position (by the lemma), since it's the sum of some option of $G$ and a nim pile equivalent to that option. Therefore, $G+G\text{'}$ is a P-position, and by another application of our lemma, $G approx G\text{'}$.

So now, by our lemma, we need to show that $G+*m$ is a P-position. We do so by giving an explicit strategy for the second player in the equivalent $G\text{'}+*m$.

Suppose that the first player moves in the component $*m$ to the option $*m\text{'}$ where minimal excluded number, the second player can move in $G\text{'}$ to $*m\text{'}$.

Suppose instead that the first player moves in the component $G\text{'}$ to the option $*n_i$. If $n_i < m$ then the second player moves from $*m$ to $*n_i$. If $n_i > m$ then the second player, using the induction hypothesis, moves to $*m$; there must be one since $*n_i$ is the mex of the options of $*n_i$. It's not possible that $n_i = m$ because $m$ was defined to be different from all the $n_i$.

Therefore, $G\text{'}+*m$ is a P-position, and hence so is $G+*m$. By our lemma, $G approx *m$ as desired.

## Development

The Sprague–Grundy theorem has been developed into the field of combinatorial game theory, notably by E. R. Berlekamp, John Horton Conway and others. The field is presented in the books Winning Ways for your Mathematical Plays and On Numbers and Games.