MinMax in der Praxis: rückwärts denken, vom schlimmsten Gegner ausgehen, abkürzen wo möglich.
Konzepte 8 min Fortgeschritten 26. April 2026
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.
1997 Wettbewerbe
Deep Blue besiegt Kasparov
Der erste Sieg 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: neue 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 – Kasparov resignierte in einer noch spielbaren Stellung, 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
Spielbaum (Game Tree)
AnalogieDefinition
Stell dir zwei Schachspieler vor, die im Kopf vorausdenken: "Wenn ich Zug A mache, wird sie Zug B machen, dann könnte ich Zug C machen..." Diese mentale Kette aus Zügen und Gegenzügen IST der Spielbaum — der Algorithmus baut ihn nur systematisch statt intuitiv auf.
Analogie:
Stell dir zwei Schachspieler vor, die im Kopf vorausdenken: "Wenn ich Zug A mache, wird sie Zug B machen, dann könnte ich Zug C machen..." Diese mentale Kette aus Zügen und Gegenzügen IST der Spielbaum — der Algorithmus baut ihn nur systematisch statt intuitiv auf.
Definition:
Ein Spielbaum ist ein gerichteter Graph, in dem jeder Knoten einen Spielzustand darstellt und jede Kante einen legalen Zug. Spieler wechseln sich ab: MAX-Knoten (der maximierende Spieler) und MIN-Knoten (der minimierende Spieler). Blattknoten tragen Bewertungswerte.
Der Vergleich hat eine wichtige Grenze: Menschen überspringen intuitiv Varianten und denken nur vielversprechende Züge durch. Der Algorithmus dagegen baut den Baum 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 der Baum 72 Knoten. Bei Schach mit einem Verzweigungsfaktor von etwa 35 und einer Tiefe von rund 80 Halbzügen gibt es mehr mögliche Stellungen als Atome im Universum.
~35
Verzweigungsfaktor Schach Durchschnittliche legale Züge pro Stellung
10⁴⁷
Mögliche Schachstellungen Mehr als Atome im beobachtbaren Universum
Irrtum: Der Computer spielt jedes Spiel bis zum Ende durch
In der Praxis ist das 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
MinMax-Algorithmus
AnalogieDefinition
Das Prinzip "Rechne mit dem Schlimmsten": In einem Nullsummenspiel ist dein Verlust der Gewinn des Gegners — deshalb wählt er immer den für dich schmerzhaftesten Zug. Du planst eine Strategie unter genau dieser Annahme und entscheidest dich für die Option, bei der dieses schlimmste Szenario am wenigsten schlimm ausfällt.
Analogie:
Das Prinzip "Rechne mit dem Schlimmsten": In einem Nullsummenspiel ist dein Verlust der Gewinn des Gegners — deshalb wählt er immer den für dich schmerzhaftesten Zug. Du planst eine Strategie unter genau dieser Annahme und entscheidest dich für die Option, bei der dieses schlimmste Szenario am wenigsten schlimm ausfällt.
Definition:
MinMax ist ein rekursiver Algorithmus, der Bewertungen von den Blättern des Spielbaums nach oben propagiert. An MAX-Knoten wird der höchste Kindwert gewählt, an MIN-Knoten der niedrigste. Das Ergebnis ist der optimale Zug unter der Annahme eines perfekt spielenden Gegners.
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.
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.
O(bᵈ)
Laufzeit MinMax b = Verzweigungsfaktor, d = Suchtiefe. Exponentielles Wachstum macht reines MinMax für komplexe Spiele unbrauchbar.
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 vollständiger 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.
Schritt 1 / 8
Die Blattknoten zeigen die Spielergebnisse. Das sind die Bewertungen, wenn das Spiel zu Ende gespielt wird.
Alpha-Beta Pruning — Klug abschneiden
Alpha-Beta Pruning
AnalogieDefinition
Stell dir vor, du vergleichst Jobangebote nach dem Gesamtgehalt. Angebot A bringt dir sicher 5.000 EUR im Monat (dein Alpha). Bei Angebot B erfährst du: Der Arbeitgeber zahlt maximal 3.000 EUR für diese Position. Du hörst sofort auf zu verhandeln — Angebot B wird Angebot A nicht übertreffen. Du hast den Rest "gepruned".
Analogie:
Stell dir vor, du vergleichst Jobangebote nach dem Gesamtgehalt. Angebot A bringt dir sicher 5.000 EUR im Monat (dein Alpha). Bei Angebot B erfährst du: Der Arbeitgeber zahlt maximal 3.000 EUR für diese Position. Du hörst sofort auf zu verhandeln — Angebot B wird Angebot A nicht übertreffen. Du hast den Rest "gepruned".
Definition:
Alpha-Beta Pruning erweitert MinMax um zwei Schranken: Alpha (bester Wert, den MAX bisher garantieren kann) und Beta (bester Wert für MIN). Sobald Alpha >= Beta gilt (ein sogenannter Beta-Cutoff), werden die verbleibenden Kinder des aktuellen Knotens übersprungen — sie können das Ergebnis nachweislich nicht mehr verändern.
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: Nach der Auswertung des linken Teilbaums 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 (Beta-Cutoff). Der zweite MAX-Knoten [0, -1] wird gar nicht mehr ausgewertet. Ergebnis: identisch (Zug links, Wert 5), aber mit weniger Berechnungen.
Reines MinMax
Wertet alle 8 Blattknoten aus. Berechnet jeden einzelnen Pfad im Baum. Garantiert optimales Ergebnis, aber maximaler Rechenaufwand.
MinMax mit Alpha-Beta
Überspringt nachweislich irrelevante Äste. Im Beispiel: 6 statt 8 Knoten ausgewertet. Exakt dasselbe Ergebnis, weniger Arbeit.
O(bᵈᐟ²)
Alpha-Beta Bestfall Effektiv doppelt so tiefe Suche in derselben Zeit. Erreicht durch optimale Zugsortierung.
200 Mio./s
Deep Blue (1997) Stellungen pro Sekunde. MinMax mit Alpha-Beta auf spezialisierter Hardware.
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.
Deep Dive: Von Shannon bis Deep Blue
1950 veröffentlichte Claude Shannon sein wegweisendes Paper zur Schachprogrammierung — eine der ersten formalen Beschreibungen computergestützter Spielstrategie. 1953 schrieb Alan Turing ein Schachprogramm, das er mangels Computer von Hand ausführte. 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.
Deep Dive: Zugsortierung — Der Schlüssel zu effizientem Pruning
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.
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.
Quiz: MinMax & Pruning
Frage 1 / 4
Noch offen
Was macht ein MIN-Knoten in einem MinMax-Baum?
1. Was macht ein MIN-Knoten in einem MinMax-Baum?
☐ A) Er wählt das Kind mit dem höchsten Wert
☐ B) Er wählt das Kind mit dem niedrigsten Wert
☐ C) Er wählt ein zufälliges Kind
☐ D) Er berechnet den Durchschnitt aller Kindwerte
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?
☐ A) 9
☐ B) 7
☐ C) 4
☐ D) 2
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?
☐ A) Der MIN-Knoten wertet seine restlichen Kinder weiter aus
☐ B) Die restlichen Kinder dieses MIN-Knotens werden abgeschnitten (Beta-Cutoff), weil 3 < 6
☐ C) Alpha wird auf 3 aktualisiert
☐ D) Der gesamte Teilbaum wird neu gestartet
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?
☐ A) Die Qualität der heuristischen Bewertungsfunktion ist ab einem bestimmten Punkt wichtiger als reine Suchtiefe
☐ B) MinMax funktioniert nicht für Schach
☐ C) Alpha-Beta Pruning funktioniert nur bei flachen Bäumen
☐ D) Schach hat zu wenige mögliche Züge, um von tieferer Suche zu profitieren
Auflösung: 1) B · 2) C · 3) B · 4) A
Checkpoint: MinMax & Pruning
Ein Schachcomputer kann nicht alle Stellungen bis zum Spielende durchrechnen. Wie löst er dieses Problem — und welche Schwäche bringt diese Lösung mit sich?
Warum ist es beim MinMax-Algorithmus entscheidend, immer davon auszugehen, dass der Gegner den für uns schlechtesten Zug macht?
Alpha-Beta Pruning schneidet ganze Äste im Spielbaum ab und ignoriert sie. Warum findet der Algorithmus trotzdem garantiert denselben besten Zug wie ohne Pruning?