Quiescence search

Quiescence search is an algorithm typically used to evaluate minimax game trees in game-playing computer programs. It is a remedy for the horizon problem faced by AI engines for various games like chess and Go.

The horizon effect

The horizon effect is a problem in artificial intelligence where, in many games, the number of possible states or positions is immense and computers can only search a small portion of it, typically a few ply down the game tree. Thus, for a computer searching only five ply, there is a possibility that it could make a move that would prove to be detrimental later on (say, after 6 moves), but it cannot see the consequences because it cannot search far into the tree. Consider this chess position with black to move: [ [http://www.chessbase.com/newsdetail.asp?newsid=2749 ChessBase.com - Chess News - Bilbao – the humans strike back ] ]

Chess diagram|=
tright
Ponomariov-Fritz (Man vs. Machine, Bilbao, 2005)
date=8 | | | | | | |kd| |date=7 | | | | | |pd| | |date=6 |pd|nd| |pd| | | | |date=5 |nl| | |pd| | |pd| |date=4 |pl|pl| |pl|pd| | |qd|date=3 | |bl|rd|bd|pl| |ql|pl|date=2 | | | | | | |kl| |date=1 | | | | |rl| | | |= a b c d e f g h
This game illustrates the danger of searching a shallow, fixed ply.

Here White is down a pawn in material, and a good move for black would be 39... Qxg3+ 40. Kxg3 f5. However, Fritz choose the suboptimal move 39... Bc2??. This move lets White force many of Black's moves, but Fritz doesn't care because it appears to be able to win more material along the way. White responds with 40. Qxh4 and Black resigns after 40. ... gxh4 41. Rc1 Rxb3? 42. Nxb3 Bxb3 43. a5 Nc4 44. b5 Ba4 45. bxa6 Bc6 46. a7 Kg7 47. a6 Ba8 48. Rb1.

This problem occurs because computers only search a certain number of moves ahead. Human players usually have enough intuition to decide whether to abandon a bad-looking move, or search a promising move to a great depth. A quiescence search attempts to emulate this behavior by instructing a computer to search "interesting" positions to a greater depth than "quiet" ones (hence its name) to make sure there are no hidden traps and, usually equivalently, to get a better estimate of its value.

Any sensible criterion may be used to distinguish "quiet" moves from "noisy" moves; high activity (high movement on a chess board, extensive capturing in Go, for example) is commonly used for board games. As the main motive of quiescence search is usually to get a good value out of a poor evaluation function, it may also make sense to detect wide fluctuations in values returned by a simple heuristic evaluator over several ply. Modern chess engines may search certain moves up to 2 or 3 times deeper than the minimum. In highly "unstable" games like Go and reversi, a rather large proportion of computer time may be spent on quiescence searching.

This pseudocode illustrates the concept in an algorithmic manner:

function quiescence_search("node", "depth") if "node" appears quiet or "node" is a terminal node or "depth" = 0 return estimated value of "node" else //One might use minimax or alpha-beta search here... search children of "node" using recursive applications of quiescence_search return estimated value of children //...and here function normal_search("node", "depth") if "node" is a terminal node return estimated value of "node" else if "depth" = 0 if "node" appears quiet return estimated value of "node" else return estimated value from quiescence_search("node", reasonable_depth_value) else search children of node using recursive applications of normal_search return estimated value of children

References