Nim-Spiel

Das Nim-Spiel ist ein Strategiespiel für zwei Spieler. Es ist in der Spieltheorie von Interesse, da es vollständig analysiert werden kann.

Spielregel

Beim Nim-Spiel sind mehrere Reihen mit Streichhölzer 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 wegNimt, 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.

Dazu müssen Spielsituationen nach G- und U-Situationen (s.u.) unterschieden werden.

Alternative Regeln

Es existieren eine Reihe von Spielvarianten, die nicht weiter besprochen oder analysiert werden. Diese Regeln werden teilweise eingeführt, um das Spiel interessanter zu gestalten, indem Anwenden der unten genannten optimalen Strategie ausgeschlossen wird.

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.

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

Andere Gewinnregel

• Der Spieler, der die letzten Streichhölzer entNimt, hat nicht gewonnen, sondern verloren.

Varianten des Spiels

Eine Variante des Spiels ist Ziel 100.

Strategie

Ein Spieler kann bei einer gegebenen Spielsituation erkennen, ob aus der Spielsituation ein Sieg erzwungen werden kann. Dazu ist es notwendig, die Situation als eine G-Situation oder als eine U-Situation zu identifizieren. Jede Situation ist entweder eine G- oder eine U-Situation.

Definition der G- und U-Situationen

Um zu erkennen, ob eine gegebene Situation eine G- oder eine U-Situation ist, wird die Anzahl der Streichhölzer jeder Reihe zuerst als Binärzahl aufgeschrieben.

Im zweiten Schritt wird für jede Binärstelle der Binärzahlen gezählt, wie oft die Ziffer '1' auftritt (Anzahl der '1'-en).

Im dritten Schritt wird festgestellt, ob die Anzahl der '1'-en gerade (g) oder ungerade (u) ist; die Null zählt als gerade Zahl.

Wenn alle Anzahlen der 1-en gerade sind, liegt eine G-Situation vor. Wenn mindestens eine Anzahl der 1-en ungerade ist, liegt eine U-Situation vor.

Beispiel

Als Beispiel diene die Spielsituation S1, in der vier Reihen mit 22, 5, 13 und 15 von Streichhölzern vorhanden sind.

Die Binärzahlen sind

• 1-0-1-1-0 (für 22),
• 0-0-1-0-1 (für 5),
• 0-1-1-0-1 (für 13),
• 0-1-1-1-1 (für 15).

Zählen der '1'-en ergibt

• 1-2-4-2-3

Die erste und letzte Stelle sind ungerade, alle anderen sind gerade:

• u-g-g-g-u.

Somit ist Beispiel S1 eine U-Situation.

Eigenschaften der G- und U-Situationen

Wenn ein Spieler in einer G-Situation am Zug ist, entsteht immer eine U-Situation; wenn dagegen ein Spieler in einer U-Situation am Zug ist, kann er immer einen Zug finden, der zu einer G-Situation führt.

Weiterhin ist Gewinner des Spiels, wer die letzten Streichhölzer Nimt, d.h. wer seinem Gegenspieler eine (spezielle) G-Situation überläßt.

Beispiel

Wenn in der Spielsituation S1 aus der 1. Reihe (mit 22 Streichhölzern) 15 entfernt werden, entsteht Spielsituation S2 mit 7, 5, 13 und 15 Streichhölzern in 4 Reihen.

Die Binärzahlen sind

• 0-0-1-1-1 (für 7),
• 0-0-1-0-1 (für 5),
• 0-1-1-0-1 (für 13),
• 0-1-1-1-1 (für 15).

Zählen der '1'-en ergibt

• 0-2-4-2-4

Alle Stellen sind gerade:

• g-g-g-g-g.

Somit ist S2 eine G-Situation, die aus der U-Situation S1 entstand.

Optimale Strategie

Der Spieler, der eine U-Situation vorfindet, gewinnt das Spiel auf jeden Fall, wenn er sich an folgende Strategie hält:

• (1) Führe einen Spielzug aus, der aus der U-Situation eine G-Situation erzeugt.
  Falls danach keine Streichhölzer mehr vorhanden sind (auch das ist eine G-Situation) ist das Spiel gewonnen, ansonsten geht es mit (2) weiter.
• (2) Der Gegenspieler hat keine andere Wahl, als durch seinen Spielzug die vorgefundene G-Situation in eine U-Situation umzuwandeln.
  Da eine U-Situation nicht die Gewinnsituation ist, kann der Gegenspieler hier nicht gewinnen.
  Der erste Spieler das Spiel kann deshalb wie unter (1) weiterspielen.

Offensichtlich ist das Nim-Spiel, sobald beide Spieler die optimale Strategie kennen, nicht interessant zu spielen, da Sieger und Verlierer von vorneherein feststehen.

Merkschema: Um zu gewinnen, ist es günstig, dem Gegenspieler immer eine G-Situation zu überlassen.

Beispiel

Um aus Situation S1 zu einem Sieg zu kommen, hat der erste Spieler 15 Streichhölzer aus Reihe 1 entnommen, und seinem Gegenspieler die G-Situation S2 gegeben. Es ergibt sich der folgende mögliche Spielablauf:

U-Situation: 7 - 5 - 13 - 22

G-Situation: 7 - 5 - 13 - 15

U-Situation: 7 - 5 - 13 - 4

G-Situation: 7 - 5 - 6 - 4

U-Situation: 0 - 5 - 6 - 4

G-Situation: 0 - 5 - 1 - 4

U-Situation: 0 - 0 - 1 - 4

G-Situation: 0 - 0 - 1 - 1

U-Situation: 0 - 0 - 0 - 1

G-Situation: 0 - 0 - 0 - 0

U- und G-Situationen treten immer abwechselnd auf. Der Spieler, der mit der U-Situation S1 begann, erreichte mit jedem Zug eine G-Situation. Der Gegenspieler konnte keine der G-Situationen in eine andere G-Situation umwandeln. Der Spieler, der das Spiel begann, siegte.