2.3 Spielbäume: Minimax, α-β & MCTS

Worum geht’s#

Die Suchverfahren des vorigen Themas planen gegen eine passive Welt: Das Labyrinth wehrt sich nicht, der Graph ändert sich nicht, während ich ihn durchsuche. Spiele kippen genau diese Annahme. Zwischen meine Züge schiebt sich ein Gegner, der mit derselben Sorgfalt das Gegenteil von dem will, was ich will. Ein Plan ist nur dann etwas wert, wenn er auch gegen die beste gegnerische Antwort hält — und genau diese Verschränkung „ich maximiere, du minimierst” ist der Kern dieses Kapitels.

Mich fasziniert an Spielbäumen, dass eine fast triviale Idee — nimm an, der Gegner spielt optimal — eine vollständige, beweisbar optimale Spielstrategie liefert, und dass die ganze restliche Forschungsgeschichte ein einziger Kampf gegen die kombinatorische Explosion ist. Tic-Tac-Toe lässt sich noch vollständig durchrechnen; Schach hat geschätzte $10^{40}$ Stellungen, Go noch weit mehr. Drei Werkzeuge gegen diese Wand strukturieren die Seite: das α-β-Pruning, das ganze Teilbäume beweisbar überspringt; die Bewertungsfunktion mit Tiefenbegrenzung, die rät, wo Rechnen unmöglich wird; und die Monte-Carlo-Tree-Search, die statt vollständiger Suche das Spielende zufällig ausstichprobt — der Sprung von Deep Blue zu AlphaGo.

Kernkonzepte#

Nullsummenspiel und der Minimax-Wert#

Wir betrachten deterministische Zwei-Personen-Nullsummenspiele mit vollständiger Information: kein Zufall, kein verstecktes Wissen, und was der eine gewinnt, verliert der andere. Der Gewinn des einen Spielers ist also exakt das Negative des anderen — deshalb genügt eine Zahl pro Endstellung, aus Sicht des Spielers MAX. Sein Gegner MIN versucht, dieselbe Zahl klein zu halten.

Der Minimax-Wert ist mehr als eine Zahl: Er ist die optimale Strategie. An jedem MAX-Knoten wählt man das Kind mit dem höchsten Minimax-Wert — das ist der Zug, der den garantierten Ausgang unter optimalem Gegenspiel maximiert. Der Algorithmus ist eine Tiefensuche (Thema 2.2), nur dass sich die Auswahlvorschrift je Ebene abwechselt.

α-β-Pruning: dasselbe Ergebnis, weniger Arbeit#

Das teure an Minimax ist, dass es alle Blätter besucht — bei Verzweigungsgrad $b$ und Tiefe $d$ sind das $b^d$. Die zentrale Beobachtung des α-β-Prunings ist, dass man viele Teilbäume gar nicht ansehen muss, weil sie das Endergebnis nicht mehr ändern können. Man führt zwei Schranken mit:

• $\alpha$ — der beste (höchste) Wert, den MAX auf dem Weg zur Wurzel schon sicher erreichen kann;
• $\beta$ — der beste (niedrigste) Wert, den MIN schon sicher erreichen kann.

Der Gewinn hängt entscheidend von der Zugreihenfolge ab. Im ungünstigsten Fall spart α-β nichts; bei idealer Sortierung (beste Züge zuerst) sinkt der Aufwand von $O(b^d)$ auf $O(b^{d/2})$ — man kann also bei gleichem Zeitbudget doppelt so tief suchen. Die interaktive Insel zeigt beides: Erst läuft reines Minimax über alle Blätter, dann schaltet man α-β zu und sieht, wie ganze Teilbäume grau werden, während der Wurzelwert sich nicht rührt.

Tiefenbegrenzung, Bewertungsfunktion und der Horizont#

Bei echten Spielen ist der Baum viel zu groß, um ihn bis zu den Endstellungen auszurechnen. Die Standardlösung ist ein Cutoff: Man sucht nur bis zu einer festen Tiefe und ersetzt die fehlenden Blattwerte durch eine statische Bewertungsfunktion $\text{Eval}(s)$, die eine Stellung schätzt, ohne weiterzurechnen — beim Schach etwa als gewichtete Summe von Materialwert, Königssicherheit und Mobilität. Aus exakter Optimalität wird damit eine Heuristik: Die Qualität des Spielers steht und fällt mit der Bewertungsfunktion. Die Folien beziffern den Effekt am Schach nur grob: Schon bei $b = 35$ wächst die Zahl der Knoten extrem schnell ($35^4 \approx 1{,}5$ Mio. für vier Halbzüge). Ein typisches Programm schafft laut Folie etwa 8 Halbzüge (Master-Niveau), Deep Blue rechnete etwa 12 Halbzüge voraus.

Diese Abkürzung handelt sich ein berüchtigtes Problem ein, den Horizont-Effekt: Eine Katastrophe, die genau einen Zug hinter der Suchtiefe liegt, bleibt unsichtbar, und der Spieler hält eine in Wahrheit verlorene Stellung für gut. Abhilfen sind die Ruhesuche (an „unruhigen” Stellungen, etwa mitten in einem Schlagabtausch, wird selektiv tiefer gesucht) und die iterative Tiefensuche, die die Tiefe schrittweise erhöht und so unter Zeitdruck stets ein verwertbares Zwischenergebnis hat.

Monte-Carlo-Tree-Search und AlphaZero#

Wo sich keine gute Bewertungsfunktion von Hand bauen lässt — der Klassiker ist Go —, ersetzt Monte-Carlo-Tree-Search (MCTS) das Bewerten durch Ausprobieren. Statt eines vollständigen Baums wächst ein asymmetrischer Suchbaum, der vier Schritte wiederholt:

1. Selektion — von der Wurzel an einem Pfad entlang absteigen, dabei an jedem Knoten das Kind nach UCB1 wählen: $$\text{UCB1}(c) = \underbrace{\frac{w_c}{n_c}}_{\text{Ausbeutung}} + c_{\text{p}}\underbrace{\sqrt{\frac{\ln N}{n_c}}}_{\text{Erkundung}};$$ der erste Term bevorzugt bisher erfolgreiche Züge (Ausbeutung), der zweite selten besuchte (Erkundung) — das klassische Explore/Exploit-Dilemma.
2. Expansion — am Pfadende einen neuen Kindknoten anlegen.
3. Simulation — von dort aus mit Zufallszügen bis zum Spielende „ausrollen” (Rollout) und das Ergebnis ablesen.
4. Backpropagation — Gewinn/Verlust entlang des besuchten Pfades zurück zur Wurzel buchen ($n_c$, $w_c$ erhöhen).

Nach vielen Iterationen wählt man den meistbesuchten Wurzelzug. MCTS braucht keine Stellungsbewertung und konzentriert seine Rechenzeit dort, wo es spannend wird. AlphaZero treibt das auf die Spitze: Statt zufälliger Rollouts liefert ein neuronales Netz Zugwahrscheinlichkeiten und Stellungswert für die MCTS-Suche, und dieses Netz lernt ausschließlich aus Selbstspiel — ein direkter Brückenschlag zum bestärkenden Lernen (Thema 6.1).

Praxis#

Aufgabe 1 (Blatt 5) — der Minimax-Baum#

(a) Bedeutung der Zahlen. Die Blattwerte sind der Nutzen der jeweiligen Endstellung aus Sicht von MAX: ein großer Wert ist gut für MAX, ein kleiner (negativer) gut für MIN. Plausibel interpretiert etwa als Punktedifferenz oder als Bewertung eines Spielausgangs — $+9$ ein klarer Sieg für MAX, $-9$ ein klarer Sieg für MIN, $0$ ausgeglichen. Die Zahlen an den inneren Knoten sind keine Eingabe, sondern das Ergebnis der Minimax-Propagation: der Wert, der bei beidseitig optimalem Spiel ab diesem Knoten erreicht wird.

(b) Minimax-Bewertung. Von unten nach oben (Ebenen Blätter → MIN → MAX → MIN → MAX-Wurzel):

• MIN-Ebene (Tiefe 3): $\min(9,6)=6$, $\min(4,7)=4$, $\min(7,6)=6$, $\min(1,-9)=-9$, $\min(1,9)=1$, $\min(0,-4)=-4$, $\min(4,-1)=-1$, $\min(2,-3)=-3$.
• MAX-Ebene (Tiefe 2): $\max(6,4)=6$, $\max(6,-9)=6$, $\max(1,-4)=1$, $\max(-1,-3)=-1$.
• MIN-Ebene (Tiefe 1): $\min(6,6)=6$, $\min(1,-1)=-1$.
• MAX-Wurzel: $\max(6,-1)=\mathbf{6}$.

Der Wurzelwert ist 6. Das Skript unten rechnet dies nach und bricht per assert ab, falls es nicht 6 wäre.

(c) Sichere Gewinnstrategie. Der Wurzelwert 6 ist positiv — MAX kann sich unabhängig vom Gegenspiel einen Ausgang von mindestens $6$ garantieren. MAX zieht an der Wurzel nach links (dort steht 6, rechts nur $-1$). Antwortet MIN mit seinem besten Zug, landet man wieder bei einem MAX-Knoten mit Wert 6, von dem aus MAX erneut den Wert-6-Zweig wählt. Ob das ein „Gewinn” ist, hängt davon ab, wo die Gewinnschwelle liegt: Ist $6$ ein Sieg, hat MAX eine sichere Gewinnstrategie; ist nur $\ge 9$ ein Sieg, garantiert MAX zumindest ein deutlich positives Ergebnis. MIN hat keine Strategie, die MAX unter $6$ drückt.

(d) Aufwand bei binärem Baum der Tiefe $d$. Ein vollständiger binärer Baum der Tiefe $d$ hat $2^d$ Blätter und $2^{d+1}-1$ Knoten insgesamt. Minimax besucht jeden Knoten genau einmal, also $O(2^d)$ Blattauswertungen bzw. $O(2^{d+1})$ Knotenbesuche. Allgemein bei Verzweigungsgrad $b$: $O(b^d)$ Blätter — exponentiell in der Tiefe. Für unseren konkreten Baum ($b=2$, $d=4$): $2^4 = 16$ Blätter.

(e) α-β-Pruning. Ich werte von links nach rechts mit $\alpha=-\infty,\ \beta=+\infty$. Die wesentlichen Schnitte:

• Linker Wurzelteilbaum, erster MAX-Knoten: $\min(9,6)=6 \Rightarrow \alpha=6$. Beim Geschwister $\min(4,\dots)$ liefert schon die $4$ einen MIN-Wert $\le 4 < 6=\alpha$ → α-Schnitt, die $7$ wird übersprungen. MAX-Knoten $=6$.
• Im linken MIN-Knoten ist damit $\beta=6$. Der zweite MAX-Knoten erreicht über $\min(7,6)=6$ den Wert $6=\beta$ → β-Schnitt, der Teilbaum mit $1,-9$ entfällt. Linker Wurzelteilbaum $=6$, also $\alpha=6$ an der Wurzel.
• Rechter Wurzelteilbaum, MIN-Knoten mit $\alpha=6$: Der erste MAX-Knoten liefert über $\min(1,\dots)$ schon nach der $1$ einen α-Schnitt (die $9$ entfällt), ebenso über $\min(0,\dots)$ (die $-4$ entfällt), Wert $\max(1,0)=1$. Da $1 \le 6=\alpha$, α-Schnitt am MIN-Knoten → der gesamte zweite MAX-Teilbaum ($4,-1,2,-3$, vier Blätter) entfällt.

Übersprungen werden so $7,\;1,-9,\;9,\;-4,\;$ und $4,-1,2,-3$ — neun Blätter. Ausgewertet werden 7 von 16 Blättern, der Wurzelwert bleibt 6.

(f) Aufwandsvergleich. Reines Minimax wertet $16$ Blätter aus, α-β nur $7$ — eine Ersparnis von $9$ Blättern bzw. $56\,\%$, ohne das Ergebnis zu verändern. Im Idealfall (beste Züge zuerst) reduziert α-β den Aufwand von $O(b^d)$ auf $O(b^{d/2})$; der konkrete Baum liegt hier dank günstiger Reihenfolge nahe an diesem besten Fall.

(g) Schnellster Sieg. Der reine Minimax-Wert sagt nur ob, nicht wie schnell MAX gewinnt — mehrere Pfade können zum selben Wert führen. Wer den Sieg in möglichst wenigen Zügen will, macht die Tiefe zum Teil des Nutzens: Man zieht für gewinnende Endstellungen die Distanz ab (z. B. Nutzen $= W - \text{Tiefe}$), sodass unter gleich guten Gewinnen der flachere bevorzugt wird. Genau so erzwingt man in Endspielen das schnellste Matt; symmetrisch lohnt es sich, eine verlorene Stellung möglichst lange hinauszuzögern.

(h) Praxisprobleme. (i) Der Baum explodiert exponentiell — vollständige Suche ist außer bei winzigen Spielen unmöglich; man begrenzt die Tiefe und bewertet Zwischenstellungen heuristisch. (ii) Damit handelt man sich den Horizont-Effekt ein (Bedrohungen knapp jenseits der Suchtiefe bleiben unsichtbar) — Gegenmittel sind Ruhesuche und iterative Tiefensuche. (iii) Die Bewertungsfunktion ist schwer zu entwerfen und entscheidet über die Spielstärke. (iv) Selbst α-β bleibt exponentiell; bei Spielen wie Go versagt der Ansatz und man weicht auf MCTS aus.

Aufgabe 2 (Blatt 5) — Tic-Tac-Toe#

(a) Sichere-Niederlage-Knoten. Der Schlüssel ist Mins Drohung: $O$ steht auf Feld $1$ und $4$ und droht, mit Feld $7$ die Mittelspalte $1$–$4$–$7$ zu vollenden. MAX hat fünf mögliche Züge (Felder $3,5,6,7,8$). Statt den ganzen Baum aufzurollen, expandiere ich gezielt diese Knoten und lasse Minimax die Pfade bewerten:

=== Aufgabe 2a — gegebene Stellung (X O X / . O . / . . .), Max am Zug ===
  X auf Feld 3: Minimax = -1 (NIEDERLAGE)  (O kontert bei Feld 7 -> Spalte 1-4-7)
  X auf Feld 5: Minimax = -1 (NIEDERLAGE)  (O kontert bei Feld 7 -> Spalte 1-4-7)
  X auf Feld 6: Minimax = -1 (NIEDERLAGE)  (O kontert bei Feld 7 -> Spalte 1-4-7)
  X auf Feld 7: Minimax = +0 (Remis)
  X auf Feld 8: Minimax = -1 (NIEDERLAGE)  (O kontert bei Feld 7 -> Spalte 1-4-7)
  -> Sichere Niederlage bei Zügen [3, 5, 6, 8]; einziger rettender Zug: [7].

Vier der fünf Züge ($3,5,6,8$) tragen den Minimax-Wert $-1$: Spielt MAX einen davon, vollendet $O$ im nächsten Halbzug die Spalte $1$–$4$–$7$ und gewinnt — das sind die sicheren Niederlage-Knoten. Nur das Blocken auf Feld 7 wendet die Niederlage ab; sein Minimax-Wert ist $0$ (Remis), kein Sieg. MAX kann aus dieser Stellung also bestenfalls noch ein Unentschieden retten, und das auch nur über den einzigen Zug, der Mins Drohung pariert.

(b) MCTS bei Tic-Tac-Toe. Tic-Tac-Toe ist klein genug für exaktes Minimax, MCTS wäre hier überdimensioniert — aber es illustriert das Verfahren gut: Statt den Baum vollständig zu bewerten, schätzt MCTS den Wert eines Zugs durch viele zufällige Partien („Rollouts”) bis zum Spielende und bevorzugt dann den Zug mit der besten Stichproben-Bilanz. Der Vier-Phasen-Zyklus:

Vollständiges Minimax als Gegenprobe. Weil der Baum mit höchstens $9! = 362\,880$ Zugfolgen winzig ist, habe ich Tic-Tac-Toe zusätzlich komplett gelöst: Das Skript bewertet das leere Brett und spielt von jeder X-Eröffnung aus optimal gegen optimal. Der Spielwert ist $0$, über alle neun Eröffnungen gibt es ausschließlich Remis — MAX verliert in keiner Variante. Das bestätigt die Schulhof-Weisheit formal und ordnet die obige Stellung ein: Sie ist nur deshalb für MAX verloren bzw. bestenfalls remis, weil MAX zuvor suboptimal gespielt hat (zwei Ecken statt der Drohungsabwehr).

Aufgabe 3 (Blatt 5) — 4 Gewinnt#

(b) Suchbaumgröße. Klassisches 4-Gewinnt verwendet ein $7 \times 6$-Gestell. Spätestens nach $42$ Zügen ist das Spiel zu Ende, der Suchbaum also endlich; mit höchstens $7$ Spalten pro Halbzug ergibt sich als grobe obere Schranke ein Baum mit weniger als $7^{42}$ Knoten. (c) Der tatsächliche Baum ist viel kleiner, weil Spalten sich füllen und ausfallen (der Verzweigungsgrad sinkt von 7 gegen 0), weil viele Partien vorzeitig durch einen Vierer enden, und weil α-β plus identische Stellungen (Transpositionen) große Teile abschneiden. Laut der Analyse von James D. Allen (1990, auf den Folien zitiert) hat MAX bei perfektem Spiel sogar eine sichere Gewinnstrategie, wenn er den ersten Stein in die mittlere Spalte wirft, ein Remis bei der 3. oder 5. Spalte und verliert bei den Randspalten. (d) Zwei Heuristiken für die $\text{Eval}$ bei nur 4 Halbzügen Tiefe:

• $h_1$ — gewichtete Drohungszählung: Zähle die offenen Dreierreihen (drei eigene Steine plus freies, erreichbares viertes Feld) abzüglich der gegnerischen, mit höherem Gewicht als Zweierreihen. Eine offene Drei ist eine direkte Gewinndrohung — die wichtigste taktische Information, die bei flacher Suche sonst hinter dem Horizont läge.
• $h_2$ — Feldgewichtung nach Linienpotenzial: Bewerte jeden eigenen Stein nach der Zahl der noch vollendbaren Viererlinien durch sein Feld. Die mittlere Spalte liegt in den meisten Linien und ist deshalb am wertvollsten; diese Heuristik lenkt das Spiel früh ins Zentrum, ohne tief rechnen zu müssen.

Beide sind billig auszuwerten (nur Linien zählen) und damit auf einem schwachen Prozessor tragbar — genau die Bedingung der Aufgabe.

Lauffähiger Code#

Der Kern ist α-β mit einem Blattzähler — eine einzige Zeile (break) trennt es von reinem Minimax:

def alphabeta(node, is_max, alpha, beta, counter):
    if isinstance(node, int):        # Blatt
        counter[0] += 1
        return node
    if is_max:
        value = -math.inf
        for c in node:
            value = max(value, alphabeta(c, False, alpha, beta, counter))
            alpha = max(alpha, value)
            if beta <= alpha:
                break                # β-Schnitt: restliche Geschwister egal
        return int(value)
    else:
        value = math.inf
        for c in node:
            value = min(value, alphabeta(c, True, alpha, beta, counter))
            beta = min(beta, value)
            if beta <= alpha:
                break                # α-Schnitt
        return int(value)

Das vollständige Skript (Baum aus der Blattliste, Tic-Tac-Toe-Minimax, Selbstspiel, Grafiken) liegt in python/src/eport_figures/praxis/p_2_3_spielbaeume.py. Seine Ausgabe:

=== Aufgabe 1 — Blatt-5-Minimax-Baum ===
  Blattwerte (v.l.n.r.): [9, 6, 4, 7, 7, 6, 1, -9, 1, 9, 0, -4, 4, -1, 2, -3]
  Minimax-Wurzelwert     = 6  (Handrechnung: 6)
  α-β-Wurzelwert         = 6  (muss identisch sein)
  Ausgewertete Blätter  ohne Pruning: 16 / 16
  Ausgewertete Blätter  mit  α-β    : 7 / 16
  -> 9 Blätter gespart (56 %).

=== Aufgabe 2 — Tic-Tac-Toe, vollständiges Minimax ===
  Spielwert leeres Brett (X=MAX am Zug): 0  (Remis)
  Optimaler Eröffnungszug: Feld 0
  Selbstspiel optimal-gegen-optimal über alle 9 Eröffnungen von X:
    X gewinnt: 0
    Remis: 9
    O gewinnt: 0
  -> X (Minimax) verliert in keiner Eröffnung; durchweg Remis bei beidseitig optimalem Spiel.

Die assert-Anweisungen im Skript machen es zu einem selbstprüfenden Beweis: weicht der Wurzelwert von 6 ab oder verliert X auch nur eine Partie, bricht der Lauf ab. Beides tritt nicht ein.

Aufgabe 4 (Blatt 5) — ein Monte-Carlo-Spieler für 4 Gewinnt#

(a) Aufbau des MCTS-Spielers. Ich habe einen vollständigen UCT-Spieler (MCTS mit UCB1-Selektion) für das $7\times6$-Gestell in Python gebaut — kein gefundener Code, sondern eine eigene, getestete Implementierung. Die vier Phasen aus 2b, hier als lauffähiger Kern:

def mcts_zug(b, spieler, sims, rng, cp=1.4):
    wurzel = _MCTSNode(b, spieler)
    for _ in range(sims):
        node = wurzel
        while not node.untried and node.kinder:          # 1) Selektion (UCB1)
            node = max(node.kinder.values(),
                       key=lambda k: k.W/k.N + cp*sqrt(log(node.N)/k.N))
        if node.untried:                                  # 2) Expansion
            m = rng.choice(node.untried); node.untried.remove(m)
            node = node.kinder.setdefault(m, _MCTSNode(c4_drop(node.b, m, node.spieler),
                                                       3 - node.spieler, node))
        sieger = c4_gewinner(node.b) or _c4_rollout(node.b, node.spieler, rng)  # 3) Simulation
        while node is not None:                           # 4) Backpropagation
            node.N += 1
            node.W += 1.0 if sieger == 3 - node.spieler else 0.5 if sieger == 0 else 0.0
            node = node.parent
    return max(wurzel.kinder.items(), key=lambda kv: kv[1].N)[0]   # meistbesucht

Wichtig ist die Buchung: In jedem Knoten zähle ich Siege aus Sicht des Spielers, der den Zug zu dieser Stellung gemacht hat — sonst optimiert die Selektion die falsche Seite. Den vollständigen Code (Brett, Gewinnprüfung, Rollout, UCT, ein tiefenbegrenztes α-β-Minimax als klassischer Gegner) findet man in python/src/eport_figures/praxis/p_2_3_spielbaeume.py.

Testläufe. Ich habe den MCTS-Spieler gegen zwei Gegner antreten lassen (Anziehender wird je Spiel getauscht, fester Zufalls-Seed für Reproduzierbarkeit):

=== Aufgabe 4 — Monte-Carlo-Spieler (MCTS/UCT) für 4 Gewinnt ===
  MCTS(200 Sim.) vs. Zufall  (30 Spiele): MCTS 30 : 0 Zufall, 0 Remis  -> Siegquote 100%
  MCTS(300 Sim.) vs. Minimax(Tiefe 2) (16 Spiele): MCTS 6 : 10 Minimax  -> Siegquote 38%
  Siegquote vs. Zufall je Simulationszahl: 10->83%, 30->100%, 100->100%, 300->100%

Der zweite Befund ist ehrlich und lehrreich: In einem taktisch scharfen Spiel wie 4 Gewinnt, in dem jeder unmittelbare Vierer sofort entscheidet, schlägt ein flaches, aber exaktes α-β (das jeden Ein-Zug-Sieg und jede Ein-Zug-Drohung garantiert sieht) einen MCTS mit moderatem Budget. MCTS müsste hier deutlich mehr Rollouts (oder ein gelerntes Bewertungsnetz wie AlphaZero) bekommen, um gleichzuziehen. Genau das ist die Pointe der Folien: MCTS spielt seine Stärke dort aus, wo sich keine gute Bewertungsfunktion bauen lässt (Go), nicht in kleinen, taktisch exakt durchrechenbaren Spielen.

(b) Klassische Suche vs. MCS — der wesentliche Unterschied. Klassisches Minimax/α-β ist erschöpfend und exakt: Es baut den Baum bis zur Cutoff-Tiefe vollständig auf und braucht eine Bewertungsfunktion, die jede Nicht-Endstellung beziffert; seine Spielstärke steht und fällt mit dieser handgebauten Heuristik. MCS/MCTS ist stichprobenbasiert und asymmetrisch: Es baut den Baum selektiv dort tiefer, wo es nach UCB1 aussichtsreich ist, und ersetzt die Bewertungsfunktion durch viele Zufalls-Rollouts bis zum echten Spielende — es braucht also gar keine Stellungsbewertung, nur die Spielregeln. Klassische Suche investiert ihr Budget gleichmäßig und garantiert (innerhalb der Tiefe) Optimalität; MCTS investiert es ungleich und liefert eine statistische Schätzung, die mit der Zahl der Simulationen gegen den wahren Wert konvergiert (vgl. den $1/\sqrt{n}$-Verlauf rechts).

Querbezüge#

• 2.2 (Suchverfahren): Minimax ist eine Tiefensuche; es erbt deren Speichervorteil ($O(bd)$ statt $O(b^d)$) und tauscht nur die Knotenauswahl gegen das abwechselnde max/min. Die iterative Tiefensuche aus dem Schach kommt direkt aus 2.2.
• 2.4 (CSP): Beide Themen leben vom Beschneiden des Suchraums — der α-β-Schnitt ist der Spiel-Verwandte des Constraint-Propagierens, das bei CSP inkonsistente Wertzuweisungen früh ausschließt.
• 6.1 (Reinforcement Learning): Hier schließt sich der Kreis. AlphaZero ersetzt die handgebaute Bewertungsfunktion durch ein Netz, das aus Selbstspiel lernt — genau das Self-Play-Prinzip des bestärkenden Lernens. UCB1 in MCTS ist dieselbe Explore/Exploit-Abwägung wie bei den Multi-Armed-Bandits dort.
• Spieltheorie / Mikroökonomie: Der Minimax-Wert eines Nullsummenspiels ist exakt der Gleichgewichtswert aus von Neumanns Minimax-Theorem (1928) — die Informatik berechnet hier, was die Spieltheorie als Existenz beweist.
• Algorithmen & Datenstrukturen: Die rekursive Baumtraversierung, der Branch-and-Bound-Charakter von α-β und die Komplexitätsanalyse $O(b^d)$ vs. $O(b^{d/2})$ sind klassisches AuD-Material.
• Stochastik / Numerik: MCTS ist eine Monte-Carlo-Methode — Schätzen eines Erwartungswerts durch Stichproben, mit derselben $1/\sqrt{n}$-Konvergenz wie bei der Monte-Carlo-Integration.

Quellen#

• Foliensatz _230_GameSearch.pdf („Suchverfahren für Strategiespiele”) — Grundlage für Notation (MAX/MIN, α-β-Schranken), die durchgerechneten Beispiele (NIM, Tic-Tac-Toe, 4-Gewinnt) und den Aufbau von Minimax zu MCTS. Die Folien führen die Verfahren sauber ein; die kritische Einordnung (Horizont-Effekt, Self-Play als Brücke zu Kapitel 6) habe ich ergänzt.
• Übungsblatt 5 ki_ueb230_GameSearch.pdf — Quelle der gelösten Aufgaben. Die Blattwerte und die α-β-Schnitte habe ich per Code gegengerechnet, um die Handrechnung abzusichern.
• Russell & Norvig, Artificial Intelligence: A Modern Approach, Kap. 5 („Adversarial Search”) — als Referenz für die präzise Formulierung des α-β-Theorems und der Ruhesuche konsultiert.
• von Neumann (1928), Zur Theorie der Gesellschaftsspiele (Mathematische Annalen) — die Primärquelle des Minimax-Theorems, das den in den Querbezügen erwähnten Gleichgewichtswert begründet.
• Silver et al., Mastering the game of Go without human knowledge (Nature 2017, AlphaGo Zero) und das AlphaZero-Paper (Science 2018) — überflogen für das Zusammenspiel von MCTS und neuronalem Netz; Beleg, dass MCTS + Self-Play handgebaute Bewertungsfunktionen überflüssig machen kann.
• Allis (1988), A Knowledge-based Approach of Connect-Four — die kanonische akademische Quelle für die gelöste 4-Gewinnt-Stellung (Sieg des Anziehenden bei Mittelspalten-Eröffnung), unabhängig zeitgleich auch von James D. Allen gelöst, auf den sich die Folien beziehen.
• Das interaktive Tic-Tac-Toe (JS) habe ich ausprobiert, um die Remis-Aussage von Aufgabe 2 spielerisch zu prüfen, bevor ich sie per Minimax bewiesen habe.