Alpha-Beta-Pruning beschleunigt die Minimax-Suche, indem es Teilbäume ungeprüft verwirft, sobald feststeht, dass sie das Ergebnis nicht mehr beeinflussen können. Das Resultat bleibt exakt dasselbe, der Aufwand sinkt erheblich.
Wer einen Zug prüft und dabei feststellt, dass der Gegner darauf eine vernichtende Antwort hat, muss dessen übrige Antworten nicht mehr ansehen — der Zug ist bereits erledigt. Genau das formalisiert das Verfahren. Es führt zwei Schranken mit: Alpha, den bisher gesicherten Wert der maximierenden Seite, und Beta, den der minimierenden. Sobald an einem Knoten feststeht, dass sein Wert außerhalb dieses Fensters liegen muss, wird der restliche Teilbaum abgeschnitten.
Das Ergebnis ist mit dem von Minimax identisch — abgeschnitten wird nur, was nachweislich ohne Einfluss ist. Bei günstiger Zugreihenfolge halbiert sich der Exponent des Aufwands: In derselben Zeit lässt sich etwa die doppelte Tiefe durchrechnen. Bei Schach ist das der Unterschied zwischen ordentlichem und starkem Spiel.
Der Gewinn hängt daran, dass gute Züge früh geprüft werden: Nur dann stehen die Schranken schnell eng genug, um viel abzuschneiden. Im schlechtesten Fall — die besten Züge kommen zuletzt — spart das Verfahren gar nichts. Deshalb wird viel Aufwand in die Vorsortierung gesteckt, etwa über Züge, die sich in ähnlichen Stellungen bereits bewährt haben (Killerzüge), oder über eine flache Vorabsuche.
Die Idee wurde in den 1950er-Jahren mehrfach unabhängig gefunden, unter anderem von John McCarthy im Umfeld der Dartmouth-Konferenz; die vollständige Analyse lieferten Donald Knuth und Ronald Moore 1975. Alpha-Beta war der algorithmische Kern der Schachprogramme bis hin zu Deep Blue, das 1997 den Weltmeister Garri Kasparow schlug — ein Sieg, der auf sehr schneller, sehr tiefer Suche beruhte und nicht auf gelerntem Wissen.
Hallo! Ich bin dein KI-Tutor.
Melde dich an, um mit mir zu chatten — ich erinnere mich dann auch an eure letzten Gespräche.
