MinMax & Pruning
MinMax in der Praxis: rückwärts denken, vom schlimmsten Gegner ausgehen, abkürzen wo möglich.
1997 besiegte IBMs Deep Blue den amtierenden Schachweltmeister Garry Kasparov. Die Maschine verstand Schach nicht — sie bewertete 200 Millionen Stellungen pro Sekunde mit einer Idee, die auf Arbeiten von Ernst Zermelo (1913) und John von Neumann (1928) zurückgeht. Diese Idee ist der MinMax-Algorithmus, und er bildet bis heute die Grundlage klassischer Spiel-KI.
Deep Blue besiegt Kasparov
Der erste Matchsieg einer Maschine über einen amtierenden Schachweltmeister unter Turnierbedingungen. Am 11. Mai 1997 schrieb Deep Blue Geschichte, als der IBM-Supercomputer Garry Kasparov im Revanche-Match in New York mit 3½:2½ besiegte. Nach der 1996er-Niederlage hatte IBM das System grundlegend überarbeitet: mehr als doppelt so viele, verbesserte Schachchips verdoppelten die Geschwindigkeit auf 200 Millionen Positionen pro Sekunde, verbesserte Endspieldatenbanken und Großmeister-Beratung verfeinerten die Spielstärke. Das entscheidende sechste Spiel dauerte nur eine Stunde – nach einem Springeropfer geriet Kasparov rasch in eine objektiv verlorene Stellung und gab bereits im 19. Zug auf, ein beispielloser Moment in seiner Karriere. Der Sieg demonstrierte erstmals die Überlegenheit von Computern in komplexem strategischem Denken und markierte einen Wendepunkt für die öffentliche KI-Wahrnehmung. Das Preisgeld von 700.000 Dollar für Deep Blue unterstrich die historische Bedeutung dieses Triumphs der Maschinenintelligenz.
In diesem Artikel lernst du, wie ein Computer systematisch alle Züge durchdenkt, den optimalen Zug gegen einen perfekten Gegner findet und dabei ganze Teilbäume überspringt, ohne das Ergebnis zu verändern.
Der Spielbaum — Alle Möglichkeiten durchdenken
Definition
Spielbaum (Game Tree)
Analogie
Definition
Der Vergleich hat eine wichtige Grenze: Menschen überspringen intuitiv Varianten und denken nur vielversprechende Züge durch. Der Algorithmus dagegen baut den Baum bis zur gewählten Tiefe systematisch und vollständig auf — er "vergisst" nichts.
Ein konkretes Beispiel: Bei Tic-Tac-Toe hat MAX zu Beginn 9 mögliche Züge. Für jeden davon hat MIN 8 Antworten. Bereits nach nur zwei Halbzügen enthält die zweite Ebene des Baums 72 Knoten. Bei Schach mit einem Verzweigungsfaktor von etwa 35 und einer Tiefe von rund 80 Halbzügen gibt es mehr mögliche Partieverläufe als Atome im Universum.
Verzweigungsfaktor Schach
~35
Durchschnittliche legale Züge pro Stellung
Mögliche Schachstellungen
~10 ⁴⁵
Legale Stellungen; mögliche Partien sogar über 10¹²⁰ — mehr als Atome im Universum
Achtung
Irrtum: Der Computer spielt jedes Spiel bis zum Ende durch
Bei großen Spielen wie Schach ist das in der Praxis unmöglich. Stattdessen verwendet man ein Tiefenlimit und eine heuristische Bewertungsfunktion. Bei Schach zählt diese zum Beispiel den Materialwert der Figuren. Der Baum wird also nie vollständig aufgebaut — die Bewertungsfunktion schätzt die Qualität einer Stellung ab, ohne das Spiel tatsächlich zu Ende zu spielen.
Der MinMax-Algorithmus — Optimal gegen den perfekten Gegner
Definition
MinMax-Algorithmus
Analogie
Definition
Die Analogie ist korrekt: MinMax denkt pessimistisch. Aber gegen schwächere Gegner kann diese Vorsicht dazu führen, dass ausnutzbare Schwächen des Gegners übersehen werden.
Merke
MinMax-Berechnung: Schritt für Schritt
- 1. Ganz unten im Baum stehen die Ergebnisse: [3, 5], [6, 9], [1, 2], [0, -1]. Das sind die Bewertungen, wenn das Spiel zu Ende gespielt wird.
- 2. An den unteren Knoten sind wir (MAX) dran. Wir wählen jeweils das Bessere: max(3,5) = 5, max(6,9) = 9, max(1,2) = 2, max(0,-1) = 0.
- 3. Jetzt ist der Gegner dran (MIN). Er will uns schaden und gibt uns immer das Schlechteste: Links wählt er min(5,9) = 5, rechts min(2,0) = 0. Rechts bekämen wir also nur 0 Punkte.
- 4. Zurück bei uns (MAX): Links sicher 5 Punkte, rechts nur 0. max(5, 0) = 5 — wir gehen nach links.
Der Algorithmus wählt den linken Teilbaum mit dem garantierten Wert 5. Egal wie der Gegner spielt — schlechter als 5 kann es für MAX nicht werden.
Laufzeit MinMax
O(bᵈ)
b = Verzweigungsfaktor, d = Suchtiefe. Exponentielles Wachstum macht reines MinMax für komplexe Spiele unbrauchbar.
Achtung
Irrtum: MinMax findet immer den besten Zug
MinMax garantiert den optimalen Zug nur unter drei Bedingungen: (1) der Gegner spielt perfekt, (2) es handelt sich um ein Nullsummenspiel mit perfekter Information (der Gewinn des einen ist der Verlust des anderen, und beide Spieler sehen alle Informationen — wie bei Schach, aber nicht bei Poker), und (3) der Baum wird bis zur ausreichenden Tiefe durchsucht. Gegen imperfekte Gegner können aggressivere Strategien besser sein. Bei unzureichender Suchtiefe hängt die Qualität von der heuristischen Bewertungsfunktion ab.
Interaktiv: MinMax-Spielbaum
Im Artikel wird beschrieben, wie MinMax Bewertungen von den Blättern nach oben propagiert. Hier kannst du den Algorithmus Schritt für Schritt durchspielen und sehen, wie MAX und MIN ihre Entscheidungen treffen.
Die Blattknoten zeigen die Spielergebnisse. Das sind die Bewertungen, wenn das Spiel zu Ende gespielt wird.
Alpha-Beta Pruning — Klug abschneiden
Definition
Alpha-Beta Pruning
Analogie
Definition
Die Jobanalogie zeigt einen einfachen Vergleich. Im Spielbaum sind die Bewertungen verschachtelt — aber das Kernprinzip "aufhören, wenn es nachweislich schlechter wird" ist identisch.
Zurück zu unserem Beispiel: Schon links wird gespart — nach max(3,5) = 5 steht fest, dass MIN höchstens 5 zulässt; sobald der zweite MAX-Knoten die 6 sieht, wird die 9 übersprungen. Danach hat die Wurzel Alpha = 5. Im rechten Teilbaum ergibt der erste MAX-Knoten max(1,2) = 2. Der MIN-Knoten hat jetzt den Kandidaten 2, der bereits kleiner als Alpha = 5 ist (Alpha-Cutoff). Der zweite MAX-Knoten [0, -1] wird gar nicht mehr ausgewertet. Ergebnis: identisch (Zug links, Wert 5), aber mit weniger Berechnungen.
Wertet alle 8 Blattknoten aus. Berechnet jeden einzelnen Pfad im Baum. Garantiert optimales Ergebnis, aber maximaler Rechenaufwand.
Überspringt nachweislich irrelevante Äste. Im Beispiel: 5 statt 8 Blattknoten ausgewertet. Exakt dasselbe Ergebnis, weniger Arbeit.
Alpha-Beta Bestfall
O(bᵈᐟ²)
Effektiv doppelt so tiefe Suche in derselben Zeit. Erreicht durch optimale Zugsortierung.
Deep Blue (1997)
200 Mio./s
Stellungen pro Sekunde. MinMax mit Alpha-Beta auf spezialisierter Hardware.
Achtung
Irrtum: Pruning liefert ein anderes oder ungenaues Ergebnis
Alpha-Beta Pruning liefert exakt dasselbe Ergebnis wie reines MinMax. Es ist keine Näherung — es ist ein mathematischer Beweis, dass bestimmte Teilbäume das Ergebnis nicht beeinflussen können. Der gewählte Zug ist identisch.
1950 veröffentlichte Claude Shannon sein wegweisendes Paper zur Schachprogrammierung — eine der ersten formalen Beschreibungen computergestützter Spielstrategie. 1952 führte Alan Turing sein Schachprogramm mangels Computer in einer Partie von Hand aus. In den folgenden Jahrzehnten wurden MinMax und Alpha-Beta Pruning (formal analysiert von Knuth und Moore, 1975) zum Standardverfahren. Der Höhepunkt: 1997 besiegte Deep Blue, ein IBM-Supercomputer mit spezialisierten Schach-Chips, Garry Kasparov. Fast zwei Jahrzehnte später kam der nächste Durchbruch: 2016 markierte AlphaGo mit Monte Carlo Tree Search und neuronalen Netzen den nächsten Paradigmenwechsel.
Die Effizienz von Alpha-Beta Pruning hängt stark davon ab, in welcher Reihenfolge Züge ausgewertet werden. Werden die besten Züge zuerst betrachtet, schneidet der Algorithmus maximal viele Äste ab — im Bestfall auf die Quadratwurzel der ursprünglichen Laufzeit — das bedeutet effektiv doppelte Suchtiefe in derselben Zeit. Werden die schlechtesten Züge zuerst betrachtet, wird nichts abgeschnitten und Alpha-Beta verhält sich wie reines MinMax. In der Praxis nutzen Schachprogramme die "Killerzug-Heuristik": Züge, die in parallelen Varianten bereits Cutoffs erzeugt haben, werden bevorzugt untersucht.
Merke
Das Wichtigste auf einen Blick
- Ein Spielbaum bildet alle möglichen Zugfolgen ab. MAX-Knoten wählen den höchsten Wert, MIN-Knoten den niedrigsten — so wird der schlimmste Gegner modelliert.
- MinMax garantiert den optimalen Zug gegen einen perfekten Gegner, aber seine exponentielle Laufzeit macht ihn ohne Optimierung für komplexe Spiele unbrauchbar.
- Alpha-Beta Pruning liefert exakt dasselbe Ergebnis wie MinMax, schneidet aber nachweislich irrelevante Äste ab — und ermöglicht so effektiv die doppelte Suchtiefe in derselben Zeit.
Prüfen
Quiz: MinMax & Pruning
Was macht ein MIN-Knoten in einem MinMax-Baum?
Wähle eine Antwort
1. Was macht ein MIN-Knoten in einem MinMax-Baum?
2. Ein MinMax-Baum hat eine Wurzel (MAX) mit zwei Kindern (MIN-Knoten). Die Kinder des linken MIN-Knotens haben die Werte [4, 7]. Die Kinder des rechten MIN-Knotens haben die Werte [2, 9]. Welchen Wert hat die Wurzel?
3. Beim Alpha-Beta Pruning ist Alpha aktuell 6 an einem MAX-Knoten. Ein Kind-MIN-Knoten wertet sein erstes Kind aus und erhält 3. Was passiert?
4. Deep Blue besiegte 1997 Kasparov mit MinMax und Alpha-Beta Pruning. Ein Entwickler argumentiert, dass einfach mehr Suchtiefe immer ein stärkeres Schachprogramm ergibt. Welchen kritischen Faktor übersieht dieses Argument?
Prüfen
Checkpoint: MinMax & Pruning
Kannst du das in eigenen Worten erklären? Hake ab, was sitzt.
0 von 3 sitzen