¶ Idee
Aspiration Windows erweitern die Alpha-Beta Suche und dienen der Verringerung des Suchraums. Diese Fenster sollen dabei helfen, die Knoten im Baum mit der meisten Information zu bewerten und Knoten mit wenig bis keinen nützlichen Informationen zu vernachlässigen.
Wenn es aus einer Spielposition einen Zug gibt, der besonders gut ist, kann dieser direkt ausgewählt werden, ohne dass alle anderen Züge betrachtet werden. Selbst wenn dieser Zug dann nicht optimal ist, ist er dem Optimum recht nah.
Menschliche Spieler können manche Züge schnell als besonders schlechte oder gute einschätzen und somit Zeit sparen.
¶ Umsetzung
Für jede Suchtiefe wird ein Suchfenster definiert. Die obere und untere Grenze begrenzen das Fenster und definieren somit, welche Werte die Knoten im Baum in dieser Tiefe haben können. Falls ein Knoten einen höheren oder tieferen Wert hat, wird die Suche für diesen Pfad unterbrochen und der Wert des Knotens für die restlichen Berechnungen verwendet.
Durch die Anwendung von Aspiration Windows wird die Evaluierungsfunktion auf jeden Knoten angewendet und nicht ausschließlich auf die Blattknoten.
Pseudo-Code Aspiration Windows:
estimation = eval(state)
if estimation < lowerBound OR estimation > upperBound then
stop and use estimation as result
else
continue with parsing the tree
Problematisch ist die Festlegung der Fenstergrenzen. Bei einer tieferen Suchtiefe sollten diese näher beisammen liegen, da die noch verbleibende Suchtiefe kleiner ist. Grundlegend sollten die Fenster mit zunehmender Tiefe schmaler werden.
Je schmaler die Fenster sind, desto schneller ist die Suche - es wird aber auch an Qualität eingebüßt. Jedoch können durch die erhöhte Geschwindigkeit auch mehr Knoten in der gleichen Zeit besucht werden, wodurch die Qualität wieder erhöht wird.
Es wird also nach Grenzen gesucht, die die Qualität der Suche maximieren.
Es gibt verschiedene Ansätze, der grundlegende sieht eine stückweise Verringerung der Fensterbreite vor:
Graphisch kann dies als umgedrehter, gezackter Kegel wie in Abb. 1 dargestellt werden.
¶ Referenzen
Papadopoulos, Athanasios, et al. "Exploring optimization strategies in board game abalone for alpha-beta search." 2012 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 2012. IEEE