Satz von Sprague-Grundy

Der Satz von Sprague-Grundy ist ein Theorem aus der Kombinatorischen Spieltheorie. Roland Sprague und Patrick Michael Grundy entdeckten^[1] 1935 und 1939 unabhängig voneinander, dass sich die heute so genannten neutralen Spiele, bei denen der zuletzt ziehende Spieler gewinnt, so auffassen lassen, als wären sie Reihen des Nim-Spiels.

Ein Spiel mit perfekter Information für zwei Spieler ohne Unentschieden wird neutrales Spiel (englisch: impartial game, seltener auch übersetzt als objektives Spiel^[2]) genannt, wenn die Zugmöglichkeiten in einer Position unabhängig davon sind, welcher Spieler zieht. Oft zerfallen solche Spiele in verschiedene Komponenten: Dabei muss jeweils in genau einer Komponente gezogen werden, und durch einen Zug in einer Komponente bleiben die Zugmöglichkeiten in den anderen Komponenten unverändert. Man spricht in solchen Fällen von einer Summe von Positionen. Beispiele für solche Summen von Positionen sind die nebeneinander gelegten Reihen beim Nim-Spiel und ebenso bei dessen Varianten.

Emanuel Lasker beschrieb 1931 eine Variante des Nim-Spiels, in der man – statt nur Streichhölzer aus einer Reihe zu nehmen – auch die Reihen (bei Lasker Haufen) in nicht unbedingt gleiche Teile teilen darf. Sprague und Grundy entdeckten nun, dass sich dieses Lasker-Nim-Spiel und alle weiteren neutralen Spiele mit einer allgemeinen Gewinnstrategie nach dem Vorbild der Strategie beim Nim-Spiel spielen lassen.

Das Theorem von Sprague-Grundy besagt, dass bei einem neutralen Spiel, bei dem der zuletzt ziehende Spieler gewinnt, jede Spielstellung äquivalent zu einer Reihe des Standard-Nim-Spiels ist, deren Größe Grundy-Wert genannt wird. Das heißt, dass diese Stellung innerhalb jeder beliebigen Summe von Positionen durch eine normale Nim-Reihe ersetzt werden kann, ohne dass sich dadurch die Gewinnaussichten ändern.^[3]

Der Grundy-Wert einer Stellung kann durch die in einem Zug erreichbaren Positionen berechnet werden: Er ist gleich der kleinsten natürlichen Zahl, die nicht Grundy-Wert einer Nachfolgestellung ist. Um zu gewinnen, muss ein Spieler stets versuchen, eine Stellung mit dem Grundy-Wert 0 zu erreichen.

• Jörg Bewersdorff: Glück, Logik und Bluff. Mathematik im Spiel, Methoden, Ergebnisse und Grenzen. 5. Auflage. 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 (Erstauflage in 2 Bänden, 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.

• • deutsch: Gewinnen. Strategien für mathematische Spiele. Vieweg, Braunschweig 1985/86 (4 Bände).

1. Von der Pike auf. 1985, ISBN 3-528-08531-2, doi:10.1007/978-3-322-83170-5.
2. Bäumchen-wechsle-dich. 1986, ISBN 3-528-08532-0, doi:10.1007/978-3-322-83171-2.
3. Fallstudien. 1986, ISBN 3-528-08533-9, doi:10.1007/978-3-322-83172-9.
4. Solitärspiele. 1985, ISBN 3-528-08534-7. doi:10.1007/978-3-322-83173-6.

• Emanuel Lasker: Brettspiele der Völker. Rätsel- und mathematische Spiele. Scherl Verlag, Berlin 1931, urn:nbn:at:at-ubms:3-1736.
• Roland Sprague: Über mathematische Kampfspiele. In: Tôhoku Mathematical Journal/1. Serie. Band 41 (1935), S. 438–444, ISSN 0040-8735 (Online-Version).
• Patrick M. Grundy: Mathematics and games. In: Eureka. The journal of the Archimedeans. Band 2, 1939, S. 6–8, Nachdruck Eureka, Band 27 (1940), S. 9–11, ISSN 0071-2248 (Online-Version (Memento vom 3. März 2016 im Internet Archive))

1. ↑ Roland P. Sprague: Über mathematische Kampfspiele. S. 438–444,
   Patrick M. Grundy: Mathematics and games. S. 9–11.
2. ↑ John Horton Conway: Über Zahlen und Spiele. Vieweg, Braunschweig 1983, ISBN 3-528-08434-0, doi:10.1007/978-3-322-88997-3
3. ↑ Jörg Bewersdorff: Glück, Logik und Bluff. S. 121.