Alpha–Beta-Pruning ist ein Baumsuchalgorithmus, der darauf abzielt, die Anzahl der Knoten zu verringern, die vom Minimax-Algorithmus in seinem Suchbaum bewertet werden. Es handelt sich um einen adversarialen Suchalgorithmus, der häufig für maschinelles Spielen von Zwei-Spieler-Kombinationsspielen wie Tic-tac-toe, Schach und Connect 4 verwendet wird. Der Algorithmus stoppt die Bewertung eines Zuges, sobald mindestens eine Möglichkeit gefunden wurde, die beweist, dass der Zug schlechter ist als ein zuvor untersuchter Zug, sodass solche Züge nicht weiter bewertet werden müssen. Wenn er auf einen standardmäßigen Minimax-Baum angewendet wird, liefert er denselben Zug wie Minimax, entfernt jedoch Äste, die die endgültige Entscheidung nicht beeinflussen können.
Der Algorithmus ist ein klassisches Beispiel für einen Branch-and-Bound-Ansatz in Artificial intelligence und bildet die Grundlage vieler spielender Programme, einschließlich früher Schachcomputer und moderner Engines. Seine Effizienzgewinne ermöglichen tiefere Suchen innerhalb desselben Rechenbudgets, was ihn zu einer grundlegenden Technik in adversarialer Suche macht.
Geschichte
John McCarthy traf während des Dartmouth-Workshops im Jahr 1956 Alex Bernstein von IBM, der ein Schachprogramm schrieb. McCarthy erfand die Alpha–Beta-Suche und empfahl sie Bernstein, aber Bernstein war „nicht überzeugt.“ Allen Newell und Herbert A. Simon, die verwendeten, was McCarthy eine „Annäherung“ nannte, im Jahr 1958, schrieben, dass Alpha–Beta „mehrfach neu erfunden zu sein scheint.“ Arthur Samuel hatte eine frühe Version für eine Damesimulation. Richards, Timothy Hart, Michael Levin, und/oder Daniel Edwards erfanden Alpha–Beta ebenfalls unabhängig in den Vereinigten Staaten. McCarthy schlug ähnliche Ideen während des Dartmouth-Workshops vor und empfahl sie einer Gruppe seiner Studenten, einschließlich Alan Kotok am MIT im Jahr 1961. Alexander Brudno konzipierte den Alpha–Beta-Algorithmus unabhängig und veröffentlichte seine Ergebnisse im Jahr 1963. Donald Knuth und Ronald W. Moore verfeinerten den Algorithmus im Jahr 1975. Judea Pearl bewies seine Optimalität hinsichtlich der erwarteten Laufzeit für Bäume mit zufällig zugewiesenen Blattwerten in zwei Arbeiten. Die Optimalität der randomisierten Version von Alpha–Beta wurde von Michael Saksund Avi Wigderson im Jahr 1986 gezeigt.
Kernidee
Ein Spielbaum kann viele Zwei-Spieler-Nullsummenspiele darstellen, wie Schach, Dame, und Reversi. Jeder Knoten im Baum repräsentiert eine mögliche Situation im Spiel. Jeder Endknoten (Ergebnis) eines Zweigs erhält eine numerische Bewertung, die den Wert des Ergebnisses für den Spieler mit dem nächsten Zug bestimmt.
Der Algorithmus verwaltet zwei Werte, Alpha und Beta, die jeweils die Mindestpunktzahl, die der maximierende Spieler sicher hat, und die Höchstpunktzahl, die der minimierende Spieler sicher hat, darstellen. Anfänglich ist Alpha negative Unendlichkeit und Beta positive Unendlichkeit, was bedeutet, dass beide Spieler mit ihrer schlechtestmöglichen Punktzahl beginnen. Wann immer die Höchstpunktzahl, die der minimierende Spieler (der „Beta“-Spieler) sicher hat, geringer wird als die Mindestpunktzahl, die der maximierende Spieler (der „Alpha“-Spieler) sicher hat (d.h., Beta < Alpha), muss der maximierende Spieler keine weiteren Nachkommen dieses Knotens berücksichtigen, da sie im tatsächlichen Spiel nie erreicht werden.
Um dies mit einem realen Beispiel zu veranschaulichen, nehmen wir an, jemand spielt Schach, und es ist sein Zug. Zug „A“ verbessert die Position des Spielers. Der Spieler sucht weiter nach Zügen, um sicherzustellen, dass kein besserer übersehen wurde. Zug „B“ ist ebenfalls ein guter Zug, aber der Spieler erkennt dann, dass er dem Gegner ermöglichen wird, in zwei Zügen Schachmatt zu erzwingen. Somit müssen andere Ergebnisse aus dem Spielen von Zug B nicht mehr berücksichtigt werden, da der Gegner einen Sieg erzwingen kann. Die Höchstpunktzahl, die der Gegner nach Zug B erzwingen könnte, ist negative Unendlichkeit: eine Niederlage für den Spieler. Dies ist geringer als die Mindestposition, die zuvor gefunden wurde;; Zug A führt nicht zu einer erzwungenen Niederlage in zwei Zügen.
Verbesserungen gegenüber naivem Minimax
Der Vorteil von Alpha–Beta-Pruning liegt in der Tatsache, dass Äste des Suchbaums eliminiert werden können. Auf diese Weise kann die Suchzeit auf den „vielversprechenderen“ Teilbaum beschränkt werden, und eine tiefere Suche kann in derselben Zeit durchgeführt werden. Wie sein Vorgänger gehört er zur Branch-and-Bound-Klasse von Algorithmen. Die Optimierung reduziert die effektive Tiefe auf etwas mehr als die Hälfte der von einfachem Minimax, wenn die Knoten in einer optimalen oder nahezu optimalen Reihenfolge bewertet werden (beste Wahl für die Seite am Zug zuerst an jedem Knoten.
Mit einem (durchschnittlichen oder konstanten) Verzweigungsfaktor von b,und einer Suchtiefe von d Ply, ist die maximale Anzahl bewerteter Blattknotenpositionen (wenn die Zugreihenfolge pessimal ist) O(b^d) - dieselbe wie eine einfache Minimax-Suche. Wenn die Zugreihenfolge für die Suche optimal ist (was bedeutet, dass die besten Züge immer zuerst gesucht werden), beträgt die Anzahl bewerteter Blattknotenpositionen etwa O(b 1 b 1 ... b) für ungerade Tiefe und O(b 1 b 1 ... 1) für gerade Tiefe, oder O(b^(d/2)) = O(sqrt(b^d)). Im letzteren Fall, wo die Ply einer Suche gerade ist, wird der effektive Verzweigungsfaktor auf seine Quadratwurzel reduziert, oder äquivalent, kann die Suche doppelt so tief mit derselben Rechenmenge gehen. Die Erklärung von b1b1... ist, dass alle Züge des ersten Spielers untersucht werden müssen, um den besten zu finden, aber für jeden, wird nur der beste Zug des zweiten Spielers benötigt, um alle außer dem ersten (und besten) Zug des ersten Spielers zu widerlegen - Alpha–Beta stellt sicher, dass keine anderen Züge des zweiten Spielers berücksichtigt werden müssen.
Wenn Knoten in zufälliger Reihenfolge betrachtet werden ((d.h., der Algorithmus randomisiert), ist asymptotisch die erwartete Anzahl bewerteter Knoten in uniformen Bäumen mit binären Blattwerten Theta(((b-1+sqrt(b^2+14b+1))/4)^d). Für dieselben Bäume, wenn die Werte den Blattwerten unabhängig voneinander zugewiesen werden und sagen wir Null und Eins beide gleich wahrscheinlich sind, beträgt die erwartete Anzahl bewerteter Knoten Theta((b/2)^d).
Implementierungsüberlegungen
In der Praxis wird Alpha–Beta-Pruning oft mit iterativer Vertiefung implementiert, wobei die Suchtiefe schrittweise erhöht wird. Die Zugreihenfolge ist entscheidend für nahezu optimale Leistung;; häufige Heuristiken umfassen das Untersuchen von Schlagzügen zuerst, die Verwendung von Killer-Moves,und den Einsatz von Transpositionstabellen. Der Algorithmus kann mit Techniken wie Quiescence-Suche erweitert werden, um Horizonteffekte zu vermeiden,und er bildet die Grundlage für fortgeschrittenere Algorithmen wie Principal-Variation-Suche und Negascout. Alpha–Beta-Pruning wird häufig in Schachprogrammen verwendet, einschließlich solcher, die auf Plattformen wie Chess computer-Systemen laufen,und es wurde in verschiedene spielende KI-Frameworks integriert.
Vermächtnis und Auswirkungen
Alpha–Beta-Pruning hat einen bleibenden Einfluss auf Artificial intelligenceund Spieltheorie gehabt. Es war eine Schlüsselkomponente in frühen Schachprogrammen und bleibt relevant in modernen Spiel-Engines, besonders für Spiele mit großen Verzweigungsfaktoren. Die Effizienzverbesserungen des Algorithmus wurden umfassend untersucht,und seine Prinzipien haben andere Bereiche von Suche und Optimierung beeinflusst. Obwohl neuere Techniken wie Machine learningund Deep learning das Spiel-KI transformiert haben, dient Alpha–Beta-Pruning weiterhin als grundlegendes Werkzeug in adversarialer Suche,und seine historische Entwicklung unterstreicht den kollaborativen und iterativen Charakter der KI-Forschung.