MatchMath

Das Spiel heißt Misère-Nim; die Stellung 1-3-5-7 ist als Marienbad-Spiel bekannt (nach dem Film Letztes Jahr in Marienbad, 1961). Normales Nim wurde 1901 von Charles Bouton vollständig gelöst, die Misère-Variante gleich mit.

Die Nim-Summe

Schreibe die Zeilenlängen binär und verknüpfe sie mit XOR (Addition ohne Übertrag):

1 ⊕ 3 ⊕ 5 ⊕ 7 = 0

Eine Stellung mit Nim-Summe 0 ist eine Verluststellung für den Spieler am Zug: Jeder Zug zerstört die Null, und der Gegner kann sie immer wiederherstellen. Da die Startstellung bereits 0 ist, verliert der Anziehende bei perfektem Spiel — der Nachziehende gewinnt.

Die Strategie in zwei Regeln

1. Normalphase (mindestens eine Zeile hat ≥ 2 Hölzer): Ziehe so, dass die Nim-Summe danach 0 ist.
2. Endphase-Umschaltung: Sobald dein Zug eine Stellung erzeugen kann, in der nur noch Einer-Zeilen übrig sind, hinterlasse eine ungerade Anzahl davon (1, 3, 5 …). Dann muss der Gegner das letzte Holz nehmen.

Nur Regel 2 unterscheidet Misère von normalem Nim — und genau daran scheitern die meisten, die „nur die XOR-Regel“ kennen.

Als Anziehender trotzdem gewinnen?

Gegen perfektes Spiel: unmöglich, das ist bewiesen. Bleibt das Fallenstellen — einen Zug wählen, nach dem der Gegner möglichst wenige rettende Antworten hat. 12 der 16 Eröffnungszüge lassen genau eine korrekte Antwort offen:

Ausgerechnet der intuitive Zug „nimm das einzelne Holz in Zeile 1“ ist die schwächste Falle. Am fiesesten sind die drei „nimm 2“-Züge oben.

Im Normalspiel gewinnt, wer das letzte Holz nimmt. Bei 1-3-5-7 ändert das am Ausgang nichts: die Nim-Summe ist 0, also gewinnt auch hier der Nachziehende. Über den ganzen Stellungsraum unterscheiden sich die beiden Regeln in nur 16 von 384 Stellungen (4,2 %) — und ausnahmslos in der Endphase, in der jede Zeile höchstens ein Holz hat.

Die Strategie wird sogar einfacher: hinterlasse immer Nim-Summe 0, ohne jede Ausnahme. Die Endphasen-Umschaltung entfällt. Praktisch:

1. Bilde s = XOR aller Zeilen.
2. Suche eine Zeile mit r ⊕ s < r — die gibt es immer, wenn s ≠ 0.
3. Reduziere diese Zeile auf r ⊕ s.

Dahinter steht der Satz von Sprague–Grundy: Jede Stellung eines unparteiischen Normalspiels hat einen Grundy-Wert, und Summen von Spielen verrechnen sich per XOR. Eine Komponente mit Grundy-Wert g ist damit in jeder Umgebung durch einen Nim-Haufen der Größe g ersetzbar. Deshalb ist Nim das Modell für alle diese Spiele — und deshalb zeigt die Analyse oben im Normalspiel einen Grundy-Wert an.

Kayles ist nach dem alten Kegelspiel benannt (engl. kayles, von frz. quilles). Eine Reihe Hölzer steht nebeneinander; ein Zug nimmt eines oder zwei benachbarte — und zerlegt die Reihe dabei in zwei unabhängige Reihen. Zum Ziehen klickst du ein Holz an, oder die Lücke zwischen zwei benachbarten Hölzern.

Genau dieses Zerfallen macht Kayles interessant: aus einem Spiel wird laufend eine Summe von Spielen. Und Summen sind der Punkt, an dem Normal- und Misèrespiel auseinanderfallen.

Hier kippt der Regelwechsel also tatsächlich den Gewinner — anders als bei 1-3-5-7. Und eine einzelne Kayles-Reihe verliert der Anziehende im Misèrespiel bei den Längen 1, 4, 9, 12 und sonst bei keiner bis 18. Das sieht nach Quadratzahlen aus, bis die 12 kommt.

Warum es keine Formel gibt

Eine Kayles-Reihe der Länge 5 hat den Grundy-Wert 4 und ist im Normalspiel ein Nim-Haufen der Größe 4 — beweisbar in jeder Umgebung. Im Misèrespiel stimmt das nicht mehr: stellt man beiden eine einzelne Kayles-Reihe der Länge 1 zur Seite, verliert der Anziehende bei Kayles5, gewinnt aber bei Nim4. Damit fällt genau die Ersetzbarkeit weg, auf der Sprague–Grundy beruht: Man kann ein Spiel nicht mehr analysieren, indem man seine Teile analysiert.

Deshalb steht im Analysefeld bei Kayles im Misèrespiel kein Kennwert — es gibt keinen. Die Bewertung dort stammt aus der vollständig durchgerechneten Tabelle, nicht aus einer Regel. Für unbegrenzte Spielfamilien ist das der Grund, warum viele Misère-Varianten bis heute offen sind; Misère-Kayles selbst wurde erst in den 1990ern von Sibert und Conway gelöst.