Contents  Why Bother?  Quiet, Please!  Null-Move  Aspirated Search  Singular  Extensions  Printable version     The Series  Getting Started  Data Structures  Move Generation  Basic Search  Advanced Search  Evaluation  Functions

Singular Extensions

One last thing before we leave the topic of search: in chess, some moves are obviously better than others, and it may not be necessary to waste too much time searching for alternatives.

For example, suppose that after running your iterative algorithm to depth N-1, you discover that one of your moves is worth +9000 (i.e., a capture of the opponent's queen) and all others are below 0.  If saving time is a consideration, like in tournaments, you may want to bypass the whole depth N search and only look at the best move to depth N instead: if this extra ply does not lower its evaluation much, then you assume that the other moves won't be able to catch up, and you stop searching early.  (Remember: if there are 35 valid moves at each ply on average, you may have just saved 97% of your total effort!)

Deep Blue's team has pushed this idea one step further and implemented the concept of "singular extensions".  If, at some point in the search, a move seems to be a lot better than all of the alternatives, it will be searched an extra ply just to make sure that there are no hidden traps there.  (This is a vast oversimplification of the whole process, of course, but that's the basic idea.)  Singular extensions are costly: adding an extra ply to a node roughly doubles the number of leaves in the tree, causing a commensurate increase in the number of calls to the evaluator; in other words, Deep Blue's specialized hardware can afford it, my cranky Java code can't.  But it's hard to argue with the results, isn't it?

Next Month

In Part VI, we wrap up the series with a discussion of evaluation functions, the code which actually tells your program whether a given board position is good or bad.  This is an immense topic, and people can (and do) spend years refining their own evaluators, so we will have to content ourselves with a rather high-level discussion of the types of features which should be examined and their relative importance.  If everything goes according to plan, I should also have some Java code for you to sink your teeth into at about that time, so stick around, won't you?

François Dominic Laramée, September 2000