Minimax verständlich erklärt
Wer in einem Spiel zu zweit den nächsten Zug wählt, rechnet damit, dass der Gegner jedes Mal den besten Gegenzug findet, und nimmt den Zug, dessen schlechtester Ausgang noch am besten ist. Diese Seite erklärt die Regel namens Minimax am Beispiel Vier gewinnt, zuerst ohne Formeln, danach für Fachleute mit Modell, Formel, Messwerten und Grenzen.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Der Zug mit dem besten schlimmsten Fall
Stellen Sie sich Vier gewinnt vor, ein Brettspiel für zwei. Man lässt abwechselnd Steine in ein senkrecht stehendes Brett fallen, und wer zuerst vier eigene Steine in einer Reihe hat, gewinnt. Eine Partie endet mit Sieg, Niederlage oder Unentschieden, mit dem Fachwort Remis. Ein Sieg zählt am meisten, eine Niederlage am wenigsten, das Remis liegt dazwischen.
Vor jedem Zug überlegen Sie: Wenn ich hier setze, was setzt der andere? Rechnen Sie damit, dass der Gegner immer den Zug findet, der Ihnen am meisten schadet. Dann wählen Sie den Zug, bei dem selbst dieser schlimmste Fall noch am besten für Sie ausgeht. Das ist nicht der Zug, der bei Glück am schönsten endet, sondern der sicherste gegen einen Gegner, der keinen Fehler macht.
Diese Regel heißt Minimax. Der Name steht für beides: Der Gegner drückt Ihr Ergebnis nach unten (Minimum), und Sie wählen unter Ihren Zügen den mit dem höchsten dieser gedrückten Ergebnisse (Maximum).
Wie eine Maschine das ausrechnet
Eine Maschine spielt dafür alle Möglichkeiten durch. Von jeder Lage auf dem Brett führen mehrere Züge zu neuen Lagen mit weiteren Zügen. Das verzweigt sich wie ein Baum, ein Spielbaum. Seine Enden sind beendete Partien.
Ein Beispiel mit zwei möglichen Zügen für Sie. Nach dem ersten kann der Gegner mit einem Sieg für sich oder mit einem Remis antworten, nach dem zweiten mit einem Remis oder einer Niederlage für sich. Er nimmt jeweils die Antwort, die für ihn besser ist: nach dem ersten Zug den Sieg, nach dem zweiten das Remis. Für Sie endet der erste Zug also mit einer Niederlage, der zweite mit einem Remis. Sie wählen den zweiten.
Die Maschine rechnet so von den Enden zurück zum Anfang: Wo der Gegner zieht, nimmt sie seine beste Antwort, wo Sie ziehen, Ihre beste. Bei einer vollständigen Suche, die wirklich alles durchsieht, ist das Ergebnis ein Beweis und keine Schätzung: Es steht fest, ob man bei fehlerfreiem Spiel beider Seiten gewinnt, remis spielt oder verliert. Das gilt, solange nichts dem Zufall überlassen ist (kein Würfel, keine verdeckten Karten), beide abwechselnd ziehen und der Gewinn des einen genau der Verlust des anderen ist.
Der Preis der Gründlichkeit
Die Gründlichkeit kostet Rechenarbeit, denn mit jedem freien Feld mehr kommen sehr viele Fortsetzungen hinzu, nicht nur ein paar. In der Demo, einem Programm zum Ausprobieren im Browser, ist ein kleines Brett in Sekundenbruchteilen durchsucht. Ein Brett mit einer Spalte mehr und einer Zeile weniger braucht einige Sekunden, das größte Brett der Demo so lange wie eine Kaffeepause (ein Bild, keine Messung). Ein Brett in Standardgröße ist noch größer als jedes Brett dort.
Es gibt Abkürzungen, bei denen die Maschine Züge gar nicht erst prüft, weil sie das Ergebnis nicht mehr verbessern können. Die Demo verzichtet bewusst darauf, damit man die volle Größe der Suche sieht.
Wie ernst ist das Modell zu nehmen?
Die Demo ist stark vereinfacht: ein kleines Brettspiel ohne Zufall und ohne Zeitlimit. Sie zeigt, wie die Regel arbeitet und wie schnell die Suche wächst, nicht wie stark ein fertiges Spielprogramm ist.
Was Sie mitnehmen: Die Regel passt, wo ein Gegenspieler genau gegen Sie arbeitet und sein Gewinn Ihr Verlust ist, etwa in einem Brettspiel. Bei einem Wettbewerber, der auf Ihren Preis reagiert, trifft das nur bedingt zu, denn beide können zugleich verlieren oder gewinnen; dort liefert sie höchstens eine vorsichtige Untergrenze, und nur, solange der Gegner wirklich so gut spielt wie angenommen. Fragen Sie den Anbieter eines Programms, das Züge plant, ob es alle Fortsetzungen durchrechnet oder nach wenigen Zügen abbricht und schätzt, und womit es schätzt. Woran Sie es im eigenen Betrieb erkennen: Die Rechenzeit wächst steil, sobald das Programm einen Zug weiter vorausplanen soll. Das ist eine eigene Einschätzung, keine Messung der Demo.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Modell und Annahmen
Dieser Teil ist eigenständig lesbar. Er fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.
- Spiel: deterministisches Nullsummenspiel mit zwei abwechselnd ziehenden Gegnern. Vehikel ist Mini-Vier-Gewinnt: Steine fallen in die unterste freie Zeile einer Spalte, die Sieglänge ist fest 4, Rot beginnt immer.
- Spielwert: +1 = Sieg Rot, -1 = Sieg Gelb, 0 = Remis bei perfektem Spiel beider Seiten. Rot maximiert, Gelb minimiert.
- Brettgrößen: live wählbar sind nur drei vorab gemessene, unter 2,5 s liegende Größen (3×3, 4×3, 3×4); größere Bretter (ab 4×4) erscheinen nur als vorab gemessener Referenzpunkt. Voreinstellung ist 4 Zeilen × 3 Spalten.
- Suche: vollständige, ungeprunte Rekursion ab der angefragten Stellung (
mm_minimax.solve_position). Als optimal gelten alle Spalten, deren Nachfolgewert dem Wert der Stellung gleicht; die App markiert sie mit ★. Ein Knoten ist laut Quelltext jeder Aufruf der Rekursion für eine noch nicht entschiedene Stellung.
Die Formel
Für eine Stellung \(s\) mit Spieler \(p\) am Zug und Nachfolgestellungen \(s'\) aus \(\text{Züge}(s)\) ist der Spielwert rekursiv definiert: Endstellungen tragen ihr Ergebnis, an allen anderen Stellungen maximiert Rot und minimiert Gelb über die Nachfolger.
\[\text{minimax}(s) = \begin{cases} +1 & s \text{ ist Sieg Rot} \\ -1 & s \text{ ist Sieg Gelb} \\ 0 & s \text{ ist Remis (Brett voll, kein Sieger)} \\ \max_{s'} \text{minimax}(s') & p = \text{Rot} \\ \min_{s'} \text{minimax}(s') & p = \text{Gelb} \end{cases}\]
Die Rekursion endet immer, weil jede Stellung höchstens Zeilen × Spalten freie Felder hat. Der Baum ist endlich, seine Größe wächst aber mit dem Verzweigungsfaktor \(b\) (Spaltenzahl) hoch der Tiefe \(d\) (freie Felder), also höchstens wie \(b^d\) (obere Schranke, keine Gleichheit).
Befunde
Alle Zahlen stammen aus der README der Demo. Gemessen wurde die naive Minimax-Suche ohne Pruning ab dem leeren Brett, mit der tatsächlich ausgelieferten Suche (mm_minimax.solve_position, siehe tests/test_claims.py).
| Frage | Befund |
|---|---|
| Brett 3×3 | 3.568 Knoten, 0,01 s, live wählbar. |
| Brett 4×3 | 69.877 Knoten, 0,24 s, live wählbar. |
| Brett 3×4 | 700.777 Knoten, 2,39 s, live wählbar. |
| Brett 4×4 | 83.078.201 Knoten, 334 s (~5,6 min), nicht live wählbar (nur Referenzpunkt). Laut README vorab gemessen und im Test nur als Konstante hinterlegt, nicht nachgerechnet. |
| Wie stark wächst die Suche mit der Brettgröße? | Von 3×3 auf 4×4 (nur 7 zusätzliche Felder) wächst die Knotenzahl um das rund 23.284-fache. |
| Verzweigungsfaktor oder Tiefe? | 4×3 und 3×4 haben beide 12 Felder, aber 3×4 (mehr Spalten, höherer Verzweigungsfaktor) hat rund das 10-fache an Suchknoten gegenüber 4×3 (mehr Zeilen, mehr Tiefe). Der Verzweigungsfaktor wirkt in diesem Vergleich stärker als die Tiefe. Ob das allein daran liegt, ist laut README offen: Auf 4×3 sind nur senkrechte, auf 3×4 nur waagerechte Viererreihen möglich, was die Bäume ebenfalls unterscheidet. |
| Wer gewinnt bei perfektem Spiel? | Die live gerechneten Bretter (3×3, 4×3, 3×4) enden ab der Startstellung remis (getestet). Das ist zum Teil schon durch die Geometrie vorgegeben (siehe Grenzen). Für 4×4 ist das Ergebnis in der Demo nicht nachgerechnet. |
Die Zeiten hängen vom Rechner ab; die README nennt ihn nicht, und auf Streamlit Cloud können sie höher liegen. Die Knotenzahlen sind dagegen eine Eigenschaft der Suche und nicht des Rechners.
Grenzen
- Kein Pruning: bewusst der Punkt dieser Demo, macht sie aber für Bretter ab 4×4 unbrauchbar langsam. Das Pruning (Alpha-Beta) behandelt eine eigene Demo zum Thema.
- Keine Zeitkontrolle: Es gibt keine Schachuhr, nur die reine Spielbaumgröße.
- Kleine Bretter, kleine Aussagekraft: Der bekannte Vorteil des Startspielers bei Standard-Vier-Gewinnt (7×6) zeigt sich auf diesen Brettern nicht. Bei Sieglänge 4 passt auf 3×3 keine Viererreihe, auf 4×3 nur eine senkrechte, auf 3×4 nur eine waagerechte; das Remis ist dort also zum Teil schon durch die Geometrie vorgegeben. Für 4×4 ist das Ergebnis in der Demo nicht nachgerechnet.
- Keine unabhängige Referenz: Für diese Nicht-Standardgrößen gibt es keinen öffentlichen Referenzlöser. Die Korrektheit sichern handverifizierte Trivialfälle (1×1, 1×4) und eine strukturell unabhängige zweite Implementierung (Alpha-Beta, testintern) ab, siehe
tests/test_minimax.py. - Nicht enthalten: Eröffnungsbücher, Zeitkontrolle, Turniermodus und live berechenbare Bretter ab 4×4.
Quellen
- Allis, V. (1988): Beweis, dass bei Standard-Vier-Gewinnt (7×6) der Startspieler im Vorteil ist, wie in der README der Demo genannt (genauer Titel nicht angegeben).
- Quelltext und Tests der Demo (46 Tests): github.com/sebastian-hanisch/minimax-demo.
Die genannte Arbeit wurde für diese Seite nicht nachgeschlagen; der Literaturhinweis stammt aus der README der Demo. Die Beschreibung des Verfahrens folgt der Demo, nicht einem Lehrbuch.