Alpha-Beta-Suche

Die Alpha-Beta-Suche, auch Alpha-Beta-Cut genannt, ist eine algorithmisch optimierte Variante des Minimax-Suchverfahrens und wird hauptsächlich bei Spielen mit zwei gegnerischen Parteien eingesetzt. Während der Suche werden zwei Werte Alpha und Beta aktualisiert, die angeben, welches Ergebnis die Spieler bei optimaler Spielweise erzielen können. Mit Hilfe dieser Werte kann entschieden werden, welche Teile des Suchbaumes nicht untersucht werden müssen, weil sie das Ergebnis der Problemlösung nicht beinflussen können.

Die einfache (nicht optimierte) Alpha-Beta-Suche liefert exakt dasselbe Ergenis wie die Minimax-Suche.

Informelle Beschreibung

Der Minimax-Algorithmus bewertet den vollständigen Suchbaum. Dabei werden aber auch Knoten betrachtet, die in das Ergebnis (die Wahl des Zweiges an der Wurzel) nicht einfließen. Die Alpha-Beta-Suche ignoriert genau eben diese Konten.

Folgendes Beispiel erklärt diesen Sachverhalt anschaulich: Nehmen wir an es gibt einige Taschen voll mit Gegenständen mit mehr oder weniger Wert und Sie erhalten einen Gegenstand aus einer der Taschen. Sie dürfen die Tasche wählen, und der Gegner wählt einen Gegenstand daraus. Sobald sie eine Tasche gewählt haben, wird ihr Gegner natürlich den wertlosesten Gegenstand daraus wählen. Sie wählen daher die Tasche, deren wertlosester Gegenstand immer noch mehr Wert besitzt, als der jeweils wertloseste der anderen Taschen.

Wendet man den Minimax-Algorithmus an, durchsucht man einfach alle Taschen vollständig und kennt damit den Wert eines jeden Gegenstandes, und somit kann man genau die richtige Tasche für sich wählen. Aber dieses Durchsuchen dauert eben ziemlich lange.

Also geht man folgendermaßen vor: Man durchsucht die erste Tasche vollständig. Nehmen wir an, darin befinden sich die Schlüssel für einen Neuwagen und ein 20 Euro Schein. Würden wir diese Tasche wählen, bekämen wir vom Gegner wohl den Geldschein zugeteilt, weil das der wertloseste Gegenstand in dieser Tasche ist. Egal wie wertvoll die anderen Dinge in dieser Tasche auch sein würden, wir bekämen immer nur diesen Geldschein daraus.

Wenn wir die zweite Tasche durchsuchen und darin als erstes einen 50 Euro Schein finden, steigt die Hoffnung, dass noch mehr wertvolle Gegenstände darin enthalten sind, und wir nehmen den zweiten Gegenstand daraus. Angenommen dabei handelt es sich um einen Apfel, dann wird uns der Gegner aus dieser Tasche wohl lieber diesen Apfel als den Geldschein geben. Dieser Apfel ist aber wertloser als der 20 Euro Schein, den wir aus der ersten Tasche bekämen. Also werden wir nie die zweite Taschen wählen, und durchsuchen sie nicht weiter. Die restlichen Gegenstände darin interessieren nicht mehr, diese können natürlich noch wertloser sein, als der Apfel. Wie wertlos aber diese Tasche genau ist, spielt keine Rolle, ausschlaggebend ist, dass sie wertloser als die erste Tasche ist, nicht, wie viel wertloser sie ist. Auch wenn die restlichen Gegenstände der Tasche großen Wert besitzen, wir bekämen doch nur höchstens diesen Apfel, also legen wir die Tasche beseite.

Der Algorithmus

Die Alpha-Beta-Suche arbeitet prinzipiell genauso wie obige informelle Beschreibung. Die Idee ist, dass zwei Werte (Alpha und Beta) weitergereicht werden, die das Worst-Case-Szenario der Spieler beschreiben. Der Alpha-Wert ist das Ergebnis, das Spieler A mindestens erreichen wird, der Beta-Wert ist das Ergebnis, das Spieler B mindestens erreichen wird.

Besitzt ein maximierender Konten (von Spieler A) einen Zug, dessen Rückgabe den Beta-Wert überschreitet, wird die Suche in diesem Konten abgebrochen (Beta-Cutoff, denn Spieler B würde erst gar nicht diese Variante wählen, weil sie ein zu gutes Ergebnis für Spieler A liefern würde). Liefert der Zug stattdessen ein Ergebnis, das den Alpha-Wert übersteigt, wird dieser entsprechend nach oben angehoben. Analoges gilt für die minimierenden Knoten, wobei bei Werten kleiner als Alpha abgebrochen wird (Alpha-Cutoff) und der Beta Wert nach unten angepasst wird.

Obige Abbildung zeigt einen Beispielbaum mit 18 Blätter, von denen nur 12 ausgewertet werden. Die drei umrandeten Werte eines inneren Knotens beschreiben den Alpha-Wert, den Rückgabewert und den Beta-Wert.

Der Suchalgorithmus verwendet ein sogenanntes Alpha-Beta-Fenster, dessen untere Grenze der Alpha-Wert und dessen obere Grenze der Beta-Wert darstellt. Dieses Fenster wird zu den Kindknoten weitergegeben, wobei in der Wurzel mit maximalen Fenster begonnen wird.

Die Blätter 1, 2 und 3 werden von einem maximierend Knoten ausgewertet und der beste Wert 10 wird dem minimierenden Vaterkoten übergeben. Dieser passt den Beta-Wert an (signalisiert durch die orange Linie links unten) und übergibt das neue Fenster [-inf,10] dem nächsten maximierenden Kindknoten, der die Blätter 4, 5 und 6 besitzt. Der Rückgabewert 12 von Blatt 5 ist aber so gut, dass er den Beta-Wert 10 überschreitet. Somit muss Blatt 6 nicht mehr betrachtet werden, weil das Ergebnis 12 dieses Teilbaumes besser ist, als das des linken Teilbaumes, und deshalb vom minimierenden Spieler nie gewählt werden würde.

Ähnlich verhält es sich beim minimierenden Knoten mit dem 3-Alpha-Cutoff. Obwohl dieser Teilbaum erst teilweise ausgewertet wurde, ist klar, dass der maximiernde Wurzelknoten diese Variante niemals wählen würde, weil der minimierende Knoten mindestens das Ergebnis 3 erzwingen könnte, während aus dem mittleren Teilbaum das Ergebnis 12 sichergestellt ist.

Implementierung

Anmerkung: Unterschiede zum einfachen Minimax sind blau gekennzeichnet.

Die NegaMax-Variante lautet:

Anmerkung: Während die Standard-Implementierung für einen Spieler maximiert und für den anderen Spieler minimiert, maximiert die Negamax-Variante für beide Spieler und vertauscht und negiert Alpha und Beta bei der Rekursion. Daraus folgt, dass sich die Bewertungsfunktion in beiden Implementierung unterschiedlich verhalten muss.

• Standard-Implementierung: Je besser die Brettstellung für den maximierenden Spieler ist, desto größer ist der Rückgabewert der Bewertungsfunktion. Je besser sie für den minimierenden Spieler ist, desto kleiner ist der Rückgabewert.
• Negamax-Implementierung: Da beide Spieler maximieren, muss die Bewertungsfunktion desto größere Werte liefern, je besser die Brettposition des gerade Ziehenden ist.

Optimierungen

Anders als beim Minimax-Algorithmus spielt bei der Alpha-Beta-Suche die Reihenfolge, in der Kindknoten (Züge) bearbeitet werden, eine wesentliche Rolle. Je schneller das Alpha-Beta-Fenster verkleinert wird, desto mehr Cutoffs werden erreicht. Deshalb ist es wichtig, zuerst die Züge zu betrachten, die das beste Ergebnis versprechen. In der Praxis werden verschiedene Heuristiken verwendet.

Vorsortierung der Züge

Die möglichen Züge werden nach bestimmten Regeln vorsortiert. Bei Schach kann man die Züge danach sortieren, ob bzw. welche Figur geschlagen wird, oder auch welche Figure schlägt. "Turm schlägt Dame" wird danach vor "Turm schlägt Turm" einsortiert und "Bauer schlägt Turm" wird zwischen beiden einsortiert.

Principal Variation Suche

Ein Knoten bei der Alpha-Beta-Suche gehört einer von drei Kategorien an (bezogen auf die NegaMax-Variante):

• Alpha-Knoten: Jeder Folgezug liefert einen Wert kleiner oder gleich Alpha, was bedeutet, dass hier keiner guter Zug möglich ist.
• Beta-Knoten: Mindestens ein Folgezug liefert einen Wert größer oder gleich Beta, was einen Cutoff bedeutet.
• Principal Variation-Knoten: Mindestens ein Folgezug liefert einen Wert größer als Alpha, aber alle liefert einen Wert kleiner oder gleich Beta.

Manchmal kann man frühzeitig erkennen, um welchen Knoten es sich handelt. Liefert der erste getestete Folgezug einen Wert größer gleich Beta, dann ist es ein Beta-Knoten. Liefert er einen Wert kleiner gleich Alpha, dann ist es möglicherweise ein Alpha-Knoten (vorrausgesetzt, die Züge sind gut vorsortiert). Liefert er aber einen Wert zwischen Alpha und Beta, so handelt sich möglicherweise um einen Principal Variation-Knoten.

Die Principal-Variation-Suche nimmt nun an, dass ein Folgezug, der einen Wert zwischen Alpha und Beta liefert, sich als bester möglicher Zug herausstellen wird. Deshalb wird das Alpha-Beta-Fenster im folgenden minimal verkleinert, um eine maximale Anzahl an Cutoffs zu erreichen, aber dennoch die verbleibenden Züge als schlechter zu beweisen.

Stellt sich bei Suche mit dem minimierten Alpha-Beta-Fenster heraus, dass es zu klein gewählt wurde, muss die Suche mit dem originalen Fenster wiederholt werden. Deshalb erreicht man durch dieses Verfahren nur dann Erfolge, wenn die Züge gut vorsortiert wurden. Andererseit können diese Principal Variation-Knoten in Verbindung mit dem Iterative Deepening auch für die Sortierung der Züge verwendet werden.

Iterative Deepening

Iterative Deepening ist die schrittweise Erhöhung der Rechentiefe. Da die Alpha-Beta-Suche eine Tiefensuche ist, kann man meistens vorher nicht bestimmen, wie lange die Berechnung dauern wird. Deshalb beginnt man mit einer geringen Suchtiefe und erhöht diese nach und nach. Das Ergebnis einer Berechnung kann benutzt werden, um bei der nächsten Berechnung die Züge besser vorzusortieren.

Aspiration Windows

Aspiration windows werden zusammen mit dem Iterative Deepening verwendet. Grundsätzlich beginnt die Alpha-Beta-Suche an der Wurzel mit einem maximalen Fenster. Beim Iterative Deepening kann aber angenommen werden, dass eine neue Berechnung mit höherer Tiefe einen ähnlichen Wert als Ergebnis liefert wird. Deshalb kann das Suchfenster initial auf einen (relativ) kleinen Bereich um den Ergebniswert der vorherigen Berechnung gesetzt werden. Stellt sich heraus, dass dieses Fenster zu klein war, muss man (ähnlich wie bei der Principal Variation-Suche) die Suche mit maximalem Fenster wiederholen.

Killer Heuristik

Man nimmt hierbei an, dass Züge, die einen Cutoff verursacht haben, auch in anderen Teilen des Suchbaumes (bei gleicher Tiefe) einen Cutoff verursachen werden. Oft wird so vorgegangen, dass für jede Tiefe des Baumes eine gewisse Anzahl solcher Killer-Züge gespeichert wird und immer zuerst betrachtet werden (sofern diese Züge bei der neuen Brettstellung noch gültig sind).

Quiescent-Suche

Die Alpha-Beta-Suche bzw. der Minimax-Algorithmus allgemein haben das Problem, dass bei einer gewissen Tiefe die Suche strikt abgebrochen wird, obwohl das Ergebnis an dieser Stelle die Brettstellung nicht besonders gut widergibt. Anstatt die Alpha-Beta-Suche bei der erreichten Höchsttiefe abzubrechen, wird eine Quiescent-Suche fortgeführt, die nur noch wenige wichtige der möglichen Züge betrachtet. Bei Schach wird zum Beispiel der Schlagabtausch weiter betrachtet.

Vergleich von Minimax und AlphaBeta

Nachfolgende Tabelle zeigt eine Beispielberechnung einer Schachstellung bei konstanter Suchtiefe von vier Halbzügen (jeder Spieler zieht zweimal). Es wurde der normale Minimax-Algorithmus angewendet und Alpha-Beta ohne Zugsortierung und mit (einfacher) Zugsortierung. Die Prozentangabe bei den Cutoffs beziehen sich auf den gesamten Suchbaum und beschreibt, wieviel des gesamten Suchbaumes nicht ausgewertet wurde. Es handelt sich dabei um Schätzungen, denen zugrunde liegt, dass die Teilbäume in etwa gleich groß sind (bei Cutoffs ist nicht bekannt, wie groß der weggeschnittene Teilbaum wirklich wäre).

Es ist deutlich zu erkennen, dass die Alpha-Beta-Suche eine erhebliche Geschindigkeitssteigerung gegenüber Minimax bedeutet. Auch die Zugsortierung verbessert die Rechenzeit in diesem Beispiel um den Faktor 10. Die Tatsache, dass mit Zugsortierung die Anzahl der Cutoffs absolut sinkt, lässt such dadurch erklären, dass diese auf höheren Ebenen im Suchbaum erfolgen und somit größere Teile weggeschnitten werden.