Das NIM-Spiel ist ein altes Spiel. Bereits seit 1901 gibt es eine sichere Gewinnstrategie. Die Lösung basiert auf Binärzahlen und das wiederum führte dazu, dass es mit als eines der erstes Computer-Spiele programmiert wurde.
Quelle: Wikipedia (zur Wikipedia Nim-Spiel-Seite)
Wir benutzen normalerweise Dezimalzahlen. Wir kennen 10 Ziffern: 0, 1, 2, 3, 4, 5, 6, 7, 8 und 9. Für die nächst größere Zahl haben wir keine Ziffer mehr. Wir benutzen statt dessen die 1 mit einer 0 hintendran.
Die größte Zahl mit 2 Ziffern ist die 99. Für die nächst größere Zahl benutzen wir wieder die 1 mit 2 Nullen hintendran.
Binärzahlen kennen nur 2 Ziffern: 0 und 1. Da es keine 2 gibt benutzt man ebenfalls eine 1 mit einer 0 hintendran. Unsere Dezimalzahl 2 wird als zur 10.
Die größte Zahl mit 2 Ziffern ist hier die 11 (unsere 3). Für die nächst größere Zahl benutzt man wie bei uns eine 1 mit 2 Nullen hintendran. Unsere Dezimalzahl 4 wird also zur 100.
Rechts siehst Du die Übersetzungstabelle für Dezimal- und Binärzahlen von 0 bis 16. Für mein NIM-Spiel brauchst Du nur die Zahlen von 0 - 9.
Spielst Du die Variante mit maximal 3 Streichhölzern pro Zug brauchst Du nur die Zahlen von 0 - 3.
|
Dezimal |
Binär |
|---|---|
|
0 |
0 |
|
1 |
1 |
|
2 |
10 |
|
3 |
11 |
|
4 |
100 |
|
5 |
101 |
|
6 |
110 |
|
7 |
111 |
|
8 |
1000 |
|
9 |
1001 |
|
10 |
1010 |
|
11 |
1011 |
|
12 |
1100 |
|
13 |
1101 |
|
14 |
1110 |
|
15 |
1111 |
|
16 |
10000 |
|
Addieren |
Subtrahieren |
Multiplizieren |
Dividieren |
|---|---|---|---|
|
0 + 0 = 0 |
0 - 0 = 0 |
0 x 0 = 0 |
0 : 0 = Fehler |
|
0 + 1 = 1 |
0 - 1 = -1 |
0 x 1 = 0 |
0 : 1 = 0 |
|
1 + 0 = 1 |
1 - 0 = 1 |
1 x 0 = 0 |
1 : 0 = Fehler |
|
1 + 1 = 10 |
1 - 1 = 0 |
1 x 1 = 1 |
1 : 1 = 1 |
Man sieht, das alle Ergebnisse mit unserem Dezimalsystem übereinstimmen. Einzige Ausnahme ist die Addition von 1 + 1 (10 statt 2).
Für das NIM-Spiel benötigen wir nur die Regeln für die Addition.
Wenn Du alle Streichhölzer aus einer Reihe entfernen darfst musst Du folgende Schritte ausführen:
Ist die Summe vor Deinem Zug schon 0 hast Du bereits verloren
Wir nehmen an, dass 3, 4, 5 Hölzer auf dem Spielfeld liegen. Wir sind am Zug.
|
Reihe |
Anzahl |
Binär |
|---|---|---|
|
1 |
3 |
011 |
|
2 |
4 |
100 |
|
3 |
5 |
101 |
|
Summe |
|
0 1 0 |
Schritt 1: Wir wandeln zunächst alle Zahlen in Binärzahlen um.
Schritt 2: Wir addieren nun die einzelnen Spalten der Binärzahlen.
Ich beginne mal an der letzten Spalte 1+0+1 ergibt (ohne Übertrag) 0.
Bei der 2. Spalte von Rechts haben müssen wir 1 + 0 + 0 addieren. Sehr leicht ergibt 1.
In der dritten Spalte addieren wir 0+1+1 = Summe (ohne Übertrag) 0.
Unsere Summe ist ungleich 0. Wir können also noch gewinnen.
Schritt 3: Nachfolgend muss nun getestet werden, aus welcher Reihe wir wieviel Streichhölzer wegnehmen müssen um auf die Summe 0 zu kommen.
|
Reihe |
Anzahl |
Binär |
|---|---|---|
|
1 |
3 |
011 |
|
2 |
4 |
100 |
|
Summe |
|
1 1 1 |
Wir addieren nun für alle Reihen (außer der letzten) die einzelnen Spalten der Binärzahlen.
Ich beginne wieder an der letzten Spalte 1+0 ergibt 1.
Bei der 2. Spalte von Rechts haben müssen wir jetzt 0 + 0 addieren. Sehr leicht ergibt 0.
In der dritten Spalte addieren wir 0+1 = Summe 1.
Unsere Summe ohne die letzte Reihe ist binär 111 = dezimal 7. Wir müssten aus der 5 eine 7 machen. Geht also nicht.
|
Reihe |
Anzahl |
Binär |
|---|---|---|
|
1 |
3 |
011 |
|
3 |
5 |
101 |
|
Summe |
|
1 1 0 |
Wir addieren nun die einzelnen Spalten der Binärzahlen für die 1. und letzte Reihe.
Ich beginne wieder an der letzten Spalte 1+1 ergibt (ohne Übertrag) 0.
Bei der 2. Spalte von Rechts haben müssen wir 1+ 0 addieren. Ergibt 1.
In der dritten Spalte addieren wir 0+1. Leicht zu rechnen ergibt 1.
Unsere binäre Summe ist also 110 entspricht dezimal der 6. Wir müssten aus der 4 eine 6 machen. Geht auch nicht.
|
Reihe |
Anzahl |
Binär |
|---|---|---|
|
2 |
4 |
100 |
|
3 |
5 |
101 |
|
Summe |
|
0 0 1 |
Wir addieren nun die einzelnen Spalten der Binärzahlen für die zweite und dritte Reihe.
Ich beginne wieder an der letzten Spalte 0+1 ergibt 1.
Bei der 2. Spalte von Rechts haben müssen wir 0 + 0. Ergibt in Summe 0.
In der dritten Spalte addieren wir 1+1 = Summe (ohne Übertrag) 0.
Unsere binäre Summe ist jetzt 1 und entspricht unserer dezimalen 1. Jetzt haben wir die Chance aus der 3 eine 1 zu machen. Das geht indem wir 2 Streichhölzer entfernen.
Wenn Du nur eine bestimmte Anzahl Hölzer aus einer Reihe entfernen darfst muss Du folgenden Schritte ausführen:
Die Schritte 2 - 4 sind also identisch mit den Schritten 1 -3 für alle Streichhölzer. Im Spiel wird bei der Vorschau und im Spielverlauf stets die Original-Anzahl und die Modulo-Anzahl dargestellt. Beim folgenden Beispiel 345 steht dann 0345≡0301
Beispiel für max 3 Streichhölzer
|
Anzahl |
Rest ( Modulo 4) |
|---|---|
|
4 |
0 |
|
5 |
1 |
|
6 |
2 |
|
7 |
3 |
|
8 |
0 |
|
9 |
1 |
|
Reihe |
Anzahl |
Modulo 4 |
Binär |
|---|---|---|---|
|
1 |
3 |
3 |
011 |
|
2 |
4 |
0 |
000 |
|
3 |
5 |
1 |
001 |
|
Summe |
|
|
010 |
Schritt 1: Wir ermitteln für alle Zahlen den ganzahligen Rest der Division durch 4.
Das Ergebnis steht in der Spalte Modulo 4.
Schritt 2: Wir wandeln alle Reste in Binärzahlen um.
Das Ergebnis steht in der Spalte Binär
Schritt 3: Wir addieren nun die einzelnen Spalten der Binärzahlen.
Ich beginne mal an der letzten Spalte 1+0+1 ergibt (ohne Übertrag) 0
Bei der 2. Spalte von Rechts haben müssen wir 1 + 0 + 0 addieren.
Sehr leicht ergibt 1. Die dritte Spalte hat nur Nullen = Summe 0.
Unsere Summe ist also binär 10 entspricht dezimal einer 2.
Um in der Summe 0 zu bekommen muss aus dieser 2 eine 0 werden.
Schritt 4: Nachfolgend muss nun getestet werden, in welcher Reihe wir erfolgreich sind.
|
Reihe |
Anzahl |
Modulo 4 |
Binär |
|---|---|---|---|
|
1 |
3 |
3 |
011 |
|
2 |
4 |
0 |
000 |
|
Summe |
|
|
0 1 1 |
Wir addieren nun spaltenweise die Binärzahlen der ersten und zweiten Reihe.
Ich beginne wieder an der letzten Spalte 1+0 ergibt 1.
Bei der 2. Spalte von Rechts addieren wir 1+0 in der Summe wieder 1.
Unsere Zwischensumme ist also binär 11 entspricht dezimal einer 3: Wir müssen also aus der letzen Reihe soviel Streichhölzer wegnehmen dass 3 übrig bleiben. Das läßt sich machen.
|
Reihe |
Anzahl |
Modulo 4 |
Binär |
|---|---|---|---|
|
1 |
3 |
3 |
011 |
|
3 |
5 |
1 |
001 |
|
Summe |
|
|
0 1 0 |
Wir addieren nun wieder die einzelnen Spalten der Binärzahlen für die erste und letzte Reihe.
Ich beginne wieder an der letzten Spalte 1+1 ergibt (ohne Übertrag) 0
Bei der 2. Spalte von Rechts addieren wir 1 + 0 ergibt eine 1.
Unsere Summe ist also binär 10 = dezimal 2. Können wir aus den 4 Streichhölzern in der zweiten Reihe eine 2 machen? Ja, auch dieser Zug führt zu einer Summe 0.
|
Reihe |
Anzahl |
Modulo 4 |
Binär |
|---|---|---|---|
|
2 |
4 |
0 |
000 |
|
3 |
5 |
1 |
001 |
|
Summe |
|
|
0 0 1 |
Auch hier addieren wir nun die einzelnen Spalten der Binärzahlen der 2. und dritten Reihe.
Ich beginne wieder an der letzten Spalte 0+1 ergibt 1.
Bei der 2. Spalte von Rechts addieren wir 0+0 ergibt 0.
Unsere Zwischensumme ist also binär 1 entspricht dezimal 1: Können wir aus der 3 in der ersten Reihe eine 1 machen. Wieder ist die Antwort Ja. Wir dürfen 2 Streichhölzer aus der ersten Reihe wegnehmen.
Das bedeutet in diesem Beispiel mit 3,4,5 sowie max. 3 Streichhölzern dass wir aus einer beliebigen Reihe 2 Streichhölzer wegnehmen könnten.
Für Erläuterung dieser Variante brauche ich noch ein bischen Zeit. Ich habe nur 3 Monate gebraucht um die sogenannte Misère-Variante ins Spiel einzubauen.
Im Prinzip muss man genauso spielen wie normal nur am Ende muss man die Strategie ändern. Es muss dann am Ende immer eine 1 als binäre Summe ohne Übertrag herauskommen. Wenn Du Dir den detailierten Vorschlag anzeigen lässt, wirst Du über die Abweichungen zur normalen Regel informiert.
Spiele am Anfang immer nur die Variante: Wer das letzte Streichholz nimmt gewinnt.