Bevor

Nim ist ein mathematisches Strategiespiel für zwei Spieler. Das Spiel beginnt mit mehreren Stapeln von Gegenständen – traditionell Steine, Münzen oder Streichhölzer. Die Spieler entfernen abwechselnd eine beliebige Anzahl von Gegenständen von einem einzelnen Stapel (mindestens einen, bis hin zum gesamten Stapel). In der Standardversion (normales Spiel) gewinnt der Spieler, der den letzten Gegenstand nimmt. In der Misère-Variante verliert der Spieler, der gezwungen ist, den letzten Gegenstand zu nehmen. Nim ist eines der grundlegendsten Spiele der kombinatorischen Spieltheorie.

Regeln (Normalspiel)

1. Das Spiel beginnt mit einer Reihe von Stapeln, die jeweils einen oder mehrere Gegenstände enthalten. Eine übliche Startaufstellung sind Stapel mit 3, 5 und 7 Gegenständen.
2. Zwei Spieler sind abwechselnd am Zug.
3. In jedem Zug muss ein Spieler mindestens einen Gegenstand von genau einem Stapel entfernen. Er darf so viele Objekte von diesem Stapel nehmen, wie er möchte, bis einschließlich des gesamten Stapels.
4. Der Spieler, der das letzte Objekt vom letzten verbleibenden Stapel nimmt, gewinnt.

Regeln (Misère-Variante)

Wie oben, mit dem Unterschied, dass der Spieler verliert, der gezwungen ist, das letzte Objekt zu nehmen.

Strategien

• Nim-Sum (XOR-Strategie): Der Schlüssel zum Sieg bei Nim ist die binäre digitale Summe (XOR) aller Stapelgrößen. Ist das XOR aller Stapel 0, ist die Position für den Spieler, der am Zug ist, verloren (bei perfektem Spiel des Gegners). Ist das XOR ungleich Null, kann der aktuelle Spieler immer einen Zug machen, der den Gegner in eine XOR-Null-Position bringt.
• So berechnet man die Nim-Summe: Wandle die Größe jedes Stapels in Binärzahlen um und berechne das XOR aller Stapelgrößen. Beispiel: Stapel mit 3 (011), 5 (101), 7 (111) → XOR = 001 (ungleich Null, der aktuelle Spieler kann gewinnen).
• Gewinnzug: Um aus einer XOR-Position ungleich Null zu gewinnen, suche einen Stapel, bei dem das Entfernen einiger Objekte den Gesamt-XOR auf Null setzt. Es gibt immer mindestens einen solchen Stapel.
• Misère-Strategie: Wende dieselbe XOR-Strategie wie beim normalen Nim an, jedoch mit einer Ausnahme: Wenn alle verbleibenden Stapel die Größe 1 haben, nimm so viele, dass eine ungerade Anzahl von Stapeln übrig bleibt (wodurch dein Gegner gezwungen ist, den letzten zu nehmen).
• Endspiel mit einem Stapel: Wenn nur noch ein Stapel übrig ist, nimm den gesamten Stapel (normales Spiel) oder alle bis auf einen (Misère).
• Zwei gleich große Stapel: Wenn genau zwei Stapel gleicher Größe vorhanden sind, ist dies im normalen Spiel eine verlorene Position (XOR = 0). Spiegeln Sie die Züge Ihres Gegners bis zum Endspiel.

Nim hat uralte Wurzeln, auch wenn sich die genaue Entstehungsgeschichte nur schwer nachvollziehen lässt. Spiele, bei denen Gegenstände von Stapeln entfernt werden, werden seit Jahrhunderten in vielen Kulturen gespielt. Der Name „Nim“ wurde von Charles L. Bouton geprägt, einem Mathematikprofessor an der Harvard-Universität, der 1901 in einer Abhandlung mit dem Titel „Nim, A Game with a Complete Mathematical Theory“ die vollständige mathematische Analyse des Spiels veröffentlichte. Die Herkunft des Namens ist ungewiss – er könnte vom deutschen Wort „nimm“ (nehmen) oder vom veralteten englischen Wort „nim“ (stehlen) stammen.

Boutons entscheidende Erkenntnis war die auf XOR basierende Gewinnstrategie, die er streng mathematisch bewies. Dies war eines der ersten Spiele, das mathematisch vollständig gelöst wurde, und es legte den Grundstein für das Gebiet der kombinatorischen Spieltheorie. Seine Analyse zeigte, dass sich das gesamte Spiel auf eine einfache binäre Berechnung reduzieren ließ, was Nim zu einer der elegantesten Schnittstellen zwischen Mathematik und Spielen macht.

Im Jahr 1939 bauten Edward U. Condon, Willard A. Derr und Gerald L. Tawney bei Westinghouse den „Nimatron“, eine elektromechanische Maschine, die Nim spielte. Sie wurde 1940 auf der Weltausstellung in New York ausgestellt, wo sie etwa 90 % der 100.000 gegen sie gespielten Partien gewann und damit zu einer der frühesten spielenden Maschinen wurde. Im Jahr 1951 wurde der Computer „Nimrod“ speziell zum Spielen von Nim gebaut und auf dem Festival of Britain ausgestellt; er wurde damit zu einem der frühesten Beispiele für digitale Spielcomputer.

Die mathematische Theorie von Nim, insbesondere der Sprague-Grundy-Satz (entwickelt von Roland Sprague im Jahr 1935 und Patrick Grundy im Jahr 1939), wurde zur Grundlage der kombinatorischen Spieltheorie. Der Satz besagt, dass jedes unparteiische Spiel (bei dem beiden Spielern dieselben Züge zur Verfügung stehen) einer Nim-Position entspricht. Das bedeutet, dass die Strategie für Nim theoretisch auf jedes unparteiische Spiel angewendet werden kann. Nim ist nach wie vor ein Standardthema in der Mathematik- und Informatikausbildung und wird häufig verwendet, um Schülern die Spieltheorie und die binäre Arithmetik näherzubringen.