Der Alpha-Beta-Algorithmus ist eine Optimierung des Minimax-Algorithmus zur effizienteren Suche in Entscheidungsbäumen. Er verwirft (pruned) ganze Teilbäume, wenn klar ist, dass sie das Endergebnis nicht beeinflussen können – basierend auf zwei Grenzen: Alpha (beste bisher bekannte Option für den Maximierer) und Beta (beste Option für den Minimierer). Dadurch wird die Anzahl der untersuchten Zustände deutlich reduziert, ohne das Ergebnis zu verändern.
Der Minimax-Algorithmus wurde bereits 1928 entdeckt und in den 1940er Jahren von Turing und Shannon als zentral für die Schachprogrammierung erkannt. Die Alpha-Beta-Suche entstand hingegen erst Ende der 1950er-Jahre, zunächst mit Fokus auf Alpha-Cutoffs. Erst in den 1960ern wurde sie fest in Schachprogramme integriert, wobei Alexander Brudno 1963 eine exakte Beschreibung und einen Korrektheitsbeweis veröffentlichte. Eine umfassende Analyse folgte schließlich 1975.
Der Minimax-Algorithmus ist ein Entscheidungsverfahren für Zwei-Spieler-Spiele, bei dem beide Spieler optimal spielen. Er durchläuft rekursiv alle möglichen Spielzüge bis zu einem bestimmten Tiefenlimit und bewertet die resultierenden Endzustände mit einer Bewertungsfunktion. Der Maximierer wählt dabei Züge, die seinen Nutzen maximieren, während der Minimierer Züge wählt, die den Nutzen des Gegners minimieren. Durch diesen Wechsel simuliert Minimax die bestmögliche gegnerische Strategie. Der Hauptnachteil ist die hohe Rechenlast, weshalb der Algorithmus häufig mit Optimierungen wie Alpha-Beta-Pruning kombiniert wird.
besterZug = NULL;
int Suchtiefe = 4;
int bewertung = max(Suchtiefe,
-unendlich, +unendlich);
if (besterZug == NULL)
es gab keine weiteren Zuege mehr (Matt oder Patt);
else
spiele(besterZug);
def max(int tiefe, int alpha, int beta):
if (tiefe == 0 or keineZuegeMehr(spieler_max))
return bewerten();
int maxWert = alpha;
Zugliste = generiereMoeglicheZuege(spieler_max);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = min(tiefe-1,
maxWert, beta);
macheZugRueckgaengig(Zug);
if (wert > maxWert) {
maxWert = wert;
if (tiefe == Suchtiefe)
besterZug = Zug;
if (maxWert >= beta)
break;
}
}
return maxWert;
def min(int tiefe, int alpha, int beta):
if (tiefe == 0 or keineZuegeMehr(spieler_min))
return bewerten();
int minWert = beta;
Zugliste = generiereMoeglicheZuege(spieler_min);
for each (Zug in Zugliste) {
fuehreZugAus(Zug);
int wert = max(tiefe-1,
alpha, minWert);
macheZugRueckgaengig(Zug);
if (wert < minWert) {
minWert = wert;
if (minWert <= alpha)
break;
}
}
return minWert;
Bei der Alpha-Beta-Suche ist die Reihenfolge, in der Züge geprüft werden, entscheidend für die Effizienz, da eine gute Zugreihenfolge mehr Abschneidungen ermöglicht. Deshalb betrachtet man zuerst vielversprechende Züge, oft mithilfe von Heuristiken. Beim Schach z.B. werden Züge priorisiert, bei denen starke Figuren geschlagen werden, um die Suche zu optimieren.
Die iterative Tiefensuche erhöht die maximale Suchtiefe schrittweise, anstatt von Anfang an in großer Tiefe zu suchen. Da man bei der Alpha-Beta-Suche nicht genau vorhersagen kann, wie lange eine Suche dauert, startet man zunächst mit einer niedrigen Tiefe. Anschließend wird die Tiefe nach und nach erhöht. Die Ergebnisse früherer Durchläufe helfen dabei, die Zugreihenfolge bei tieferer Suche gezielter und effizienter zu wählen.