Nullfenster-Suche
Ein Nullfenster (engl.: null window, minimal window) ist ein bis zur Größe Null reduziertes Suchintervall, das in der Spielbaumsuche zur Beschleunigung der Minimaxwert-Berechnung eingesetzt wird. Während die Vorteile des normalen, d.h. nicht-leeren Suchfensters schon seit langem in Theorie und Praxis bekannt ist, kam man erst in de 80er Jahren auf die Idee, das Suchfenster bis zum absoluten Minimum zu reduzieren. Auf den ersten Blick mutet die Nullfenster-Suche nicht besonders effizient an, denn sie birgt das Risiko, daß einzelne Teile des Spielbaums mehrfach durchsucht werden müssen. Der Mehraufwand ist jedoch gering, und er tritt so selten auf, daß die mit dem Nullfenster erzielten Einsparungen überwiegen. Dies gilt für Zufalls-Bäume und in besonderem Maße für praktische Anwendungen, in denen heuristische Verfahren zur Knoten-Vorsortierung für eine günstige Expansionsreihenfolge sorgen.
Schach, Dame und Go sind typische Beispiele für Zwei-Parteien-Null-Summen-Spiele, in denen die Nullfenster-Suche angewendet wird. Zwei Spieler führen abwechselnd Züge aus, bis das Spielende erreicht ist und der Gewinn entsprechend dem Spielerfolg aufgeteilt wird. Die möglichen Spielverläufe ergeben einen Spielbaum, dessen Knoten die Spielstellungen und dessen gerichtete Kanten die Zugvarianten repräsentieren. Die Blätter sind mit (echten oder geschätzten) Stellungswerten bewertet. Ein Spieler wird versuchen, seinen Gewinn zu maximieren, während sein Gegenspieler nach dem Gegenteil, der Minimierung, trachtet. Ziel der Baumsuche ist die Berechnung des Minimaxwertes der Wurzel, der dem Spielergebnis der Ausgangsstellung entspricht.
Alpha-Beta
Grundlage der Nullfenster-Suche ist der Alpha-Beta-Algorithmus ein tiefenorientiertes Suchverfahren, das mittels einer ausgeklügelten Verzahnung von Knotenexpansion und Minimax-Rückbewertung redundante Teile des Suchbaums abschneidet, d.h. überspringt. Der Alpha-Beta-Algorithmus ist eine Erweiterung des bekannten Branch-and-Bound-Verfahrens für Zwei-Parteien-Spiele. Er expandiert den Baum mit zwei Schrankenwerten. Die untere alpha-Schranke entspricht dem Mindestgewinn, den der maximierende Spieler (MAX) bei beliebigem Gegenspiel garantiert erzielen kann. Analog bezeichnet beta den Mindestgewinn des MIN-Spielers unter Berücksichtigung aller MAX-Reaktionen. Zusammen begrenzen die beiden Schrankenwerte ein Intervall das (alpha,beta)-Suchfenster, in dem der Minimaxwert des Spielbaums gesucht wird. Knoten mit einem Wert von < alpha oder > beta werden ohne Informationsverlust abgeschnitten (Abb. 1). (MAX-Knoten sind als Quadrate und MIN-Knoten als Kreise dargestellt; die endgültigen Minimaxwerte befinden sich innerhalb der Knotensymbole.)
Fenstersuche
Je kleiner das Suchfenster, desto mehr Knoten können abgeschnitten werden. Zwar schrumpft das anfänglich mit (- unendlich, + unendlich) initialisierte Fenster automatisch mit jeder neuen gefundenen Zugvariante. Um den Langsamen Schrumpfungsprozeß zu beschleunigen, kann man die Suche aber auch sogleich mit einem reduzierten Fenster (nu - epsilon, nu + epsilon) starten, das um einen vorab geschätzten Minimaxwert nu angeordnet ist. Diese im Englischen als "aspiration search" bezeichnete Methode hat sich besonders gut in Kombination mit der iterativen Suche bewährt, bei der derselbe Baum mehrfach mit sukzessiv erhöhter Suchtiefe (1, 2, ..., d) expandiert wird. Trotz der Mehrfachexpansionen ist die iterative Suche mit einem direkten Suche einem direkten Suchvorgang der Tiefe d überlegen, weil die in der vorangegangenen Iteration gewonnenen Knoten-Informationen größere Einsparungen ermöglichen. So wird u.a. der vorhergehende Minimaxwert Nu zur Initialisierung des nächsten Suchfensters (nu - epsilon, nu + epsilon) verwendet.
Nullfenster
Nullfenster-Suchverfahren expandieren den Baum mit einem extrem reduzierten Suchfenster, dem sog. Nullfenster. Dabei handelt es sich um ein leeres Such-Intervall (nu, nu + 1), das kein Element enthält - vorausgesetzt, der Wertebereich ist ganzzahlig. Nullfenster sind natürlich nicht zur Berechnung des Minimaxwertes geeignet, da dieser stets außerhalb des Fensters liegt. Mit ihnen kann jedoch geprüft werden, ob der Minimaxwert unter oder oberhalb eines gegebenen Referenzwertes r liegt (Abb. 2).
Auf den ersten Blick erscheint die Nullfenster-Suche ein riskantes Unterfangen, da selbst bei guter Knoten-Sortierung Wiederholungssuchen nicht gänzlich vermieden werden können. Empirische und analytische beweisen jedoch, daß die mit dem Nullfenster erzielten Einsparungen den Mehraufwand gelegentlicher Wiederholungssuchen bei weitem übertreffen. Die negativen Auswirkungen der Wiederholungssuche können durch Verwendung eines möglichst engen Schrankenwertes weiter reduziert werden. Der Erfolg der Nullfenster-Suche beruht darauf, daß es einfacher ist, die Unterlegenheit eines Unterbaums zu beweisen, als seinen exakten Minimaxwert zu berechnen (was sich im nachhinein oftmals als überflüssig herausstellt). Dieses Vorgehen erlaubt neben den üblichen alpha- und beta-Schnitten eine weitere Schnittart, die Nullfenster-Schnitte. In Abb. 3 expandiert NegaScout den rechten Wurzel-Unterbaum mit dem Nullfenster (5, 6), um zu beweisen, daß sein Wert <= 5 (dem bisherigen Referenzwert) ist. Dabei tritt ein Nullfenster-Schnitt auf, den Alpha-Beta mit seinem größeren Suchfenster (5, unendlich) nicht durchführen kann.
NegaScout profitiert von den bekannten heuristischen Verfahren zur Vorsortierung der Knoten-Expansionsreihenfolge sowie von diversen Speichertabellen, ohne die moderne Schachprogramme gar nicht mehr konkurrenzfähig wären, genau diejenigen Informationen die auch zur Abkürzung (bzw. Vermeidung) von Wiederholungssuchen erforderlich sind. Das hat zur Folge, daß NegaScout in Bäume der Breite w und Tiefe d oft nur geringfügig mehr als die minimale Knotenzahl w**[d/2] + w**[d/2] - 1 durchsucht .
Literatur
- Brudno, A.L.: Boudaries and estimates for abridging the search of estimates. Probl. Cybernet. 10, 225-241 (1963)
- Kaindl, H., Shams, R., Horaces, H.: minimax search algorithms with and without aspiration windows. IEEE Trans. Pattern Anal. Mach. Intell. PAMI-13 1225-1235 (1991)
- Knuth, D.E., Moore, R.W.: An analysis of alpha-beta pruning. Art. Intell. 6, 293-326 (1975)
- Pearl, J.: Heuristics: Intelligent Search Strategies for Computer Problem Solving, Reading, Mass.: Addison-Wesley 1984
- Reinefeld, A.: Spielbaum-Suchverfahren. Informatik-Fachberichte 200, Berlin: Springer 1989
- Slate, D.J., Atkin L.R.: Chess 4.5 - The Northwestern University chess programm, in: P.W. Frey (ed.): Chess Skill in Man and Machine, p. 82-118. New York: Springer 1977
Autor und Copyright
Alexander Reinefeld
Paderborner Zentrum für Paralleles Rechnen
Warburger Str. 100, W-4790 Paderborn
ar@uni-paderborn.de
© 1992 Informatik Spektrum, Springer-Verlag Berlin Heidelberg