Nim-Spiel

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Ausgangsstellung
des Spiels aus dem Film Letztes Jahr in Marienbad

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.

Gewinnstrategie nach Bouton[Bearbeiten | Quelltext bearbeiten]

Für alle diese Spiele, Standard-Nim, Misère-Nim und viele andere Spiele, ist bei jedem Spielstand klar und meist 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 (nach jedem beliebigen Zug des Anziehenden) erzwingen. Für Standard-Nim und Misère-Nim gilt die folgende Gewinnstrategie:

Man stellt die Anzahlen der Hölzchen in den Reihen dual dar und errechnet daraus pro Dualstelle die Spaltensummen.

Findet man eine Stellung mit ausschließlich geradzahligen Spaltensummen vor, so ist dies für den ziehenden Spieler eine Verluststellung, die bei optimalem Spiel des Gegners dazu führt, dass er in der Verliererrolle bleibt und am Ende des Spiels dem Gegner eine Gewinnvorlage für seinen letzten Zug (finale Gewinnstellung) übergeben muss. Ist andererseits mindestens eine der Spaltensummen ungerade, so ist dies eine Gewinnstellung (mögliche Ausnahme: das Endspiel des Misère-Nim). 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 bitweisen exklusiv-ODER-Summe (»XOR-Summe«) der Dualdarstellungen. Für diese bitweise exklusiv-ODER-Summe findet sich häufig, so auch in diesem Artikel, die mathematische Notation bei paarigen Operanden und beim Gebrauch mit Laufvariablen.

Zusammengefasst

Aus einer Verluststellung muss man immer eine Gewinnstellung machen, aus einer Gewinnstellung kann man immer eine Verluststellung erzeugen.

Die Strategie anhand eines Beispiels[Bearbeiten | Quelltext bearbeiten]

Als Beispiel diene die folgende Stellung mit Reihen enthaltend die Anzahlen von 1, 2, 3, 4 und 7 Hölzchen mit den Dualdarstellungen (wobei rechts vom ≙-Zeichen die Hölzchen den Dualstellen entsprechend gruppiert sind):

  ≙   |
  ≙   ||
  ≙   || |
  ≙   ||||
  ≙   |||| || |
  ≙   || |

Dabei bilden die beiden Summenzeichen die spaltenweisen Summen über die Bitvektoren , und zwar die übliche Summe in und diejenige in , wobei die Anzahl der Spalten (= der Dualstellen) so groß gewählt sei, dass diese zur Bildung aller ausreichen.

Nun ist die Summe der Ziffern in der -er-Spalte gerade, aber die -er- und die -er-Spalte haben eine ungerade Summe, nämlich jeweils 3. Die Stellung ist also eine Gewinnstellung.[2]

Wenn in dieser Spielstellung gemäß der Gewinnstrategie entweder aus der 2. Reihe ein Hölzchen oder aus der 3. oder 5. drei Hölzchen entfernt werden, entsteht für den Nachziehenden eine Verluststellung mit nur geraden Spaltensummen. Es gibt außer diesen drei Zugmöglichkeiten viele andere regelkonforme, die aber alle dazu führen würden, dass der Gegner eine Gewinnstellung statt einer Verluststellung bekommt. – Hier als Beispiel die Stellung nach dem Zug, der aus der 5. Reihe 3 Hölzchen entfernt.

Die Dualzahlen nach der Wegnahme von 3 Hölzchen aus der 5. Reihe:

  ≙   |
  ≙   ||
  ≙   || |
  ≙   ||||
  ≙   ||||
  ≙     (leer)  

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

Andererseits gibt es 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 her die erste (also die höchstrangige) Spalte mit ungerader Summe (im obigen Beispiel war es die -er-Spalte). Es muss dann eine Reihe geben, die in dieser Spalte eine '1' hat. Aus einer solchen Reihe entnehme man Hölzchen in einer Weise, dass in dieser Spalte und in allen Spalten weiter rechts (links stimmt's vorher schon) gerade Spaltensummen entstehen.[3]

Die Regel von Bouton enthält eine sehr einfache Unterregel. Hat der Spieler beim letzten Mal seinem Gegner eine Verluststellung übergeben, die zwei Reihen mit gleich vielen Hölzchen enthält, und entnimmt der Gegner aus einer der beiden Reihen eine gewisse Anzahl Hölzchen, dann erzeugt die Entnahme von gleich vielen Hölzchen aus der anderen Reihe wieder eine Verluststellung. (Zu beachten ist allerdings ggf. das Endspiel des Misère-Nim.)

Bemerkenswert an dieser Gewinnstrategie ist, dass Anzahlen sowohl als gewöhnliche Zahlen wie auch als Bitvektoren angesehen werden müssen. Im Fall einer Realisierung bedeutet das hardwareseitig eine Bevorzugung binär arbeitender Computer und softwareseitig eine von Programmiersprachen der C-Familie, bei denen ohne Umwandlung des Datentyps Zahlen zugleich als Bitvektoren mit zugehörigen bitweisen Operationen aufgefasst werden können.

Frühe Nim-Computer[Bearbeiten | Quelltext 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 | Quelltext bearbeiten]

Beim Misère-Spiel hat der Spieler, der das letzte Hölzchen nimmt, nicht gewonnen, sondern verloren. Eine verbreitete Variante des Misère-Nim ist Marienbad, dessen Ausgangsstellung in der Abbildung gezeigt ist.

In der Hauptsache regiert dieselbe Gewinnstrategie wie beim Standard-Nim. Erst zum Schluss wird von ihr abgewichen. Irgendwann gibt es nämlich genau eine Reihe mit mehr als einem Hölzchen. Von dieser Reihe kann man regelgemäß alle Hölzchen oder alle bis auf eines wegnehmen. Will man gewinnen, übergibt man eine ungerade Anzahl von Einser-Reihen. (Beim Standard-Nim wäre es eine gerade Anzahl, was übrigens gleichbedeutend ist mit der Geradzahligkeit der Spaltensummen.)

Weitere Varianten[Bearbeiten | Quelltext bearbeiten]

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

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

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

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. C. L. Bouton: Nim, a game with a complete mathematical theory. In: Annals of Mathematics. (2) 3 (1901), S. 35–39 (Abstract im Electronic Research Archive for Mathematics)
  2. Bouton entwickelte eine Nim-Addition. Sie folgt aus der bitweisen XOR-Summe der Dualdarstellungen. (Vergleiche: Bewersdorff: Glück, Logik... 2010, S. 117.) Dort werden Dualzahlen spaltenweise zu einer dualen Summe (modulo 2 im Ring ) addiert, also ohne irgendwelche Überträge zu einer Nachbarspalte. Diese Summe wird Nim-Summe genannt. Sie ist genau dann 0, wenn alle Spaltensummen gerade sind, und ≠ 0, wenn mindestens eine Spaltensumme ungerade ist.
  3. Nach erfolgter Wahl der Reihe ist der Rest des Zuges eindeutig. Ist nämlich dann ist der Bitvektor für die neue Anzahl der Hölzchen
    An der höchstrangigen Dualstelle, an der er sich von unterscheidet, hat er eine '0' anstelle einer '1', so dass sein Zahlenwert kleiner ist. Der Zug ist also regelkonform.
  4. Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Gewinnen – Strategien für mathematische Spiele, Band 1.
  5. Lösung in B. Kummer,Spiele auf Graphen. Deutscher Verlag der Wissenschaften, Berlin 1979; Birkhäuser, Basel 1980 (ISNM Series, Vol 44), doi:10.1007/978-3-0348-5481-8, S. 47, Aufgabe 1.
  6. Bewersdorff: Glück, Logik 2010, S. 124.
  7. Bewersdorff: Glück, Logik 2010, S. 176.