Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search

Ein Spiel als Suchproblem, der Spielbaum, Minimax, Alpha-Beta-Suche, Bewertungsfunktionen und MCTS — am Beispiel Tic-Tac-Toe, wo sich alles ausrechnen lässt, und der Weg von Deep Blue zu AlphaZero.

14 Minuten Matěj Žalmánek 2026-10-15

Serie KI-Grundlagen Teil 22 von 52

1. Landkarte der künstlichen Intelligenz: was was ist und wie alles zusammenpasst
2. Eine kurze Geschichte der künstlichen Intelligenz: von Turing bis zu Sprachmodellen
3. Daten, Modell, Training, Inferenz: die Grundbegriffe an einem einzigen Beispiel
4. Mathematische Notation lesen: Symbole, Indizes, Summen und Quantoren
5. Mengen und Relationen: der Baukasten, aus dem Definitionen in der KI bestehen
6. Funktionen und Abbildungen: warum jedes KI-Modell eine Funktion ist
7. Logik und Beweise: die Regeln, nach denen KI schließt
8. Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen
9. Lineare Algebra für maschinelles Lernen: Vektoren, Matrizen und warum KI vor allem multipliziert
10. Ableitungen, Gradient und Kettenregel: wie ein Modell herausfindet, in welche Richtung es lernen soll
11. Gradientenabstieg: wie ein Modell lernt
12. Was ist Wahrscheinlichkeit: vom Würfelwurf zu den Kolmogorow-Axiomen
13. Bedingte Wahrscheinlichkeit und der Satz von Bayes: wie du deine Einschätzung änderst, wenn du etwas Neues erfährst
14. Zufallsvariable und Verteilungsfunktion: eine Funktion, die alles über eine Verteilung verrät
15. Dichtefunktion und Wahrscheinlichkeitsfunktion: warum eine stetige Zufallsvariable in einem Punkt die Wahrscheinlichkeit null hat
16. Erwartungswert, Varianz und Kovarianz: wo eine Verteilung liegt, wie breit sie ist und was womit zusammenhängt
17. Überblick über Wahrscheinlichkeitsverteilungen: Bernoulli-, Binomial-, Poisson-, Gleich-, Normal- und Exponentialverteilung
18. Gesetz der großen Zahlen und zentraler Grenzwertsatz: Warum sich Durchschnitte so vorhersagbar verhalten
19. Statistik und Parameterschätzung: Maximum Likelihood, MAP und Konfidenzintervalle
20. Informationstheorie: Entropie, Kreuzentropie und KL-Divergenz — woher Verlustfunktionen kommen
21. Zustandsraumsuche: BFS, DFS, UCS und A* mit Animationen
22. Spiele und Gegner: Minimax, Alpha-Beta-Suche und Monte Carlo Tree Search
23. Constraint Satisfaction: Backtracking, Constraint-Propagierung und AC-3 an Sudoku und einer Karte tschechischer Regionen
24. Logik und wissensbasierte Systeme: Vorwärts- und Rückwärtsverkettung, Resolution und Expertensysteme
25. Planung: STRIPS, die Blockwelt, Heuristiken aus Relaxierung und Planung in KI-Agenten
26. Lokale Suche und simulierte Abkühlung: ein Handlungsreisender durch die tschechischen Regionalhauptstädte
27. Genetische Algorithmen: Population, Kreuzung, Mutation und Selektion am Rucksack für die Wanderung
28. Evolutionsstrategien und genetische Programmierung: von der 1/5-Erfolgsregel zum Keplerschen Gesetz
29. Ameisenkolonieoptimierung: wie eine Pheromonspur einen kurzen Weg findet
30. Partikelschwarmoptimierung: Trägheit, eigene Erfahrung und die Erfahrung des Schwarms
31. Neuroevolution: Evolution der Gewichte und der Gestalt neuronaler Netze und der Algorithmus NEAT
32. Fuzzy-Mengen und Zugehörigkeitsfunktionen: wie man „etwas warm“ aufschreibt
33. Fuzzy-Logik und Wahrscheinlichkeit: warum „etwas warm“ nicht „wahrscheinlich warm“ bedeutet
34. Fuzzy-Logik: t-Normen, Implikationen und WENN–DANN-Regeln
35. Fuzzy-Regelung: Mamdani und Sugeno vom Ventilator bis zum Pendel auf dem Wagen
36. Fuzzy-Clustering: der Algorithmus fuzzy c-means und Punkte zwischen den Clustern
37. Neuro-Fuzzy-Systeme (ANFIS): Fuzzy-Regeln, die aus Daten lernen
38. Markow-Ketten: Übergangsmatrix, stationäre Verteilung und PageRank
39. Hidden-Markov-Modelle: der Viterbi-Algorithmus und das unehrliche Kasino
40. Bayessche Netze: warum das Gras nass ist und was das für den Rasensprenger bedeutet
41. Der Kalman-Filter: wie man aus ungenauen Messungen schätzt, wo ein Auto ist und wie schnell es fährt
42. Arten des maschinellen Lernens: überwacht, unüberwacht, halbüberwacht und mehr
43. Prompts, Kontext und RAG: wie man einem Modell die richtigen Informationen gibt
44. Variational Autoencoder (VAE): neue Bilder aus einem stetigen latenten Raum
45. Generative Adversarial Networks (GAN): der Fälscher gegen den Detektiv
46. Diffusionsmodelle: wie aus reinem Rauschen ein Bild wird
47. Markow-Entscheidungsprozesse: Zustände, Aktionen, Belohnungen und Bellman-Gleichungen
48. Q-Learning und DQN: den Wert von Aktionen lernen, von der Tabelle bis zum neuronalen Netz
49. Policy Gradient und PPO: die Strategie direkt lernen
50. Wie ein KI-Agent funktioniert: ein Sprachmodell in einer Schleife mit Werkzeugen
51. Programmieren mit KI-Agenten: Auftrag, Tests und Kontrolle
52. Bewertung und Sicherheit von KI-Systemen: wie man misst und wie man überwacht

Der ganze Lehrplan der Serie 52 von 83 Themen fertig

Im Labyrinth aus dem letzten Teil stand das Männchen allein da. Die Welt bewegte sich nicht, und jeder Zug führte dorthin, wohin er sollte. Im Spiel aber sitzt dir jemand gegenüber, der genau das Gegenteil will — und auf jeden deiner Züge mit dem antwortet, der dir am meisten wehtut. Einen Weg zum Ziel zu suchen, reicht nicht mehr: Du musst eine Strategie suchen, die gegen jede Antwort besteht. Schach, Dame und Go waren jahrzehntelang der Maßstab der künstlichen Intelligenz, und die Algorithmen aus diesem Teil stecken hinter Deep Blue wie hinter AlphaGo.

Er baut auf den Teilen Zustandsraumsuche und Graphen und Bäume auf.

1. Ein Spiel als Suchproblem

Definition — Zweipersonenspiel

Ein Zweipersonenspiel (deterministisch, mit vollständiger Information und Nullsumme) ist ein Siebentupel

Γ = (S, s₀, Spieler, A, T, K, U),

das Folgendes erfüllt:

1. S ist eine nichtleere Menge von Zuständen (Stellungen) und s₀ ∈ S ist der Anfangszustand;
2. K ⊆ S ist die Menge der Endzustände — in ihnen endet das Spiel;
3. Spieler : S ∖ K → {MAX, MIN} legt fest, wer in einem Zustand am Zug ist;
4. A ordnet jedem Zustand s ∈ S ∖ K eine endliche nichtleere Menge A(s) von Zügen (Aktionen) zu, und in Endzuständen ist A(s) = ∅;
5. T ist die Übergangsfunktion: Für s ∈ S ∖ K und a ∈ A(s) ist T(s, a) ∈ S der Zustand nach dem Zug a (die Züge sind deterministisch);
6. die Spieler ziehen abwechselnd: Ist s ∈ S ∖ K, a ∈ A(s) und T(s, a) ∉ K, dann gilt Spieler(T(s, a)) ≠ Spieler(s);
7. U : K → ℝ ist der Nutzen eines Endzustands aus Sicht des Spielers MAX; der Nutzen des Spielers MIN ist −U (Nullsumme: U(s) + (−U(s)) = 0 für jedes s ∈ K).

Beide Spieler kennen das ganze Siebentupel und sehen in jedem Moment den aktuellen Zustand (vollständige Information). Das Spiel ist endlich genau dann, wenn es keine unendliche Folge s₀, s₁, s₂, … mit s_i = T(s_i−1, a_i) für irgendwelche a_i ∈ A(s_i−1) gibt — jede Partie endet also nach endlich vielen Zügen in K. Alle Spiele in diesem Teil sind endlich.

Eine Strategie des Spielers MAX ist eine Funktion σ, die jedem Zustand s ∈ S ∖ K mit Spieler(s) = MAX einen Zug σ(s) ∈ A(s) zuordnet; eine Strategie τ des Spielers MIN ist ebenso für Zustände mit Spieler(s) = MIN definiert. Ein Paar von Strategien (σ, τ) bestimmt eindeutig eine Partie ab dem Zustand s₀ und damit auch ihren Nutzen.

Der Unterschied zur Suche ist grundlegend. Die Lösung ist kein Pfad mehr — den kannst du nicht wählen, denn jeden zweiten Zug macht der Gegner. Die Lösung ist eine Strategie: eine Vorschrift, wie man auf jeden Zug antwortet, den der Gegner spielen kann.

2. Der Spielbaum

Definition — Spielbaum

Sei Γ = (S, s₀, Spieler, A, T, K, U) ein endliches Zweipersonenspiel. Der Spielbaum des Spiels Γ ist ein Wurzelbaum (siehe den Teil Graphen und Bäume), für den gilt:

1. die Knoten sind alle Zugfolgen (a₁, …, a_k), k ≥ 0, die sich ab s₀ spielen lassen, d. h. s_i−1 ∉ K, a_i ∈ A(s_i−1) und s_i = T(s_i−1, a_i) für i = 1, …, k; zum Knoten gehört der Zustand s_k;
2. die Wurzel ist die leere Folge () mit dem Zustand s₀;
3. die Kinder eines Knotens (a₁, …, a_k) mit dem Zustand s_k ∉ K sind die Knoten (a₁, …, a_k, a) für alle a ∈ A(s_k) mit den Zuständen T(s_k, a);
4. die Blätter sind genau die Knoten, deren Zustand ein Endzustand ist (s_k ∈ K).

Ein Knoten ist also keine Stellung, sondern die Geschichte, die zu ihr geführt hat — in denselben Zustand kann man über verschiedene Zugfolgen gelangen, und im Baum taucht er dann mehrfach auf. Knoten, in denen MAX am Zug ist, zeichnen wir als Dreieck mit der Spitze nach oben, MIN-Knoten mit der Spitze nach unten.

Sei b = max_{s ∈ S ∖ K} |A(s)| der Verzweigungsfaktor und m die größte Länge einer Partie (Zahl der Züge). Dann hat der Baum höchstens b^m Blätter.

Tic-Tac-Toe auf einem 3 × 3-Spielfeld ist ein kleines Spiel, und trotzdem hat sein Baum 549 946 Knoten und 255 168 Blätter — so viele verschiedene Partien lassen sich spielen. Verschiedene Stellungen gibt es dabei nur 5 478: In dieselbe Stellung gelangt man über viele Zugfolgen. Schach hat einen Verzweigungsfaktor von etwa 35, und eine Partie dauert Dutzende Züge; Claude Shannon schätzte seinen Baum 1950 auf 10¹²⁰ Partien. Go mit einem Verzweigungsfaktor von etwa 250 liegt noch viele Größenordnungen darüber. Den ganzen Baum durchlaufen wir also nur bei kleinen Spielen — bei großen müssen wir lernen, welche Äste wir auslassen.

Beispiel — die obere Schranke für den Tic-Tac-Toe-Baum und die Shannon-Zahl

Würde Tic-Tac-Toe immer bis zum vollen Feld gespielt, hätte der Baum in der Tiefe k genau 9 · 8 · … · (9 − k + 1) = 9!/(9 − k)! Knoten (k = 0, …, 9). Insgesamt

∑_k=0⁹ 9!/(9 − k)! = 1 + 9 + 72 + 504 + 3 024 + 15 120 + 60 480 + 181 440 + 362 880 + 362 880 = 986 410 Knoten und 9! = 362 880 Blätter.

Der tatsächliche Baum hat 549 946 Knoten und 255 168 Blätter, weil eine Partie, in der jemand drei in einer Reihe legt, früher endet und ihr Ast sich nicht weiter verzweigt. Die Abschätzung b^m ist also eine obere Schranke; hier mit b, das von 9 auf 1 fällt.

Shannon (Programming a Computer for Playing Chess, 1950) rechnete beim Schach mit etwa 10³ Möglichkeiten pro Zugpaar (Weiß und Schwarz) und einer typischen Partie von 40 Zugpaaren: (10³)⁴⁰ = 10¹²⁰. Das ist eine grobe Schätzung der Größenordnung, keine genaue Zahl.

3. Minimax

Definition — Minimax-Wert

Sei Γ = (S, s₀, Spieler, A, T, K, U) ein endliches Zweipersonenspiel. Der Minimax-Wert ist die Funktion MM : S → ℝ, rekursiv definiert für jedes s ∈ S:

1. MM(s) = U(s), falls s ∈ K;
2. MM(s) = max_{a ∈ A(s)} MM(T(s, a)), falls s ∉ K und Spieler(s) = MAX;
3. MM(s) = min_{a ∈ A(s)} MM(T(s, a)), falls s ∉ K und Spieler(s) = MIN.

Die Rekursion ist wohldefiniert: Das Spiel ist endlich, sodass jede Kette rekursiver Aufrufe in einem Endzustand endet, und A(s) ist endlich und nichtleer, sodass Maximum und Minimum existieren.

Ein Zug a* ∈ A(s) ist ein optimaler Zug des Spielers MAX im Zustand s mit Spieler(s) = MAX genau dann, wenn

a* ∈ argmax_{a ∈ A(s)} MM(T(s, a)), d. h. MM(T(s, a*)) = MM(s);

ein optimaler Zug des Spielers MIN ist entsprechend ein Element von argmin. Die Strategie, die in jedem Zustand einen optimalen Zug wählt, ist die Minimax-Strategie.

Der linke MIN-Knoten wählt aus den Blättern 4, 6 und 9 die 4, der mittlere aus 2, 7 und 8 die 2, der rechte aus 5, 3 und 9 die 3. MAX in der Wurzel wählt dann zwischen 4, 2 und 3 und spielt den linken Zug mit dem Wert 4. Beachte, dass der rechte Ast eine Neun verbirgt — nur kommt MAX nie an sie heran, weil MIN stattdessen die Drei spielen würde.

Satz — was Minimax garantiert

Sei Γ ein endliches Zweipersonenspiel und σ* die Minimax-Strategie des Spielers MAX. Dann gilt:

1. für jede Strategie τ des Spielers MIN hat die vom Paar (σ*, τ) gespielte Partie einen Nutzen ≥ MM(s₀);
2. ist auch τ* die Minimax-Strategie des Spielers MIN, hat die vom Paar (σ*, τ*) gespielte Partie genau den Nutzen MM(s₀).

Beweis (Skizze), durch Induktion nach der Höhe des Knotens: In einem Blatt erhält MAX genau U(s) = MM(s). In einem MAX-Knoten zieht er in das Kind mit dem größten Wert und behauptet dort nach Induktionsvoraussetzung mindestens diesen Wert, also mindestens MM(s). In einem MIN-Knoten wählt der Gegner ein beliebiges Kind, aber jedes hat einen Wert ≥ min = MM(s), und in jedem behauptet MAX nach Voraussetzung mindestens dessen Wert. Für s = s₀ ist das Punkt 1. Mit derselben Überlegung bei vertauschten Rollen sichert sich MIN mit der Minimax-Strategie τ* einen Nutzen von höchstens MM(s₀) gegen jede Strategie von MAX; beide Ungleichungen zusammen ergeben Punkt 2. ∎

Minimax durchläuft den Baum in die Tiefe: Zeit O(b^m), Speicher O(b · m).

4. Minimax bei Tic-Tac-Toe

Tic-Tac-Toe auf 3 × 3 ist klein genug, dass Minimax den ganzen Baum durchläuft. Das Ergebnis kennt jeder, der es länger als ein paar Minuten gespielt hat: Der Minimax-Wert des leeren Felds ist 0 — wenn beide fehlerfrei spielen, ist es immer ein Remis. Interessanter ist, was Minimax über eine konkrete Stellung sagt. Am Zug ist X (MAX), und in jedem freien Feld steht der Wert des Zugs dorthin:

Gewinnen tut ein einziger Zug — die Mitte. X baut damit eine Gabel: Es droht, die mittlere Zeile und die Diagonale zu vollenden, und O kann nicht beides blockieren. Der Zug unten in die Mitte hält das Remis. Die übrigen drei Züge sehen harmlos aus, verlieren aber: O antwortet darauf mit einer eigenen Gabel. Ein Mensch müsste das durchdenken; Minimax rechnet es einfach aus.

def minimax(board):
    end = winner(board)                 # "X", "O", "draw" oder None
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    values = [minimax(play(board, move)) for move in empty_squares(board)]
    return max(values) if to_move(board) == "X" else min(values)

5. Alpha-Beta-Suche

Minimax durchläuft den ganzen Baum, obwohl er zur Hälfte überflüssig ist. Schau dir noch einmal den mittleren Ast an: Das erste Blatt zeigte 2. MIN erreicht in diesem Ast also 2 oder weniger — und MAX hat den linken Ast mit dem Wert 4 schon sicher. Wie auch immer die übrigen zwei Blätter aussehen, MAX geht nicht in den mittleren Ast. Er muss sie sich nicht einmal ansehen.

Definition — Alpha-Beta

Sei Γ ein endliches Zweipersonenspiel. Alpha-Beta ist eine Tiefensuche, die zwei Schranken α, β ∈ ℝ ∪ {−∞, +∞} mit sich trägt:

1. α — der höchste Wert, den sich MAX irgendwo auf dem Weg von der Wurzel schon gesichert hat (anfangs −∞);
2. β — der niedrigste Wert, den sich MIN schon gesichert hat (anfangs +∞).

Die Funktion AB(s, α, β) für einen Zustand s ∈ S:

1. Ist s ∈ K, gib U(s) zurück.
2. Ist Spieler(s) = MAX, setze v ← −∞; sonst v ← +∞.
3. Berechne für die Züge a ∈ A(s) nacheinander (in fester Reihenfolge) h ← AB(T(s, a), α, β) und
   • setze in einem MAX-Knoten v ← max(v, h) und α ← max(α, v),
   • setze in einem MIN-Knoten v ← min(v, h) und β ← min(β, v);
   sobald α ≥ β, werden die übrigen Züge abgeschnitten — sie werden nicht durchsucht — und es geht mit Schritt 4 weiter.
4. Gib v zurück.

Alpha-Beta in der Wurzel ist der Aufruf AB(s₀, −∞, +∞).

Satz. Sei Γ ein endliches Zweipersonenspiel. Dann gilt AB(s₀, −∞, +∞) = MM(s₀) — Alpha-Beta liefert in der Wurzel denselben Wert wie Minimax (in inneren Knoten, in denen geschnitten wurde, liefert es nur eine Schranke, nicht den genauen Wert). Hat der Baum den Verzweigungsfaktor b und die Tiefe m und sind die Züge in der bestmöglichen Reihenfolge sortiert, untersucht Alpha-Beta nur O(b^m/2) Knoten.

schneide ab, wenn α ≥ β

α

das Beste, was sich MAX anderswo auf dem Weg von der Wurzel schon gesichert hat. In einen Ast, der weniger bringt, geht er nie — er hat eine bessere Wahl

β

das für MAX Schlechteste, was ihm MIN in diesem Ast schon aufzwingen kann. Mehr als β bekommt MAX von hier nicht, wie auch immer die übrigen Kinder ausfallen

≥

das Fenster [α, β] ist leer: Ein Wert, um den es hier noch gehen könnte, müsste zugleich mindestens α und höchstens β sein. So einen gibt es nicht (bei Gleichheit wäre er nicht besser als das, was MAX schon hat), also kann der Rest des Asts die Wurzel nicht beeinflussen

Alpha-Beta kam zum selben Ergebnis — MAX spielt links und erhält 4 —, hat aber nur 6 von 9 Blättern bewertet. Im mittleren Ast hat es zwei Blätter gleich nach der Zwei abgeschnitten, im rechten eines nach der Drei. Beim abgeschnittenen MIN-Knoten steht deshalb nur die Schranke „≤ 2“ bzw. „≤ 3“: Den genauen Wert kennen wir nicht, und wir brauchen ihn auch nicht.

Was die Animation an den Knoten zeigt, hier Schritt für Schritt in einer Tabelle. Eine Zeile hält das Fenster eines Knotens beim Betreten fest und dann nach jedem Kind, das einen Wert zurückgegeben hat:

Ein MIN-Knoten bekommt vom Elternknoten α = 4 und ändert nur sein β; ein MAX-Knoten ändert umgekehrt nur α. Das Fenster jedes Knotens wird so nur enger. Im rechten Ast löst das erste Blatt (5) keinen Schnitt aus — 5 ist mehr als 4, MIN könnte MAX hier mehr geben als links —, erst das zweite Blatt (3) zieht β unter α.

Bei Tic-Tac-Toe ist der Unterschied dramatischer. Vollständiges Minimax besucht vom leeren Feld aus 549 946 Stellungen, Alpha-Beta mit derselben Zugreihenfolge nur 18 297 — etwa dreißigmal weniger — und liefert dieselbe Null. Der Exponent m/2 im Satz bedeutet, dass du in derselben Zeit doppelt so tief vorausschaust. Deshalb kommt es so sehr auf die Zugreihenfolge an: Schachprogramme probieren zuerst Schlagzüge und Züge, die beim letzten Mal gut waren.

Beispiel — wie viele Blätter Alpha-Beta bei bester Reihenfolge spart

Die genaue Schranke bewiesen D. E. Knuth und R. W. Moore (An Analysis of Alpha-Beta Pruning, 1975): In einem Baum mit dem Verzweigungsfaktor b und der Tiefe d bewertet Alpha-Beta bei bester Zugreihenfolge

b^⌈d/2⌉ + b^⌊d/2⌋ − 1 Blätter statt b^d.

Schach, b = 35, Tiefe d = 6 Halbzüge: Minimax 35⁶ = 1 838 265 625 Blätter, Alpha-Beta 35³ + 35³ − 1 = 42 875 + 42 875 − 1 = 85 749 Blätter — etwa 21 000-mal weniger. Und umgekehrt: 12 Halbzüge durchläuft Alpha-Beta mit 35⁶ + 35⁶ − 1 ≈ 3,7 · 10⁹ Blättern, also nur mit dem Doppelten der Arbeit, die Minimax für 6 Halbzüge braucht.

Der kleine Baum aus der Abbildung (b = 3, d = 2): Die Schranke ist 3 + 3 − 1 = 5 Blätter. Alpha-Beta hat 6 bewertet, weil die Reihenfolge der Blätter nicht die bestmögliche ist — im rechten Ast steht die Drei erst an zweiter Stelle.

def alphabeta(board, alpha=-inf, beta=inf):
    end = winner(board)
    if end:
        return {"X": 1, "O": -1, "draw": 0}[end]
    maximizing = to_move(board) == "X"
    v = -inf if maximizing else inf
    for move in empty_squares(board):
        h = alphabeta(play(board, move), alpha, beta)
        if maximizing:
            v = max(v, h); alpha = max(alpha, v)
        else:
            v = min(v, h); beta = min(beta, v)
        if alpha >= beta:
            break                          # Schnitt: der Rest des Asts ändert nichts
    return v

6. Begrenzte Tiefe und Bewertungsfunktion

Auch Alpha-Beta durchläuft den Schachbaum nicht bis zum Ende der Partie. Echte Programme suchen deshalb nur bis zu einer festen Tiefe und schätzen die Stellung, in der sie ankommen.

Definition — Minimax mit begrenzter Tiefe

Sei Γ = (S, s₀, Spieler, A, T, K, U) ein Zweipersonenspiel. Eine Bewertungsfunktion ist eine Funktion E : S → ℝ mit E(s) = U(s) für alle s ∈ K; für s ∉ K ist E(s) eine Schätzung von MM(s). Meist ist sie eine gewichtete Summe von n ≥ 1 Merkmalen der Stellung f₁, …, f_n : S → ℝ mit den Gewichten w₁, …, w_n ∈ ℝ:

E(s) = w₁f₁(s) + … + w_nf_n(s).

Minimax mit begrenzter Tiefe ist für jedes d ∈ ℕ₀ die Funktion MM_d : S → ℝ, rekursiv nach d definiert:

1. MM_d(s) = E(s), falls s ∈ K oder d = 0;
2. MM_d(s) = max_{a ∈ A(s)} MM_d−1(T(s, a)), falls s ∉ K, d ≥ 1 und Spieler(s) = MAX;
3. MM_d(s) = min_{a ∈ A(s)} MM_d−1(T(s, a)), falls s ∉ K, d ≥ 1 und Spieler(s) = MIN.

Der Wert MM_d(s) berechnet Minimax also nur d Halbzüge voraus und ersetzt die Stellungen, in denen er ankommt, durch die Schätzung E. Ist d mindestens die Länge der längsten Partie ab s, gilt MM_d(s) = MM(s).

E(s) = ∑_i w_i · (p_i(s) − p′_i(s))

E(s)

die Schätzung des Stellungswerts aus Sicht von MAX (Weiß) — sie wird dort eingesetzt, wo die Suche endet, anstelle des echten Minimax-Werts

∑_i

über die Figurenarten: Bauer, Springer, Läufer, Turm, Dame. Eine Summe, weil sich das Material verschiedener Figuren im einfachsten Modell einfach addiert

w_i

der Wert der Figur: 1, 3, 3, 5, 9. Das Gewicht rechnet „Stücke“ in eine gemeinsame Währung um, damit sich ein Turm mit zwei Springern vergleichen lässt

p_i − p′_i

wie viele Figuren dieser Art Weiß mehr hat als Schwarz. Die Differenz, nicht die Anzahl, weil das Spiel ein Nullsummenspiel ist: Was der Gegner mehr hat, ist ein Verlust

def minimax_d(s, d):
    if is_terminal(s) or d == 0:
        return E(s)                        # weiter sehen wir nicht: Schätzung statt echtem Wert
    values = [minimax_d(T(s, a), d - 1) for a in actions(s)]
    return max(values) if player(s) == "MAX" else min(values)

def iterative_deepening(s, time):         # in s ist MAX am Zug
    d, best = 1, None
    while time_left(time):
        best = max(actions(s), key=lambda a: minimax_d(T(s, a), d - 1))
        d += 1                             # nächste Runde einen Halbzug tiefer
    return best

Die begrenzte Tiefe hat ihre Falle: den Horizonteffekt. Endet die Suche mitten in einem Figurentausch — du hast gerade die Dame geschlagen, der Gegner schlägt sie im nächsten Zug zurück —, sieht die Bewertungsfunktion nur die erste Hälfte und überschätzt die Stellung. Programme wehren sich dagegen, indem sie „unruhige“ Stellungen weiter durchsuchen, bis sie sich beruhigen. Und weil sie nie wissen, wie viel Zeit sie haben, suchen sie mit der iterativen Vertiefung aus dem letzten Teil: Tiefe 1, 2, 3, … bis die Zeit abläuft. Die Ergebnisse der flachen Durchläufe dienen außerdem als Zugreihenfolge für die tieferen — und Alpha-Beta schneidet dann viel mehr ab.

7. Monte Carlo Tree Search

An der Bewertungsfunktion für Schach haben Menschen jahrzehntelang gefeilt. Für Go wollte es nicht gelingen, eine zu schreiben — eine Stellung, die ruhig aussieht, kann zwanzig Züge später verloren sein. Monte Carlo Tree Search (MCTS) verzichtet ganz auf eine Bewertungsfunktion. Statt die Stellung zu schätzen, spielt sie sie zu Ende: zufällig, viele Male, und schaut, wie oft es gut ausgegangen ist.

Definition — eine Iteration von MCTS

Sei Γ = (S, s₀, Spieler, A, T, K, U) ein endliches Zweipersonenspiel, in dem jede Partie das Ergebnis Sieg, Remis oder Niederlage hat. Eingabe: ein Zustand s₀ ∉ K (die Wurzel) und eine Zahl von Iterationen (oder ein Zeitlimit). Ausgabe: ein Zug a ∈ A(s₀).

MCTS baut einen Suchbaum auf — einen Teil des Spielbaums, der nur mit der Wurzel beginnt und in jeder Iteration um einen Knoten wächst. Jeder Knoten i des Baums merkt sich:

1. die Zahl der Besuche n_i ∈ ℕ₀ — wie viele Simulationen durch den Knoten gegangen sind;
2. die Summe der Ergebnisse w_i ∈ [0, n_i] aus Sicht des Spielers, der in den Knoten gezogen hat, wobei das Ergebnis einer Partie 1 für einen Sieg, ½ für ein Remis und 0 für eine Niederlage ist.

Ein Knoten ist vollständig erweitert genau dann, wenn er im Baum ein Kind für jeden Zug a ∈ A(s) seines Zustands s hat. Eine Iteration von MCTS hat vier Schritte:

1. Auswahl — beginne in der Wurzel; solange der aktuelle Knoten vollständig erweitert und sein Zustand kein Endzustand ist, gehe in das Kind mit dem höchsten UCT-Wert (Definition unten).
2. Erweiterung — ist der Zustand des aktuellen Knotens kein Endzustand, wähle einen noch nicht ausprobierten Zug a, füge ein Kind mit dem Zustand T(s, a) und n = w = 0 hinzu und gehe in dieses.
3. Simulation — spiele vom Zustand des aktuellen Knotens aus die Partie mit zufälligen Zügen (jeder aus A(s) mit derselben Wahrscheinlichkeit) bis zu einem Endzustand s_K ∈ K zu Ende.
4. Rückpropagierung — setze für jeden Knoten i auf dem Weg vom aktuellen Knoten zurück zur Wurzel (beide eingeschlossen) n_i ← n_i + 1 und w_i ← w_i + das Ergebnis der Partie s_K aus Sicht des Spielers, der in den Knoten i gezogen hat.

Die Iterationen werden wiederholt, bis die Zahl der Iterationen oder die Zeit aufgebraucht ist. Dann wird der Zug aus der Wurzel in das Kind mit dem größten n_i gespielt.

def mcts(root, iterations):
    for _ in range(iterations):
        u = root
        while u.all_children() and u.children:     # 1. Auswahl
            u = max(u.children, key=uct)
        if u.untried and not is_terminal(u.state): # 2. Erweiterung
            u = u.add_child(random_choice(u.untried))
        s = u.state
        while not is_terminal(s):                  # 3. Simulation
            s = T(s, random_choice(actions(s)))
        while u is not None:                       # 4. Rückpropagierung
            u.n += 1
            u.w += result(s, for_=u.who_moved)     # 1, ½ oder 0
            u = u.parent
    return max(root.children, key=lambda c: c.n).move

Definition — UCT

Ein Knoten des MCTS-Suchbaums habe N ≥ 1 Besuche und die Kinder i = 1, …, k, jedes mit n_i ≥ 1 Besuchen und der Summe der Ergebnisse w_i ∈ [0, n_i] (Bezeichnungen aus der Definition von MCTS oben). Sei c > 0 eine feste Explorationskonstante, meist c = √2. Der UCT-Wert (Upper Confidence bounds applied to Trees) des Kindes i ist

UCT(i) = w_i/n_i + c · √ln N/n_i.

Im Auswahlschritt wird das Kind i* ∈ argmax_{i ∈ {1, …, k}} UCT(i) gewählt. Kocsis und Szepesvári (2006) bewiesen, dass mit wachsender Zahl von Iterationen die Wahrscheinlichkeit, dass MCTS mit UCT einen anderen als den minimax-optimalen Zug empfiehlt, gegen null geht.

UCT(i) = w_i/n_i + c · √ln N/n_i

UCT(i)

die Punktzahl des Kindes i bei der Auswahl; das größte gewinnt. Es ist keine Schätzung des Zugwerts, sondern „wie sehr es sich lohnt, ihn noch einmal zu probieren“

w_i/n_i

das durchschnittliche Ergebnis des Zugs (0 bis 1) — Ausnutzen: Züge, die bisher gut ausgingen, werden bevorzugt

c

die Explorationskonstante — wie viel die Neugier gegenüber den bisherigen Ergebnissen wiegt. Der Wert √2 stammt aus der Regel UCB1 für mehrarmige Banditen (Auer, Cesa-Bianchi und Fischer, 2002) für Ergebnisse in [0, 1]; auf Bäume übertrugen sie Kocsis und Szepesvári (2006). In der Praxis wird er abgestimmt

ln N

wächst mit der Zahl der Besuche des Elternknotens, aber nur langsam. Dank ihm wächst der Bonus wenig probierter Züge langsam: Jeder Zug wird früher oder später erneut probiert

n_i

wie oft der Zug schon probiert wurde — im Nenner, sodass der Bonus umso größer ist, je weniger wir ihn kennen. Die Wurzel entspricht (vereinfacht) dem, wie schnell der Durchschnitt genauer wird: Seine Unsicherheit sinkt wie 1/√n

Lassen wir MCTS auf die Stellung los, die Minimax oben entschlüsselt hat. Die Zahlen in den Feldern sind die Besuche nach 100, 300 und 1000 Iterationen, darunter das durchschnittliche Ergebnis für X:

Nach 100 Iterationen hat die Mitte 47 Besuche und die übrigen Züge zusammen mehr. Nach tausend hat sie 856 und ein durchschnittliches Ergebnis von 0,94; der Remiszug unten in der Mitte bekam 52 Besuche, die verlierenden Züge noch weniger. Dabei kennt MCTS weder den Begriff Gabel noch irgendeine Bewertungsfunktion — nur die Regeln und den Zufall. Und trotzdem hat es denselben Zug gefunden wie Minimax, das den ganzen restlichen Baum durchlaufen musste.

Warum gerade diese Verteilung der Besuche? Berechnen wir die UCT-Werte der Züge aus der Wurzel nach 1000 Iterationen (N = 1000, ln N ≈ 6,908, c = √2; Farben nach der Formel oben):

Die UCT-Werte sind fast gleich — im Bereich von 1,049 bis 1,068. Das ist kein Zufall: Die Auswahl besucht jedes Mal den Zug mit dem höchsten UCT und senkt damit seinen Bonus (der Durchschnitt ändert sich dabei nur wenig), sodass sich die Werte nach und nach angleichen. Die Mitte hat den besten Durchschnitt und braucht deshalb zum Ausgleich nur einen kleinen Bonus — also viele Besuche. Die übrigen Züge haben einen schlechteren Durchschnitt und gleichen ihn mit einem großen Bonus aus, für den wenige Besuche reichen. (Die Summen in der Tabelle rechnen wir aus ungerundeten Werten, in der letzten Stelle können sie sich deshalb um 1 unterscheiden.)

8. Von Deep Blue zu AlphaZero

• Deep Blue (1997) besiegte Weltmeister Garri Kasparow. Darin steckten Alpha-Beta mit einer handgeschriebenen Bewertungsfunktion und spezialisierte Hardware, die etwa 200 Millionen Stellungen pro Sekunde schaffte.
• Chinook spielte schon in den 90er-Jahren Dame gegen Weltmeister, und 2007 haben seine Autoren das Spiel gelöst: Sie gingen so viele Stellungen durch, dass sie bewiesen, dass eine fehlerfreie Partie remis endet — genau wie Tic-Tac-Toe auf 3 × 3.
• AlphaGo (2016) besiegte Lee Se-dol 4 : 1. Es verband MCTS mit neuronalen Netzen: Ein Netz schlug vielversprechende Züge vor (statt der zufälligen Auswahl), ein zweites schätzte den Wert der Stellung (statt der ganzen zufälligen Partie).
• AlphaZero (2017) verzichtete auch auf menschliche Partien. Es lernte Schach, Shogi und Go nur durch Spiele gegen sich selbst — durch bestärkendes Lernen — und besiegte in jedem der Spiele das bis dahin beste Programm.
• Spiele mit Zufall und verdeckter Information brauchen mehr. Beim Backgammon entscheidet der Würfel, deshalb fügt man dem Baum Zufallsknoten mit Erwartungswert hinzu (Expectiminimax). Beim Poker siehst du die Karten des Gegners nicht; das Programm Libratus (2017) besiegte trotzdem Profis im Poker zu zweit.

Definition — Expectiminimax

Sei Γ = (S, s₀, Spieler, A, T, K, U) ein endliches Spiel wie in der Definition des Zweipersonenspiels, nur kommt zu den Spielern MAX und MIN der „Spieler“ ZUFALL hinzu: Spieler : S ∖ K → {MAX, MIN, ZUFALL}, und die Bedingung des abwechselnden Ziehens wird nicht verlangt. Für jeden Zustand s mit Spieler(s) = ZUFALL ist A(s) eine endliche nichtleere Menge möglicher Zufallsergebnisse r (etwa Augenzahlen eines Würfels), und es ist eine Wahrscheinlichkeitsverteilung P_s : A(s) → [0, 1] mit ∑_{r ∈ A(s)} P_s(r) = 1 gegeben (siehe den Teil über Wahrscheinlichkeit); das Ergebnis r tritt mit der Wahrscheinlichkeit P_s(r) ein und führt in den Zustand T(s, r).

Der Expectiminimax-Wert ist die Funktion EMM : S → ℝ, rekursiv definiert:

1. EMM(s) = U(s), falls s ∈ K;
2. EMM(s) = max_{a ∈ A(s)} EMM(T(s, a)), falls Spieler(s) = MAX;
3. EMM(s) = min_{a ∈ A(s)} EMM(T(s, a)), falls Spieler(s) = MIN;
4. ist Spieler(s) = ZUFALL, so ist EMM(s) der Erwartungswert der Werte der Nachfolger: EMM(s) = ∑_{r ∈ A(s)} P_s(r) · EMM(T(s, r)).

In MAX- und MIN-Knoten wird der Wert also wie bei Minimax berechnet und in Zufallsknoten als Durchschnitt, gewichtet mit den Wahrscheinlichkeiten der Ergebnisse. Aufschlüsselung der letzten Formel (P_s kurz als P):

EMM(s) = ∑_r P(r) · EMM(T(s, r))

EMM(s)

der Wert eines Zufallsknotens — was MAX von der Stellung im Durchschnitt erwarten kann, denn das Ergebnis des Wurfs beeinflusst weder er noch der Gegner

∑_r

über alle möglichen Zufallsergebnisse; statt das Beste (max) oder Schlechteste (min) auszuwählen, wird hier nichts ausgewählt — jedes wird mitgezählt

P(r)

die Wahrscheinlichkeit des Ergebnisses als Gewicht: Ein häufiges Ergebnis beeinflusst den Wert stärker als ein seltenes

EMM(T(s, r))

der Wert der Stellung nach dem jeweiligen Ergebnis, rekursiv nach derselben Regel berechnet

Der Gedanke „Schau voraus, bevor du etwas tust“ ist von den Schachbrettern nicht verschwunden. Planende Sprachagenten probieren mehrere Varianten eines Vorgehens aus, bewerten sie und machen mit der vielversprechendsten weiter — nur wählen sie statt Figurenzügen Lösungsschritte.

9. Zusammenfassung

• Ein Zweipersonen-Nullsummenspiel ist ein Suchproblem, bei dem du dir die Züge mit dem Gegner teilst; die Lösung ist eine Strategie, kein Pfad.
• Minimax berechnet den Wert von hinten: MAX nimmt das Maximum, MIN das Minimum. Das Ergebnis ist gegen jeden Gegner garantiert.
• Alpha-Beta liefert denselben Wert, schneidet aber Äste ab, die das Ergebnis nicht ändern können; mit guter Zugreihenfolge schaut es doppelt so tief voraus.
• Große Spiele werden bis zu einer begrenzten Tiefe mit einer Bewertungsfunktion durchsucht — und Vorsicht vor dem Horizonteffekt.
• MCTS spielt eine Stellung statt sie zu bewerten viele Male zufällig zu Ende und baut den Baum dort aus, wo es vielversprechend ist; mit neuronalen Netzen wurde daraus AlphaGo.

Willst du es selbst ausprobieren? Lass einen KI-Agenten Tic-Tac-Toe mit Minimax schreiben und zähle dann, wie viele Stellungen Alpha-Beta einspart, wenn du die Züge von der Mitte zu den Rändern sortierst.

Siehst du das anders? Schreib an support@coden-app.com.