Das Nim-Spiel
Inhalt dieser Webseite
Was ist das Nim-Spiel?
Simulation des Nim-Spiels 
Nim-Spiel mit einer Strategie
Variationen des Spiels 
Nim-Spiel mit mehreren Haufen
Literatur
Nim-Spiel im Internet 
.
Zur Hauptseite   "Mathematische Basteleien"
Was ist das Nim-Spiel?
...... Das Nim-Spiel ist ein Spiel für zwei Personen. 

Gegeben ist ein Haufen von 13 Streichhölzern. Abwechselnd nehmen zwei Personen 1, 2 oder 3 Streichhölzer. Derjenige, der den Haufen leerräumt, hat gewonnen.

Statt der Streichhölzer kann man auch Münzen, Spielkarten, Bierdeckel oder andere gleichartige Gegenstände verwenden.

Neben diesem Nim-Spiel gibt es Versionen mit mehreren Haufen, die unten beschrieben werden. 

Simulation des Nim-Spiels mit 13 Streichhölzer     top
Eine Analyse des Spiels läuft auf eine Zerlegung der Zahl 13 in die Summanden 1, 2 oder 3 hinaus. 
Es ist für einen Computer eine leichte Aufgabe, diese zu ermitteln. 
Es wird angenommen, dass Rot beginnt. Weder Rot noch Schwarz haben eine Strategie. 
Folgende Spielverläufe sind möglich.
0001) 13 = 1+1+1+1+1+1+1+1+1+1+1+1+1 1 Spiel mit 13 Zügen
Rot gewinnt, Schwarz verliert. 


0002) 13 = 1+1+1+1+1+1+1+1+1+1+1+2
...
0013) 13 = 2+1+1+1+1+1+1+1+1+1+1+1..
12 Spiele mit 12 Zügen
Rot verliert, Schwarz gewinnt 

0014) 13 = 2+1+1+1+1+1+1+1+1+1+3
...
0079) 13 = 2+1+1+1+1+1+1+1+1+1+3....
66 Spiele mit 11 Zügen
Rot gewinnt, Schwarz verliert

0080) 13 = 2+1+1+1+1+1+1+1+1+1 
...
0289) 13 = 2+1+1+1+1+1+1+1+1+1.......
210 Spiele mit 10 Zügen
Rot verliert, Schwarz gewinnt

0290) 13 = 2+1+1+1+1+1+1+1+
...
0703) 13 = 2+1+1+1+1+1+1+1+1...........
414 Spiele mit 9 Zügen
Rot gewinnt, Schwarz verliert

0704) 13 = 2+1+1+1+1+1+1+1 
...
1207) 13 = 2+1+1+1+1+1+1+1..............
504 Spiele mit 8 Zügen
Rot verliert, Schwarz gewinnt

1208) 13 = 2+1+1+1+1+1+1
...
1564) 13 = 2+1+1+1+1+1+1................
357 Spiele mit 7 Zügen
Rot gewinnt, Schwarz verliert

1565) 13 = 2+1+1+1+1+1 
...
1690) 13 = 2+1+1+1+1+1...................
126 Spiele mit 6 Zügen
Rot verliert, Schwarz gewinnt

1691) 13 = 1+3+3+3+
...
1705) 13 = 3+3+3+3+1.......................
15 Spiele mit 5 Zügen
Rot gewinnt, Schwarz verliert


Ergebnis: Es sind 1705 Spiele möglich.
Rot gewinnt 1+66+414+357+15= 853 Spiele. Schwarz gewinnt 13+210+504+126 = 852 Spiele. 
Die Wahrscheinlichkeit ein Spiel zu gewinnen ist für Rot oder Schwarz fast gleich.

Nim-Spiel mit einer Strategie  top
Das Nim-Spiel ist nicht fair. Es gibt für den Spieler, der beginnt, eine Strategie, so dass er nie verlieren kann. 
Zu Beginn nimmt der spätere Gewinner Rot einen Streichholz. Dann richtet er sich nach seinem Gegner Schwarz. Nimmt dieser 1 Streichholz, so nimmt er 3, nimmt dieser 2 Streichhölzer, so nimmt er auch 2 und nimmt dieser 3 Streichhölzer, so nimmt er nur 1 Streichholz. Bei jeder Runde werden also zusammen 4 Streichhölzer genommen. Mit 4 Streichhölzern vor der letzten Runde kann man nicht verlieren.
Die Spielverläufe haben immer 7 Züge. Von den 1705 möglichen Spielen von oben bleiben noch 27 übrig. 
01)  13 = 1+(1+3)+(1+3)+(1+3)
02)  13 = 1+(1+3)+(1+3)+(2+2)
...
26)  13 = 1+(3+1)+(3+1)+(2+2)
27)  13 = 1+(3+1)+(3+1)+(3+1)

Der Gegner kann die simple Strategie schnell durchschauen und die Strategie übernehmen. Deshalb sollte man die Regeln verschleiern und sie erst gegen Ende des Spiels anwenden.

Variationen des Spiels   top
Es gib viele Abänderungen der Regeln, die jeweils eine neue Strategie erfordern.
> Die Anzahl 13 der Hölzer zu Beginn wird erhöht oder erniedrigt.
> Es dürfen nicht 1, 2 oder 3 Hölzer genommen werden, sondern andere Kombinationen.
> Nicht derjenige, der das letzte Streichholz nimmt, hat gewonnen sondern verloren.


Das Nim-Spiel mit mehreren Haufen   top
Das klassische Nim-Spiel besteht aus drei Haufen mit 3, 4 und 5 Streichhölzern. Zwei Personen nehmen von einem Haufen abwechselnd beliebig viele Hölzer. Derjenige, der leerräumt, hat gewonnen.
Auch für diese Version gibt es eine Strategie, die von Anfang an zu einem sicheren Sieg führt. 
Der Gewinner nimmt zu Beginn zwei Hölzer links weg und ist dann in einer Gewinnstellung.
Die Gewinnregel heißt: Man muss jeweils so viele Hölzer wegnehmen, dass die "Nim-Summen" gerade bleiben. 

Man erhält die Nimsummen, wenn man die Anzahl eines jeden Haufens in Vielfache von 4, 2 und 1 zerlegt wie bei der Umrechnung einer Zahl vom Zehnersystem in das Zweiersystem. Die farbig gekennzeichneten Vorzahlen werden addiert. Diese Summen sind die drei Nimsummen.
Ergebnis: Die Nimsummen sind 2,1 und 2. 
In der ersten Runde soll der spätere Gewinner A links 2 Hölzer wegnehmen.
Ergebnis: Die Nimsummen sind 2,0 und 2, also durchweg gerade. Spieler A ist in einer Gewinnstellung.
Der weitere Spielverlauf könnte so sein.
Zweite Runde (B nimmt rechts 5):
Ergebnis: Zwei Nimsummen sind ungerade.

Dritte Runde (A nimmt von der Mitte 3):
Ergebnis: Die Nimsummen sind 0,0 und 2, also gerade. 
Vierte Runde (B nimmt von der Mitte 1): 
Fünfte Runde (A ist an der Reihe): Der Spieler A nimmt das letzte Streichholz und hat gewonnen.



Die Theorie des Nim-Spiels geht auf den Mathematik-Professor Charles Bouton von der Harvard-Universität zurück (1901) und gilt für eine beliebige Anzahl von Haufen und für eine beliebige Anzahl von Streichhölzern in einem Haufen. 

Literatur   top
Bild der Wissenschaft, 11/1970
Bild der Wissenschaft, 4/1977
Martin Gardner, Mathematical Puzzles & Diversions, New York 1959 (Englisch)


Nim-Spiel im Internet  top

Deutsch

Gerhard Saurer
1-auf-7-Streichholz-Pyramide, 1-2-3-Streichholz-wegnehmen

Wikipedia
Nim-Spiel



Englisch

Charly Founès 
Marienbad

transience
Pearls Before Swine

A. Bogomolny (cut-the-knot)
The Hot Game of Nim

Wikipedia
Nim


Feedback: Emailadresse auf meiner Hauptseite

Diese Webseite ist auch in Englisch vorhanden.

URL meiner Homepage:
http://www.mathematische-basteleien.de/

©  2000 Jürgen Köller

top