Upcoming Events
Unite 2010
11/10 - 11/12 @ Montréal, Canada

GDC China
12/5 - 12/7 @ Shanghai, China

Asia Game Show 2010
12/24 - 12/27  

GDC 2011
2/28 - 3/4 @ San Francisco, CA

More events...
Quick Stats
88 people currently visiting GDNet.
2406 articles in the reference section.

Help us fight cancer!
Join SETI Team GDNet!
Link to us Events 4 Gamers
Intel sponsors gamedev.net search:


 Why Bother?
 Quiet, Please!
 Aspirated Search

 Printable version


  The Series

 Getting Started
 Data Structures
 Move Generation
 Basic Search
 Advanced Search


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.

Next : Quiet, Please!