Alpha-Beta-Suche

Die Alpha-Beta-Suche beschleunigt die Suche einer Schachengine, also eines Programms, das Züge und Antworten vergleicht. Die Suche lässt sich als Baum darstellen: Jeder Knoten ist eine Stellung und jeder Zweig ein legaler Zug. Ohne Pruning müsste das Programm viele Fortsetzungen untersuchen, die sich am Ende als bedeutungslos erweisen.

Das Verfahren verwaltet während der Suche zwei Schranken. Alpha ist das beste Ergebnis, das eine Seite auf dem aktuellen Pfad bereits garantieren kann. Beta ist eine Schranke, die durch eine dem Gegner schon verfügbare Alternative entsteht. Sobald eine Fortsetzung so schlecht ist, dass ein rationaler Spieler sie niemals wählen würde, kann ihre weitere Untersuchung die Entscheidung am übergeordneten Knoten nicht mehr ändern.

Der Zweig wird wegen einer logischen Schranke im Baum beendet und nicht bloß, weil ein Zug unattraktiv aussieht. Bei gleicher Tiefe und denselben Bewertungen an der Suchgrenze liefert Alpha-Beta dieselbe Wahl wie eine vollständige Suche, die voraussetzt, dass beide Seiten jeweils bestmöglich antworten.

Die Ersparnis hängt stark von der Zugreihenfolge ab. Werden starke Züge früh geprüft, entstehen nützliche Schranken schneller und mehr Zweige können ohne tiefere Untersuchung beendet werden. Eine Bewertungsfunktion, die einer Stellung einen Zahlenwert zuweist, liefert die Werte an den Punkten, an denen die endliche Suche endet.