|
Hey, it looks like there are dozens (and dozens) of you reading this series! I'm tickled pink!
In this next-to-last article, we will examine advanced search-related techniques which can speed up and/or strengthen your chess-playing program. In most cases, the concepts (if not the actual code) also apply to a variety of other 2-player games; adapting them to your particular problem, however, shall remain an exercise for the proverbial reader.
Why Bother?
So far, all of the search algorithms we have looked at examine a position's consequences to a fixed "depth". However, this is rarely a good thing. For example, suppose that your program uses an iterative-deepening alpha-beta algorithm with maximum depth 5-ply. Now look at these cases:
- Along a certain line of play, you discover a position where one of the players is checkmated or stalemated at depth 3. Obviously, you don't want to keep searching, because the final state of the game has been resolved. Not only would searching to depth 5 be a colossal waste of effort, it may also allow the machine to finagle its way into an illegal solution!
- Now, suppose that, at depth 5, you capture a pawn. The program would be likely to score this position in a favorable light, and your program might decide that the continuation leading to it is a useful one. However, if you had looked one ply further, you might have discovered that capturing the pawn left your queen undefended. Oops.
- Finally, suppose that your queen is trapped. No matter what you do, she will be captured by the opponent at ply 4, except for one specific case where her death will happen at ply 6. If you search to depth 5, the continuations where the queen is captured at ply 4 will be examined accurately, and scored as likely disasters. However, the unique line of play where the queen is only captured at ply 6 (outside of the search tree) doesn't reveal the capture to the machine, which thinks that the queen is safe and gives it a much better score! Now, if all you have to do to push the queen capture outside of the search tree is delay the opponent with a diversion, doing so may be worth the risk: although it could damage your position, it might also cause the opponent to make a mistake and allow the queen to escape. But what if you can only delay the queen capture by sacrificing a rook? To the machine, losing a rook at ply 4 is less damaging than losing a queen, so it will merrily throw its good piece away and "hide" the too-horrible-to-mention queen capture beyond its search horizon. (During its next turn, of course, the machine will discover that the queen must now be captured at ply 4 in all cases, and that it has wasted a rook for no gain.) Hans Berliner described this "horizon effect" a long time ago, and it is the most effective justification for the "quiescence search" described in the next section.
The bottom line is this: a great many positions in chess (and in other games as well) are just too chaotic to be evaluated properly. An evaluation function can only be applied effectively to "quiet" positions where not much of importance is likely to happen in the immediate future. How to identify these is our next topic.
|
Unite 2010
