Die Alpha-Beta-Suche (auch Alpha-Beta-Pruning) ist ein optimierter Suchalgorithmus für Zwei-Personen-Nullsummenspiele (wie Schach, Go, Tic-Tac-Toe oder Dame). Er ist eine Erweiterung des Minimax-Algorithmus, der darauf abzielt, die Anzahl der zu bewertenden Knoten im Suchbaum drastisch zu reduzieren, ohne das Ergebnis zu verändern.
Der Algorithmus ist heute das Standardverfahren in fast allen spielstarken Engines und ermöglicht es, bei gleicher Rechenzeit deutlich tiefere Suchbäume zu analysieren als mit dem naiven Minimax-Verfahren.
Das Grundprinzip des Algorithmus ist das "Abschneiden" (Pruning) von Ästen im Suchbaum, die für das Endergebnis irrelevant sind. Wenn der Algorithmus feststellt, dass ein Zweig zu einem Ergebnis führt, das schlechter ist als eine bereits gefundene Alternative, wird dieser Zweig sofort verworfen.
Dazu führt der Algorithmus zwei Werte (Schranken) mit sich, die während der Suche aktualisiert werden:
Ein Teilbaum wird nicht weiter durchsucht (abgeschnitten), sobald gilt:
Logik dahinter:
Der Maximizer hat bereits eine Alternative gefunden (), die besser oder gleich gut ist wie das Beste, was der Minimizer in diesem aktuellen Zweig zulassen würde (). Da der Minimizer (als optimaler Gegner) diesen Pfad niemals wählen würde, wenn er eine bessere Option hat, und der Maximizer diesen Pfad niemals betreten muss (da er schon ein besseres hat), ist das genaue Ergebnis dieses Zweigs irrelevant.
Hier ist eine generische Implementierung, die sich leicht in Python übertragen lässt.
def alpha_beta_search(node, depth, alpha, beta, maximizing_player):
# 1. Abbruchbedingung: Maximale Tiefe erreicht oder Spielende (Blattknoten)
if depth == 0 or is_terminal(node):
return heuristic_value(node)
if maximizing_player:
value = float('-inf')
for child in generate_children(node):
# Rekursiver Aufruf mit vertauschten Rollen
value = max(value, alpha_beta_search(child, depth - 1, alpha, beta, False))
alpha = max(alpha, value)
if alpha >= beta:
break
return value
else: # Minimizing Player
value = float('inf')
for child in generate_children(node):
value = min(value, alpha_beta_search(child, depth - 1, alpha, beta, True))
beta = min(beta, value)
if alpha >= beta:
break
return value
Die Effizienz von Alpha-Beta hängt extrem stark von der Sortierung der Züge (Move Ordering) ab. Der Algorithmus arbeitet am besten, wenn er gute Züge früh untersucht, da er dann schnell enge Fenster () etablieren und schlechte Zweige abschneiden kann.
Ein Suchbaum mit Verzweigungsgrad (Anzahl der Züge pro Stellung) und Tiefe hat im Worst Case Knoten.
Schlechtester Fall (Worst Case):
Die Züge werden in der schlechtestmöglichen Reihenfolge geprüft (die besten Züge zuletzt). In diesem Szenario greift kein Cut-off, und der Algorithmus muss alle Knoten besuchen.
Bester Fall (Best Case):
Die besten Züge werden immer zuerst geprüft. Das maximiert die Anzahl der Cut-offs. In diesem Fall muss der Algorithmus nur etwa die Quadratwurzel der Knoten des Minimax-Baums untersuchen.
Praktische Bedeutung:
Im Idealfall kann Alpha-Beta bei gleicher Rechenzeit doppelt so tief suchen wie der naive Minimax-Algorithmus. In der Praxis erreichen starke Programme durch Heuristiken zur Zugsortierung (z.B. Killer Heuristic oder History Heuristic) Ergebnisse, die sehr nah am Best Case liegen.