Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
Quiet, Please!There are two ways to assess a position's value: dynamic evaluation (i.e., look at what it may lead to) and static evaluation (i.e., see what it looks like on its own, irrespective of consequences). Dynamic evaluation is performed through search; as we have just mentioned, static evaluation is only feasible when the position is not likely to undergo an overwhelming change of balance in the near future. Such relatively stable positions are called "quiet" or "quiescent", and they are identified via "quiescence search". The basic concept of Quiescence Search is the following: once the program has searched everything to a fixed depth (say, 6-ply), we continue each line of play selectively, by searching "non-quiescent" moves only, until we find a quiescent position, and only then apply the evaluator. Finding a quiet position requires some knowledge about the game. For example, which moves are likely to cause a drastic change in the balance of power on the board? For chess, material balance tends to be the overwhelming consideration in the evaluator, so anything that changes material is fair game: captures (especially those of major pieces) and pawn promotions certainly qualify, while checks may also be worth a look (just in case they might lead to checkmate). In checkers, captures and promotions also seem like reasonable choices. In Othello, every single move is a capture, and "material balance" can change so much in so little time that it might be argued that there are no quiet positions at all! My own program uses a simple quiescence search which extends all lines of play (after a full-width search to depth X) by looking exclusively at captures. Since there are usually not that many legal captures in a given position, the branching factor in the quiescence search tends to be small (4-6 on average, and quickly converging to 0 as pieces are eaten on both sides). Nevertheless, the quiescence search algorithm is called on a LOT of positions, and so it tends to swallow 50% or more of the entire processing time. Make sure that you need such a scheme in your own game before committing to it. Only when no capture is possible does my program apply its evaluator. The result is a selectively-extended search tree which is anything but fixed-depth, and which defeats most of the nasty consequences of the "horizon effect".
|
|
|
|
