Nim-Spiel

Aus Wikiludia
Wechseln zu: Navigation, Suche

1. Motivation

Das Nim-Spiel ist ein Spiel mit vollständiger Information und in der Spieltheorie insofern von Interesse, da es vollständig analysiert werden kann.

2.Ablauf

Das Nim-Spiel ist ein Spiel für 2 Personen, Spieler A und Spieler B. Gegeben ist ein Haufen von 13 Streichhölzern, von dem beide Spieler abwechselnd entweder 1, 2 oder 3 Streichhölzer ziehen müssen. Wer das letzte Streichholz erhält hat gewonnen.

3.Simulation des Spiels

Nehmen wir an, dass Spieler A beginnt und das beide Spieler erstmal keine besondere Strategie verfolgen. Es wären folgende Spielverläufe möglich ( da es äußerst aufwendig und konfus wäre, einen Spielbaum dieser Dimension hier zu erstellen, begnügen wir uns mit einer verbalen Erklärung):

Folgende Spiele sind möglich:

0001) 13 = 1+1+1+1+1+1+1+1+1+1+1+1+1 13 Züge Spieler A gewinnt, Spieler B verliert (insgesamt ein Spiel)


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 Züge Spieler A verliert, Spieler B gewinnt (insgesamt 12 Spiele)


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 11 Züge Spieler A gewinnt, Spieler B verliert (insgesamt 66 Spiele)


0080) 13 = 2+1+1+1+1+1+1+1+1+1´

...

0289) 13 = 2+1+1+1+1+1+1+1+1+1 10 Züge Spieler A verliert, Spieler B gewinnt (insgesamt 210 Spiele)


0290) 13 = 2+1+1+1+1+1+1+1+1

...

0703) 13 = 2+1+1+1+1+1+1+1+1 9 Züge Spieler A gewinnt, Spieler B verliert (insgesamt 414 Spiele)


0704) 13 = 2+1+1+1+1+1+1+1

...

1207) 13 = 2+1+1+1+1+1+1+1 8 Züge Spieler A verliert, Spieler B gewinnt (insgesamt 504 Spiele)


1208) 13 = 2+1+1+1+1+1+1

...

1564) 13 = 2+1+1+1+1+1+1 7 Züge Spieler A gewinnt, Spieler B verliert (insgesamt 357 Spiele)


1565) 13 = 2+1+1+1+1+1

...

1690) 13 = 2+1+1+1+1+1 6 Züge Spieler A verliert, Spieler B gewinnt (insgesamt 126 Spiele)


1691) 13 = 1+3+3+3+3

...

1705) 13 = 3+3+3+3+1 5 Zügen Spieler A gewinnt, Spieler B verliert (insgesamt 15 Spiele)


Es sind also gesamt 1705 Spiele möglich, davon gewinnt Spieler A bei 853 Spielen und Spieler B bei 852 Spielen. Es hat also im ersten Moment den Anschein, als ob dieses Spiel 'fair' wäre, da beide in diesem Sinne nahezu die gleiche Wahrscheinlichkeit haben, ein Spiel zu gewinnen.

4. Das Nim-Spiel mit einer Strategie

Das Spiel ist nicht fair, da Spieler A mit einer gewissen Strategie immer gewinnt, d.h. Spieler B keine Möglichkeit hat, den Ausgang des Spiels zu beeinflussen. Zu Beginn 'muss' Spieler A 1 Streichholz nehmen. Danach richtet er sich nach Spieler B. 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 Spieler A nicht verlieren. Dieses Spiel hat insgesamt 7 Züge und wie oben zu entnehmen ist, gewinnt immer Spieler A bei dieser Anzahl von Zügen. Von den ursprünglich 1705 möglichen Spielen bleiben somit 27 Spiele ü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)

5. Variationen des Nim-Spiels

1) Man ändert die Anzahl der Streichhölzer bzw. die Anzahl der Streichhölzer, die pro Runde gezogen werden dürfen. Bei beispielsweise 5 Streichhölzern und der Auswahl, entweder 1 oder 2 Streichhölzer zu ziehen muss Spieler A anfangs 2 Steichhölzer ziehen, um auf alle Fälle zu gewinnen.

2) Es gewinnt der Spieler, der nicht das letzte Streichholz bekommt. In diesem Fall gibt es eine sichere Strategie für Spieler B, indem er von Anfang so auf die Wahl von Spieler A zu reagieren, dass pro Runde 4 Streichhölzer gezogen werden.

Hierzu ein kleines Beispielprogramm. Es handelt sich um ein Java JAR-Archiv. Der Quelltext ist enthalten. Starten kann man es von der Kommandozeile mit dem Befehl "java -jar nim.jar".
Konkret wurden folgende Abwandlungen gemacht:
- Die Zahl der Streichhölzer am Anfang wird zufällig gewählt und beträgt zwischen 10 und 100.
- Man muß mindestens eines, darf aber höchstens die Hälfte der Streichhölzer ziehen.
- Wer das letzte Streichholz zieht, verliert.
Zu Beginn des Spiels wird ebenfalls zufällig entschieden:
- wer beginnt
- ob der Computergegner clever spielt oder nur zufällig Züge macht
Das Programm kann durch minimale Änderungen im Quelltext jedoch problemlos an die eigenen Wünsche angepaßt werden (zum erneuten kompilieren braucht man natürlich das Java Development Kit):
-die Variablen MIN und MAX in Haufen.java legen fest, zwischen welchen Werten die Anfangszahl der Streichhölzer liegt.
-CLEVER_WK in Spieler.java legt fest, mit welcher Wahrscheinlichkeit der Computergegner seine Gewinnstrategie anwenden soll. Standard ist 0.5; 0 entspricht immer dumm, 1 immer klug.
-KI_FAENGT_AN in Spiel.java legt fest, mit welcher Wahrscheinlichkeit der Computer beginnen darf.

5.1 Allgemeiner Fall

Die Anzahl der Streichhölzer auf den Haufen sei nun n, die Anzahl der Streichhölzer die ein Spieler nehmen kann sei m. Spielerzahl weiterhin 2, Spieler A fängt an.
Fall A) Der Spieler, der das letzte Streichholz nimmt, gewinnt.
Fall B) Der Spieler, der das letzte Streichholz nehmen muss, verliert.
Betrachten wir nun Fall A : Ziel ist, den Gegner zu einen Zug zu bewegen, in dem 0 mod (m + 1) Streichhölzer übrig sind. Denn falls dies der Fall ist, kann man pro Spielzug immer m+1 Streichhölzer vom Stapel nehmen, bis der Gegner von einem Stapel mit m+1 Hölzern nehmen muss. Dieser hat dann offensichtlich verlohren. Spieler A gewinnt immer, außer der Haufen hat genau 0 mod m+1 Streichhölzer, weil dann kann Spieler B die oben erwähnte Strategie durchziehen. Fall B ist an sich analog, nur ist das Ziel dem Gegner einen Haufen mit 1 mod (m+1) Hölzern zu überlassen.

6. Nim-Spiel mit mehreren Haufen

Eine Variante ist das Nim-Spiel mit mehreren Haufen. Seien drei Haufen mit 3, 4, und 5 Streichhölzern gegeben. 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 jeweiligen Vorzahlen werden addiert:
Der linke Haufen sei im Folgenden die ober Zeile, der mittlere sei die mittlere Zeile und der rechte die untere Zeile:

3 = 0*4 + 1*3 + 0*1
4 = 1*4 + 0*3 + 0*1
5 = 1*4 + 0*3 + 1*1

Es ergeben sich also folgende Nim-Summen: 2 (0+1+1), 1 (1+0+0), 2 (1+0+1)
In der ersten Runde nimmt nun der spätere Gewinner Spieler A links zwei Hölzer weg. Es folgt:

1 = 0*4 + 0*3 + 1*1
4 = 1*4 + 0*3 + 0*1
5 = 1*4 + 0*3 + 1*1

Somit sind die Nim-Summen: 2 (0+1+1), 0 (0+0+0), 2 (1+0+1). Sie sind also gerade und somit Spieler A in einer Gweinnstellung.
Nehme jetzt bspw. Spieler B rechts alle 5 Streichhölzer weg. Es folgt:

1 = 0*4 + 0*3 + 1*1
4 = 1*4 + 0*3 + 0*1
0 = 0+4 + 0*3 + 0*1

Somit sind die Nim-Summen: 1 (0+1+0), 0 (0+0+0), 1 (1+0+0) und somit ungerade.
Jetzt muss Spieler A wieder darauf achten, die Nim-Summen gerade zu bekommen. Er nimmt also aus der Mitte 3 Streichhölzer weg.

1 = 0*4 + 0*3 + 1*1
1 = 0*4 + 0*3 + 1*1
0 = 0+4 + 0*3 + 0*1

Es ergeben sich die Nim-Summen 0 (0+0+0), 0 (0+0+0), 2 (0+1+1), sie sind also gerade.
In der nächsten Runde muss Spieler B dann das Streichholz links oder das in der Mitte nehmen. Das Resultat ist das Gleiche: Es bleibt auf alle Fälle eins übrig. Somit kann Spieler A im nächsten Zug dieses nehmen und hat somit gewonnen.
Analog funktioniert diese 'Strategie' auch, wenn Spieler B in seinem ersten Zug eine andere Wahl trifft.

7. Historisches

Vermutlich geht das Nim-Spiel ungefähr auf das Jahr 1900 zurück. Hinter der Lösung verbirgt sich eine besondere Formel, die 1902 von Charles Bouton gefunden wurde.

'Nim, a game with a complete mathematical theory': Bouton, Charles L.; Annals of Mathematics, Series II (3), 35–39.

Das Nim-Spiel ist im Übrigen das erste Spiel, das jemals von einer Maschine gespielt wurde, da es schaltungstechnisch sehr einfach realisiert werden kann.

1940 prasentierte die Firma Westinghouse auf der New Yorker Weltausstellung ihr Gerät 'Nimatron', welches durch seine zahlreichen Relais mehr als eine Tonne wog. Es spielte Nim mit bis zu vier Haufen mit jeweils höchstens sieben Steinen.

1951 beeindruckte ein anderes Gerät namens 'Nimrod' die Öffentlichkeit dadurch, dass es den damaligen deutschen Wirtschaftsminister Ludwig Erhard schlug.

(Quellen: Wikipedia.de, Mathematische-Basteleien.de)

Meine Werkzeuge