Nim-Spiel

Das Nim-Spiel ist ein Spiel mit perfekter Information für zwei Spieler ohne Unentschieden und damit auch ein Spiel mit vollständiger Information.

Es wurde unabhängig voneinander 1935 von R. Sprague^[1] und 1939 von P. Grundy^[2] detailliert untersucht und zum Paradebeispiel dieser Art von Spielen gemacht (siehe auch Theorem von Sprague-Grundy in der englischen Wikipedia). Insofern markiert es einen Ausgangspunkt der mathematischen Spieltheorie.

Spielregel

Beim Nim-Spiel sind mehrere Reihen mit Streichhölzern vorhanden. Zwei Spieler nehmen abwechselnd Streichhölzer 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. Derjenige Spieler, der den letzten Zug macht, also die letzten Streichhölzer wegnimmt, gewinnt.

Es existiert eine optimale Spielstrategie, die es einem der beiden Spieler ermöglicht, das Spiel auf jeden Fall zu gewinnen, unabhängig von den Aktionen des Gegenspielers.

Alternative Regeln

Es existiert eine Reihe von Spielvarianten, die hier nicht weiter besprochen oder analysiert werden. Diese Regeln werden teilweise eingeführt, um das Spiel interessanter zu gestalten oder um die Anwendung der bekannten optimalen Strategie auszuschließen.

Spezielle Anfangssituationen

• Variante:
  • Jede Reihe enthält die gleiche Anzahl von Streichhölzern.
• Variante:
  • Die 1. Reihe enthält 1 Streichholz,
  • die 2. Reihe enthält 2 Streichhölzer,
  • die 3. Reihe enthält 3 Streichhölzer,
  • usw.

Andere Gewinnregel

Der Spieler, der die letzten Streichhölzer entnimmt, hat nicht gewonnen, sondern verloren. Eine solche Variante heißt Misère-Spiel. Eine verbreitete Variante des Misère-Spiels ist Marienbad, das durch den Film Letztes Jahr in Marienbad von Alain Resnais bekannt wurde.

Spezialfall des Spiels

Ein Spezialfall des Spiels ist bekannt als ein Spiel des Bachet, später auch als „Ziel 100“.

Einschränkungen bei der Zugfolge

Die Anzahl der Streichhölzer, die aus einer Reihe entfernt werden dürfen, ist nach oben begrenzt (z. B.: es dürfen nur zwischen 1 und 3 Streichhölzer bei einem Zug entnommen werden).

Die Bubi-Variante

Die Bubi-Variante ist eine gute Alternative zum üblichen Spiel, da das Nim-Spiel an Reiz verliert, sobald ein Mitspieler nach der Idealstrategie spielt. Hierbei bleibt das Ziel gleich, nur die Anzahl der wegnehmbaren Streichhölzer wird verändert. Zum Beispiel wird nur das Entfernen von 1, 3 und 5 Streichhölzer pro Zug erlaubt. Dadurch wird die Idealstrategie unbrauchbar und muss bei jeder Untervariante der Bubi- Variante geändert, wenn nicht sogar völlig neu aufgestellt werden. Die erlaubte Anzahl kann beliebig variieren. Es muss jedoch das Kriterium erfüllt werden, dass mindestens eine ungerade und eine gerade Zahl unter den erlaubten Streichhölzern vorhanden ist. Der Schwierigkeitsgrad kann noch weiter erhöht werden, indem man sowohl die erlaubte Anzahl der wegnehmbaren Streichhölzern vergrößert als auch größere Sprünge zwischen den Zahlen einbaut. Dies setzt jedoch eine höhere Gesamtzahl der Streichhölzer voraus.

Strategie

Wie bei allen schrumpfenden Spielen mit perfekter Information ohne Unentschieden für zwei Spieler gibt es zwei Kategorien von Spielstellungen (wenn man von einer Endstellung des Spiels zunächst absieht):

1. die Z-Stellung (von „Zwang“): Aus einer Z-Stellung muss immer eine C-Stellung gemacht werden.
2. die C-Stellung (von „Chance“): Aus einer C-Stellung kann immer eine Z-Stellung gemacht werden.

Graphentheoretische Charakterisierung

Die Stellungen lassen sich in einem gerichteten Graphen darstellen mit Knoten für die Stellungen und Bögen (gerichteten Kanten) für die möglichen Züge. In graphentheoretischer Sprechweise wird eine Menge von Knoten, die die oben erwähnte Kategorisierung ausdrückt, als Kern bezeichnet, d. i. eine stabile Untermenge von Knoten, die zugleich dominierend ist.^[3] Der Kern ist die Menge der Z-Knoten. Die Stabilität steht für den Zwang, von einem Z-Knoten zu einem C-Knoten gehen zu müssen, und die Dominanz für die Chance, von einem C-Knoten zu einem Z-Knoten gehen zu können.

In der Graphentheorie gibt es Theoreme, unter welchen Bedingungen Kerne existieren und ob sie eindeutig sind. Ferner gibt es Algorithmen zur Berechnung von Kernen (siehe auch graphentheoretischer Algorithmus).

Numerische Charakterisierung

Dieser Abschnitt beschränkt sich auf die Standard- und die Misère-Variante des Nim-Spiels, allerdings bei einer konzeptionell beliebigen Anzahl von Streichhölzern.

Fall A: Es gibt wenigstens zwei Reihen mit wenigstens zwei Streichhölzern:

(„Nim-Summen-Kriterium“)

Man stellt die Anzahlen der Streichhölzer in den Reihen dual (= binär) dar. Eine Spielstellung ist eine Z-Stellung, wenn jede Dualstelle („Spalte“) mit einer geraden Anzahl (über die Reihen hinweg) von '1'-en belegt ist.

In den anderen Fällen, wenn also mindestens eine Dualstelle ungeradzahlig oft mit '1' belegt ist, liegt eine C-Stellung vor.

Fall B: Es gibt genau eine Reihe mit mehr als einem Streichholz:

Eine solche Stellung ist eine C-Stellung. Es gibt genau eine siegbringende Nachfolgestellung, die leicht auszuzählen ist.

Fall C: Es gibt keine Reihe mit mehr als einem Streichholz

(d. h., alle übrig gebliebenen Reihen enthalten genau ein Streichholz):

Die übrig gebliebenen Wahlmöglichkeiten können den Ausgang des Spiels nicht mehr beeinflussen.

Fall Cg: Die Anzahl der Streichhölzer ist gerade:

Der übergebende Spieler wird das letzte Streichholz nehmen, d. h. bei der Standard-Regel (das Nehmen des letzten Streichholzes gewinnt) gewinnen und bei der Misère-Regel (das Nehmen des letzten Streichholzes verliert) verlieren.

Fall Cu: Die Anzahl der Streichhölzer ist ungerade:

Der Spieler am Zug wird bei der Standard-Regel gewinnen und bei der Misère-Regel verlieren.

(Übrigens braucht man bei der Standard-Regel die Fallunterscheidung nicht zu machen, sie führt zu demselben Ergebnis wie das Nim-Summen-Kriterium.)

Da beide Charakterisierungen, die graphentheoretische wie die numerische, eindeutige Ergebnisse liefern, müssen diese übereinstimmen. Die Begründungen hierfür wurden von R. Sprague^[1] und P. Grundy^[2] gefunden (siehe auch Theorem von Sprague-Grundy in der englischen Wikipedia). Sie verallgemeinern die Konzepte auf andere, ähnliche Spiele und auf das Zusammensetzen von Graphen mehrerer Nim-Spiele, wie es z. B. schon mehrere Nim-Reihen darstellen, und dementsprechend ihrer mehreren Kerne.

Beispiel

Als Beispiel diene die folgende Spielstellung, S1 genannt, mit vier Reihen zu 22, 5, 13 und 27 Streichhölzer:

|||| |||| |||| |||| ||   (22 Streichhölzer)
||||   (5 Streichhölzer)
|||| |||| |||   (13 Streichhölzer)
|||| |||| |||| |||| |||| ||   (27 Streichhölzer)

Die Dualdarstellungen sind:

(16 8 4 2 1   relevante Zweierpotenzen)
  1-0-1-1-0  (für die 22 Streichhölzer der 1. Reihe)
  0-0-1-0-1  (für die  5 Streichhölzer der 2. Reihe)
  0-1-1-0-1  (für die 13 Streichhölzer der 3. Reihe)
  1-1-0-1-1  (für die 27 Streichhölzer der 4. Reihe)

Zählen der '1'-en pro Spalte ergibt:

  2-2-3-2-3

Die Vierer- und die Einer-Spalte haben jeweils eine ungerade Summe, alle anderen Spaltensummen sind gerade (u für ungerade und g für gerade):

  g-g-u-g-u

(Diese sog. „Nim-Summe“ ist auch als „Exklusiv-Oder-Summe“, XOR-Summe oder Vektoraddition über ${ \color{Blue} \mathbb F_2 = GF(2)}$ bekannt und wurde 1901 von Bouton^[4] gefunden.)

Die Stellung S1 ist also eine C-Stellung.

Wenn in der Spielstellung S1 aus der 1. Reihe 3 Streichhölzer entfernt werden, entsteht die Spielstellung S2 mit 19, 5, 13 und 27 Streichhölzern in 4 Reihen.

Die Binärziffern sind bei S2:

(16 8 4 2 1   relevante Zweierpotenzen)
  1-0-0-1-1  (für 19)
  0-0-1-0-1  (für  5)
  0-1-1-0-1  (für 13)
  1-1-0-1-1  (für 27)

Die Spaltensummen sind:

  2-2-2-2-4

Alle Stellen haben gerade Summe:

  g-g-g-g-g

Somit ist S2 eine Z-Stellung. Da der Spieler, der jetzt am Zug ist, aus genau einer Reihe mindestens 1 Streichholz entnehmen muss, muss er in dieser Reihe mindestens eine '1' zu einer '0' machen, wodurch diese Dualstelle eine ungerade Spaltensumme bekommt. (Eine Kompensation in einer anderen Reihe lässt die Spielregel nicht zu.) Er muss also eine C-Stellung erzeugen.

Es gibt immer mindestens eine Möglichkeit, um aus einer C-Stellung eine Z-Stellung zu machen. Bei S1 gibt es außer der genannten jedoch noch zwei weitere, nämlich das Entnehmen von 5 Streichhölzern aus der 2. oder 3. Reihe. Die Anzahl solcher Möglichkeiten ist immer ungerade, nämlich gleich der Spaltensumme der zur höchsten Zweierpotenz gehörenden Spalte mit ungerader Summe. Die Anzahl der zu entnehmenden Streichhölzer ist für jede dieser in Frage kommenden Reihen eindeutig bestimmt.

Um aus der Stellung S1 zu einem Sieg zu kommen, hat der erste Spieler, genannt A, 3 Streichhölzer aus der 1. Reihe entnommen und die Z-Stellung S2 an seinen Gegenspieler, genannt B, übergeben.

Folgender Spielablauf ist möglich und optimal seitens des anziehenden Spielers A. Hierbei stellt der lange senkrechte Strich │ den im Diagramm ausgeführten Zug dar, wogegen der kürzere | einen alternativen optimalen Zug aufzeigt, d. i. eine andere Reihe zur Entnahme von Streichhölzern, deren eindeutig bestimmte, strategisch optimale Anzahl im Diagramm jedoch nicht angegeben ist (beidesmal 5).

S1:         22 -  5 - 13 - 27    (C-Stellung)
A zieht:     │    |    |
S2:         19 -  5 - 13 - 27    (Z-Stellung)
B zieht:                    │
S3:         19 -  5 – 13 -  0    (C-Stellung)
A zieht:     │
S4:          8 -  5 - 13         (Z-Stellung)
B zieht:               │
S5:          8 -  5 -  4         (C-Stellung)
A zieht:     │
S6:          1 -  5 -  4         (Z-Stellung)
B zieht:               │
S7:          1 -  5 -  0         (C-Stellung)

Nur noch 1 Reihe hat mehr als ein Streichholz, nämlich die 2. mit 5 – der Fall B ist eingetreten.

Die Gewinnstrategie bei der Standard-Regel:

S7:          1 –  5              (C-Stellung)
A zieht:          │
S8:          1 -  1              (Z-Stellung bei der Standard-Regel)
B zieht:          │
S9:          1 -  0              (C-Stellung)
A nimmt und gewinnt!

Die Gewinnstrategie bei der Misère-Regel:

S7:          1 –  5              (C-Stellung)
A zieht:          │
S8:          1 -  0              (Z-Stellung bei der Misère-Regel)
B nimmt, wodurch A gewinnt!

Fazit

Offensichtlich ist es nicht interessant, Nim zu spielen, wenn beide Spieler die optimale Strategie kennen, da dann Sieger und Verlierer von vorneherein feststehen. Tatsächlich steht der Gewinner genau dann von vorneherein fest, wenn einer der beiden Spieler die optimale Strategie spielt und an eine C-Stellung gerät.

Da bei einer vorliegenden C-Stellung die Z-Stellungen unter den Nachfolgestellungen eine verschwindende Minderheit darstellen, hat ein perfekter Spieler, der bei einer Z-Stellung beginnen – also seinem Gegenspieler eine C-Stellung überlassen – muss, umso größere Gewinnchancen, je größer das Ausgangstableau ist und je mehr „Fehler“-Möglichkeiten damit für den Gegenspieler bestehen. Und nach dem ersten Fehlgriff seines Gegenspielers ist er von der Straße des Sieges nicht mehr abzubringen.

Ausblick

Die Theorie des Nim-Spiels wurde ab etwa 1970 zur Kombinatorischen Spieltheorie verallgemeinert.

Literatur

G.H. Hardy, E. M. Wright: An introduction to the theory of numbers. Fifth edition. The Clarendon Press, Oxford University Press, New York, 1979. p.117-120.

Weblinks

• Ein nach dem oben beschriebenen System programmiertes Freewarespiel in Pyramidenform
• Freeware-Nim-Spiel in einer Reihe
• www.schwalfenberg.com/Spiele/Nimm Einfache Nim-Spiel-Variante mit wählbaren Spielfeld
• Eine browserbasierte Nim-Variante gegen den Computer
• Nim-Spiel-Variante in Flash
• Nim-Variante als Flash-Game

Einzelnachweise

1. ↑ ^{a b} Roland P. Sprague: Über mathematische Kampfspiele, Tôhoku Mathematical Journal, 41 (1935), S. 438-444 (Online-Version).
2. ↑ ^{a b} Patrick M. Grundy: Mathematics and games, Eureka. 27 (1940), S. 9-11 (Online-Version).
3. ↑ Claude Berge: Graphs et hypergraphes. Dunod, Paris 1970, Chapitre 14 Noyaux et fonctions de Grundy, S. 290-313.
4. ↑ 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)