Spielregeln

Beim Domineering legen zwei Spieler abwechselnd Dominosteine auf ein schachbrettartiges Spielfeld, wobei ein Stein genau zwei Felder abdeckt, die beim Setzen beide noch frei sein müssen. Wie in der kombinatorischen Spieltheorie allgemein üblich, werden die beiden Spieler als Links und Rechts bezeichnet. Der linke Spieler legt die in den folgenden Abbildungen blau dargestellten Dominosteine immer vertikal und der rechte Spieler seine rot dargestellten Steine immer horizontal auf das Brett. Wie bei allen Spielen der kombinatorischen Spieltheorie verliert derjenige Spieler das Spiel, der nicht mehr ziehen kann.

Will man eine Position analysieren, kommt es offensichtlich nur auf die Menge der noch freien Felder an, aber nicht, in welcher Weise die bereits belegten Felder bedeckt wurden.

Beispielpartie

Eine Partie auf einem 3×3-Brett könnte z. B. so verlaufen, wie es die nachfolgende Abbildung zeigt: Links eröffnet durch Setzen des mit „1“ gekennzeichneten Steins. Rechts legt darauf den mit „2“ gekennzeichneten Stein, worauf Links durch Setzen des mit „3“ markierten Steins die Partie für sich entscheidet, weil Rechts dann keinen Platz mehr hat für einen horizontal zu setzenden, roten Stein.

Zur beispielhaft angeführten Partie bleibt noch anzumerken, dass Links in der mit dem dritten Zug erreichten Endposition sogar noch eine Zugmöglichkeit gehabt hätte. Außerdem kann die Menge der freien Felder, die alle weiteren Zugmöglichkeiten bestimmt, in Komponenten zerlegt werden, sofern diese Komponenten nicht über Seitenrändern von Feldern zusammenhängen. Zum Beispiel könnte bei der Endposition die Zerlegung

vorgenommen werden. Diese Möglichkeit der Zerlegung einer Position bzw. der umgekehrte Vorgang eines Nebeneinanderlegens von Positionen ist eine ganz wesentliche Eigenschaft kombinatorischer Spiele (siehe Summe von Spielen).

Allgemeine Schreibweise

Bei der Schreibweise hat sich die Notation von z. B. ${\displaystyle \{L_{1},L_{2}\,|R_{1}\}}$ für das Paar ${\displaystyle (\{L_{1},L_{2}\},\{R_{1}\})}$ eingebürgert, wenn der Spieler Links die beiden Zugmöglichkeiten nach ${\displaystyle L_{1},L_{2}}$ und Rechts nur die Zugmöglichkeit nach ${\displaystyle R_{1}}$ besitzt:

A B C D

${\displaystyle ={\Bigg \{}}$

C D

${\displaystyle ,}$

A D

${\displaystyle {\Bigg |}}$

A B

${\displaystyle {\Bigg \}}}$

Ausgehend von dieser Schreibweise und der jeweiligen Identifikation einer Position mit dem Spiel, das von dieser Position startet, gelangt man zur folgenden Definition.

Definition eines Spiels

Ein Spiel (im Sinne von Spielposition, engl. game) ist über folgende selbstreferentielle Konstruktion definiert:

Konstruktionsregel

Sind ${\displaystyle {\mathcal {L}}}$ und ${\displaystyle {\mathcal {R}}}$ zwei Mengen von Spielen, dann ist ${\displaystyle \{{\mathcal {L}}|{\mathcal {R}}\}}$ ein Spiel.

Die Mengen ${\displaystyle {\mathcal {L}}=\{L_{1},L_{2},...\}}$ und ${\displaystyle {\mathcal {R}}=\{R_{1},R_{2},...\}}$ werden auch die linken bzw. rechten Optionen des Spiels genannt und repräsentieren die Spielpositionen, die der linke bzw. rechte Spieler mit einem Zug aus der aktuellen Spielposition heraus erreichen kann.

Wie bereits für das Eingangsbeispiel erläutert, werden zur Verkürzung der Notation in der Regel die Optionen direkt aufgelistet und die Mengenklammern weggelassen:

${\displaystyle \{{\mathcal {L}}|{\mathcal {R}}\}=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$

Elementare Spiele

Das Fundament dieser rekursiven Definition bildet das Spiel 0, bei dem keiner der beiden Spieler mehr ziehen kann (die Menge der linken und rechten Optionen ist leer). Die entsprechende Position im Domineering ist das 1x1-„Brett“.

In einem nächsten Schritt lassen sich nun weitere Spiele finden:

A B		A B		A B C
${\displaystyle 1:=\{0|\}}$		${\displaystyle -1:=\{|0\}}$		${\displaystyle *:=\{0|0\}}$

Gewinnklassen

In Bezug auf die mit guten Strategien sicher erzielbaren Gewinnaussichten gehört jede Position zu genau einer der folgenden vier Klassen:

• Links kann bei optimaler Spielweise gewinnen, unabhängig davon, wer beginnt (Positiv)
• Rechts kann das Spiel gewinnen, unabhängig davon, wer beginnt (Negativ)
• Der den ersten Zug ausführende Spieler besitzt eine Gewinnstrategie (Fuzzy)
• Der nachziehende Spieler besitzt eine Gewinnstrategie (Null)

Die bereits definierten elementaren Spiele können wie folgt klassifiziert werden: 1 ist positiv, −1 ist negativ, 0 ein Null-Spiel und * ist fuzzy.

Viele der untersuchten Spiele zerfallen im Laufe der Partie in unabhängige Einzelkomponenten (Endspiele im Go, Reihen beim Nim). Diese Teil-Spiele sind oft einfach genug, um vollständig analysiert zu werden. Daher ist eine zentrale Fragestellung der kombinatorischen Spieltheorie, wie sich die Gewinnaussichten des Gesamtspiels aus den Informationen zu den Teil-Spielen ableiten lassen. Die Temperaturtheorie liefert einen Algorithmus, mit dem man annähernd optimal spielen kann. Die maximale Abweichung von der theoretisch besten Strategie lässt sich dabei eingrenzen.

In einigen Fällen kann man bereits aus den Gewinnklassen Schlüsse ziehen:

• Sind die beiden Komponenten eines Spiels positiv, so ist das gesamte Spiel positiv. Gleiches gilt für negative Spiele.
• Null-Spiele haben die Eigenschaft, dass sie als Komponente keinen Einfluss auf den Ausgang des Spiels haben und die Gewinnklasse unverändert lassen. Zwei Spiele, die sich nur um ein Null-Spiel unterscheiden, werden daher als gleichwertig betrachtet.

Summe von Spielen

Die Summe zweier Spiele ist ein zentrales Konzept der kombinatorischen Spieltheorie, mit dem das vom Nim bekannte Nebeneinanderlegen von Positionen formalisiert und verallgemeinert wird: Eine Nim-Position besteht aus mehreren Haufen von Spielsteinen, und bei jedem Zug wird genau ein Haufen ausgewählt, wo der aktuelle Zug durchgeführt wird. Dabei hängen die Zugmöglichkeiten nur vom ausgewählten Haufen ab. Außerdem lässt jeder Zug die nicht ausgewählten Haufen unverändert.

Analog kann man zwei Spiele dadurch miteinander addieren, dass man sie nebeneinanderlegt und die Zugmöglichkeiten derart definiert, dass der ziehende Spieler einen der beiden Summanden auswählen muss, um dann dort einen zulässigen Zug auszuführen. Insbesondere besitzt ein Spieler, der in keinem der Summanden ziehen kann, keine Zugmöglichkeit mehr, so dass er verloren hat.

Formal ist die Summe der Spiele ${\displaystyle G=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$ und ${\displaystyle {\widehat {G}}=\{{\widehat {L}}_{1},{\widehat {L}}_{2},...|{\widehat {R}}_{1},{\widehat {R}}_{2},...\}}$ rekursiv definiert als

${\displaystyle G+{\widehat {G}}:=\{L_{1}+{\widehat {G}},L_{2}+{\widehat {G}},...,G+{\widehat {L}}_{1},G+{\widehat {L}}_{2},...|R_{1}+{\widehat {G}},R_{2}+{\widehat {G}},...,G+{\widehat {R}}_{1},G+{\widehat {R}}_{2},...\}}$

Vergleich zweier Spiele

Um zwei Spiele G und H miteinander vergleichen zu können, bestimmt man die Gewinnklasse des Differenzspiels ${\displaystyle G-H=G+(-H)}$. Das Inverse ${\displaystyle -H}$ entspricht dabei einer Vertauschung der Rollen von Links und Rechts. Im Domineering kann dies durch ein Drehen des Brettes um 90 Grad erreicht werden. Formal ist

${\displaystyle -\{L_{1},L_{2},...|R_{1},R_{2},...\}:=\{-R_{1},-R_{2},...|-L_{1},-L_{2},...\}}$

Auch diese Definition ist rekursiv.

Ist das Differenzspiel ${\displaystyle G_{1}-G_{2}}$ zweier Spiele ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ ein Null-Spiel, so hat für jedes Spiel ${\displaystyle H}$ die Summe ${\displaystyle G_{1}+H}$ dieselbe Gewinnklasse wie die Summe ${\displaystyle G_{2}+H}$. Daher werden ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ als äquivalent angesehen. Unter Identifikation von Äquivalenzklasse und Vertreter schreibt man:

${\displaystyle G_{1}=G_{2}}$, falls ${\displaystyle G_{1}-G_{2}}$ ein Null-Spiel ist.

Weiterhin wird definiert:

${\displaystyle G>H}$, falls ${\displaystyle G-H}$ positiv ist.

${\displaystyle G<H}$, falls ${\displaystyle G-H}$ negativ ist.

${\displaystyle G\parallel H}$, falls ${\displaystyle G-H}$ fuzzy ist.

sowie

${\displaystyle G\geq H}$, falls ${\displaystyle G>H}$ oder ${\displaystyle G=H}$

${\displaystyle G\leq H}$, falls ${\displaystyle G<H}$ oder ${\displaystyle G=H}$

Entsprechend dieser Symbolik ist ein „größeres“ Spiel immer vorteilhaft für den linken Spieler.

Alternativ lassen sich die Ordnungsrelationen auch etwas formeller einführen, ohne Bezugnahme auf das nicht im Detail ausgeführte Konzept der optimalen Spielweise.

Mit diesen Operatoren und Relationen erfüllen die Spiele (modulo Äquivalenz) die Eigenschaften einer kommutative Gruppe mit partieller Ordnung. Die Gesamtheit aller Spiele kann als echte Klasse jedoch genau genommen keine Gruppe sein, da die Definition einer Gruppe sich nur auf Mengen erstreckt. Wesentliche Beziehungen, welche sich im Fall von Mengen aus der Gruppeneigenschaft ableiten lassen, sind allerdings auch auf Klassen übertragbar.

Vereinfachung von Spielen und Normalform

Ein Spiel kann mit den folgenden zwei Regeln vereinfacht werden, ohne dass sich dabei der Wert des Spiels ändert (d. h. ohne die Äquivalenzklasse zu verlassen).

Dominierte Optionen

Sind in dem Spiel ${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ zwei linke Optionen vergleichbar, z. B. ${\displaystyle L_{1}\leq L_{2}}$, so ist ${\displaystyle L_{1}}$ eine durch ${\displaystyle L_{2}}$ dominierte Option. Entsprechend ist eine rechte Option ${\displaystyle R_{1}}$ durch ${\displaystyle R_{2}}$ dominiert, falls ${\displaystyle R_{1}\geq R_{2}}$.

Dominierte Optionen können weggelassen werden, ohne den Wert eines Spiels zu verändern:

${\displaystyle L_{1}\leq L_{2}\Rightarrow \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$

${\displaystyle R_{1}\geq R_{2}\Rightarrow \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{1},L_{2},L_{3},...|R_{2},R_{3},...\}}$

Anschaulich gesehen entspricht dies einer Spielsituation, in der ein Spieler eine Zugmöglichkeit hat, die eindeutig schlechter als ein alternativer Zug ist. Der Spieler wird unter keinen Umständen den schlechteren Zug wählen – somit spielt es für den Ausgang der Partie keine Rolle, ob der schlechte Zug überhaupt existiert oder nicht.

Umkehrbare Züge

In einem Spiel ${\displaystyle G=\{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ wird der Zug des rechten Spielers nach ${\displaystyle R_{1}}$ umkehrbar genannt, falls eine linke Option ${\displaystyle R_{1}^{L}}$ von ${\displaystyle R_{1}}$ existiert mit ${\displaystyle R_{1}^{L}\geq G}$. D.h. ${\displaystyle R_{1}^{L}}$ ist für Links mindestens so gut wie die ursprüngliche Position. (Entsprechend ist ein Zug des linken Spielers nach ${\displaystyle L_{1}}$ umkehrbar, falls eine rechte Option ${\displaystyle L_{1}^{R}}$ von ${\displaystyle L_{1}}$ existiert mit ${\displaystyle L_{1}^{R}\leq G}$.)

Für einen umkehrbaren Zug ändert sich der Wert des Spieles ${\displaystyle G}$ nicht, wenn man annimmt, dass der Zug stets unmittelbar vom Gegenspieler beantwortet wird:

Ist in dem Spiel ${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$ die rechte Option ${\displaystyle R_{1}}$ über ${\displaystyle R_{1}^{L}=\{...|K_{1},K_{2},...\}}$ umkehrbar, so gilt

${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{L_{1},L_{2},L_{3},...|K_{1},K_{2},...,R_{2},R_{3},...\}}$.

Ist die linke Option ${\displaystyle L_{1}}$ über ${\displaystyle L_{1}^{R}=\{K_{1},K_{2},...|...\}}$ umkehrbar, so gilt

${\displaystyle \{L_{1},L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}=\{K_{1},K_{2},...,L_{2},L_{3},...|R_{1},R_{2},R_{3},...\}}$.

Umkehrbare Spielzüge können durchaus sinnvoll sein. Der Spieler sollte nach der Umkehrung allerdings in dieser Teilposition weiterspielen, andernfalls wäre der Abtausch ein reiner Verlust.

Für endliche Spiele (solche, die insgesamt endlich viele Positionen enthalten) führt eine wiederholte Anwendung dieser zwei Regeln zur Normalform des Spiels, welche für jede Äquivalenzklasse eindeutig ist.

Im allgemeinen Fall lässt sich zumindest folgende Aussage machen: Haben zwei Spiele ${\displaystyle G}$ und ${\displaystyle H}$ weder dominierte Optionen, noch umkehrbare Züge, so folgt aus ${\displaystyle G=H}$, dass ${\displaystyle G}$ und ${\displaystyle H}$ gleiche linke und rechte Optionen haben. D.h. für jede linke / rechte Option ${\displaystyle A}$ von ${\displaystyle G}$ gibt es eine linke / rechte Option ${\displaystyle B}$ von ${\displaystyle H}$ mit ${\displaystyle A=B}$.

Beispiele für Spiele höherer Stufe

Mit vier Feldern lassen sich im Domineering Spiele der nächsten Stufe bilden:

A B C D

${\displaystyle ={\Bigg \{}}$

A D

${\displaystyle ,}$

C D

${\displaystyle {\Bigg |}\;{\Bigg \}}={\Bigg \{}}$

A

${\displaystyle +}$

D

${\displaystyle ,}$

C D

${\displaystyle {\Bigg |}\;{\Bigg \}}=\{0+0,1|\}=\{0,1|\}=\{1|\}}$

(Die letzte Vereinfachung kann erfolgen, da ${\displaystyle 0\leq 1}$ und ${\displaystyle 0}$ damit eine dominierte Option ist.)

Andererseits ist auch

${\displaystyle 1+1=\{0|\}+\{0|\}=\{0+1,1+0|\}=\{1|\}}$

Man definiert

${\displaystyle 2:=\{1|\}}$

${\displaystyle 3:=\{2|\}}$

${\displaystyle 4:=\{3|\}}$, usw.

d. h.

${\displaystyle -2=\{|{-1}\}}$

${\displaystyle -3=\{|{-2}\}}$, usw.

Die Spiele ${\displaystyle ...,-2,-1,0,1,2,...}$ lassen sich als eine Art Punktestand deuten: Der linke bzw. rechte Spieler hat nicht nur gewonnen, sondern könnte sogar noch eine gewisse Zahl weiterer Züge machen. Neben den ganzzahligen Spielen, gibt es auch solche, die als Punktestand ${\textstyle {\frac {1}{2}}}$ interpretiert werden können:

A B C D

${\displaystyle ={\Bigg \{}}$

C D

${\displaystyle ,}$

A D

${\displaystyle {\Bigg |}}$

A B

${\displaystyle {\Bigg \}}={\Bigg \{}}$

C D

${\displaystyle ,}$

A

${\displaystyle +}$

D

${\displaystyle {\Bigg |}}$

A B

${\displaystyle {\Bigg \}}=\{-1,0|1\}=\{0|1\}}$

Man definiert

${\displaystyle \textstyle {\frac {1}{2}}:=\{0|1\}}$.

Diese Zuordnung ist durch die folgenden Eigenschaften motiviert:

${\displaystyle 0<\textstyle {\frac {1}{2}}<1}$

${\displaystyle \textstyle {\frac {1}{2}}+\textstyle {\frac {1}{2}}=1}$,

wobei sich die zweite Beziehung wie folgt nachrechnen lässt:

${\displaystyle \textstyle {\frac {1}{2}}-1=\{0|1\}+\{|0\}=\{-1|1-1,\textstyle {\frac {1}{2}}\}=\{-1|0,\textstyle {\frac {1}{2}}\}=\{-1|0\}=-\textstyle {\frac {1}{2}}}$.

Des Weiteren gibt es aber auch Spiele, die sich nicht wie ein ausgespielter Punktestand verhalten. Sie sind „heiß“, in dem Sinne, dass jeder Spieler seine Situation verbessern kann, indem er in der entsprechenden Stellung zieht:

A B C D

${\displaystyle ={\Bigg \{}}$

C D

${\displaystyle {\Bigg |}}$

A D

${\displaystyle {\Bigg \}}={\Bigg \{}}$

C D

${\displaystyle {\Bigg |}}$

A

${\displaystyle +}$

D

${\displaystyle {\Bigg \}}=\{1|0\}}$

Im Mittel hat ${\displaystyle \{1|0\}}$ denselben Wert wie ${\displaystyle \textstyle {\frac {1}{2}}}$:

${\displaystyle \{1|0\}+\{1|0\}=1}$

Im Unterschied zu ${\displaystyle \textstyle {\frac {1}{2}}}$ lässt sich ${\displaystyle \{1|0\}}$ jedoch nicht präzise einordnen, sondern ist fuzzy gegenüber Werten im abgesteckten Intervall:

${\displaystyle \{1|0\}>-1,\quad \{1|0\}\parallel 0,\quad \{1|0\}\parallel \textstyle {\frac {1}{2}},\quad \quad \{1|0\}\parallel 1,\quad \{1|0\}<2}$

Auf dem Zahlenstrahl lässt sich ${\displaystyle \{1|0\}}$ daher nur unbestimmt in dem Bereich von 0 bis 1 verorten.

Surreale Zahlen

Unter den Spielen gibt es solche, welche mit reellen Zahlen identifiziert werden können, da sie derselben Arithmetik folgen. Genauer lassen sie sich die als surreale Zahlen bezeichneten Spiele wie folgt charakterisieren:

Eine surreale Zahl ${\displaystyle n=\{l_{1},l_{2},...|r_{1},r_{2},...\}}$ ist ein Spiel, bei dem

• alle linken und rechten Optionen surreale Zahlen sind
• ${\displaystyle l_{i}<r_{j}}$ gilt, für jede linke Option ${\displaystyle l_{i}}$ und rechte Option ${\displaystyle r_{j}}$.

Im Kontext der kombinatorischen Spieltheorie werden surreale Zahlen auch kurz als Zahl (engl. number) bezeichnet. Von den bereits definierten Spielen sind ${\displaystyle ...,-2,-1,0,1,2,...}$ und ${\displaystyle \textstyle {\frac {1}{2}}}$ Zahlen, nicht jedoch ${\displaystyle *}$ und ${\displaystyle \{1|0\}}$.

Zahlen zeichnen sich dadurch aus, dass sie total geordnet sind, d. h. für zwei Zahlen ${\displaystyle x}$ und ${\displaystyle y}$ gilt entweder ${\displaystyle x<y}$, ${\displaystyle x>y}$ oder ${\displaystyle x=y}$. Surreale Zahlen sind eine reichhaltige Klasse mit den Eigenschaften eines geordneten Körpers, welche nicht nur die ganzen, rationalen und reellen Zahlen enthält, sondern auch infinitesimale und infinite Vertreter hat. Genaueres dazu im Hauptartikel zu surrealen Zahlen.

Als Komponente in einer Spiel-Summe lassen sich Zahlen nach folgendem Satz sehr einfach Spiel-strategisch einordnen:

Zahl-Vermeidungs-Satz

Ist ${\displaystyle n}$ eine surreale Zahl und ${\displaystyle G}$ ein Spiel, aber keine surreale Zahl, so ist es im Summenspiel ${\displaystyle n+G}$ immer von Vorteil, im Spiel ${\displaystyle G}$ zu ziehen, sofern dies möglich ist.

D.h. in einem Spiel aus mehreren Komponenten ziehen die Spieler nur so lange in einer Komponente, bis eine Zahl (praktisch ein endgültiger Punktestand) erreicht ist. Am Ende wird abgerechnet, indem die verbleibenden Zahlen summiert werden: Ist die Summe positiv, so gewinnt Links, ist sie negativ gewinnt Rechts, ist sie 0, so gewinnt der nachziehende Spieler.

Eine unmittelbare Konsequenz des Satzes ist folgende Rechenregel:

Translationsprinzip

Ist ${\displaystyle n}$ eine Zahl und ${\displaystyle G=\{L_{1},L_{2},...|R_{1},R_{2},...\}}$ keine Zahl, so gilt

${\displaystyle \{L_{1},L_{2},...|R_{1},R_{2},...\}+n=\{L_{1}+n,L_{2}+n,...|R_{1}+n,R_{2}+n,...\}}$.

Hier wird vorausgesetzt, dass ${\displaystyle G}$ mindestens eine linke bzw. rechte Option besitzt. Dann folgt die Identität, da die restlichen Optionen der Summe nach dem Zahl-Vermeidungs-Satz dominiert sind.

Nim

Das bekannteste neutrale Spiel ist Nim. Gespielt wird es mit mehreren Haufen von Spielsteinen. In einem Zug müssen von genau einem Haufen beliebig viele Steine, mindestens aber ein Stein, entfernt werden.

Im Sinne der Kombinatorischen Spieltheorie entspricht jeder Nim-Position eine Summe von Spielen, die jeweils mit einem Haufen beginnen: Bezeichnet man, wie in der Kombinatorischen Spieltheorie üblich, mit ${\displaystyle *n}$ das Spiel, das mit einem aus ${\displaystyle n}$ Steinen bestehenden Haufen beginnt, dann entspricht die Nim-Position, die aus den Haufen der Größen ${\displaystyle n_{1},\dots ,n_{k}}$ besteht, dem Spiel ${\displaystyle *n_{1}+\dots +*n_{k}}$.

Bereits 1901 veröffentlichte Charles Leonard Bouton eine Gewinnstrategie für Nim, die auf einer expliziten Formel beruht, bei der die binär dargestellten Haufengrößen zu addieren sind. Dabei sollte man, sofern möglich, so ziehen, dass nach dem Zug die XOR-„Summe“ der binär dargestellten Haufengrößen gleich 0 ist. Zum Beispiel ist ein Zug zur Position, die aus den drei Haufen ${\displaystyle 5,4,1}$ besteht, ein Gewinnzug, weil die XOR-Summe dieser drei Haufengrößen gleich 0 ist: ${\displaystyle 5+_{2}4+_{2}1=0}$, wobei das Symbol ${\displaystyle +_{2}}$ die XOR-Operation bezeichnet, die man auch als übertragslose Binäraddition auffassen kann.

Im Sinne der Äquivalenz von kombinatorischen Spielen entspricht Boutons Gewinnformel der Eigenschaft ${\displaystyle *n+*m=*(n+_{2}m)}$. In Worten: Legt man zwei Haufen der Größen ${\displaystyle n}$ und ${\displaystyle m}$ zu einer neuen Position nebeneinander, dann ist die so entstehende Position äquivalent zu einer Position mit einem Haufen, der aus ${\displaystyle n+_{2}m}$ Steinen besteht. Das bedeutet: In jeder Position des Nim-Spiels und sogar in jeder Position eines kombinatorischen Spiels, in der die beiden Nim-Haufen mit ${\displaystyle n}$ und ${\displaystyle m}$ Steinen vorkommen, können die beiden Haufen durch einen einzigen Haufen mit ${\displaystyle n+_{2}m}$ Steinen ersetzt werden, ohne dass sich dadurch die Gewinnklasse, d. h. Null oder Fuzzy, ändert. Mit dieser Ersetzung wird die Komplexität einer Minimax-Analyse zum Finden eines optimalen Zuges entscheidend reduziert, da eine aus mehreren Haufen bestehende Nim-Position schrittweise auf einen einzigen Haufen reduziert werden kann:

${\displaystyle *n_{1}+\dots +*n_{k}=*(n_{1}+_{2}\dots +_{2}n_{k})}$

Völlig formal, d. h. ohne jeden Bezug auf die verbal beschriebenen Nim-Spielregeln, lassen sich die Spiele der Form ${\displaystyle *n}$ innerhalb der Kombinatorischen Spieltheorie wie folgt definieren, wobei man die für beide Spieler identischen Optionen zur Vereinfachung nur einmal notiert:

${\displaystyle *n=\{*(n-1),\dots ,*1,*0|*(n-1),\dots ,*1,*0\}=:\{*(n-1),\dots ,*1,*0\}}$

${\displaystyle *0=\{|\}=0}$

Im Englischen wird für diese Spiele das aus den Begriffen numbers und nim gebildete Wortspiel nimbers als Bezeichnung verwendet, zum Teil als Nim-Zahlen ins Deutsche übersetzt.

Nim-Varianten

Seit Bouton wurden viele Varianten des Nim vorgeschlagen, die wie Nim meist mit mehreren Haufen von Spielsteinen gespielt werden, für die aber die erlaubten Züge durch abweichende Spielregeln definiert werden. Die wohl älteste solche Variante wurde vom Schachweltmeister und Mathematiker Emanuel Lasker ersonnen und untersucht. Sie wird daher heute als Lasker-Nim bezeichnet. Bei diesem Spiel besteht ein Zug darin, entweder wie beim Standard-Nim beliebig viele Steinen von einem Haufen zu nehmen oder einen Haufen in zwei Haufen zu teilen, ohne dabei einen Stein zu entfernen.

Eine vollständige Analyse eines neutralen Spieles ist immer dadurch möglich, dass jeder Position eine äquivalente, aus nur einem Haufen bestehende Position des Standard-Nim zugeordnet wird. Diese Möglichkeit der Reduktion wurde unabhängig voneinander von 1935 von Roland Sprague und 1940 von Patrick Michael Grundy gefunden und wird daher auch als Satz von Sprague-Grundy bezeichnet. Ansätze der Reduktion hatte zuvor bereits der Schachweltmeister und Mathematiker Emanuel Lasker erörtert.

Die Größe des Nim-Haufens, die einer Position ${\displaystyle H}$ eines neutralen Spiels zugeordnet ist, wird auch als dessen Grundy-Zahl ${\displaystyle g(H)}$ bezeichnet. Es gilt dann im Sinne einer Äquivalenz kombinatorischer Spiele:

${\displaystyle H=*g(H)}$

Die Grundy-Zahl ${\displaystyle g(H)}$ eines neutralen Spiels ${\displaystyle H=\{H_{1},\dots ,H_{k}\}}$ kann relativ einfach rekursiv, d. h. aus den Grundy-Zahlen der in einem Zug erreichbaren Positionen ${\displaystyle H_{1},\dots ,H_{k}}$, berechnet werden: Sie ist gleich der kleinsten natürlichen Zahl, die nicht Grundy-Zahl einer Nachfolgeposition ist, weswegen man auch von mex für minimum excluded spricht:

${\displaystyle g(H)=min(\mathrm {N} -\{g(H_{1}),\dots ,g(H_{k})\})}$

Grundy-Zahlen besitzen die folgenden beiden Eigenschaften, die unmittelbar aus den entsprechenden Eigenschaften für das Standard-Nim hervorgehen:

• Der anziehende Spieler verfügt genau dann über eine Gewinnstrategie, wenn die Grundy-Zahl ungleich 0 ist.
• Die Grundy-Zahl einer Summe von Positionen ist gleich der XOR-Summe der Grundy-Zahlen der Summanden. Diese Eigenschaft reduziert maßgeblich die Komplexität der Analyse von Positionen, die aus mehreren Haufen zusammengesetzt sind.

Die beiden Eigenschaften erlauben es, für Nim-Varianten wie zum Beispiel das genannte Lasker-Nim einen Gewinnzug zu finden: Sucht man zum Beispiel für die Lasker-Nim-Position mit vier Haufen der Größen ${\displaystyle 1,3,5,8}$ einen Gewinnzug, dann kann man dazu die Standard-Nim-Position mit den vier Haufen der Größen ${\displaystyle g(1)=1,g(3)=4,g(5)=5,g(8)=7}$ analysieren, für die der Zug zur Standard-Nim-Position ${\displaystyle 1,3,5,7}$ ein Gewinnzug ist. Demgemäß sollte auch in der ursprünglichen Lasker-Nim-Position der zweite Haufen verändert werden, und zwar derart, dass eine Grundy-Zahl 3 entsteht. Möglich ist dies mit einer Teilung des zweiten Haufens, wodurch die Lasker-Nim-Position ${\displaystyle 1,{\underline {1,2}},5,8}$ erreicht wird.

Misère-Version des Nim

Bereits Bouton hatte auch die sogenannte Misère-Version des Standard-Nim gelöst, bei der abweichend von der üblichen Definition eines kombinatorischen Spiels der zuletzt ziehende Spieler verliert. Bouton fand, dass beim Standard-Nim die Fuzzy-Positionen, d. h. die dem Anziehenden eine Gewinnstrategie erlaubenden Positionen, zwischen Misère-Version und normaler Version weitgehend übereinstimmen. Die einzigen Ausnahmen sind die Positionen, die ausschließlich aus Haufen der Größe 1 bestehen. Bei ihnen kehrt sich das Gewinnverhalten um.

Misère-Versionen anderer Nim-Varianten

Für andere Nim-Varianten sind die Misère-Versionen zum Teil deutlich schwieriger zu lösen. Eine Möglichkeit ergibt sich dadurch, dass der der Äquivalenz-Begriff von Spielen weniger eng gefasst wird. In diesem Sinn gelten zwei Positionen ${\displaystyle G_{1}}$ und ${\displaystyle G_{2}}$ der Misère-Version einer Nim-Variante bereits dann als äquivalent, wenn für jede Position ${\displaystyle H}$ dieser Nim-Variante (aber nicht unbedingt für jedes kombinatorische Spiel ${\displaystyle H}$) die beiden Positionen ${\displaystyle G_{1}+H}$ und ${\displaystyle G_{2}+H}$ stets den gleichen Gewinntyp, Fuzzy oder Null, aufweisen.

Auf Basis dieses Äquivalenzbegriffs lässt sich zum Beispiel die Misère-Version des Kegel-Nims (engl. Kayles) lösen: Beim Kegel-Nim müssen pro Zug von einem Haufen ein oder zwei Steine genommen werden, wobei der derart verkleinerte Haufen anschließend optional noch geteilt werden darf. Das Spiel verdankt seinen Namen der Sichtweise, bei der man sich eine Position als eine Reihe nebeneinander stehender, Lücken aufweisender Kegel vorstellen kann, bei denen pro Zug ein oder zwei Kegel, innerhalb oder am Rand einer Gruppe, herausgekegelt werden. Dabei entspricht der Fall, bei dem Kegel innerhalb einer Gruppe von Kegeln getroffen werden, dem Teil der Spielregel, bei dem die zuvor verkleinerte Gruppe von Kegeln geteilt wird.

Beim Kegel-Nim gibt es 40 Positionen, so dass jede Kegel-Nim-Position unter den Misère-Regeln äquivalent zu genau einer dieser Positionen ist. Daher kann die Analyse des Misère-Kegel-Nims darauf reduziert werden, für eine gegebene Position die zugehörige Äquivalenzklasse in Form einer äquivalenten Position unter diesen 40 Repräsentanten zu finden. Dies geschieht in zwei Schritten:

• Zunächst wird beschrieben, wie die Äquivalenzklassen addiert werden. Eine, wenn auch wenig elegante, Beschreibung erfolgt in Form einer 40×40-Tabelle. Diese Additionstabelle definiert für die Menge der Misère-Kegel-Nim-Äquivalenzklassen die Struktur einer abelschen Halbgruppe.
• Außerdem muss für jede Position, die aus einem einzelnen Haufen besteht, die zugehörige Äquivalenzklasse bekannt sein. Beim Misère-Kegel-Nim ist für Ein-Haufen-Positionen die Zuordnung zu einer Äquivalenzklasse ab einer Haufengröße von 71 periodisch mit einer Periodenlänge von 12.

Erstmals gelöst, wenn auch auf einem anderen Weg, wurde die Misère-Version des Kegel-Nim im Jahr 1973. Eine Veröffentlichung erfolgte aber erst 1992. In Analogie zur Lösung der Misère-Version des Standard-Nims wurden die Kegel-Nim-Positionen charakterisiert, bei denen sich bei der Misère-Version ein anderer Gewinntyp ergibt als beim Kegel-Nim mit normaler Regel.