Back Up Next

Iterative Deepening

A idea that is even better than it sounds

If you are about to start searching a chess position, how deep should you search it?  It is difficult to predict in advance how long a search will take, since the time it takes to complete a search of depth D is dependent upon factors that  might not be obvious.  In a complex middlegame position, you might search not very deeply at all, while in an ending you might search significantly deeper, and in some king+pawn endings you might be able to search a hundred plies.

An idea is to search to depth one.  If this search completes in less than the amount of time allocated, search again to depth two.  And then to depth three.  And so on, until you run out of time.

This all but guarantees pretty good time usage.  If you are able to perform a deep search quickly, you'll continue along and search even deeper the next time, and perhaps you'll finish that.  If the position is more complicated than you expected, you won't finish many plies of search, but you will have at least some legal move to play, since it's almost impossible to not finish a 1-ply search.

This idea is called iterative deepening, because what happens is you iterate the search, going one ply deeper each time (there is nothing magic about going one ply deeper, for instance you could try two, but one works very well).

Here is the code:

for (depth = 1;; depth++) {

    val = AlphaBeta(depth, -INFINITY, INFINITY);

    if (TimedOut())

        break;

}

It might surprise you that this is actually an extremely efficient way to search.  If you enhance alpha-beta so that it returns a principal variation, you can feed this principle variation back into the next iteration of search.

For instance, if a one-ply search indicates that 1. e4 is the best move, you will search 1. e4 first when you perform a two-ply search.  If that returns the line 1. e4 e5, you will search that line first when you perform a three-ply search.

The effect of this is that the first line you search tends to be good.  Alpha-beta is extremely sensitive to move ordering.  If your move ordering is bad, in chess your branching factor will be about 35.  If your move ordering is good, the branching factor will be closer to 6.  The principal variation from the previous iteration of the search function tends to be very good.

Iterative deepening provides you with a simple means of interrupting the search when you run out of time, and it makes your search more efficient.

 
Send mail to brucemo@seanet.com with questions or comments about this web site.
Copyright © 2001 Bruce Moreland
Last modified: 11/04/02