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 name for this problem is the horizon effect. A full-width search sees everything up to its horizon, and nothing beyond. It will happily go for moves that look good within the horizon but soon turn bad, like the queen takes knight example above. It will also happily make a bad move in the face of an inevitable problem, if the bad move pushes the problem over the horizon: “Uh oh, I’m going to lose a pawn unless I play this check.... Oh, I’m still going to lose a pawn, and now my pieces are on bad squares to boot.”

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 simpleminded depth-limited search algorithms, the kind that provide strong play in many games, usually need a quiescence search to avoid errors (though of course it depends on the game). 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.

All this, of course, only applies to depth-limited searches. Monto Carlo tree searches of the kind used in backgammon and go do not have simple depth limits and therefore do not suffer from the horizon effect.