Sprague-Grundy theorem
|
|
In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game is equivalent to a nimber. It was discovered independently by R. P. Sprague and P. M. Grundy.
| 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 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. For impartial games, this is the same as the condition that G+G' is a P-position.
Proof
We prove the theorem by structural induction on the set representing the game.
Consider a game <math>G = \{G_1, G_2, \ldots, G_k\}<math>. By the induction hypothesis, all of the options are equivalent to nimbers, say <math>G_i = *n_i<math>. We will show that <math>G = *m<math>, where <math>m<math> is the mex of the numbers <math>n_1, n_2, \ldots, n_k<math>, that is the minimal excluded number: the smallest non-negative integer not equal to some <math>n_i<math>.
So now we need to show that <math>G+*m<math> is a P-position. We do so by giving an explicit strategy for the second player.
Suppose that the first player moves in the component <math>*m<math> to the option <math>*m'<math> where <math>m'
Suppose instead that the first player moves in the component <math>G<math> to the option <math>G_i<math>, which is equivalent to <math>*n_i<math>. If <math>n_i < m<math> then the second player moves from <math>*m<math> to <math>*n_i<math>. If <math>n_i > m<math> then the second player moves <math>*n_i<math> to <math>*m<math>. It's not possible that <math>n_i = m<math> because <math>m<math> was defined to be different from all the <math>n_i<math>.
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.
External links
- Grundy's game (http://www.cut-the-knot.org/Curriculum/Games/Grundy.shtml) and other games.