Nim-Spiel

Nim

Streichhölzer werden in Reihen für ein Nim-Spiel aufgestellt. Die Spieler wählen abwechselnd eine Reihe aus und entfernen eine beliebige Anzahl von Streichhölzern aus dieser Reihe. ⓘ
Genres	Mathe, Strategie
Spieler	2

Nim ist ein mathematisches Strategiespiel, bei dem zwei Spieler abwechselnd Objekte von verschiedenen Haufen oder Stapeln entfernen (oder "nimming"). In jedem Zug muss ein Spieler mindestens ein Objekt entfernen, wobei er beliebig viele Objekte entfernen kann, sofern sie alle vom selben Haufen oder Stapel stammen. Je nach Spielvariante besteht das Ziel des Spiels entweder darin, das letzte Objekt zu vermeiden oder das letzte Objekt zu nehmen. ⓘ

Varianten von Nim werden seit der Antike gespielt. Das Spiel soll seinen Ursprung in China haben - es ähnelt dem chinesischen Spiel 捡石子 jiǎn-shízi oder "Steine sammeln" -, aber der Ursprung ist ungewiss; die frühesten europäischen Erwähnungen von Nim stammen aus dem Anfang des 16. Jahrhunderts. Der heutige Name wurde von Charles L. Bouton von der Harvard University geprägt, der 1901 auch die vollständige Theorie des Spiels entwickelte, aber der Ursprung des Namens wurde nie vollständig geklärt. ⓘ

Nim wird in der Regel als Misère-Spiel gespielt, bei dem der Spieler, der das letzte Objekt nimmt, verliert. Nim kann auch als normales Spiel gespielt werden, bei dem der Spieler, der das letzte Objekt nimmt, gewinnt. Dies wird als normales Spiel bezeichnet, weil der letzte Zug in den meisten Spielen ein Gewinnzug ist, auch wenn dies nicht die normale Art ist, wie Nim gespielt wird. Wenn die Anzahl der Haufen mit mindestens zwei Objekten genau gleich eins ist, kann der Spieler, der als Nächstes zieht, sowohl im normalen Spiel als auch in einem Misère-Spiel leicht gewinnen. Wenn dieser entweder alle oder alle Objekte außer einem aus dem Haufen mit zwei oder mehr Objekten entfernt, dann hat kein Haufen mehr als ein Objekt, so dass die Spieler gezwungen sind, abwechselnd genau ein Objekt zu entfernen, bis das Spiel endet. Hinterlässt ein Spieler eine gerade Anzahl von Haufen, die nicht Null sind (wie im normalen Spiel), so nimmt er als letzter, hinterlässt er eine ungerade Anzahl von Haufen (wie im Misère-Spiel), so nimmt der andere Spieler als letzter. ⓘ

Das Normalspiel Nim (oder genauer gesagt das System der Nimber) ist grundlegend für das Sprague-Grundy-Theorem, das im Wesentlichen besagt, dass im Normalspiel jedes unparteiische Spiel einem Nim-Haufen entspricht, der das gleiche Ergebnis liefert, wenn er parallel zu anderen unparteiischen Spielen des Normalspiels gespielt wird (siehe disjunkte Summe). ⓘ

Während allen unparteiischen Spielen im Normalspiel ein Nim-Wert zugewiesen werden kann, ist dies unter der Misère-Konvention nicht der Fall. Nur zahme Spiele können mit der gleichen Strategie wie misère Nim gespielt werden. ⓘ

Nim ist ein Spezialfall eines Poset-Spiels, bei dem das Poset aus disjunkten Ketten (den Heaps) besteht. ⓘ

Der Evolutionsgraph des Nim-Spiels mit drei Haufen ist derselbe wie drei Zweige des Evolutionsgraphen des Ulam-Warburton-Automaten. ⓘ

Auf der New Yorker Weltausstellung von 1940 stellte Westinghouse einen Automaten, den Nimatron, aus, der Nim spielte. Vom 11. Mai 1940 bis zum 27. Oktober 1940 gelang es nur wenigen Menschen, den Automaten in diesem sechswöchigen Zeitraum zu schlagen; wer es schaffte, erhielt eine Münze mit der Aufschrift Nim Champ. Es war auch eines der ersten elektronischen Computerspiele überhaupt. Ferranti baute einen Nim-Spielcomputer, der 1951 auf dem Festival of Britain ausgestellt wurde. 1952 entwickelten Herbert Koppel, Eugene Grant und Howard Bailer, Ingenieure der W. L. Maxon Corporation, eine 23 Kilogramm schwere Maschine, die Nim gegen einen menschlichen Gegner spielte und regelmäßig gewann. Es wurde eine Nim-Spielmaschine beschrieben, die aus TinkerToy hergestellt wurde. ⓘ

Das Spiel Nim war das Thema von Martin Gardners Kolumne Mathematische Spiele im Scientific American vom Februar 1958. Eine Version von Nim wird in dem französischen New-Wave-Film Letztes Jahr in Marienbad (1961) gespielt und hat symbolische Bedeutung. ⓘ

Spielt man das Spiel mit nur einer Reihe (ähnlich dem Bachet’schen Spiel), so wird eine Höchstzahl von wegnehmbaren Hölzchen pro Zug festgelegt. ⓘ

In der Arbeit von Grundy wird die Gewinnstrategie bei neutralen Spielen über so genannte Grundy-Werte auf die Strategie beim Nim-Spiel zurückgeführt (s. Satz von Sprague-Grundy). Des Weiteren verallgemeinert sich die Theorie des Nim-Spiels ab etwa 1970 zur Kombinatorischen Spieltheorie. ⓘ

Spielablauf und Illustration

Das normale Spiel findet zwischen zwei Spielern statt und wird mit drei Haufen aus einer beliebigen Anzahl von Gegenständen gespielt. Die beiden Spieler nehmen abwechselnd eine beliebige Anzahl von Gegenständen aus einem der Haufen. Ziel ist es, als letzter einen Gegenstand zu nehmen. Beim Misère-Spiel besteht das Ziel stattdessen darin, den Gegner zu zwingen, den letzten verbleibenden Gegenstand zu nehmen. ⓘ

Das folgende Beispiel für ein normales Spiel wird zwischen den fiktiven Spielern Bob und Alice gespielt, die mit Haufen von drei, vier und fünf Objekten beginnen. ⓘ

Haufen A	Haufen B	Haufen C	Zug ⓘ
3	4	5	Das Spiel beginnt
1	4	5	Bob nimmt 2 von A
1	4	2	Alice nimmt 3 von C
1	3	2	Bob nimmt 1 von B
1	2	2	Alice nimmt 1 von B
0	2	2	Bob nimmt den gesamten Haufen von A, so dass zwei 2er übrig bleiben
0	1	2	Alice nimmt 1 von B
0	1	1	Bob nimmt 1 von C, so dass zwei 1en übrig bleiben. (Bei einem falschen Spiel würde er 2 von C nehmen, so dass (0, 1, 0) übrig bleibt).
0	0	1	Alice nimmt 1 von B
0	0	0	Bob nimmt den gesamten Haufen C und gewinnt

Gewinnende Positionen

Die praktische Strategie, um beim Nim-Spiel zu gewinnen, besteht darin, dass ein Spieler den anderen in eine der folgenden Stellungen bringt, und in jedem weiteren Zug sollte er in der Lage sein, eine der kleineren Stellungen zu erreichen. Nur der letzte Zug unterscheidet sich zwischen Misere und normalem Spiel. ⓘ

2 Haufen	3 Haufen	4 Haufen ⓘ
1 1 *	1 1 1 **	1 1 1 1 *
2 2	1 2 3	1 1 n n
3 3	1 4 5	1 2 4 7
4 4	1 6 7	1 2 5 6
5 5	1 8 9	1 3 4 6
6 6	2 4 6	1 3 5 7
7 7	2 5 7	2 3 4 5
8 8	3 4 7	2 3 6 7
9 9	3 5 6	2 3 8 9
n n	4 8 12	4 5 6 7
	4 9 13	4 5 8 9
	5 8 13	n n m m
	5 9 12	n n n n

* Gilt nur für das normale Spiel. ⓘ

** Gilt nur für Miserere. ⓘ

Für die Verallgemeinerungen können n und m einen beliebigen Wert > 0 haben, und sie können gleich sein. ⓘ

Mathematische Theorie

Nim wurde mathematisch für eine beliebige Anzahl von Anfangshaufen und Objekten gelöst, und es gibt einen leicht zu berechnenden Weg, um zu bestimmen, welcher Spieler gewinnen wird und welche Gewinnzüge ihm offen stehen. ⓘ

Der Schlüssel zur Spieltheorie ist die binäre digitale Summe der Haufengrößen, d. h. die Summe (in binärer Form) unter Vernachlässigung aller Überträge von einer Ziffer zur anderen. Diese Operation wird auch als "bitweises xor" oder "Vektoraddition über GF(2)" (bitweise Addition modulo 2) bezeichnet. In der kombinatorischen Spieltheorie wird sie üblicherweise als Nim-Summe bezeichnet, so wie es auch hier der Fall sein wird. Die Nim-Summe von x und y wird mit x ⊕ y geschrieben, um sie von der gewöhnlichen Summe x + y zu unterscheiden. Ein Beispiel für die Berechnung mit Haufen der Größe 3, 4 und 5 lautet wie folgt:

Binär Dezimal ⓘ

  0112 310 Haufen A
  1002 410 Haufen B
  1012 510 Haufen C
  ---
  0102 210 Die Nim-Summe der Heaps A, B und C, 3 ⊕ 4 ⊕ 5 = 2

Ein äquivalentes Verfahren, das gedanklich oft einfacher auszuführen ist, besteht darin, die Haufengrößen als Summen verschiedener Potenzen von 2 auszudrücken, Paare gleicher Potenzen zu streichen und dann zu addieren, was übrig bleibt:

3 = 0 + 2 + 1 = 2 1 Haufen A
4 = 4 + 0 + 0 = 4 Haufen B
5 = 4 + 0 + 1 = 4 1 Haufen C
--------------------------------------------------------------------
2 = 2 Was bleibt nach dem Streichen von 1en und 4en übrig?

Im normalen Spiel besteht die Gewinnstrategie darin, jeden Zug mit einer Nim-Summe von 0 zu beenden. Dies ist immer möglich, wenn die Nim-Summe vor dem Zug nicht Null ist. Wenn die Nim-Summe Null ist, dann verliert der nächste Spieler, wenn der andere Spieler keinen Fehler macht. Um herauszufinden, welcher Zug zu machen ist, sei X die Nim-Summe aller Haufengrößen. Finde einen Haufen, bei dem die Nim-Summe aus X und Haufengröße kleiner ist als die Haufengröße; die Gewinnstrategie besteht darin, in einem solchen Haufen zu spielen und diesen Haufen auf die Nim-Summe seiner ursprünglichen Größe mit X zu reduzieren. Im obigen Beispiel ist die Nim-Summe der Größen X = 3 ⊕ 4 ⊕ 5 = 2. Die Nim-Summen der Heap-Größen A=3, B=4 und C=5 mit X=2 sind ⓘ

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

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7 ⓘ

Der einzige Haufen, der verkleinert wird, ist der Haufen A. Der Gewinn besteht also darin, die Größe des Haufens A auf 1 zu reduzieren (indem zwei Objekte entfernt werden). ⓘ

In einem besonders einfachen Fall, wenn nur noch zwei Haufen übrig sind, besteht die Strategie darin, die Anzahl der Objekte im größeren Haufen zu verringern, um die Haufen gleich zu machen. Danach kann man, egal welchen Zug der Gegner macht, den gleichen Zug auf dem anderen Haufen machen und hat damit die Garantie, dass man das letzte Objekt nimmt. ⓘ

Wenn man Nim als Misère-Spiel spielt, ist die Strategie nur dann anders, wenn der normale Spielzug nur Haufen der Größe eins übrig lassen würde. In diesem Fall besteht der richtige Zug darin, eine ungerade Anzahl von Haufen der Größe eins zu hinterlassen (im normalen Spiel wäre der richtige Zug der, eine gerade Anzahl solcher Haufen zu hinterlassen). ⓘ

Diese Strategien für das normale Spiel und das Misère-Spiel sind gleich, bis die Anzahl der Haufen mit mindestens zwei Objekten genau gleich eins ist. Dann entfernt der nächste Spieler entweder alle Objekte (oder alle bis auf eines) aus dem Haufen mit zwei oder mehr Objekten, so dass kein Haufen mehr als ein Objekt hat (mit anderen Worten: alle verbleibenden Haufen haben jeweils genau ein Objekt), so dass die Spieler gezwungen sind, abwechselnd genau ein Objekt zu entfernen, bis das Spiel endet. Bei einem normalen Spiel hinterlässt ein Spieler eine gerade Anzahl von Haufen, die nicht Null sind, so dass derselbe Spieler zuletzt nimmt; bei einem Misère-Spiel hinterlässt ein Spieler eine ungerade Anzahl von Haufen, die nicht Null sind, so dass der andere Spieler zuletzt nimmt. ⓘ

In einem Misère-Spiel mit Haufen der Größe drei, vier und fünf würde die Strategie wie folgt angewandt werden:

A B C nim-sum ⓘ 

3 4 5 0102=210 Ich nehme 2 von A, so dass eine Summe von 000 übrig bleibt, also gewinne ich.
1 4 5 0002=010 Du nimmst 2 von C
1 4 3 1102=610 Ich nehme 2 von B
1 2 3 0002=010 Du nimmst 1 von C
1 2 2 0012=110 Ich nehme 1 von A
0 2 2 0002=010 Du nimmst 1 von C
0 2 1 0112=310 Die normale Spielstrategie wäre, 1 aus B zu nehmen, so dass eine gerade Anzahl (2)
                 Haufen der Größe 1.  Beim Misère-Spiel nehme ich den gesamten Haufen von B, so dass eine ungerade
                 Anzahl (1) von Haufen der Größe 1.
0 0 1 0012=110 Du nimmst 1 von C und verlierst. ⓘ

Findet man eine Stellung mit ausschließlich geradzahligen Spaltensummen vor, so ist dies für den ziehenden Spieler eine Verluststellung, die bei optimalem Spiel des Gegners dazu führt, dass er in der Verliererrolle bleibt und am Ende des Spiels dem Gegner eine Gewinnvorlage für seinen letzten Zug (finale Gewinnstellung) übergeben muss. Ist andererseits mindestens eine der Spaltensummen ungerade, so ist dies eine Gewinnstellung (mögliche Ausnahme: das Endspiel des Misère-Nim). Es ist dann möglich, gerade Spaltensummen durch den eigenen Zug zu erreichen, wodurch man dem Gegner eine Verluststellung übergibt. ⓘ

Zusammengefasst ⓘ

Aus einer Verluststellung muss man immer eine Gewinnstellung machen; aus einer Gewinnstellung kann man immer eine Verluststellung erzeugen. ⓘ

Beweis der Gewinnformel

Die Solidität der oben beschriebenen optimalen Strategie wurde von C. Bouton bewiesen. ⓘ

Theorem. In einem normalen Nim-Spiel hat der Spieler, der den ersten Zug macht, nur dann eine Gewinnstrategie, wenn die Nim-Summe der Größen der Haufen ungleich Null ist. Andernfalls hat der zweite Spieler eine Gewinnstrategie. ⓘ

Der Beweis: Man beachte, dass die Nim-Summe (⊕) den üblichen Assoziativ- und Kommutativgesetzen der Addition (+) gehorcht und außerdem eine zusätzliche Eigenschaft erfüllt, nämlich x ⊕ x = 0. ⓘ

Seien x₁, ..., xn die Größen der Haufen vor einer Verschiebung, und y₁, ..., yn die entsprechenden Größen nach einer Verschiebung. Es sei s = x₁ ⊕ ... ⊕ xn und t = y₁ ⊕ ... ⊕ yn. Wenn der Zug im Haufen k war, haben wir xi = yi für alle i ≠ k, und xk > yk. Aus den oben genannten Eigenschaften von ⊕ ergibt sich

    t = 0 ⊕ t
      = s ⊕ s ⊕ t
      = s ⊕ (x1 ⊕ ... ⊕ xn) ⊕ (y1 ⊕ ... ⊕ yn)
      = s ⊕ (x1 ⊕ y1) ⊕ ... ⊕ (xn ⊕ yn)
      = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (xk ⊕ yk) ⊕ 0 ⊕ ... ⊕ 0
      = s ⊕ xk ⊕ yk ⓘ

(*) t = s ⊕ xk ⊕ yk.

Das Theorem folgt durch Induktion auf die Länge des Spiels aus diesen beiden Lemmata. ⓘ

Lemma 1. Wenn s = 0 ist, dann ist t ≠ 0, egal welcher Zug gemacht wird. ⓘ

Beweis: Wenn es keinen möglichen Zug gibt, dann ist das Lemma leer wahr (und der erste Spieler verliert das normale Spiel per Definition). Andernfalls ergibt jeder Zug im Haufen k t = xk ⊕ yk aus (*). Diese Zahl ist ungleich Null, da xk ≠ yk. ⓘ

Lemma 2: Wenn s ≠ 0 ist, ist es möglich, einen Zug zu machen, so dass t = 0 ist. ⓘ

Beweis: Sei d die Position des ganz linken (höchstwertigen) Nicht-Null-Bits in der Binärdarstellung von s, und wähle k so, dass das d-te Bit von xk ebenfalls Nicht-Null ist. (Ein solches k muss existieren, da sonst das d-te Bit von s 0 wäre.) Mit yk = s ⊕ xk behaupten wir, dass yk < xk ist: alle Bits links von d sind in xk und yk gleich, das Bit d fällt von 1 auf 0 (was den Wert um 2d verringert), und jede Änderung in den übrigen Bits beträgt höchstens 2d-1. Der erste Spieler kann also einen Zug machen, indem er xk - yk Objekte vom Haufen k nimmt, dann

t = s ⊕ xk ⊕ yk (durch (*))
  = s ⊕ xk ⊕ (s ⊕ xk)
  = 0.

Die Modifikation für misère play wird durch die Feststellung demonstriert, dass die Modifikation zuerst in einer Stellung auftritt, die nur einen Haufen der Größe 2 oder mehr hat. Beachten Sie, dass in einer solchen Stellung s ≠ 0 ist und diese Situation daher eintreten muss, wenn der Spieler am Zug ist, der die Gewinnstrategie verfolgt. Die normale Spielstrategie besteht darin, dass der Spieler diesen auf die Größe 0 oder 1 reduziert, so dass eine gerade Anzahl von Haufen mit der Größe 1 übrig bleibt, und die Misère-Strategie besteht darin, das Gegenteil zu tun. Von diesem Zeitpunkt an sind alle Züge erzwungen. ⓘ

Variationen

Das Subtraktionsspiel

Interaktives Subtraktionsspiel: Die Spieler entfernen abwechselnd 1, 2 oder 3 Objekte aus einem anfänglichen Pool von 21 Objekten. Der Spieler, der das letzte Objekt entfernt, gewinnt.

In einem anderen Spiel, das allgemein als Nim bekannt ist (aber besser als Subtraktionsspiel bezeichnet wird), wird eine Obergrenze für die Anzahl der Objekte festgelegt, die in einem Zug entfernt werden können. Anstatt beliebig viele Objekte zu entfernen, kann ein Spieler nur 1 oder 2 oder ... oder k auf einmal entfernen. Dieses Spiel wird in der Praxis häufig mit nur einem Haufen gespielt (z. B. mit k = 3 im Spiel Thai 21 bei Survivor: Thailand, wo es als Immunitätsherausforderung erschien). ⓘ

Die Analyse von Bouton lässt sich leicht auf die allgemeine Version dieses Spiels mit mehreren Haufen übertragen. Der einzige Unterschied besteht darin, dass wir in einem ersten Schritt vor der Berechnung der Nim-Summen die Größe der Heaps modulo k + 1 reduzieren müssen. Wenn dadurch alle Haufen die Größe Null haben (im Misère-Spiel), besteht der Gewinnzug darin, k Objekte aus einem der Haufen zu nehmen. Insbesondere kann der zweite Spieler im idealen Spiel von einem einzigen Haufen mit n Objekten nur dann gewinnen, wenn ⓘ

0 = n (mod k + 1) (im normalen Spiel), oder

1 = n (mod k + 1) (im Misère-Spiel). ⓘ

Dies folgt aus der Berechnung der nim-Folge von S(1,2,...,k), ⓘ

${\displaystyle }$ ⓘ

aus der sich die obige Strategie nach dem Sprague-Grundy-Theorem ergibt. ⓘ

Das Spiel 21

Das Spiel "21" wird als Misère-Spiel mit einer beliebigen Anzahl von Spielern gespielt, die abwechselnd eine Zahl sagen. Der erste Spieler sagt "1" und jeder Spieler erhöht reihum die Zahl um 1, 2 oder 3, darf aber 21 nicht überschreiten; der Spieler, der gezwungen ist, "21" zu sagen, verliert. Dies kann als Subtraktionsspiel mit einem Haufen von 21-n Objekten modelliert werden. Die Gewinnstrategie für die Zwei-Spieler-Version dieses Spiels besteht darin, immer ein Vielfaches von 4 zu sagen; dann ist garantiert, dass der andere Spieler am Ende 21 sagen muss; in der Standardversion, bei der der erste Spieler mit "1" beginnt, beginnt er also mit einem Verlustzug. ⓘ

Das 21-Spiel kann auch mit anderen Zahlen gespielt werden, z. B. "Höchstens 5 addieren; bei 34 verlieren". ⓘ

Ein Beispielspiel von 21, bei dem der zweite Spieler die Gewinnstrategie verfolgt:

Spieler Nummer
  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 Variante ist das "100er-Spiel": Zwei Spieler beginnen bei 0 und addieren abwechselnd eine Zahl von 1 bis 10 zu der Summe. Der Spieler, der 100 erreicht, gewinnt. Die Gewinnstrategie besteht darin, eine Zahl zu erreichen, bei der die Ziffern aufeinander folgen (z. B. 01, 12, 23, 34,...) und das Spiel zu kontrollieren, indem man durch alle Zahlen dieser Folge springt. Sobald ein Spieler 89 erreicht hat, kann der Gegner nur noch Zahlen von 90 bis 99 wählen, und die nächste Antwort kann in jedem Fall 100 sein. ⓘ

Eine Mehrfachhaufen-Regel

In einer anderen Variante von Nim darf man nicht nur beliebig viele Objekte von einem einzigen Haufen entfernen, sondern auch die gleiche Anzahl von Objekten von jedem Haufen. ⓘ

Kreisförmiges Nim

Eine weitere Variante von Nim ist das "kreisförmige Nim", bei dem eine beliebige Anzahl von Gegenständen in einen Kreis gelegt wird und zwei Spieler abwechselnd ein, zwei oder drei benachbarte Gegenstände entfernen. Ein Beispiel: Man beginnt mit einem Kreis aus zehn Gegenständen,

. . . . . . . . . .

werden im ersten Zug drei Objekte entfernt

_ . . . . . . . _ _

dann drei weitere

_ . _ _ _ . . . _ _

dann eine

_ . _ _ _ . . _ _ _

aber dann können nicht drei Objekte in einem Zug herausgenommen werden. ⓘ

Grundy's Spiel

Bei Grundys Spiel, einer weiteren Variante von Nim, wird eine Anzahl von Gegenständen auf einen Anfangshaufen gelegt, und zwei Spieler teilen abwechselnd einen Haufen in zwei nicht leere Haufen unterschiedlicher Größe auf. So können sechs Gegenstände in Haufen von 5+1 oder 4+2, aber nicht 3+3 aufgeteilt werden. Grundy's Spiel kann entweder als Misère oder als normales Spiel gespielt werden. ⓘ

Gieriges Nim

Gieriges Nim ist eine Variante, bei der die Spieler nur Steine vom größten Stapel wählen dürfen. Es ist ein endliches unparteiisches Spiel. Greedy Nim Misère hat die gleichen Regeln wie Greedy Nim, aber hier verliert der letzte Spieler, der einen Zug machen kann. ⓘ

Die größte Anzahl von Steinen in einem Stapel sei m und die zweitgrößte Anzahl von Steinen in einem Stapel sei n. pm sei die Anzahl von Stapeln mit m Steinen und pn sei die Anzahl von Stapeln mit n Steinen. Dann gibt es ein Theorem, dass Spielpositionen mit pm gerade P-Positionen sind.

Dieses Theorem kann gezeigt werden, indem man die Positionen betrachtet, bei denen pm ungerade ist. Wenn pm größer als 1 ist, können alle Steine von diesem Stapel entfernt werden, um pm um 1 zu verringern, und das neue pm wird gerade sein. Wenn pm = 1 ist (d. h. der größte Haufen ist eindeutig), gibt es zwei Fälle:

• Wenn pn ungerade ist, wird die Größe des größten Haufens auf n reduziert (dann ist das neue p_m gerade).
• Wenn pn gerade ist, wird der größte Heap vollständig entfernt, so dass eine gerade Anzahl von größten Heaps übrig bleibt. ⓘ

Es gibt also einen Übergang zu einem Zustand, in dem pm gerade ist. Umgekehrt, wenn pm gerade ist, muss ein möglicher Zug (pm ≠ 0) das Spiel in einen Zustand bringen, in dem pm ungerade ist. Die Endstellung des Spiels ist gerade (pm = 0). Folglich muss jede Stellung des Spiels, in der pm gerade ist, eine P-Stellung sein. ⓘ

Index-k Nim

Eine Verallgemeinerung von Multi-Haufen-Nim wurde "Nim" genannt${\displaystyle }$"oder "index-k" Nim von E. H. Moore genannt, der es 1910 analysierte. Bei index-k Nim können die Spieler Objekte nicht nur aus einem Haufen, sondern aus mindestens einem, aber bis zu k verschiedenen Haufen entfernen. Die Anzahl der Elemente, die aus jedem Haufen entfernt werden können, kann entweder beliebig sein oder auf höchstens r Elemente begrenzt werden, wie im obigen "Subtraktionsspiel". ⓘ

Die Gewinnstrategie sieht folgendermaßen aus: Wie im gewöhnlichen Multi-Heap-Nim betrachtet man die binäre Darstellung der Heapgrößen (oder Heapgrößen modulo r + 1). In gewöhnlichem Nim bildet man die XOR-Summe (oder Summe modulo 2) jeder Binärziffer, und die Gewinnstrategie besteht darin, jede XOR-Summe zu Null zu machen. Bei der Verallgemeinerung auf index-k Nim bildet man die Summe jeder Binärziffer modulo k + 1. ⓘ

Auch hier besteht die Gewinnstrategie darin, sich so zu bewegen, dass diese Summe für jede Ziffer Null ist. Der auf diese Weise berechnete Wert ist nämlich für die Endposition gleich Null, und bei einer Konfiguration von Haufen, für die dieser Wert gleich Null ist, führt jede Änderung von höchstens k Haufen dazu, dass der Wert ungleich Null wird. Umgekehrt kann man bei einer Konfiguration, bei der der Wert ungleich Null ist, immer von höchstens k sorgfältig ausgewählten Haufen nehmen, so dass der Wert Null wird. ⓘ

Nim bauen

Building Nim ist eine Variante von Nim, bei der die beiden Spieler zunächst das Spiel Nim konstruieren. Bei n Steinen und s leeren Stapeln legen die Spieler abwechselnd genau einen Stein auf einen Stapel ihrer Wahl. Sobald alle Steine platziert sind, beginnt eine Partie Nim, beginnend mit dem nächsten Spieler, der ziehen würde. Dieses Spiel wird mit BN(n,s) bezeichnet. ⓘ

Höherdimensionales Nim

n-d Nim wird gespielt auf einem ${\displaystyle }$ Brett gespielt, auf dem eine beliebige Anzahl von kontinuierlichen Steinen aus einer beliebigen Hyperreihe entfernt werden kann. Die Startposition ist in der Regel das volle Brett, aber es sind auch andere Optionen möglich. ⓘ

Graph Nim

Das Startbrett ist ein unzusammenhängender Graph, und die Spieler entfernen abwechselnd benachbarte Eckpunkte. ⓘ

Candy Nim

Candy Nim ist eine Variante des normalen Nim-Spiels, bei der die Spieler versuchen, zwei Ziele gleichzeitig zu erreichen: das letzte Objekt (in diesem Fall eine Süßigkeit) und die maximale Anzahl an Süßigkeiten bis zum Ende des Spiels zu erreichen. ⓘ

Wordnim

Wordnim ist die verbale Version von Nim, bei der die Spieler Wörter aus anfänglichen Mengen oder Serien von Buchstaben bilden, bis keine mehr übrig sind oder kein legitimes Wort mehr gebildet werden kann. ⓘ

Die Strategie anhand eines Beispiels

Als Beispiel diene die folgende Stellung mit ${\displaystyle }$ Reihen enthaltend die Anzahlen ${\displaystyle }$ von 1, 2, 3, 4 und 7 Hölzchen mit den Dualdarstellungen ${\displaystyle }$ (wobei in der Tabelle rechts vom ≙-Zeichen die Hölzchen den Dualstellen entsprechend gruppiert sind):

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$ ⓘ

${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙			style="text-align:right"	ⓘ
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙		style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙		style="text-align:right"		style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙	style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙	style="width:1.2em;text-align:right"			style="width:.5em;text-align:right"		style="width:.35em;text-align:right"

	${\displaystyle }$	${\displaystyle }$ ⓘ
	${\displaystyle }$	${\displaystyle }$	≙		style="width:.5em;text-align:right"		style="width:.45em;text-align:right"

Die Summe der Dualziffern ist in der ${\displaystyle }$-er-Spalte gerade, aber in der ${\displaystyle }$-er- und ${\displaystyle }$-er-Spalte ungerade, nämlich jeweils 3. Die Stellung ist damit eine Gewinnstellung. ⓘ

Wenn in dieser Spielstellung gemäß der Gewinnstrategie entweder aus der 2. Reihe ein Hölzchen oder aus der 3. oder 5. drei Hölzchen entfernt werden, entsteht für den Nachziehenden eine Verluststellung mit nur geraden Spaltensummen. (Es gibt außer diesen drei Zugmöglichkeiten viele andere regelkonforme, die aber alle dazu führen würden, dass der Gegner eine Gewinnstellung statt einer Verluststellung bekommt.) ⓘ

Nach der Wegnahme von drei Hölzchen aus der 5. Reihe ergibt sich die folgende Konstellation der Anzahlen und Dualdarstellungen:

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$ ⓘ

${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙			style="text-align:right"	ⓘ
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙		style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙		style="text-align:right"		style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙	style="text-align:right"
${\displaystyle }$	${\displaystyle }$	${\displaystyle }$	≙	style="width:1.2em;text-align:right"

	${\displaystyle }$	${\displaystyle }$ ⓘ
	${\displaystyle }$	${\displaystyle }$	≙	(leer)

Dies ist eine Verluststellung für den Spieler, der jetzt am Zug ist. Er muss aus genau einer Reihe mindestens ein Hölzchen entnehmen und muss damit in dieser Reihe mindestens eine Dualziffer '1' zu einer '0' machen, wodurch diese Dualstelle eine ungerade Spaltensumme bekommt. Er muss also eine Gewinnstellung erzeugen. Es geht nicht anders. ⓘ

Andererseits gibt es immer mindestens eine Möglichkeit, um aus einer Gewinnstellung (die man vorfindet) eine Verluststellung (für den Gegner) zu machen: Dazu ermittelt man von links her die erste (also die höchstrangige) Spalte mit ungerader Summe (im obigen Beispiel war es die ${\displaystyle }$-er-Spalte). Es muss dann eine Reihe geben, die in dieser Spalte eine '1' hat. Aus einer solchen Reihe entnehme man Hölzchen in einer Weise, dass in dieser Spalte und in allen Spalten weiter rechts (links stimmt's vorher schon) gerade Spaltensummen entstehen. ⓘ

Zur Regel von Bouton gibt es eine sehr einfache Unterregel: Hat der Spieler beim letzten Mal seinem Gegner eine Verluststellung übergeben, die zwei Reihen mit gleich vielen Hölzchen enthält, und entnimmt der Gegner aus einer der beiden Reihen eine gewisse Anzahl Hölzchen, dann erzeugt die Entnahme von gleich vielen Hölzchen aus der anderen Reihe wieder eine Verluststellung. (Zu beachten ist allerdings ggf. das Endspiel des Misère-Nim.) ⓘ

Frühe Nim-Computer

Nimrod im Computerspielemuseum Berlin ⓘ

Die Strategie von Bouton macht Nim zu einem Spiel, das einfach zu programmieren ist. Frühe Computer wurden für das Nim-Spiel entwickelt. 1940 stellte die Firma Westinghouse auf der New-Yorker Weltausstellung ihr Gerät Nimatron aus und 1951 beeindruckte ein in England gebauter elektronischer Rechner namens Nimrod die Öffentlichkeit dadurch, dass er auf der Berliner Industrieausstellung den damaligen Wirtschaftsminister Ludwig Erhard im Nim-Spiel schlug. ⓘ

Bemerkenswert an der Gewinnstrategie ist, dass Anzahlen sowohl als gewöhnliche Zahlen wie auch als Bitvektoren angesehen werden müssen. Für eine Implementierung bieten hardwareseitig binär arbeitende Computer Vorteile und softwareseitig Programmiersprachen der C-Familie, in denen Zahlen des Typs unsigned int ganz ohne Umwandlung des Datentyps auch als Bitvektoren aufgefasst werden können und die dazuhin die hier benötigten bitweisen Operationen unterstützen. ⓘ

Misère

Beim Misère-Spiel hat der Spieler, der das letzte Hölzchen nimmt, nicht gewonnen, sondern verloren. Eine verbreitete Variante des Misère-Nim ist Marienbad, dessen Ausgangsstellung in der Abbildung gezeigt ist. ⓘ

In der Hauptsache regiert dieselbe Gewinnstrategie wie beim Standard-Nim. Erst gegen Ende wird von ihr abgewichen. Tritt nämlich die Situation ein, dass es genau eine Reihe mit mehr als einem Hölzchen gibt, kann man von dieser Reihe regelkonform alle Hölzchen oder alle bis auf eines wegnehmen. Will man gewinnen, übergibt man eine ungerade Anzahl von Einser-Reihen. (Beim Standard-Nim wäre es eine gerade Anzahl, ein Ergebnis, das auch bei der Geradzahligkeit der Spaltensummen herauskäme.) ⓘ