imported>Jeany-Janine: /* growthexperiments-addlink-summary-summary:1|0|0 */

2025-06-02T19:13:59Z

growthexperiments-addlink-summary-summary:1|0|0

Neue Seite

{{Anker|marienbad}}[[Datei:NimGame.svg|285px|mini|Ausgangsstellung<br />des Spiels aus dem Film ''[[Letztes Jahr in Marienbad]]'']]
Das '''Nim-Spiel''' ist ein Spiel für zwei Personen, bei dem abwechselnd eine Anzahl von Gegenständen, etwa [[Streichhölzer wegnehmen|Streichhölzer]], weggenommen werden. Gewonnen hat beim Standardspiel derjenige, der das letzte Hölzchen nimmt, bei der Misère-Variante verliert dagegen derjenige, der das letzte Hölzchen nehmen muss.

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

Spieltheoretisch interessant ist die in diesem Artikel beschriebene Spielart, bei der mehrere Reihen (in der Literatur auch: Haufen oder Zeilen) von Hölzchen vorgegeben werden. Zwei Spieler nehmen abwechselnd eins oder mehrere Hölzchen aus einer der Reihen weg. Wie viele sie nehmen, spielt keine Rolle; es dürfen bei einem Zug jedoch nur Hölzchen aus einer einzigen Reihe genommen werden.

Die Nim-Spiel-Varianten werden unter die [[Spiel mit perfekter Information|Spiele mit perfekter Information]] für zwei Spieler ohne Unentschieden eingeordnet. Nim ist ein ''neutrales'' Spiel (englisch: impartial game), weil die Zugmöglichkeiten in einer Position unabhängig davon sind, welcher Spieler zieht. Für das mehrreihige Nim-Spiel hat [[Charles Leonard Bouton]] 1901 eine Formel für ''die'' [[Gewinnstrategie]] gefunden.<ref> C. L. Bouton: ''Nim, a game with a complete mathematical theory.'' In: ''Annals of Mathematics.'' (2) 3 (1901), S. 35–39, [[doi:10.2307/1967631]] ([https://zbmath.org/32.0225.02 Abstract in zbMATH])</ref>

In der [[#Grundy|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 [[Kombinatorische Spieltheorie|Kombinatorischen Spieltheorie]].

== Gewinnstrategie nach Bouton ==

Für alle diese Spiele, Standard-Nim, Misère-Nim und viele andere Spiele, ist bei jedem Spielstand klar und meist leicht berechenbar, ob der Spieler am Zug den Sieg erzwingen kann und auf welche Weise. Und wenn der Anziehende den Sieg nicht erzwingen kann, dann kann ihn der Nachziehende (nach jedem beliebigen Zug des Anziehenden) erzwingen. Für Standard-Nim und Misère-Nim gilt die folgende Gewinnstrategie:

Man stellt die Anzahlen der Hölzchen in den Reihen [[Dualsystem|dual]] dar und errechnet daraus pro Dualstelle die Spaltensummen.

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 [[#MisèreEndspiel|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.

Diese Prüfung auf Geradzahligkeit der Spaltensummen entspricht der [[Bitweiser Operator#XOR|bitweisen exklusiv-ODER-Summe]] (»XOR-Summe«) der Dualdarstellungen. Für diese bitweise exklusiv-ODER-Summe findet sich häufig, so auch in diesem Artikel, die mathematische Notation <math>\textstyle\oplus</math> bei paarigen Operanden und <math>\textstyle\bigoplus</math> bei der Verwendung mit [[Indexmenge (Mathematik)|Laufvariablen]].

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

== Die Strategie anhand eines Beispiels ==
Als Beispiel diene die folgende Stellung mit <math>n = 5 </math> Reihen enthaltend die Anzahlen <math>a_i </math> von 1, 2, 3, 4 und 7 Hölzchen mit den '''Dualdarstellungen''' <math>b_i </math> (wobei in der Tabelle rechts vom ≙-Zeichen die Hölzchen den Dualstellen entsprechend gruppiert sind):<br />
{|
|-
|style="width:11.6em"| ||style="width:2.8em"| || <math>\mathtt{4\,|\;\!2\,|\;\!1} </math> ||style="width:3.1em;text-align:right"| <math>\mathtt{4} </math> ||style="width:.7em;text-align:left"| <math>\mathtt{2} </math> || <math>\mathtt{1} </math>
|}
{|style="border-spacing: 2px; border: 1px solid darkgray;"
|-
|<math>a_1 = 1 \;\; \implies </math> ||style="text-align:right"| <math>b_1 = </math> || <math>\mathtt{0\,|\;\!0\,|\;\!1} </math> ||   ≙   || || ||style="text-align:right"| |
|-
|<math>a_2 = 2 \;\; \implies </math> ||style="text-align:right"| <math>b_2 = </math> || <math>\mathtt{0\,|\;\!1\,|\;\!0} </math> ||   ≙   || ||style="text-align:right"| ||
|-
|<math>a_3 = 3 \;\; \implies </math> ||style="text-align:right"| <math>b_3 = </math> || <math>\mathtt{0\,|\;\!1\,|\;\!1} </math> ||   ≙   || ||style="text-align:right"| || ||style="text-align:right"| |
|-
|<math>a_4 = 4 \;\; \implies </math> ||style="text-align:right"| <math>b_4 = </math> || <math>\mathtt{1\,|\;\!0\,|\;\!0} </math> ||   ≙   ||style="text-align:right"| ||||
|-
|style="width:11.6em"| <math>a_5 = 7 \;\; \implies </math> ||style="width:2.8em;text-align:right"| <math>b_5 = </math> || <math>\mathtt{1\,|\;\!1\,|\;\!1} </math> ||   ≙   ||style="width:1.2em;text-align:right"| |||| ||style="width:.5em;text-align:right"| || ||style="width:.35em;text-align:right"| |
|}
{|
|-
| ||style="text-align:right"| <math>\textstyle\sum_{i=1}^n b_i = </math> || <math>\mathtt{2\,|\;\!3\,|\;\!3}</math>
|-
|style="width:1.6em"| ||style="width:12.8em;text-align:right"| <math>\textstyle\bigoplus_{i=1}^n b_i =</math> || <math>\mathtt{0\,|\;\!1\,|\;\!1} </math> ||   ≙   ||style="width:1.2em"| ||style="width:.5em;text-align:right"| || ||style="width:.45em;text-align:right"| | ||<ref name="summen">Die beiden Summenzeichen bilden die spaltenweisen Summen über die [[Bitvektor]]en <math>b_i</math>, und zwar <math>\textstyle\sum</math> die übliche Summe in <math>\N_0^{\,d} = \ldots \N_0 \mathtt{|} \N_0 \mathtt{|} \N_0</math> und <math>\textstyle\bigoplus</math> diejenige in <math>\bigl(\Z/(2)\bigr)^d = \mathbb F_2^{\,d} = \ldots \mathbb F_2 \mathtt{|} \mathbb F_2 \mathtt{|} \mathbb F_2</math> mit <math>d</math> als der maximalen Anzahl der Dualstellen.</ref>
|}

Die Summe der Dualziffern ist in der {{nowrap|<math>\mathtt{4} </math>-er-Spalte}} gerade, aber in der {{nowrap|<math>\mathtt{2} </math>-er-}} und {{nowrap|<math>\mathtt{1} </math>-er-Spalte}} ungerade, nämlich jeweils 3. Die Stellung ist damit eine Gewinnstellung.<ref>Bouton entwickelte eine Nim-Addition. Sie folgt aus der [[Bitweiser Operator#XOR|bitweisen XOR-Summe]] der Dualdarstellungen (in diesem Artikel notiert als <math>\oplus</math>). (Vergleiche: Bewersdorff: Glück, Logik... 2010, S. 117.) Dort werden Dualzahlen spaltenweise zu einer dualen Summe ([[modulo]] 2 im [[Ring (Algebra)|Ring]] <math>\Z/(2) = \mathbb F_2</math>) addiert, also ohne irgendwelche [[Übertrag|Überträge]] zu einer Nachbarspalte. Diese Summe wird Nim-Summe genannt. Sie ist genau dann 0, wenn alle Spaltensummen gerade sind, und {{nowrap|≠ 0,}} wenn mindestens eine Spaltensumme ungerade ist.</ref>

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''':
{|
|-
|style="width:11.6em"| ||style="width:2.8em"| || <math>\mathtt{4\,|\;\!2\,|\;\!1} </math> ||style="width:3.1em;text-align:right"| <math>\mathtt{4} </math> ||style="width:.7em;text-align:left"| <math>\mathtt{2} </math> || <math>\mathtt{1} </math>
|}
{|style="border-spacing: 2px; border: 1px solid darkgray;"
|-
|<math>a_1 = 1 \;\; \implies </math> ||style="text-align:right"| <math>b_1 = </math> || <math>\mathtt{0\,|\;\!0\,|\;\!1} </math> ||   ≙   || || ||style="text-align:right"| |
|-
|<math>a_2 = 2 \;\; \implies </math> ||style="text-align:right"| <math>b_2 = </math> || <math>\mathtt{0\,|\;\!1\,|\;\!0} </math> ||   ≙   || ||style="text-align:right"| ||
|-
|<math>a_3 = 3 \;\; \implies </math> ||style="text-align:right"| <math>b_3 = </math> || <math>\mathtt{0\,|\;\!1\,|\;\!1} </math> ||   ≙   || ||style="text-align:right"| || ||style="text-align:right"| |
|-
|<math>a_4 = 4 \;\; \implies </math> ||style="text-align:right"| <math>b_4 = </math> || <math>\mathtt{1\,|\;\!0\,|\;\!0} </math> ||   ≙   ||style="text-align:right"| ||||
|-
|style="width:11.6em"| <math>a_5 = 7-3 = 4 \;\; \implies </math> ||style="width:2.8em;text-align:right"| <math>b_5 = </math> || <math>\mathtt{1\,|\;\!0\,|\;\!0} </math> ||   ≙   ||style="width:1.2em;text-align:right"| |||| ||style="width:.5em;text-align:right"| ||style="width:.35em;text-align:right"|
|}
{|
|-
| ||style="text-align:right"| <math>\textstyle\sum_{i=1}^n b_i =</math> || <math>\mathtt{2\,|\;\!2\,|\;\!2}</math>
|-
|style="width:1.6em"| ||style="width:12.8em;text-align:right"| <math>\textstyle\bigoplus_{i=1}^n b_i =</math> || <math>\mathtt{0\,|\;\!0\,|\;\!0} </math> ||   ≙   ||   (leer)<ref name="summen"/>
|}

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 {{nowrap|<math>\mathtt{2} </math>-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.<ref>Nach erfolgter Wahl der Reihe <math>k </math> ist der Rest des Zuges festgelegt. Ist nämlich <math>\textstyle s := \bigoplus_{i=1}^n b_i ,</math> dann ist der Bitvektor für die neue Anzahl der Hölzchen
: <math>\textstyle {b_k}^{\prime} := b_k \oplus s .</math>
An der höchstrangigen Dualstelle, an der er sich von <math>b_k </math> unterscheidet, hat er eine '0' anstelle einer '1', weil <math>s </math> dort eine '1' hat. Damit verkleinert sich der Zahlenwert, und der Zug ist regelkonform.</ref>

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 [[#MisèreEndspiel|Endspiel des Misère-Nim]].)

== Frühe Nim-Computer ==
[[Datei:Nimrod in Computerspielemuseum.jpg|mini|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 (Computer)|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 (Programmiersprache)|C-Familie]], in denen Zahlen des Typs [[Integer (Datentyp)|<code>unsigned int</code>]] ganz ohne Umwandlung des [[Datentypen in C|Datentyps]] auch als Bitvektoren aufgefasst werden können und die dazuhin die hier benötigten [[Bitweiser Operator|bitweisen Operationen]] unterstützen.

== {{Anker|MisèreEndspiel}}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 (Spiel)|Marienbad]], dessen Ausgangsstellung in der [[#marienbad|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 [[#Gewinnstrategie nach Bouton|Spaltensummen]] herauskäme.)

== Weitere Varianten ==
{{Hauptartikel|Nim-Spiel-Variation}}
Neben den hier genannten Spielregeln gibt es noch weitere Nim-Spiel-Varianten.<ref>Elwyn R. Berlekamp, John H. Conway, Richard K. Guy: ''Gewinnen – Strategien für mathematische Spiele'', Band 1.</ref>

Beim ''Lasker-Nim'' entfernt ein Spieler entweder Hölzchen aus einer Reihe oder zerteilt die Reihe in zwei nicht unbedingt gleich große Teile.<ref>Lösung in B. Kummer,''Spiele auf Graphen.'' Deutscher Verlag der Wissenschaften, Berlin 1979; Birkhäuser, Basel 1980 (ISNM Series, Vol 44), [[doi:10.1007/978-3-0348-5481-8]], S. 47, Aufgabe 1.</ref>

Manchmal wird die genannte [[Spielregel]] so eingeschränkt, dass man nur eine bestimmte Anzahl von Hölzchen einer Reihe nehmen darf. Beim ''Kegel-Nim''<ref>Bewersdorff: Glück, Logik 2010, S. 124.</ref> dürfen aus einer Reihe ein oder zwei Hölzchen genommen werden, wobei die Reihe dadurch auch geteilt werden darf.

''Schwarz-Weiß-Nim'' wird mit aus [[Dame (Spiel)|Dame]]-Steinen aufgebauten Türmen gespielt. Man wählt einen Stein der eigenen Farbe aus und entfernt ihn zusammen mit den darüberliegenden Steinen.

''Nimbi'' ist eine Nim-Variante mit zwölf Steinen auf zwölf Geraden nach der Misère-Regel. Es wurde von [[Piet Hein (Wissenschaftler)|Piet Hein]], einem Miterfinder des [[Hex (Spiel)|Hex-Spiels]], etwa 1950 erfunden. Die Anfangsposition ist eine Verlustposition.<ref>Bewersdorff: Glück, Logik 2010, S. 176.</ref>

== Literatur ==
* [[Roland Sprague|Roland P. Sprague]]: ''Über mathematische Kampfspiele.'' In: ''Tôhoku Mathematical Journal.'' Band 41 (1935), S. 438–444 ([https://www.jstage.jst.go.jp/article/tmj1911/41/0/41_0_438/_article Online-Version]).
{{Anker|Grundy}}
* [[Patrick Michael Grundy|Patrick M. Grundy]]: ''Mathematics and games.'' Eureka. 27 (1940), S. 9–11 ({{Webarchiv | url=http://www.archim.org.uk/eureka/27/games.html | wayback=20070927192024 | text=Online-Version}})
* [[Jörg Bewersdorff]]: ''Glück, Logik und Bluff: Mathematik im Spiel – Methoden, Ergebnisse und Grenzen.'' Vieweg+Teubner Verlag, 5. Auflage 2010, ISBN 3-8348-0775-3, [[doi:10.1007/978-3-8348-9696-4]].
* [[Elwyn R. Berlekamp]], [[John H. Conway]], [[Richard K. Guy]]: ''Gewinnen – Strategien für mathematische Spiele.'' 1985/86, 4 Bände, ISBN 3-528-08531-2, ISBN 3-528-08532-0, ISBN 3-528-08533-9, ISBN 3-528-08534-7 (engl. Original: ''Winning Ways for your Mathematical Plays.'', 2 Bände, ISBN 0-12-091101-9, ISBN 0-12-091102-7, Academic Press 1982, aktualisierte Neuauflagen 2001 bis 2004).
* [[Emanuel Lasker]]: ''Brettspiele der Völker.'' Berlin 1931, {{URN|nbn:at:at-ubms:3-1736}}.

== Weblinks ==
* [https://www.alraft.de/altenhein/spiele/nim-spiel/index.html Nim online spielen]

== Einzelnachweise ==
<references />

[[Kategorie:Strategiespiel]]
[[Kategorie:Spieltheorie]]
[[Kategorie:Gelöstes Spiel]]

[[cs:Rozšířená forma#NIM]]

Nim-Spiel - Versionsgeschichte

imported>Jeany-Janine: /* growthexperiments-addlink-summary-summary:1|0|0 */