¶ Idee
Die Alpha-Beta Suche ist eine Erweiterung des Minimax-Algorithmus und wird angewendet, um die Suche in dem Spielbaum zu beschleunigen. Hierzu werden Zweige weggeschnitten, die keine relevanten Informationen enthalten. [1]
¶ Argumentation der Gültigkeit
Der maximierende Spieler findet einen Zug mit der Evaluation . In einem anderen Teilbaum findet der minimierende Spieler eine Suchtiefe tiefer einen Zug mit der Evaluation , wobei . Dies führt dazu, dass der Zug des maximierenden Spielers, welcher den Zug mit der Evaluation nach sich zog, nicht mehr besser als werden kann. Aus diesem Grund können alle anderen Kindknoten des Knotens vernachlässigt werden. [1:1]
Dieses Vorgehen, genannt Alpha-Beta Pruning, wird in Abb. 1 visualisiert.
Ein vollständiger Korrektheitsbeweis ist in dem Artikel von Donald E. Knuth[2] zu finden.
¶ Umsetzung
Beim Parsen des Suchbaums wird für den jeweils aktuellen Knoten ein Intervall gehalten, welches zu Beginn mit initialisiert und nachfolgend in die unteren Teilbäume übergeben wird.
Sobald für den maximierenden Spieler ein Zug gefunden wird, der für eine Bewertung sorgt, wird dies im Intervall gespeichert - für den minimierenden Spieler gilt dies mit analog.
Wenn für den maximierenden Spieler eine Zugbewertung gefunden wird, muss von dem ausgehenden Knoten nicht weitergesucht werden.
Wenn für den minimierenden Spieler eine Zugbewertung gefunden wird, muss von dem ausgehenden Knoten nicht weitergesucht werden. [1:2]
¶ Perfomance
Die Anzahl an Blattknoten in einem Suchbaum beträgt , wobei der Verzweigungsfaktor und die Suchbaumtiefe darstellen.
Wenn die Alpha-Beta Suche die maximal mögliche Anzahl an Knoten wegschneidet, verbleibt die folgende Anzahl an Blattknoten [1:3]: