Zwei Spiele, die zu Ende gedacht sind. Bei Nim sagt eine Formel aus einer Zeile, wer gewinnt — und sie lässt sich beweisen. Tic-Tac-Toe ist klein genug, um es vollständig durchzurechnen: alle Stellungen, alle Züge, ein Ergebnis.
- Nim zum Spielen — vier Reihen Hölzer, das Gegenüber spielt fehlerfrei
- Die Formel sichtbar — die Reihen binär untereinander, Spalte für Spalte; der gewinnende Zug ist auf Knopfdruck grün markiert
- Tic-Tac-Toe gegen ein Spiel, das alles weiß — mit der Bewertung jedes einzelnen Zuges daneben
- Was das Rechnen kostet — besuchte Stellungen mit und ohne Alpha-Beta, live gezählt
- Prüflauf — sieben Zeilen, darunter die Nim-Formel gegen eine erschöpfende Rückwärtsanalyse
Schreibe die Reihen binär untereinander und zähle jede Spalte. Ist jede Spalte gerade besetzt, verliert, wer am Zug ist. Das ist die Nim-Summe — das bitweise Entweder-oder aller Reihen:
3 0 1 1
5 1 0 1
7 1 1 1
4 1 0 0
─────────────
5 1 0 1 ungerade Spalten → die Stellung ist gewonnen
Der gewinnende Zug ergibt sich direkt daraus: Suche eine Reihe r mit r XOR s < r und verkleinere
sie auf genau diesen Wert. Dann ist die Nim-Summe null — und der Gegner steht vor derselben Lage
wie du eben, nur mit weniger Hölzern.
| Behauptung | Ergebnis |
|---|---|
| die Nim-Formel stimmt für jede Stellung | 4096 Stellungen (vier Reihen bis je sieben Hölzer) einzeln rückwärts durchgerechnet · 0 Abweichungen |
| aus jeder Gewinnstellung führt ein Zug hinaus | 300 Gewinnstellungen, für jede fand die Formel den Zug · 42 Verluststellungen, aus keiner führt einer zurück |
| Tic-Tac-Toe vollständig durchgezählt | 5478 erreichbare Stellungen · 255 168 Spielverläufe — 131 184 für X, 77 904 für O, 46 080 unentschieden |
| bei bestem Spiel steht es unentschieden | Wert der leeren Stellung null · alle neun Eröffnungen gleichwertig |
| Alpha-Beta liefert denselben Wert | 3610 Stellungen doppelt bewertet · 2 749 051 gegen 456 252 besuchte Stellungen — 83 % gespart, 0 Wertunterschiede |
| Drehen und Spiegeln ändert nichts | 8720 gedrehte und gespiegelte Bretter, 0 Abweichungen |
| das Spiel verliert nie | 681 Partien, in denen der Gegner jeden denkbaren Zug probiert · 0 Niederlagen |
Die Zahlen 5478 und 255 168 sind nicht aus der Literatur abgeschrieben, sondern hier gezählt — sie stehen im Blatt neben den bekannten Werten, damit die Übereinstimmung sichtbar ist und nicht bloß behauptet.
Ein Leerzeichen ist wahr. Das leere Brett war " " — neun Leerzeichen — und die
Siegprüfung fragte if (brett[a] && brett[a] === brett[b] && …). Ein Leerzeichen ist ein nicht
leerer String, also truthy: Das leere Brett meldete sofort „drei gleiche in der oberen Reihe"
und das Spiel war vorbei, bevor es anfing. Der Prüflauf hat es in derselben Sekunde aufgedeckt, in
der er zum ersten Mal lief: 1 erreichbare Stellung statt 5478, 1 Spielverlauf statt
255 168. Genau dafür stehen bekannte Vergleichszahlen im Test — ein Fehler, der auf dem Bildschirm
nur wie ein leeres Brett aussieht, wird als vierstellige Abweichung sichtbar.
„Das Spiel verliert nie" ist eine Behauptung über einen Gegner, den es nicht gibt. Ein paar Partien selbst zu spielen beweist nichts — der Mensch am Bildschirm probiert nie alles. Die letzte Prüfzeile lässt deshalb den Gegner jeden möglichen Zug machen, an jeder Stelle, und rechnet nur die eigene Antwort optimal: 681 Partien, 0 Niederlagen. Das ist der Unterschied zwischen „funktioniert bei mir" und „kann nicht anders ausgehen".
Alpha-Beta spart hier viel, weil die Zugreihenfolge zufällig gut ist. 83 % weniger besuchte Stellungen klingt nach einer Eigenschaft des Verfahrens — es ist aber zur Hälfte eine Eigenschaft der Reihenfolge, in der die Felder durchprobiert werden. Wer zuerst die guten Züge betrachtet, schneidet mehr weg. Im schlechtesten Fall spart Alpha-Beta gar nichts; im besten senkt es den Aufwand auf die Wurzel. Deshalb misst die Prüfzeile das gesparte Verhältnis, statt eine Formel dafür hinzuschreiben.
Was das Blatt nicht kann: kein Misère-Nim (wer den letzten nimmt, verliert — die Regel ist fast dieselbe, die Gewinnstrategie nicht), keine allgemeinen Sprague-Grundy-Werte für andere Spiele, keine Transpositionstabelle, keine Stellungsbewertung für Spiele, die zu groß zum Durchrechnen sind. Vier Gewinnt (4531985219092 Stellungen) wäre schon zu viel für einen Browser, Schach ohnehin.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Minimax mit Alpha-Beta, Rückwärtsanalyse, Canvas 2D, hell und dunkel.
Alle Blätter nach Feld geordnet, jedes mit eigenem Repo: ssims437.github.io
MIT