Sprague–Grundy theorem

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 was discovered independently by R. P. Sprague (1935) and P. M. Grundy (1939).

Contents

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 opponents. And in Tic-Tac-Toe, one player puts down X's, while the other puts down O's. 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}.

The normal play convention is where the last player to move wins. Alternatively, the player who first does not have any valid move loses. The opposite - the misère convention is where the last person to have a valid move or makes the last move loses.

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 choose 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 G ≈ G'.

A game can refer to two things. It can define a set of possible positions and their moves through its rules, for example, chess, or nim. It can also refer to a certain position, for example, the game *5. Generally, the meaning to be taken is clear from the context.

Lemma

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

First, we note that ≈ is an equivalence relation since equality of outcome classes is an equivalence relation.

We now show that for every game G, and P-position game A, A+G ≈ G. 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, then 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, then 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 G ≈ G', 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, G ≈ G+(G+G') ≈ (G+G)+G' ≈ G', thus G ≈ G'.

Proof

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

Consider a game 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. 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'=\{*n_1, *n_2, \ldots *n_k\}. The first thing we need to note is that G \approx G'. Consider G%2BG'. If the first player makes a move in G, then the second player can move to the equivalent *n_i in G'. 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%2BG' is a P-position, and by another application of our lemma, G \approx G'.

So now, by our lemma, we need to show that G%2B*m is a P-position. We do so by giving an explicit strategy for the second player in the equivalent G'%2B*m.

Suppose that the first player moves in the component *m to the option *m' where m'<m. But since m was the minimal excluded number, the second player can move in G' to *m'.

Suppose instead that the first player moves in the component G' to the option *n_i. If n_i < m then the second player moves in *m to *n_i. If n_i > m then the second player, moves in *n_i to *m. It's not possible that n_i = m because m was defined to be different from all the n_i.

Therefore, G'%2B*m is a P-position, and hence so is G%2B*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.

See also

References

External links