Nimm-Spiel

Das Nim-Spiel ist ein Spiel mit vollständiger Information für zwei Spieler. Es ist ein beliebtes Beispiel der Spieltheorie, da es mit Papier und Bleistift vollständig analysiert werden kann.

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

Eine spezielle Variante des Nim-Spiels ist Marienbad, das durch den Film Letztes Jahr in Marienbad von Alain Resnais bekannt wurde.

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 entnimmt, hat nicht gewonnen, sondern verloren. Diese Variante heißt Misère-Spiel.

Varianten des Spiels

Eine Variante des Spiels ist Ziel 100.

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

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 mit einer geradzahlig vielen Anzahlen von 1en 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. Tatsächlich steht der Gewinner genau dann von vorneherein fest, wenn einer der beiden Spieler die optimale Strategie spielt.

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: 22 - 5 - 13 - 15

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.

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
• Nim-Spiel-Variante in Flash