Nim ist ein mathematisches strategisches Spiel, in dem sich zwei Spieler abwechseln, Gegenstände von verschiedenen Haufen entfernend. Auf jeder Umdrehung muss ein Spieler mindestens einen Gegenstand entfernen, und kann jede Zahl von Gegenständen entfernen, vorausgesetzt dass sie alle aus demselben Haufen kommen.

Varianten von Nim sind seit alten Zeiten gespielt worden. Wie man sagt, ist das Spiel in China entstanden (es ähnelt nah dem chinesischen Spiel von "Jianshizi", oder "Auswahl von Steinen"), aber der Ursprung ist unsicher; die frühsten europäischen Verweisungen auf Nim sind vom Anfang des 16. Jahrhunderts. Sein aktueller Name wurde von Charles L. Bouton von Universität von Harvard ins Leben gerufen, der auch die ganze Theorie des Spiels 1901 entwickelt hat, aber die Ursprünge des Namens wurden nie völlig erklärt. Der Name wird wahrscheinlich aus deutscher Nimm-Bedeutung abgeleitet, "nehmen" oder das veraltete englische Verb nim derselben Bedeutung. Es sollte auch bemerkt werden, dass, das Wort rotieren lassend, NIM durch 180 Grade auf GEWINN hinausläuft (sieh Ambigram).

Nim kann als ein misère Spiel gespielt werden, in dem der Spieler, den letzten Gegenstand zu nehmen, verliert. Nim kann auch als ein normales Spiel-Spiel gespielt werden, was bedeutet, dass die Person, die die letzte Bewegung macht (d. h., wer den letzten Gegenstand nimmt), Gewinne. Das wird normales Spiel genannt, weil die meisten Spiele dieser Tagung folgen, wenn auch Nim gewöhnlich nicht tut.

Normaler Spiel-Nim (oder genauer das System von nimbers) ist für den Sprague-Grundy Lehrsatz grundsätzlich, der im Wesentlichen sagt, dass im normalen Spiel jedes gerechte Spiel zu einem Haufen von Nim gleichwertig ist, der dasselbe Ergebnis, wenn gespielt, in der Parallele mit anderem normalem Spiel gerechte Spiele nachgibt (sieh abtrennende Summe).

Während das ganze normale Spiel gerechte Spiele können ein Nim-Wert zugeteilt werden, der nicht der Fall laut der misère Tagung ist. Nur gezähmte Spiele können mit derselben Strategie wie misère nim gespielt werden.

Eine Version von Nim wird gespielt — und hat symbolische Wichtigkeit — im französischen Neuen Welle-Film im letzten Jahr an Marienbad (1961).

Es war eines der allerersten elektronischen computerisierten Spiele (1952). Herbert Koppel, Eugene Grant und Howard Bailer, Ingenieure von W.L. Maxon Corporation, haben eine 50-Pfund-Maschine entwickelt, die Nim gegen einen menschlichen Gegner gespielt hat und regelmäßig gewonnen hat..

Nim ist ein spezieller Fall eines Poset Spiels, wo Poset aus zusammenhanglosen Ketten (die Haufen) besteht.

Spielspiel und Illustration

Das normale Spiel ist zwischen zwei Spielern und gespielt mit drei Haufen jeder Zahl von Gegenständen. Die zwei Spieler lassen Einnahme jeder Zahl von Gegenständen von irgendwelchem einzelner der Haufen abwechseln. Die Absicht ist, das letzte zu sein, um einen Gegenstand zu nehmen. Im Misère-Spiel ist die Absicht stattdessen sicherzustellen, dass der Gegner gezwungen wird, den letzten restlichen Gegenstand zu nehmen.

Das folgende Beispiel-Spiel wird zwischen erfundenen Spielern Alice und Bob gespielt, die mit Haufen 3, 4 und 5 Gegenstände anfangen. Die Gewinnen-Strategie ist für einen Spieler, um immer eine gleiche Gesamtzahl 1's, 2's, und 4's zu verlassen. Im Beispiel führt Alice diese Strategie durch.

Größen von Haufen-Bewegungen

EIN B C

3 4 nimmt 5 Alice 2 von Einem

1 4 nimmt 5 Bob 3 von C

1 4 nimmt 2 Alice 1 von B

1 3 nimmt 2 Bob 1 von B

1 2 nimmt 2 Alice komplett Ein Haufen, zwei 2s abreisend.

0 2 nimmt 2 Bob 1 von B

0 1 nimmt 2 Alice 1 von C das Verlassen zwei 1s. (Im Misère-Spiel würde sie 2 von C nehmen, der (0, 1, 0) abreist.)

0 1 nimmt 1 Bob 1 von B

0 0 nimmt 1 Alice kompletten C Haufen und Gewinne.

Mathematische Theorie

Nim ist für jede Zahl von anfänglichen Haufen und Gegenständen mathematisch gelöst worden; d. h. es gibt eine leicht berechnete Weise zu bestimmen, welcher Spieler gewinnen wird, und welche Gewinnen-Bewegungen für diesen Spieler offen sind. In einem Spiel, das mit Haufen 3, 4, und 5 anfängt, wird der erste Spieler mit dem optimalen Spiel gewinnen, ob dem misère oder der normalen Spiel-Tagung gefolgt wird.

Der Schlüssel zur Theorie des Spiels ist die binäre Digitalsumme der Haufen-Größen, d. h. die Summe (in der Dualzahl) vernachlässigend alles trägt von einer Ziffer bis einen anderen. Diese Operation ist auch bekannt als "exklusiv oder" (xor) oder "Vektor-Hinzufügung über GF (2)". Innerhalb der kombinatorischen Spieltheorie wird es gewöhnlich die Nim-Summe genannt, wie hier getan wird. Die Nim-Summe von x und y wird x  y geschrieben, um es von der gewöhnlichen Summe, x + y zu unterscheiden. Ein Beispiel der Berechnung mit Haufen der Größe 3, 4, und 5 ist wie folgt:

Binäre Dezimalzahl

011 3 Häufen Einen

100 4 Haufen B

101 5 Haufen C

---

010 2 Die Nim-Summe von Haufen A, B, und C, 3  4  5 = 2

Ein gleichwertiges Verfahren, das häufig leichter ist, geistig zu leisten, soll die Haufen-Größen als Summen von verschiedenen Mächten 2 ausdrücken, Paare von gleichen Mächten annullieren, und dann hinzufügen, was verlassen wird:

3 = 0 + 2 + 1 = 2 1 Häufen Einen

4 = 4 + 0 + 0 = 4 Haufen B

5 = 4 + 0 + 1 = 4 1 Haufen C

- -

2 = 2, Was nach dem Annullieren 1s und 4s verlassen wird

Im normalen Spiel ist die Gewinnen-Strategie, jede Bewegung mit einer Nim-Summe 0 zu beenden. Das ist immer möglich, wenn die Nim-Summe nicht Null vor der Bewegung ist. Wenn die Nim-Summe Null ist, dann wird der folgende Spieler verlieren, wenn der andere Spieler keinen Fehler macht. Um der Bewegung herauszufinden, zu machen, lassen Sie X die Nim-Summe aller Haufen-Größen sein. Nehmen Sie die Nim-Summe jeder der Haufen-Größen mit X, und finden Sie einen Haufen, dessen Größe abnimmt. Die Gewinnen-Strategie ist, in solch einem Haufen zu spielen, diesen Haufen auf die Nim-Summe seiner ursprünglichen Größe mit X reduzierend. Im Beispiel oben, die Nim-Summe der Größen nehmend, ist X = 3  4  5 = 2. Die Nim-Summen der Haufen-Größen A=3, B=4 und C=5 mit X=2 sind

: ⊕ X = 3 ⊕ 2 = 1 [Da (011) ⊕ (010) = 001]

: B ⊕ X = 4 ⊕ 2 = 6

: C ⊕ X = 5 ⊕ 2 = 7

Der einzige Haufen, der reduziert wird, ist Haufen A, so soll die Gewinnen-Bewegung die Größe des Haufens zu 1 (durch das Entfernen von zwei Gegenständen) reduzieren.

Als ein besonderer einfacher Fall, wenn es nur zwei verlassene Haufen gibt, ist die Strategie, die Anzahl von Gegenständen im größeren Haufen zu vermindern, um die Haufen gleich zu machen. Danach, egal was Bewegung Ihr Gegner macht, können Sie dieselbe Bewegung des anderen Haufens machen, versichernd, dass Sie den letzten Gegenstand nehmen.

Wenn gespielt, als ein misère Spiel ist Strategie von Nim nur verschieden, wenn die normale Spiel-Bewegung keinen Haufen der Größe 2 oder größer verlassen würde. In diesem Fall soll die richtige Bewegung eine ungerade Zahl von Haufen der Größe 1 verlassen (im normalen Spiel, die richtige Bewegung würde eine gerade Zahl solcher Haufen verlassen sollen).

In einem misère Spiel mit Haufen von Größen 3, 4 und 5, würde die Strategie wie das angewandt:

Ein B C Nim-summiert

3 4 5 010=2 nehme ich 2 von A, eine Summe 000 verlassend, so werde ich gewinnen.

1 4 5 000=0 nehmen Sie 2 von C

1 4 3 110=6 nehme ich 2 von B

1 2 3 000=0 nehmen Sie 1 von C

1 2 2 001=1 nehme ich 1 von Einem

0 2 2 000=0 nehmen Sie 1 von C

0 2 1 011=3 würde Die normale Spiel-Strategie sein, 1 von B zu nehmen, eine gerade Zahl (2) verlassend

Haufen der Größe 1. Für das Misère-Spiel nehme ich den kompletten B Haufen, um einen sonderbaren zu verlassen

Nummer (1) von Haufen der Größe 1.

0 0 1 001=1 nehmen Sie 1 von C und verlieren.

Die vorherige Strategie für ein misère Spiel kann (zum Beispiel in der Pythonschlange, unten) leicht durchgeführt werden.

def nim (Haufen, misere=True):

"""Schätzt folgende Bewegung für Nim in einem normalen oder misère (Verzug) Spiel, Rücktupel (chosen_heap, nb_remove)"""

X = nehmen Sie ab (Lambda x, y: x^y, Haufen)

wenn X == 0: # Wird verlieren, wenn alle nichtleeren Haufen Größe ein nicht haben

wenn max (Haufen)> 1:

drucken Sie "Sie werden :(" verlieren

weil ich Haufen darin (Haufen) aufzählt:

wenn Haufen> 0: # Leer jeder (nichtleere) Haufen

chosen_heap, nb_remove = ich, Haufen

Brechung

sonst:

Summen = [t^X

#, Wenn Bewegung keinen Haufen der Größe 2 oder größer verlässt, verlassen Sie einen sonderbaren (misère) oder sogar (normale) Zahl von Haufen der Größe 1

wenn heaps_twomore == 0:

chosen_heap = heaps.index (max (Haufen))

heaps_one = Summe (t == 1 für t in Haufen)

# misère (resp. normal) Strategie: Wenn es sogar ist (resp. seltsam), machen es seltsam (resp. sogar), ändern Sie sonst nicht

nb_remove = Haufen [chosen_heap]-1 wenn heaps_one%2! =misere sonst Haufen [chosen_heap]

geben Sie chosen_heap, nb_remove zurück

</Quelle>

Beweis der Gewinnen-Formel

Die Stichhaltigkeit der optimalen Strategie, die oben beschrieben ist, wurde von C. Bouton demonstriert.

Lehrsatz. In einem normalen Spiel von Nim hat der Spieler, der den ersten Schritt tut, eine Gewinnen-Strategie, wenn, und nur wenn die Nim-Summe der Größen der Haufen Nichtnull ist. Sonst hat der zweite Spieler eine Gewinnen-Strategie.

Beweis: Bemerken Sie, dass die Nim-Summe () den üblichen assoziativen und auswechselbaren Gesetzen der Hinzufügung (+) folgt, und auch ein zusätzliches Eigentum, x  x = 0 befriedigt (technisch das Sprechen, bilden die natürlichen Zahlen unter  eine Gruppe von Abelian der Hochzahl 2).

Lassen Sie x..., x die Größen der Haufen vor einer Bewegung und y..., y die entsprechenden Größen nach einer Bewegung sein. Lassen Sie s = x ...  x und t = y ...  y. Wenn die Bewegung im Haufen k war, haben wir x = y für alles ich  k und x &gt; y. Durch die Eigenschaften von , der oben erwähnt ist, haben wir

t = 0  t

= s  s  t

= s  (x ...  x)  (y ...  y)

= s  (x  y) ...  (x  y)

= s  0 ...  0  (x  y)  0 ...  0

= s  x  y

(*) t = s  x  y.

Der Lehrsatz folgt durch die Induktion auf der Länge des Spiels von diesen zwei Lemmata.

Lemma 1. Wenn s = 0, dann t  0, egal was Bewegung gemacht wird.

Beweis: Wenn es keine mögliche Bewegung gibt, dann ist das Lemma ausdruckslos wahr (und der erste Spieler verliert das normale Spiel-Spiel definitionsgemäß). Sonst wird jede Bewegung im Haufen k t = x  y von (*) erzeugen. Diese Zahl ist Nichtnull, seitdem x  y.

Lemma 2. Wenn s  0, es möglich ist, eine Bewegung so dass t = 0 zu machen.

Beweis: Lassen Sie d die Position des leftmost (bedeutendstes) Nichtnullbit in der binären Darstellung von s sein, und solchen k zu wählen, dass das dth Bit von x auch Nichtnull ist. (Solch ein k muss bestehen, da sonst das dth Bit von s 0 sein würde.)

Dann y = s  x lassend, fordern wir das y &lt; x: Alle Bit links von d sind dasselbe in x und y, Bit-D-Abnahmen von 1 bis 0 (das Verringern des Werts durch 2), und jede Änderung in den restlichen Bit wird sich auf höchstens 2&minus;1 belaufen. Der erste Spieler kann so eine Bewegung machen, indem er x &minus nimmt; y protestiert vom Haufen k, dann

t = s  x  y (durch (*))

= s  x  (s  x)

= 0.

Die Modifizierung für das Misère-Spiel wird durch die Anmerkung demonstriert, dass die Modifizierung zuerst in einer Position entsteht, die nur einen Haufen der Größe 2 oder mehr hat. Bemerken Sie, dass in solch einer Position s  0 deshalb diese Situation entstehen muss, wenn es die Umdrehung des Spielers im Anschluss an die Gewinnen-Strategie ist. Die normale Spiel-Strategie ist für den Spieler, um das zu reduzieren, um 0 oder 1 nach Größen zu ordnen, eine gerade Zahl von Haufen mit der Größe 1 verlassend, und die misère Strategie ist, das Gegenteil zu tun. Von diesem Punkt auf werden alle Bewegungen gezwungen.

Andere Schwankungen von Nim

Das Subtraktionsspiel S (1,2..., k)

In einem anderen Spiel, das als Nim allgemein bekannt ist (aber wird das Subtraktionsspiel S (1,2..., k)) besser genannt, wird ein gebundener oberer der Zahl von Gegenständen auferlegt, die in einer Umdrehung entfernt werden können. Anstatt willkürlich viele Gegenstände zu entfernen, kann ein Spieler nur 1 oder 2 oder... oder k auf einmal umziehen. Dieses Spiel wird in der Praxis mit nur einem Haufen allgemein gespielt (zum Beispiel mit k = 3 in den Spielthai 21 darauf, wo es als eine Immunitätsherausforderung erschienen ist).

Die Analyse von Bouton trägt leicht zur allgemeinen Version des vielfachen Haufens dieses Spiels vor. Der einzige Unterschied ist, dass als ein erster Schritt, vor der Computerwissenschaft der Nim-Summen, wir die Größen der Haufen modulo k + 1 reduzieren müssen. Wenn das alle Haufen der Größe-Null macht (im Misère-Spiel), soll die Gewinnen-Bewegung K-Gegenstände von einem der Haufen nehmen. Insbesondere im idealen Spiel von einem einzelnen Haufen von N-Gegenständen kann der zweite Spieler iff gewinnen

: n &equiv; 0 (mod k+1) (im normalen Spiel), oder

: n &equiv; 1 (mod k+1) (im Misère-Spiel).

Das folgt aus dem Rechnen der Nim-Folge von S (1,2..., k),

:

von dem die Strategie oben durch den Sprague-Grundy Lehrsatz folgt.

Das 21 Spiel

Das Spiel "21" wird als ein misère Spiel mit jeder Zahl von Spielern gespielt, die sich abwechseln, eine Zahl sagend. Der erste Spieler sagt "1", und jeder Spieler steigert der Reihe nach die Zahl durch 1, 2, oder 3, aber kann 21 nicht zu weit gehen; der Spieler hat gezwungen, "um 21" zu sagen, verliert. Das kann als ein Subtraktionsspiel mit einem Haufen von 21-n Gegenständen modelliert werden.

Die Gewinnen-Strategie für dieses Spiel ist, ein Vielfache 4 und danach zu sagen, dass es versichert wird, dass der andere Spieler 21 wird sagen müssen, einen Fehler vom ersten Spieler verriegelnd.

Dieses Spiel hat einen Sprague-Grundy Wert der Null, d. h. es wird für den 2. Spieler beeinflusst, weil s/he zu 4 ersten kommen und dann das Spiel von dort, als kontrollieren kann, egal was der 1. Spieler nie im Stande sein wird, ein Vielfache 4 zu sagen, weil s/he nur Zunahme entweder 1, 2 oder 3 erlaubt wird.

Das 21 Spiel kann auch mit verschiedenen Zahlen gespielt werden, wie "Belaufen sich 5 und Verlieren auf 34".

Beweis (über ein Beispielspiel 21) -

Spieler-Zahl

1 1

2 4

1 5,6 oder 7

2 8

1 9,10 oder 11

2 12

1 13,14 oder 15

2 16

1 17,18 oder 19

2 20

1 21

Das 100 Spiel

Eine ähnliche Version ist das "100 Spiel": Zwei Spieler fangen von 0 an und fügen wechselweise eine Zahl von 1 bis 10 bis die Summe hinzu. Der Spieler, der 100 Gewinne erreicht. Die Gewinnen-Strategie ist, eine Zahl zu erreichen, in der die Ziffern (z.B 12, 23, 34...) nachfolgend sind und das Spiel durch das Springen durch alle Zahlen dieser Folge kontrollieren. Einmal erreicht 89 hat der Gegner verloren.

Eine Regel des vielfachen Haufens

In einer anderen Schwankung von Nim, außer dem Entfernen jeder Zahl von Gegenständen von einem einzelnen Haufen, wird man erlaubt, dieselbe Zahl von Gegenständen von jedem Haufen zu entfernen.

Kreisförmiger Nim

Und doch ist eine andere Schwankung von Nim 'Kreisförmiger Nim', wohin jede Zahl von Gegenständen in einen Kreis gelegt wird, und zwei Spieler abwechselnd 1, 2 oder 3 angrenzende Gegenstände umziehen. Zum Beispiel, mit einem Kreis von zehn Gegenständen, anfangend

..........

drei Gegenstände, in der ersten Bewegung genommen werden

_....... _ _

dann weitere drei

_. _ _ _... _ _

dann ein

_. _ _ _.. _ _ _

aber dann können drei Gegenstände nicht in einer Bewegung weggenommen werden.

Das Spiel von Grundy

Im Spiel von Grundy, einer anderen Schwankung von Nim, werden mehrere Gegenstände in einen anfänglichen Haufen gelegt, und zwei Spieler teilen abwechselnd einen Haufen in zwei nichtleere Haufen verschiedener Größen. So können 6 Gegenstände in Stapel 5+1 oder 4+2, aber nicht 3+3 geteilt werden. Das Spiel von Grundy kann entweder als misère oder als normales Spiel gespielt werden.

Gieriger Nim

Sieh gierigen Nim.

Siehe auch

• Dr NIM
• Krauses Spiel
• Nimber
• Nimrod, (rechnend)
• Oktalspiele
• Gelöste Brettspiele
• Stern (Spieltheorie)
• Ziehen Sie ein Quadrat ab
• Nullspiel
• Pfand-Duell
• Androide Nim
• Raymond Redheffer
• Im letzten Jahr an Marienbad
• W. W. Rouse Ball: Mathematische Unterhaltungen und Aufsätze, Macmillan Company, 1947.
• John D. Beasley: Die Mathematik von Spielen, Presse der Universität Oxford, 1989.
• Elwyn R. Berlekamp, John H. Conway und Richard K. Guy: Wege für Ihre Mathematischen Spiele, Academic Press, Inc., 1982 gewinnend.
• C. L. Bouton: Nim, ein Spiel mit einer ganzen mathematischen Theorie, Annalen der Mathematik 3 (1901-02), 35-39.
• Manfred Eigen und Ruthild Winkler: Gesetze des Spiels, Universität von Princeton Presse, 1981.
• Walter R. Fuchs: Computer: Informationstheorie und Kybernetik, Rupert Hart-Davis Bildungsveröffentlichungen, 1971.
• G. H. Hardy und E. M. Wright: Eine Einführung in die Theorie von Zahlen, Presse der Universität Oxford, 1979.
• Edward Kasner und James Newman: Mathematik und die Einbildungskraft, Simon und Schuster, 1940.
• M. Kaitchik: Mathematische Unterhaltungen, W. W. Norton, 1942.
• Donal D. Spencer: Spiel, das mit Computern, Hayden Book Company, Inc., 1968 Spielt.

Außenverbindungen

• 1952: 50-Pfund-Computer spielt Nim-The New Yorker Zeitschrift "Gespräch von der Stadt" August,

1952.:http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053

• 1958: Popular Electronics Zeitschrift Jan 1958, Artikel "Win at NIM with Debicon" - ein elektrischer Stromkreis, der Lichter zeigt, um beim Gewinnen eines Spiels zu helfen.
• Nim Blitz auf Kongregate
• Nim in JavaScript - einschließlich seines historischen Aspekts an Archimedes-Lab.org.
• Nim in JavaScript IE7 und FF3 vereinbarer
• Nim in JavaScript mit GWT
• Das 21 Spiel in JavaScript
• Das heiße Spiel von Nim - Theorie von Nim und Verbindungen mit anderen Spielen an der Knoten-Kürzung
• Nim und 2-dimensionaler SuperNim an der Knoten-Kürzung
• Das Spiel von Nim an sputsoft.com
• Nim auf den Beleuchtungen von NCTM
• Marienbad - Variante von Nim HTML5 Anwendung