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

Inhaltsverzeichnis 1 Spielregel 1.1 Alternative Regeln 1.1.1 Spezielle Anfangssituationen 1.1.2 Einschränkungen bei der Zugfolge 1.1.3 Andere Gewinnregel 1.1.4 Varianten des Spiels 2 Strategie 2.1 Merkmale der G- und U-Situationen 2.1.1 Beispiel 2.2 Eigenschaften der G- und U-Situationen 2.2.1 Beispiel 2.3 Optimale Strategie 2.3.1 Beispiel 3 Ausblick

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

Alternative Regeln

Es existiert eine Reihe von Spielvarianten, die nicht weiter besprochen oder analysiert werden. Diese Regeln werden teilweise eingeführt, um das Spiel interessanter zu gestalten, 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.

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. Diese Variante

heißt Misère-Spiel.

Varianten des Spiels

Eine Variante des Spiels ist Ziel 100.

Strategie

Man kann bei jeder gegebenen Spielsituation erkennen, ob der Spieler am Zuge den Sieg erzwingen kann oder nicht. Eine Situation, in der er den Sieg erzwingen kann, heißt eine "G-Situation" (Gewinn). Eine Situation, in der er den Sieg nicht erzwingen kann, heißt eine "U-Situation" (unsicher). Immer ist einer in einer G-Situation und der andere in einer U-Situation.

Merkmale der G- und U-Situationen

Um zu erkennen, ob eine gegebene Situation eine G- oder eine U-Situation ist, betrachtet man die Anzahlen der Streichhölzer in den Reihen in Dualdarstellung . Eine Spielsituation ist eine G-Situation, wenn jede Dualstelle bei geradzahlig vielen Anzahlen mit 1 belegt ist. In den anderen Fällen, wenn also mindestens eine Dualstelle ungeradzahlig oft mit 1 belegt 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 Dualdarstellungen 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 die Situation 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 nimmt, d.h. wer seinem Gegenspieler eine (spezielle) G-Situation überlässt.

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 kann das Spiel deshalb wie unter 1. weiterspielen.

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

Merkregel: 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.

Ausblick

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