Nim-Spiel

Ausgangsstellung mit Streichhölzern

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) von Streichhölzern vorgegeben werden. Zwei Spieler nehmen abwechselnd eins oder mehrere Hölzer aus einer der Reihen weg. Wie viele sie nehmen, spielt keine Rolle; es dürfen bei einem Zug jedoch nur Streichhölzer 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 als Gewinnstrategie gefunden.

In der Arbeit von Grundy wird die optimale Strategie 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.

Gewinnstrategie nach Bouton

Für alle diese Spiele, Standard-Nim, Misère-Nim und viele andere Spiele, ist bei jedem Spielstand bekannt und leicht berechenbar, ob der Spieler am Zug den Sieg erzwingen kann und auf welche Weise. Und wenn der Anziehende den Sieg nicht erzwingen kann, dann kann ihn der Nachziehende erzwingen. Für Standard-Nim und Misère-Nim gilt die folgende Gewinnstrategie:

Man stellt die Anzahlen der Streichhölzer in den Reihen dual dar und errechnet aus diesen Spalten- bzw. Stellensummen.

Findet man eine Stellung mit nur geraden Spaltensummen vor, so ist dies (für den ziehenden Spieler) eine Verluststellung, die bei optimalem Spiel des Gegners dazu führt, dass man in der Verliererrolle bleibt, am Ende des Spiels dem Gegner eine Gewinnvorlage für seinen letzten Zug zu geben. Ist mindestens eine der Spaltensummen ungerade, so ist dies entsprechend eine Gewinnstellung. Es ist dann möglich, gerade Spaltensummen durch den eigenen Zug zu erreichen, wodurch man dem Gegner eine Verluststellung übergibt.

Diese Prüfung auf Geradzahligkeit der Spaltensummen entspricht der (bitweise exklusive ODER)-Summe der Dualdarstellungen.

Aus einer Verluststellung kann nichts anderes als eine Gewinnstellung erzeugt werden, aus einer Gewinnstellung (bis hin zur Gewinnvorlage des letzten Zuges) kann man immer eine Verluststellung erzeugen. Da der Gewinner beim letzten Zug sicher nur eine Reihe vorfindet, sind die Spaltensummen nach dem vorletzten Zug auch ungerade.

Beispiel für die Strategie

Als Beispiel diene die folgende Gewinnstellung mit fünf Reihen zu 1, 2, 3, 4 und 5 Streichhölzern:

|  

| |  

| | |  

| | | |  

| | | | |  

Die Dualdarstellungen dazu

0-0-1 (Dualzahl von 1)
0-1-0 (Dualzahl von 2)
0-1-1 (Dualzahl von 3)
1-0-0 (Dualzahl von 4)
1-0-1 (Dualzahl von 5)

Summen der '1'-en pro Spalte ergeben:
2-2-3

Die rechte Spalte (Einerspalte) hat eine ungerade Summe, nämlich 3, alle anderen Spaltensummen sind gerade.

Wenn in dieser Spielstellung gemäß der Gewinnstrategie entweder aus der 1., 3. oder 5. Reihe 1 Streichholz entfernt wird, entsteht für den Nachfolger eine Verluststellung mit nur geraden Spaltensummen. Es gibt andere erlaubte Zugmöglichkeiten, sie sind aber nicht optimal gemäß der Strategie, denn sie würden dazu führen, dass der Gegner eine Gewinnstellung statt einer Verluststellung bekommt. - Hier als Beispiel die Stellung nach einem Zug der aus der 5. Reihe ein Hölzchen entfernt:

Die Dualzahlen nach der Wegnahme eines Hölzchens aus der 5. Reihe:

0-0-1 (Dualzahl von 1)
0-1-0 (Dualzahl von 2)
0-1-1 (Dualzahl von 3)
1-0-0 (Dualzahl von 4)
1-0-0 (Dualzahl von 4)
Die Spaltensummen sind:
2-2-2

Dies ist eine Verluststellung für den Spieler, der jetzt am Zug ist. Er muss aus genau einer Reihe mindestens 1 Streichholz entnehmen und muss also in dieser Reihe mindestens eine '1' zu einer '0' machen, wodurch diese Dualstelle eine ungerade Spaltensumme bekommt. Er muss also eine Gewinnstellung erzeugen. Es geht nicht anders.

Es gibt jedoch immer mindestens eine Möglichkeit, um aus einer Gewinnstellung (die man vorfindet) eine Verluststellung (für den Gegner) zu machen: Dazu ermittelt man von links die erste (also die größte) ungerade Spaltensumme und nehme aus einer der Reihen, die an dieser Stelle eine '1' haben, Streichhölzer weg. Da alle kleineren Anzahlen als bisher in dieser Reihe herstellbar sind, kann man alle Spalten weiter rechts so beeinflussen, dass auch dort gerade Spaltensummen entstehen.

Frühe Nim-Computer

Nimrod im Computerspielemuseum Berlin

Die Strategie von Bouton macht Nim zu einem Spiel, das einfach zu programmieren ist. Frühe Computer wurden für das Nim-Spiel entwickelt. 1940 stellte die Firma Westinghouse auf der New-Yorker Weltausstellung ihr Gerät Nimatron aus und 1951 beeindruckte ein in England gebauter elektronischer Rechner namens Nimrod die Öffentlichkeit dadurch, dass er auf der Berliner Industrieausstellung den damaligen Wirtschaftsminister Ludwig Erhard im Nim-Spiel schlug.

Misère

Beim Misère-Spiel hat der Spieler, der die letzten Streichhölzer nimmt, nicht gewonnen, sondern verloren. Eine verbreitete Variante des Misère-Spiels ist Marienbad.

Man verwendet die Gewinnstrategie wie beim Standard-Nim. Erst zum Schluss wird von ihr abgewichen. Kommt es zu einer Stellung, in der man durch einen Zug nur Reihen mit je einem Streichholz erhalten kann, so zieht man so, dass nach dem Zug eine ungerade Anzahl solcher Einser-Reihen entsteht.

Weitere Varianten

Neben den hier genannten Spielregeln gibt es noch weitere Nim-Spiel-Varianten.

Beim Lasker-Nim entfernt ein Spieler entweder Hölzchen aus einer Reihe oder zerteilt die Reihe in zwei nicht unbedingt gleich große Teile.

Manchmal wird die genannte Spielregel so eingeschränkt, dass man nur eine bestimmte Anzahl von Hölzchen einer Reihe nehmen darf. Beim Kegel-Nim dürfen aus einer Reihe ein oder zwei Hölzchen genommen werden, wobei die Reihe dadurch auch geteilt werden darf.

Schwarz-Weiß-Nim wird mit aus Dame-Steinen aufgebauten Türmen gespielt. Man wählt einen Stein der eigenen Farbe aus und entfernt ihn zusammen mit den darüberliegenden Steinen.

Nimbi ist eine Nim-Variante mit zwölf Steinen auf zwölf Geraden nach der Misère-Regel. Es wurde von Piet Hein, einem Miterfinder des Hex-Spiels, etwa 1950 erfunden. Die Anfangsposition ist eine Verlustposition.

Literatur

• Jörg Bewersdorff: Glück, Logik und Bluff: Mathematik im Spiel - Methoden, Ergebnisse und Grenzen, Vieweg+Teubner Verlag, 5. Auflage 2010, ISBN 3-8348-0775-3, 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 3-528-08531-2, ISBN 3-528-08532-0, ISBN 3-528-08533-9, ISBN 3-528-08534-7 (engl. Original: Winning Ways for your Mathematical Plays., 2 Bände, ISBN 0-12-091101-9, ISBN 0-12-091102-7, 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 (Memento vom 27. September 2007 im Internet Archive))