Nim-Spiel

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

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 ${\displaystyle \textstyle \oplus }$ bei paarigen Operanden und ${\displaystyle \textstyle \bigoplus }$ bei der Verwendung 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

Als Beispiel diene die folgende Stellung mit ${\displaystyle n=5}$ Reihen enthaltend die Anzahlen ${\displaystyle a_{i}}$ von 1, 2, 3, 4 und 7 Hölzchen mit den Dualdarstellungen ${\displaystyle b_{i}}$ (wobei in der Tabelle rechts vom ≙-Zeichen die Hölzchen den Dualstellen entsprechend gruppiert sind):

${\displaystyle {\mathtt {4\,|\;\!2\,|\;\!1}}}$

${\displaystyle {\mathtt {4}}}$

${\displaystyle {\mathtt {2}}}$

${\displaystyle {\mathtt {1}}}$

${\displaystyle a_{1}=1\;\;\implies }$	${\displaystyle b_{1}=}$	${\displaystyle {\mathtt {0\,|\;\!0\,|\;\!1}}}$	≙			|
${\displaystyle a_{2}=2\;\;\implies }$	${\displaystyle b_{2}=}$	${\displaystyle {\mathtt {0\,|\;\!1\,|\;\!0}}}$	≙		||
${\displaystyle a_{3}=3\;\;\implies }$	${\displaystyle b_{3}=}$	${\displaystyle {\mathtt {0\,|\;\!1\,|\;\!1}}}$	≙		||	|
${\displaystyle a_{4}=4\;\;\implies }$	${\displaystyle b_{4}=}$	${\displaystyle {\mathtt {1\,|\;\!0\,|\;\!0}}}$	≙	||||
${\displaystyle a_{5}=7\;\;\implies }$	${\displaystyle b_{5}=}$	${\displaystyle {\mathtt {1\,|\;\!1\,|\;\!1}}}$	≙	||||	||	|

	${\displaystyle \textstyle \sum _{i=1}^{n}b_{i}=}$	${\displaystyle {\mathtt {2\,|\;\!3\,|\;\!3}}}$
	${\displaystyle \textstyle \bigoplus _{i=1}^{n}b_{i}=}$	${\displaystyle {\mathtt {0\,|\;\!1\,|\;\!1}}}$	≙		||	|	[2]

Die Summe der Dualziffern ist in der ${\displaystyle {\mathtt {4}}}$-er-Spalte gerade, aber in der ${\displaystyle {\mathtt {2}}}$-er- und ${\displaystyle {\mathtt {1}}}$-er-Spalte ungerade, nämlich jeweils 3. Die Stellung ist damit eine Gewinnstellung.^[3]

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

Nach der Wegnahme von drei Hölzchen aus der 5. Reihe ergibt sich die folgende Konstellation der Anzahlen und Dualdarstellungen:

${\displaystyle {\mathtt {4\,|\;\!2\,|\;\!1}}}$

${\displaystyle {\mathtt {4}}}$

${\displaystyle {\mathtt {2}}}$

${\displaystyle {\mathtt {1}}}$

${\displaystyle a_{1}=1\;\;\implies }$	${\displaystyle b_{1}=}$	${\displaystyle {\mathtt {0\,|\;\!0\,|\;\!1}}}$	≙			|
${\displaystyle a_{2}=2\;\;\implies }$	${\displaystyle b_{2}=}$	${\displaystyle {\mathtt {0\,|\;\!1\,|\;\!0}}}$	≙		||
${\displaystyle a_{3}=3\;\;\implies }$	${\displaystyle b_{3}=}$	${\displaystyle {\mathtt {0\,|\;\!1\,|\;\!1}}}$	≙		||	|
${\displaystyle a_{4}=4\;\;\implies }$	${\displaystyle b_{4}=}$	${\displaystyle {\mathtt {1\,|\;\!0\,|\;\!0}}}$	≙	||||
${\displaystyle a_{5}=7-3=4\;\;\implies }$	${\displaystyle b_{5}=}$	${\displaystyle {\mathtt {1\,|\;\!0\,|\;\!0}}}$	≙	||||

	${\displaystyle \textstyle \sum _{i=1}^{n}b_{i}=}$	${\displaystyle {\mathtt {2\,|\;\!2\,|\;\!2}}}$
	${\displaystyle \textstyle \bigoplus _{i=1}^{n}b_{i}=}$	${\displaystyle {\mathtt {0\,|\;\!0\,|\;\!0}}}$	≙	(leer)[2]

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 ${\displaystyle {\mathtt {2}}}$-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.^[4]

Zur Regel von Bouton gibt es 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.)

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.

Bemerkenswert an der Gewinnstrategie ist, dass Anzahlen sowohl als gewöhnliche Zahlen wie auch als Bitvektoren angesehen werden müssen. Für eine Implementierung bieten hardwareseitig binär arbeitende Computer Vorteile und softwareseitig Programmiersprachen der C-Familie, in denen Zahlen des Typs unsigned int ganz ohne Umwandlung des Datentyps auch als Bitvektoren aufgefasst werden können und die dazuhin die hier benötigten bitweisen Operationen unterstützen.

Misère

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 gegen Ende wird von ihr abgewichen. Tritt nämlich die Situation ein, dass es genau eine Reihe mit mehr als einem Hölzchen gibt, kann man von dieser Reihe regelkonform 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, ein Ergebnis, das auch bei der Geradzahligkeit der Spaltensummen herauskäme.)

Weitere Varianten

→ Hauptartikel: Nim-Spiel-Variation

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

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

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

Literatur

• Roland P. Sprague: Über mathematische Kampfspiele. In: Tôhoku Mathematical Journal. Band 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))
• 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, urn:nbn:at:at-ubms:3-1736.

Weblinks

• Nim online spielen

Einzelnachweise

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)
2. Die beiden Summenzeichen bilden die spaltenweisen Summen über die Bitvektoren ${\displaystyle b_{i}}$, und zwar ${\displaystyle \textstyle \sum }$ die übliche Summe in ${\displaystyle \mathbb {N} _{0}^{\,d}=\ldots \mathbb {N} _{0}{\mathtt {|}}\mathbb {N} _{0}{\mathtt {|}}\mathbb {N} _{0}}$ und ${\displaystyle \textstyle \bigoplus }$ diejenige in ${\displaystyle {\bigl (}\mathbb {Z} /(2){\bigr )}^{d}=\mathbb {F} _{2}^{\,d}=\ldots \mathbb {F} _{2}{\mathtt {|}}\mathbb {F} _{2}{\mathtt {|}}\mathbb {F} _{2}}$ mit ${\displaystyle d}$ als der maximalen Anzahl der Dualstellen.
3. Bouton entwickelte eine Nim-Addition. Sie folgt aus der bitweisen XOR-Summe der Dualdarstellungen (in diesem Artikel notiert als ${\displaystyle \oplus }$). (Vergleiche: Bewersdorff: Glück, Logik... 2010, S. 117.) Dort werden Dualzahlen spaltenweise zu einer dualen Summe (modulo 2 im Ring ${\displaystyle \mathbb {Z} /(2)=\mathbb {F} _{2}}$) 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.
4. Nach erfolgter Wahl der Reihe ${\displaystyle k}$ ist der Rest des Zuges festgelegt. Ist nämlich ${\displaystyle \textstyle s:=\bigoplus _{i=1}^{n}b_{i},}$ dann ist der Bitvektor für die neue Anzahl der Hölzchen

   ${\displaystyle \textstyle {b_{k}}^{\prime }:=b_{k}\oplus s.}$

   An der höchstrangigen Dualstelle, an der er sich von ${\displaystyle b_{k}}$ unterscheidet, hat er eine '0' anstelle einer '1', weil ${\displaystyle s}$ dort eine '1' hat. Damit verkleinert sich der Zahlenwert, und der Zug ist regelkonform.
5. Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: Gewinnen – Strategien für mathematische Spiele, Band 1.
6. 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.
7. Bewersdorff: Glück, Logik 2010, S. 124.
8. Bewersdorff: Glück, Logik 2010, S. 176.