quiescence search

A game search that stops at a fixed depth has a problem: if a tactical action is in progress at the end of the variation, the evaluation function may give unreliable answers. In a chess search, for example, the white's last move may be queen takes knight, and the evaluation function will report that white is up a knight. If the search looked one move deeper, it would see that black has the reply pawn takes queen, and realize that black is winning.

One way out is to use a smart evaluation function that understands tactical actions and predicts their outcome. But tactics are hard, and in general to get good answers you have to do a search.

A quiescence search is an additional search, starting at the leaf nodes of the main search, which tries to solve this problem. In chess, quiescence searches usually include all capture moves, so that tactical exchanges don't mess up the evaluation. In principle, quiescence searches should include any move which may destabilize the evaluation function--if there is such a move, the position is not quiescent.

Not all search algorithms require a quiescence search. A smart selective search might, in effect, do its own quiescence searching as a natural part of its operation. But fast dumb search algorithms, the kind that provide strong play in many games, usually need a smarter quiescence search to avoid errors. It's logical to try to get the best of both worlds by combining a dumb search with a smart selective search for quiescence.

The need for quiescence search brings up some tough--oops, I mean fun--questions for machine learning in games. What kind of quiescence search will work well for a wide range of games? Is there one which, perhaps, has a few parameters that can be automatically tuned for different games? Don Beal's consistency search is a kind of game-independent quiescence search, but I don't know how well it works.

Some games, like go and backgammon, are not suited for fast dumb search. In those games, the entire search (if any) might be what is called a quiescence search in checkers or chess.