Nim-Spiel

Das Nim-Spiel ist ein Spiel für zwei Personen, bei dem abwechselnd eine Anzahl von Gegenständen, etwa Streichhölzer, weggenommen werden. Gewonnen hat beim Standardspiel derjenige, der das letzte Hölzchen nimmt, bei der Misère-Variante verliert dagegen derjenige, der das letzte Hölzchen nehmen muss.

Spielt man das Spiel mit nur einer Reihe (ähnlich dem Bachet’schen Spiel), so wird eine Höchstzahl von wegnehmbaren Hölzchen pro Zug festgelegt.

Spieltheoretisch interessant ist die in diesem Artikel beschriebene Spielart, bei der mehrere Reihen (in der Literatur auch: Haufen oder Zeilen) von Hölzchen vorgegeben werden. Zwei Spieler nehmen abwechselnd eins oder mehrere Hölzchen aus einer der Reihen weg. Wie viele sie nehmen, spielt keine Rolle; es dürfen bei einem Zug jedoch nur Hölzchen aus einer einzigen Reihe genommen werden.

Die Nim-Spiel-Varianten werden unter die Spiele mit perfekter Information für zwei Spieler ohne Unentschieden eingeordnet. Nim ist ein neutrales Spiel (englisch: impartial game), weil die Zugmöglichkeiten in einer Position unabhängig davon sind, welcher Spieler zieht. Für das mehrreihige Nim-Spiel hat Charles Leonard Bouton 1901 eine Formel für die Gewinnstrategie gefunden.^[1]

In der Arbeit von Grundy wird die Gewinnstrategie bei neutralen Spielen über so genannte Grundy-Werte auf die Strategie beim Nim-Spiel zurückgeführt (s. Satz von Sprague-Grundy). Des Weiteren verallgemeinert sich die Theorie des Nim-Spiels ab etwa 1970 zur Kombinatorischen Spieltheorie.

1. ↑ C. L. Bouton: Nim, a game with a complete mathematical theory. In: Annals of Mathematics. (2) 3 (1901), S. 35–39, doi:10.2307/1967631 (Abstract in zbMATH)