Startseite▸Algorithmen & KI▸Minimax & Alpha-Beta

♟️ Minimax & Alpha-Beta

Interaktive Spielbaum-Visualisierung: Beobachte, wie Minimax-Werte nach oben blubbern und Alpha-Beta-Pruning ganze Teilbäume durchstreicht, die das Ergebnis nicht ändern können.

Algorithmen & KI3DFortgeschritten60 FPS

Über Minimax mit Alpha-Beta-Pruning

Minimax ist ein rekursiver adversarieller Suchalgorithmus, der in Zwei-Spieler-Nullsummenspielen verwendet wird. Der MAX-Spieler (z. B. die KI) versucht, den heuristischen Wert des Spielzustands zu maximieren, während der MIN-Spieler (Gegner) versucht, ihn zu minimieren; Minimax führt eine Tiefensuche bis zu den Blattknoten durch und propagiert die Werte dann nach oben, wobei bei jeder Ebene abwechselnd das Maximum und das Minimum genommen wird. Für einen Spielbaum mit Verzweigungsfaktor b und Tiefe d wertet naives Minimax O(b^d) Knoten aus — für Schach ist dies astronomisch groß.

Alpha-Beta-Pruning ist eine Verbesserung, die zwei Grenzen verwaltet — alpha (der beste Wert, den MAX garantieren kann) und beta (der beste Wert, den MIN garantieren kann) — und jeden Teilbaum verwirft (prunt), bei dem bereits bekannt ist, dass eine bessere Option existiert. Im besten Fall reduziert Alpha-Beta die Anzahl der ausgewerteten Knoten auf O(b^(d/2)), was die Suchtiefe bei gleichen Kosten effektiv verdoppelt. Der Visualisierer lässt dich Pruning ein- und ausschalten und die in jedem Modus ausgewerteten Knoten zählen.

Häufig gestellte Fragen

Was ist der Minimax-Algorithmus und wo wird er eingesetzt?

Minimax ist ein Entscheidungsalgorithmus für Zwei-Spieler-Nullsummenspiele mit vollständiger Information wie Schach, Go, Dame, Vier gewinnt und Tic-Tac-Toe. Er geht davon aus, dass beide Spieler optimal spielen: MAX wählt immer den Zug mit dem höchsten Minimax-Wert; MIN wählt immer den mit dem niedrigsten. Der Algorithmus wurde von John von Neumann in seinem Beweis des Minimax-Theorems von 1928 formalisiert.

Wie stark reduziert Alpha-Beta-Pruning die Suche?

Im besten Fall (optimale Zugreihenfolge, bei der der beste Zug immer zuerst durchsucht wird) prunt Alpha-Beta so stark, dass nur O(b^(d/2)) Blattknoten statt O(b^d) ausgewertet werden. Für Schach (b ≈ 35) bedeutet dies, dass mit dem gleichen Rechenaufwand bis Tiefe 10 statt 5 gesucht werden kann. In der Praxis erreichen echte Schach-Engines mit guten Zugreihenfolge-Heuristiken 60–80 % des bestmöglichen Pruning, was die effektive Tiefe ungefähr verdoppelt.

Was stellen die Alpha- und Beta-Grenzen dar?

Alpha ist der beste Wert, den der MAX-Spieler von jeder Position entlang des aktuellen Pfades garantiert bekommt — er steigt nur. Beta ist der beste Wert, den der MIN-Spieler garantiert bekommt — er sinkt nur. Wenn alpha ≥ beta an einem MIN-Knoten (oder beta ≤ alpha an einem MAX-Knoten) gilt, können die verbleibenden Geschwisterknoten das Ergebnis unmöglich beeinflussen und werden geprunt. Die Bedingung alpha ≥ beta wird als Cutoff bezeichnet.

Was ist Zugreihenfolge und warum ist sie für Alpha-Beta wichtig?

Die Pruning-Effizienz von Alpha-Beta hängt stark von der Reihenfolge ab, in der Züge durchsucht werden. Wird der beste Zug zuerst untersucht, treten Cutoffs früh auf, und das maximale Pruning wird erreicht. Gängige Heuristiken zur Reihenfolge sind die Killer-Move-Heuristik (probiere Züge, die bei Geschwisterknoten Cutoffs verursacht haben), die History-Heuristik und das Durchsuchen von Schlagzügen vor ruhigen Zügen. Moderne Engines wie Stockfish investieren erheblichen Aufwand in die Zugreihenfolge, um sich der Alpha-Beta-Bestleistung anzunähern.

Was ist Negamax und wie vereinfacht es die Implementierung?

Negamax ist eine Umformulierung von Minimax, die die Nullsummen-Eigenschaft ausnutzt: Der Wert für den aktuellen Spieler ist immer das Negative des Werts für den Gegner. Dies erlaubt eine einzige rekursive Funktion statt zwei alternierender: Rückgabe des Maximums über die Kinder von (−negamax(Kind)). Alpha-Beta-Pruning integriert sich sauber: alpha = −beta_eltern, beta = −alpha_eltern bei jedem rekursiven Aufruf.

Was ist eine Transpositionstabelle und wie ergänzt sie Alpha-Beta?

Eine Transpositionstabelle ist eine Hash-Map von Brettpositionen zu zuvor berechneten Minimax-Werten und besten Zügen. Da viele verschiedene Zugfolgen zur gleichen Position führen, vermeidet das Zwischenspeichern von Ergebnissen die erneute Auswertung identischer Teilbäume. Moderne Schach-Engines verwenden 64-Bit-Zobrist-Hashing und 512-MB–2-GB-Transpositionstabellen, die im Mittelspiel oft über 90 % Trefferquote erreichen und die Wirksamkeit von Alpha-Beta stark verstärken.

Was ist der Horizont-Effekt in der Spielbaumsuche?

Der Horizont-Effekt tritt auf, wenn eine Suche bei einer festen Tiefe stoppt und dadurch die Folgen wichtiger Ereignisse knapp jenseits dieser Tiefe übersieht. Zum Beispiel könnte eine Schach-Engine eine Figur opfern, um einen unvermeidlichen Damenverlust jenseits des Suchhorizonts zu verschieben, wodurch eine verlorene Stellung neutral erscheint. Ruhesuche — die Suche an Blattknoten fortzusetzen, bis eine "ruhige" Position (keine Schlagzüge) erreicht ist — mildert dies bei moderatem Mehraufwand.

Wie unterscheidet sich Monte-Carlo-Baumsuche (MCTS) von Minimax?

MCTS verwendet keine heuristische Bewertungsfunktion. Stattdessen führt es zufällige Rollouts (Simulationen) von Knoten bis zu Endzuständen durch und nutzt die statistischen Ergebnisse, um Knotenwerte zu schätzen. Dies macht es gut geeignet für Spiele wie Go, bei denen gute Heuristiken schwer zu entwerfen sind. AlphaGo kombinierte MCTS mit tiefen neuronalen Policy-/Value-Netzwerken und erreichte 2016 übermenschliches Go-Spiel. Minimax+Alpha-Beta bleibt in klassischen Spielen wie Schach dominant, wo starke Bewertungsfunktionen existieren.

Was ist iterative Vertiefung in Verbindung mit Minimax?

Iterative-Deepening-Tiefensuche (IDDFS) führt Alpha-Beta wiederholt bis zu wachsenden Tiefen (1, 2, 3, …) aus, bis ein Zeitlimit erreicht ist. Dies scheint verschwenderisch, ist aber effizient, da die Anzahl der Knoten bei Tiefe d bei typischen Verzweigungsfaktoren die Summe aller flacheren Tiefen dominiert. Der wesentliche Vorteil ist, dass Ergebnisse aus flacheren Suchen ausgezeichnete Zugreihenfolge-Informationen für die tiefere Suche liefern und die Pruning-Effizienz verbessern.

Über diese Simulation

Diese Simulation visualisiert die Minimax-Suche auf einem Spielbaum, den du selbst formst, und zeigt, wie ein roter MAX-Spieler und ein blauer MIN-Spieler abwechselnd ziehen, während Werte von den Blättern nach oben blubbern. Schalte Alpha-Beta-Pruning ein, um zu beobachten, wie Zweige sofort durchgestrichen werden, sobald sie das Ergebnis nicht mehr ändern können.

🔬 Was gezeigt wird

Ein Spielbaum mit gewähltem Verzweigungsfaktor und Tiefe. Rote MAX-Knoten nehmen den größten Kindwert, blaue MIN-Knoten den kleinsten. Im Alpha-Beta-Modus verfolgt jeder Knoten ein α/β-Fenster, und gestrichelte graue Zweige markieren Teilbäume, die geprunt wurden, sobald β auf α oder darunter fällt.

🎮 Anwendung

Wähle eine Baumform, dann stelle Verzweigungsfaktor b und Tiefe d mit den Reglern ein. Wähle Reines Minimax oder Alpha-Beta sowie Zufällige oder Best-First-Zugreihenfolge, dann drücke Schritt, um einen Knoten nach dem anderen voranzuschreiten, oder Auto, um mit der gewählten Geschwindigkeit zu animieren.

💡 Wusstest du schon?

Mit Best-First-Reihenfolge kann Alpha-Beta-Pruning die untersuchten Knoten von etwa b^d auf b^(d/2) reduzieren — was effektiv die durchsuchbare Tiefe bei gleichem Aufwand verdoppelt, weshalb Schach-Engines darauf setzen.

Häufig gestellte Fragen

Was ist der Unterschied zwischen reinem Minimax und Alpha-Beta-Pruning?

Reines Minimax besucht jeden Knoten, um den korrekten Wert zu berechnen. Alpha-Beta erreicht das gleiche Ergebnis, überspringt aber Zweige, die das Ergebnis nachweislich nicht ändern können — der "Cutoffs"-Zähler zeigt, wie viele übersprungen wurden.

Warum beeinflusst die Zugreihenfolge, wie viel Pruning stattfindet?

Pruning greift erst, sobald ein guter Wert bekannt ist. Best-First-Reihenfolge durchsucht zuerst vielversprechende Kindknoten, verengt das Fenster früh und löst mehr Cutoffs aus; Zufällige Reihenfolge prunt im Durchschnitt weniger.

Was stellen die roten und blauen Knoten dar?

Rote Knoten sind MAX und versuchen, das Ergebnis zu maximieren; blaue Knoten sind MIN und versuchen, es zu minimieren. Die beiden Rollen wechseln bei jeder Tiefenebene.

Was passiert mit den durchgestrichenen Zweigen?

Sobald sich das α/β-Fenster eines Knotens schließt (β ≤ α), werden seine verbleibenden unerforschten Kinder übersprungen und mit einer gestrichelten Linie durchgestrichen dargestellt, da kein von ihnen gehaltener Wert die Entscheidung des Elternknotens ändern könnte.

Kombinieren sich Verzweigungsfaktor und Tiefe, um die Suchzeit zu verändern?

Ja — die Gesamtzahl der Blätter beträgt etwa b hoch d, sodass eine Erhöhung der Tiefe um eins einen ähnlichen Effekt hat wie die Multiplikation des Verzweigungsfaktors. Beobachte "Knoten gesamt" im Statistik-Panel.

⚙ Unter der Haube

Durchsuche den Spielbaum per DFS unter der Annahme, dass der Gegner optimal spielt; Alpha-Beta-Pruning überspringt Zweige, die nicht relevant sein können. Beobachte, wie sich das (α, β)-Fenster verengt, Cutoffs Teilbäume ausgrauen und besuchte Blätter im Vergleich stehen.

Canvas 2DMinimaxAlpha-BetaSpielbaumSuche

3D · Three.js / WebGL-Renderer · 60 FPS Ziel · läuft vollständig clientseitig, keine Installation nötig