Nim-Spiele
Nim-Spiele Brettspiel
| Format | verschiedene |
|---|---|
| Spieler(e) | 2 |
| Alter | ab 5 Jahren |
| Angekündigte Dauer | ca. 5 Minuten |
| körperliche Fähigkeit  Nein
|
Reflexion Entscheidung Ja
|
Chance Generator Nein
|
die Info. kompl. und perfekt Ja
|
Die Nim - Spiele sind Spiele der reinen Strategie , mit zwei Spielern. Es gibt mehrere Variationen. Sie werden mit Samen, Murmeln, Spielsteinen, Streichhölzern oder anderen leicht manipulierbaren Gegenständen gespielt.
Beispiele
Viele Spiele von Nim werden mit einem oder mehreren Stapeln von Gegenständen gespielt (zum Beispiel Streichhölzer), wobei jeder Spieler einen oder mehrere Stapel gemäß den angenommenen Regeln modifiziert. Lassen Sie uns die Version im Detail erklären, die in der Ausgabe von Fort Boyard verwendet wurde , ein solches Spiel stellt das Duell der Stöcke gegen einen Meister der Dunkelheit dar (der Stapel enthält 20 Streichhölzer). Dieses Spiel besteht darin, in jeder Runde 1, 2 oder 3 Stöcke zu entfernen. Sieger ist derjenige, der zuletzt spielen kann. Hier ist ein Beispiel für ein Spiel: 20 -> 19 -> 16 -> 13 -> 12 -> 10 -> 8 -> 5 -> 4 -> 3 -> 0
Bei diesem Spiel besteht die Strategie darin, jedes Mal - wenn Sie können - eine Anzahl von Objekten zu verlassen, die ein Vielfaches von 4 ist: Dies sind die Gewinnpositionen. Wir sehen dann, dass der Gegner nicht in der Lage sein wird, dasselbe zu tun.
Andere Variationen existieren:
- Wir können uns eine Variante der Version von Fort Boyard vorstellen, bei der derjenige, der das letzte Objekt nimmt, verliert, die Strategie darin besteht, eine Anzahl von Objekten kongruent zu 1 modulo 4 zu belassen (das heißt: 1, 5, 9, 13 .. .). Tatsächlich kehren wir zum vorherigen Fall zurück, indem wir bedenken, dass das Ziel des Spiels darin besteht, das vorletzte Objekt zu nehmen.
- Das klassische Spiel von Nim oder Spiel Marienbad wurde von einem Film bekannt geworden Alain Resnais in 1961 , Letztes Jahr in Marienbad . Es besteht aus mehreren Stapeln. Jeder Spieler wählt den Stapel seiner Wahl und nimmt sich von diesem Stapel die Anzahl der Streichhölzer seiner Wahl.
- Das Spiel Grundy wird gespielt, indem man einen der Haufen in zwei unterschiedlich große Haufen aufteilt, bis nur noch ein oder zwei Gegenstände gestapelt sind.
- Das Spiel Wythoff wird in zwei Stapeln gespielt. Jeder Spieler reduziert die beiden Stapel gleichzeitig um die gleiche Anzahl von Gegenständen oder aber einen einzelnen Stapel um die gewünschte Anzahl von Gegenständen.
Außerdem besteht das triviale Nim-Spiel (oder das Einstapel-Nim-Spiel) aus einem einzigen Stapel Streichhölzer. Wenn er an der Reihe ist, nimmt sich jeder Spieler so viele Streichhölzer, wie er möchte. Die Gewinnstrategie für den ersten Spieler besteht darin, alle Spiele zu gewinnen. Das Spiel ist trivial und hat theoretisches Interesse.
Geschichte
Die Ursprünge sind wahrscheinlich sehr alt. Die ersten Spuren werden in China unter dem Namen fan-tan gemeldet , in Afrika ist es unter dem Namen tiouk-tiouk bekannt . Der heutige Name leitet sich vom deutschen Wort Nimm ab, was "nimm!" „Es könnte aber auch vom englischen Wort WIN („wins!“) kommen, denn durch die grafische Umkehrung wird das Wort WIN zu NIM . Der aktuelle Name wurde das Spiel von dem englischen Mathematiker gegeben Charles Leonard Bouton in 1901 , als er einen gefunden Algorithmus, der die Auszahlung erlaubt.
Auf der New Yorker Weltausstellung 1940 stellte die Westinghouse Electric Corporation eine Maschine namens Nimatron aus , die Nims Spiel spielte. Vom 11. Mai 1940 bis 27. Oktober 1940 konnten nur wenige Teilnehmer die Maschine schlagen; die Gewinner bekamen eine Münze mit der Aufschrift "Nim Champ". In 1951 , die Nimrod das Konzept der Nimatron, Aufnahme, ist ein Computer , den Sie Nims Spiel zu spielen. Sein ursprünglicher Zweck besteht jedoch darin, Ferrantis Computerdesign- und Programmierfähigkeiten zu preisen , anstatt zu unterhalten .
Ziel des Spiels
Jedes Spiel wird nacheinander von zwei Spielern gespielt. Die Chance greift nicht ein. Dies beinhaltet normalerweise das Bewegen oder Aufnehmen von Objekten nach Regeln, die angeben, wie man sich von einer Position des Spiels zu einer anderen bewegt, um die zyklische Wiederholung derselben Positionen zu verhindern. Die Anzahl der Positionen ist vorbei und das Spiel endet zwangsläufig, wobei der Spieler nicht mehr als Verlierer (oder nach bestimmten Varianten als Gewinner) spielen kann.
Gewinnstrategie
Nims Spiele sind Nullsummen- Duellspiele (zwei Spieler, ein Gewinner und ein Verlierer, kein Unentschieden möglich), was dem Bewegen von einem Scheitelpunkt zum anderen eines gerichteten Graphen ohne Kreis entspricht , wobei die Scheitelpunkte des Graphen die verschiedenen möglichen Positionen von representing darstellen das Spiel und die Kanten die Übergänge von einer Position zur anderen. Es wird gezeigt, dass es eine optimale Strategie gibt, indem die verschiedenen Positionen des Spiels in zwei Teilmengen unterteilt werden, die Gewinnpositionen und die Verliererpositionen.
Diese werden rekursiv wie folgt definiert , falls der Spieler, der nicht mehr spielen kann, verloren hat:
- Die Endpositionen (von denen aus nicht mehr gespielt werden kann) gewinnen, da der Spieler, der eine erreicht, seinen Gegner am Spielen hindert und das Spiel gewinnt.
- Eine Position verliert, wenn es eine Bewegung gibt, die zu einer Gewinnposition führt. Erreicht ein Spieler eine Verliererposition, kann sein Gegner somit eine Gewinnposition erreichen.
- Eine nicht-finale Stellung ist eine gewinnende Stellung, wenn man unabhängig vom Zug, den man spielt, zu einer Verliererstellung gelangt. Wenn ein Spieler eine Gewinnposition erreicht, muss sein Gegner auf eine Verliererposition gehen.
Durch das Erhöhen von Endpositionen können wir daher nach und nach den Status jeder Position ermitteln. Die optimale Strategie besteht dann darin, von einer Gewinnposition zur anderen zu wechseln.
Die Bestimmung der Gewinnpositionen bei einem komplexen Graphen verwendet den Begriff der Grundy-Zahl oder Zahl . Dies ist wie folgt definiert:
- Die Grundy-Zahl der Endposition ist gleich 0.
- Die Grundy-Zahl einer gegebenen Position ist die kleinste positive oder Null-Ganzzahl, die nicht in der Liste der Grundy-Zahlen der Positionen unmittelbar nach der gegebenen Position auftaucht.
Die Gewinnpositionen sind diejenigen mit einer Null-Grundy-Zahl. Ausgehend von einer solchen Stellung gelangt man in der Tat, egal welchen Zug man spielt, zu einer Stellung, deren Grundy-Zahl nicht Null ist (Verlierstellung). Umgekehrt gibt es ausgehend von einer Verliererstellung mindestens einen Zug, der gespielt werden kann und der zu einer Stellung führt, bei der die Zahl der Grundy Null ist (Gewinnstellung).
Nim setzt Summe
Wir nennen die Summe der Nim-Spiele das Spiel, bei dem mehrere Nim-Spiele gleichzeitig gespielt werden. Jeder Spieler wählt der Reihe nach, welches Nim-Spiel er spielen möchte und spielt einen Zug aus diesem Spiel.Das Summenspiel endet, wenn ein Spieler keines der einzelnen Nim-Spiele spielen kann. Somit ist das klassische Spiel von Nim oder Spiel Marienbad in n Haufen die Summe von n Spielen Nim trivial.
Das Sprague-Grundy-Theorem erklärt, wie man die Gewinnpositionen einer Summe von Nim-Mengen bestimmt, indem man die Gewinnpositionen jedes einzelnen Nim-Spiels kennt. Die Grundy-Zahl einer beliebigen Position des Summenspiels wird tatsächlich erhalten, indem die Grundy-Zahlen der Positionen jedes einzelnen Spiels in Binärzahlen zerlegt werden und dann die Exklusiv-ODER-Funktion auf die Ziffern des gleichen Rangs all dieser Zahlen angewendet wird. Wir erhalten eine Binärzahl, deren Wert die Grundy-Zahl der Spielpositionssumme ist.
Dieses Phänomen wird im folgenden Absatz veranschaulicht.
Klassisches Nim-Spiel
Die klassische Version von Nims Spiel wird mit mehreren Stapeln gespielt, die jeweils aus mehreren Spielsteinen oder Bauern oder Streichhölzern bestehen. Jeder Spieler kann in seinem Zug so viele Bauern entfernen, wie er möchte, jedoch auf einem Stapel. Gewonnen hat derjenige, der den letzten Bauern entfernt (bei der sogenannten "Misery"-Version ist der Spieler, der den letzten Bauern nimmt, der Verlierer. Daraus lässt sich leicht ableiten).
Da diese Menge die Summe trivialer Nim-Sätze mit einem einzigen Stapel ist und die Grundy-Zahl jedes einzelnen Stapels die Anzahl der Bauern in diesem Stapel ist, erhalten wir die Grundy-Zahl der Stellung, indem wir die Anzahl der Bauern in jedem Stapel binär ausdrücken und indem die Summe exklusiv ODER oder XOR (auch als bezeichnet) dieser Zahlen gemacht wird. Eine Position mit einem Wert von 0 gewinnt immer für den Erfolgreichen, eine Position mit einem Wert ungleich 0 verliert immer.
Nehmen wir das Beispiel eines Spiels, das mit drei Stapeln A, B und C beginnt, Stapel A mit 3 Bauern, Stapel B mit 4 Bauern und Stapel C mit 5 Bauern. Wir haben dann:
0112 310 Pile A 1002 410 Pile B 1012 510 Pile C --- 0102 210 Nim-somme X des piles A, B et C: 3 ⊕ 4 ⊕ 5 = 2
Die Gewinnstrategie besteht darin, seinem Gegner eine Position zu überlassen, bei der die Nim-Summe X gleich 0 ist. Dies ist immer möglich, wenn man von einer Position aus startet, bei der die Nim-Summe von 0 verschieden ist, unmöglich, wenn wir von . ausgehen eine Stellung, deren Nim-Summe gleich 0 ist. Hier genügt es, zum Beispiel zwei Bauern vom Stapel A (der jetzt nur noch einen Bauern enthält) zu entfernen, um zu erhalten:
0012 110 Pile A 1002 410 Pile B 1012 510 Pile C --- 0002 010 Nim-somme X des piles A, B et C: 1 ⊕ 4 ⊕ 5 = 0
Um systematisch den zu spielenden Zug zu finden, genügt es, die Summe XOR jedes Stapels mit der Zahl X zu konstruieren. Beginnen wir zum Beispiel wieder mit unseren Stapeln A = 3 = 011 2 , B = 4 = 100 2 und C = 5 = 101 2 original und addiere das gefundene X (X = 2 = 010 2 ):
A ⊕ X = 3 ⊕ 2 = 1 [Zeichen (011) ⊕ (010) = 001] B X = 4 ⊕ 2 = 6 C X = 5 ⊕ 2 = 7Der einzige Stapel, dessen Menge abnimmt, ist Stapel A. Wir müssen also A auf diese Zahl reduzieren, also auf 1 einzelnen Bauern, also zwei Bauern von A entfernen, was genau das ist, was wir getan haben.
Eine der klassischsten Varianten besteht darin, die Anzahl der Bauern, die von jedem Stapel genommen werden können, auf maximal k Bauern zu begrenzen. Es gilt das vorherige Verfahren, vorausgesetzt, dass die Grundy-Zahl jedes Heaps als Anzahl der Modulo-Objekte (k + 1) genommen wird.
Programm
In 1977 , enthielt das Handbuch für den programmierbaren Rechner HP-25 ein Spiel namens Nimb . Das Spiel begann mit 15 Matches und jeder Spieler konnte nacheinander 1, 2 oder 3 wegnehmen. Wer den letzten nahm, hatte verloren. Das Programm, 49 Schritte , spielte an zweiter Stelle und wandte eine Gewinnstrategie an, die keine Fehler bei seinem Gegner zuließ.
Hinweise und Referenzen
- Lisa Rougetet, Die mehrfachen Vorfahren von Nims Spiel , Pour la Science, Oktober 2012, Nr. 420, S.80-85
- J.-P. Delahaye, Magische Strategien im Land von Nim , Pour la Science, März 2009, Nr. 307, S. 88-93
- Rudolf Flesch , The Art of Clear Thinking , New York, Harper and Brothers Publishers,1951, s. 3
- " ExpoMuseum / New York World's Fair, 1939-'40 " , unter www.expomuseum.com (Zugriff am 20. April 2018 )
- " 1940: Nimatron " , auf platinumpiotr.blogspot.com (abgerufen am 20. April 2018 )
- (in) " Nimb für die HP-25 "