Discover

(Redirected from 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).

Contents

Definitions

Lemma

Proof

Development

References

External links

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''.
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'''.

Lemma

For impartial games, ''G'' ≈ ''G''' if and only if ''G''+''G''' is a ''P-position''.
Firstly, we note that ≈ is an Equivalence relation since equality of outcome classes is. Furthermore, if ''G'' ≈ ''G''' then ''G+H'' ≈ ''G'+H''. This follows from the fact that for every game ''J'', ''G''+''J'' and ''G'''+''J'' are in the same outcome class. In particular, they are whenever ''J'' is of the form ''H''+''K'' for any game ''K''.
Since ''G''+
★ 0 = ''G'' for any game ''G'' and ≈ is an equivalence relation, ''G''+
★ 0 ≈ ''G'' for any game ''G''.
Also, ''G''+''G''≈
★ 0 for any game ''G''. By the definition of ≈, we need to show that ''G''+''G''+''H'' is in the same outcome class as
★ 0+''H'' for all games ''H''. Since
★ 0+''H''=''H'', this reduces to showing ''G''+''G''+''H'' and ''H'' are always in the same outcome class.
If ''H'' is an N position, then the next player to move still has a winning strategy in ''G''+''G''+''H''. First make a move in ''H'', and then when the other player moves in ''H'' respond with the winning strategy there. When the other player moves in a copy of ''G'', copy the move in the other copy.
If ''H'' is a P position, then the previous player still has a winning strategy in ''G''+''G''+''H'': respond to moves in ''H'' with the winning strategy there, and respond to moves in a copy of ''G'' with the same move in the other copy.
Finally, we can prove the lemma.
If ''G'' ≈ ''G''', then ''G''+''G'' ≈ ''G''+''G'''. Since ''G''+''G'' ≈
★ 0, we have ''G''+''G''' ≈
★ 0. In particular, ''G''+''G'''+
★ 0 = ''G''+''G''' and
★ 0+
★ 0 =
★ 0 are in the same outcome class: they're both P positions.
If ''G''+''G''' is a P position, then we can show that ''G''+''G''' ≈
★ 0. We have to show that ''G''+''G'''+''H'' is in the same outcome class as
★ 0+''H'' = ''H'' for all games ''H''. The strategies are the same as in the proof that ''G''+''G''≈
★ 0, except instead of "copying the move in the other copy of ''G''" we "respond with the winning strategy on the P position ''G''+''G'''". Since ''G''+''G''' ≈
★ 0, we can add ''G''' to both sides to get ''G''+''G'''+''G''' ≈
★ 0+''G''', which simplifies to ''G'' ≈ ''G''', as desired.

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
★ n_i. We will show that
★ 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{'}=\{$
★ n_1,
★ n_2, ldots
★ n_k}. The first thing we need to note is that . 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, .
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' where
★ m'.
Suppose instead that the first player moves in the component $G\text{'}$ to the option $$
★ n_i. If 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,
★ m as deisred.

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''.

References

★ Über mathematische Kampfspiele, Sprague, R. P., , , Tohoku Mathematical Journal, 1935–36

★ Mathematics and games, Grundy, P. M., , , Eureka, 1939 Reprinted, 1964, '27': 9–11.

★ {{cite journal
| author = Schleicher, Dierk; Stoll, Michael
| title = An introduction to Conway's games and numbers
| year = 2004
| id =

★ Combinatorial Games, Theory and Applications, Milvang-Jensen, Brit C. A., , , , 2000

External links

★ Grundy's game at cut-the-knot