Satz von Sprague-Grundy

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Neutrales Spiel[Bearbeiten]

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.

Theorem[Bearbeiten]

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.

Literatur[Bearbeiten]

Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel - Methoden, Ergebnisse und Grenzen, Vieweg+Teubner Verlag, 5. Auflage 2010, ISBN 3834807753, doi:10.1007/978-3-8348-9696-4.

Elwyn R. Berlekamp , John H. Conway, Richard K. Guy: Gewinnen - Strategien für mathematische Spiele, 1985/86, 4 Bände, ISBN 3528085312, ISBN 3528085320, ISBN 3528085339, ISBN 3528085347, doi:10.1007/978-3-322-83170-5, doi:10.1007/978-3-322-83171-2, doi:10.1007/978-3-322-83172-9, doi:10.1007/978-3-322-83173-6 (engl. Original: Winning Ways for your Mathematical Plays., 2 Bände, ISBN 0120911019, ISBN 0120911027, Academic Press 1982, aktualisierte Neuauflagen 2001 bis 2004).

Emanuel Lasker: Brettspiele der Völker, Berlin 1931.

Roland P. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438-444 (Online-Version).

Patrick M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9-11 (Online-Version)

Einzelnachweise[Bearbeiten]

  1. Roland P. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438-444 (Online-Version). Patrick M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9-11 (Online-Version).
  2. John Horton Conway: Über Zahlen und Spiele. Braunschweig, 1983, ISBN 3528084340, doi:10.1007/978-3-322-88997-3
  3. Jörg Bewersdorff: Glück, Logik und Bluff 2010, S. 121