Blatt · Spiel
Spielbaum — Spiele, die zu Ende gedacht sind
Bei manchen Spielen steht der Ausgang schon vor dem ersten Zug fest — man muss nur weit genug rechnen. Nim braucht dafür nicht einmal einen Rechner: Eine Formel aus drei Zeilen sagt, 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: unentschieden. Beides steht hier zum Spielen und zum Nachrechnen.
Die Reihen werden binär untereinander geschrieben und spaltenweise gezählt. Ist jede Spalte gerade besetzt, ist die Stellung verloren — für den, der am Zug ist. Genau das ist die Nim-Summe: das bitweise Entweder-oder aller Reihen. Wer sie auf null bringt, gewinnt; wer sie auf null vorfindet, hat verloren.
| Zug | Ausgang bei bestem Spiel |
|---|
Zwei Behauptungen stehen hier zur Prüfung. Erstens die Nim-Formel: Sie wird nicht geglaubt, sondern gegen eine stumpfe Rückwärtsanalyse gestellt, die für jede Stellung bis vier Reihen à sieben Hölzern ausrechnet, wer gewinnt — und die Formel muss in jedem einzelnen Fall dasselbe sagen. Zweitens Tic-Tac-Toe: vollständig durchgerechnet, mit der Zahl der erreichbaren Stellungen und der Spielverläufe gegen die bekannten Werte, und Alpha-Beta gegen reines Minimax — gleicher Wert, weniger Arbeit.
noch nicht geprüft
Warum Nim so einfach ist
Weil sich das Spiel in unabhängige Teile zerlegt und die Teile sich bitweise addieren lassen. Das ist der Satz von Sprague und Grundy: Jedes solche Spiel verhält sich wie ein einzelner Nim-Haufen. Die Formel ist nicht geraten, sondern die Folge davon — und die Rückwärtsanalyse im Prüflauf zeigt, dass sie bis auf die letzte Stellung stimmt.
Was Alpha-Beta wegwirft
Sobald ein Zug beweist, dass ein Teilbaum für den Gegner zu gut ist, muss man ihn nicht zu Ende rechnen — eine schlechte Antwort genügt, um den ganzen Ast zu verwerfen. Der Wert bleibt exakt derselbe, nur die Zahl der besuchten Stellungen sinkt. Wie stark, hängt an der Zugreihenfolge: gut sortiert bringt die Ersparnis am meisten.
Gelöst heißt nicht langweilig
Tic-Tac-Toe ist gelöst, Dame seit 2007, Schach nicht und wohl nie. Der Unterschied ist allein die Größe: 5478 erreichbare Stellungen gegen geschätzte 10⁴⁴. Wer ein Spiel „löst", beweist nur, dass beide Seiten bei bestem Spiel ein bestimmtes Ergebnis erzwingen — über die Frage, ob es Spaß macht, sagt das nichts.
Eine einzelne HTML-Datei. Kein Build, keine Bibliothek, nichts verlässt den Browser. Alle Blätter: ssims437.github.io