Sprague-Grundy's theorem

The Sprague-Grundy theorem is a theorem from the combinatorial game theory . Roland Sprague and Patrick Michael Grundy discovered in 1935 and 1939, independently of one another, that today's so-called neutral games, in which the last player to draw wins, can be interpreted as if they were rows of the Nim game .

Neutral game

A game with perfect information for two players without a tie is called a neutral game (English: impartial game , less often translated as an objective game ) if the move possibilities in a position are independent of which player moves. Often such games are broken down into different components: You have to move in exactly one component, and a move in one component does not change the move options in the other components. In such cases one speaks of a sum of positions. Examples of such sums of positions are the rows placed next to each other in the Nim game and also in its variants.

In 1931, Emanuel Lasker described a variant of the Nim game in which - instead of just taking matches from a row - you can also divide the rows (in Lasker Haufen ) into not necessarily equal parts. Sprague and Grundy have now discovered that this Lasker Nim game and all other neutral games can be played with a general winning strategy modeled on the strategy in the Nim game.

theorem

Sprague-Grundy's theorem states that in a neutral game where the last player to draw wins, each position is equivalent to a series of the standard Nim game, the size of which is called the Grundy value. This means that this position can be replaced by a normal Nim number within any sum of positions without changing the profit prospects.

The basic y value of a position can be calculated from the positions that can be reached in one move: It is equal to the smallest natural number that is not the basic y value of a subsequent position. In order to win, a player must always try to achieve a position with a Grundy value of 0.

literature

• Jörg Bewersdorff : luck, logic and bluff. Mathematics in the game, methods, results and limits. 5th edition. Vieweg + Teubner Verlag, Wiesbaden 2010, ISBN 978-3-8348-0775-5 ( doi: 10.1007 / 978-3-8348-9696-4 ).
• Elwyn R. Berlekamp , John H. Conway , Richard K. Guy : Winning Ways for your Mathematical Plays . Peters Publ., Wellesley, Mass. 2001/04 (first edition in 2 volumes, New York 1982)

1. 2001, ISBN 1-56881-130-6 .
2. 2003, ISBN 1-56881-142-X .
3. 2003, ISBN 1-56881-143-8 .
4. 2004, ISBN 1-56881-144-6 .

• • German: to win. Strategies for Math Games . Vieweg, Braunschweig 1985/86 (4 volumes).

1. From the bottom up . 1985, ISBN 3-528-08531-2 , doi : 10.1007 / 978-3-322-83170-5 .
2. Sapling-change-yourself . 1986, ISBN 3-528-08532-0 , doi : 10.1007 / 978-3-322-83171-2 .
3. Case studies . 1986, ISBN 3-528-08533-9 , doi : 10.1007 / 978-3-322-83172-9 .
4. Solitaire games . 1985, ISBN 3-528-08534-7 . doi : 10.1007 / 978-3-322-83173-6 .

• Emanuel Lasker : Board games of the peoples. Puzzle and math games . Scherl Verlag, Berlin 1931.
• Roland Sprague : About math fighting games. In: Tôhoku Mathematical Journal / 1. Series. Volume 41 (1935), pp. 438-444, ISSN  0040-8735 ( online version ).
• Patrick M. Grundy: Mathematics and games. In: Eureka. The journal of the Archimedeans. Volume 2, 1939, pp. 6-8, reprint Eureka, Volume 27 (1940), pp. 9-11, ISSN  0071-2248 ( online version ( Memento from September 27, 2007 in the Internet Archive ))

Individual evidence

1. ^ Roland P. Sprague: About mathematical fighting games. Pp. 438-444,
   Patrick M. Grundy: Mathematics and games. Pp. 9-11.
2. ^ John Horton Conway : About Numbers and Games . Vieweg, Braunschweig 1983, ISBN 3-528-08434-0 , doi : 10.1007 / 978-3-322-88997-3
3. ↑ Jörg Bewersdorff: Luck, Logic and Bluff. P. 121.