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 x. In einem anderen Teilbaum findet der minimierende Spieler eine Suchtiefe tiefer einen Zug mit der Evaluation y, wobei y < x. Dies führt dazu, dass der Zug des maximierenden Spielers, welcher den Zug mit der Evaluation y nach sich zog, nicht mehr besser als y werden kann. Aus diesem Grund können alle anderen Kindknoten des Knotens \leq y 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 [\alpha \; \beta] gehalten, welches zu Beginn mit [-\infty \; \infty] 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 > \alpha sorgt, wird dies im Intervall gespeichert - für den minimierenden Spieler gilt dies mit < \beta analog.

Wenn für den maximierenden Spieler eine Zugbewertung \geq \beta gefunden wird, muss von dem ausgehenden Knoten nicht weitergesucht werden.

Wenn für den minimierenden Spieler eine Zugbewertung \leq \alpha gefunden wird, muss von dem ausgehenden Knoten nicht weitergesucht werden. ^[1:2]

Perfomance

Die Anzahl T an Blattknoten in einem Suchbaum beträgt b^n, wobei b der Verzweigungsfaktor und n die Suchbaumtiefe darstellen.

Wenn die Alpha-Beta Suche die maximal mögliche Anzahl an Knoten wegschneidet, verbleibt die folgende Anzahl an Blattknoten ^[1:3]:

 T = \begin{cases}
b^{\frac{n+1}{2}} + b^{\frac{n-1}{2}} - 1 & n \text{ ungerade}
&\\
2b^{\frac{n}{2}}-1 & n \text{ gerade}
\end{cases}

Referenzen