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.
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.
Die maximale Suchtiefe wird bei Zügen, die zu einem Blattknoten führen (d.h. , die aktuelle Tiefe, ist gleich ) und in denen eine gegnerische Figur geschlagen wird, um eine Konstante 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
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