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.

Neutrales Spiel

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

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

Einzelnachweise
  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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.