Idee

Quiescence Search ist eine Erweiterung für den MiniMax-Algorithmus.
Der Algorithmus wird dadurch nicht beschleunigt, es wird die Qualität der errechneten besten Züge erhöht.

Quiescence Search versucht, ein für menschliche Spieler intuitives Verhalten zu imitieren.
Menschen analysieren Züge, die gegnerische Spielfiguren beeinflussen (schlagen, schieben etc.), viel tiefer und genauer als ruhige Züge, in denen nur eigene Spielfiguren bewegt werden.

Wenn alle Züge bis zu einer vorgeschriebenen Tiefe betrachtet werden, können schlechte Positionen als gut für einen Spieler bewertet werden. Dies ist vor allem dann der Fall, wenn der letzte Zug eine gegnerische Spielfigur beeinflusst. Hier ist es wahrscheinlich, dass der nächste gegnerische Zug eine eigene Spielfigur schlägt oder verschiebt.

Beispiel Schach

Der als letztes betrachtete Zug ist ein Schlagen eines gegnerischen Bauern durch die eigene Dame. Diese Position kann durch den MiniMax-Algorithmus grundsätzlich als positiv bewertet werden - der Gegner hat eine Figur weniger. Wenn jedoch im nächsten Zug die eigene Dame geschlagen werden kann, ist dies sehr sicher kein guter Zug. Diese Szenarien sollen mit Hilfe von Quiescence Search verhindert werden.

Umsetzung

Die maximale Suchtiefe d_{max} wird bei Zügen, die zu einem Blattknoten führen (d.h. d, die aktuelle Tiefe, ist gleich d_{max}) und in denen eine gegnerische Figur geschlagen wird, um eine Konstante q erhöht.

Pseudo-Code MiniMax:

if d >= dMax then
	stop
else
	continue with parsing the tree

Pseudo-Code Quiescence Search:

if ((d >= dMax) 
 AND amount of pieces of player 1 stay the same
 AND amount of pieces of player 2 stay the same) 
 OR (d >= dMax + q) then
	stop
else
	continue with parsing the tree

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