Nim-Spiel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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 welche aus einer der Reihen weg. Wie viele sie nehmen, spielt keine Rolle; es muss mindestens ein Streichholz sein, und es dürfen bei einem Zug nur Streichhölzer 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.[1]

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[Bearbeiten]

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[Bearbeiten]

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.[2]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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. [3]

Manchmal wird die genannte Spielregel so eingeschränkt, dass man nur eine bestimmte Anzahl von Hölzchen einer Reihe nehmen darf. Beim Kegel-Nim[4] 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.[5]

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 (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. C. L. Bouton: Nim, a game with a complete mathematical theory, Annals of Mathematics, (2) 3 (1901), S. 35-39 (Abstract im Electronic Research Archive for Mathematics)
  2. Bouton entwickelte eine Nim-Addition. (Vergleiche: Bewersdorff: Glück, Logik... 2010, S. 117.) Dort werden Dualzahlen zu einer dualen Summe so addiert, dass bei dieser Addition keine Überträge gemacht werden. Diese Summe wird Nim-Summe genannt. Sie ist genau dann '0', wenn alle Spaltensummen gerade sind und '1', wenn mindestens eine Spaltensumme ungerade ist.
  3. Lösung in B. Kummer "Spiele auf Graphen." Deutscher Verlag der Wissenschaften, Berlin 1979; Birkhäuser, Basel 1980 (ISNM Series, Vol 44), S.47, Aufgabe 1.
  4. Bewersdorff: Glück, Logik 2010, S. 124
  5. Bewersdorff: Glück, Logik 2010, S. 176