
# Aspiration Windows

An aspiration window is an enhancement to iterative deepening.  The simplest implementation of iterative deepening works as follows:

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

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

    if (TimedOut())

        break;

}

Alpha-beta is called with a "window" of +/- INFINITY, presumably large positive and negative values.

It is possible to enhance this to a degree by making the assumption that the value of the search in the next iteration is not likely to be too much different from the value of the search in the iteration just completed.  Here's the code:

#define valWINDOW  50

 

alpha = -INFINITY;

beta = INFINITY;

for (depth = 1;;) {

    val = AlphaBeta(depth, alpha, beta);

    if (TimedOut())

        break;

    if ((val <= alpha) || (val >= beta)) {

        alpha = -INFINITY;    // We fell outside the window, so try again with a

        beta = INFINITY;      //  full-width window (and the same depth).

        continue;

    }

    alpha = val - valWINDOW;  // Set up the window for the next iteration.

    beta = val + valWINDOW;

    depth++;

}

The code for this got a little ratty but you can probably get past my use of "continue" if you try.  The idea is that the value of the last iteration of alpha-beta is fed into the current iteration.  Most of the time you'll get a value back that is between alpha and beta.  If you don't, you can try again with a wider window.

My re-search logic isn't very efficient, but I'm sure you can do better.  An obvious idea is to try to expand beta if the value that came back was greater than or equal to beta, and to expand alpha if the value was less than or equal to alpha, rather than expanding both alpha and beta, as I do above.  This can cause problems if you have search instability, which you will, so you have to be careful.  The code I provided will always work.

Search instability issues
This is yet another place where you have to be careful of search instability.  When I first added an aspiration window to my chess program, I assumed that if I got a value back that was greater than or equal to beta, that the re-search would result in a higher score the next time through.  Wrong!  I had hellacious crashing problems.  Here is the code:

alpha = -INFINITY;

beta = INFINITY;

for (depth = 1;;) {

    val = AlphaBeta(depth, alpha, beta);

    if (TimedOut())

        break;

    if (val <= alpha) {      // WRONG!

        alpha = -INFINITY;

        beta = val + 1;

        continue;
    }

    if (val >= beta) {       // WRONG!

        beta = INFINITY;

        alpha = val - 1;

        continue;
    }

    alpha = val - valWINDOW;

    beta = val + valWINDOW;

    depth++;

}

The above code would work great if you could be sure that your re-search would work.  But of course what happened to me is:

The search with (alpha, beta) failed high.
The re-search with (beta - 1, INFINITY) failed low.
The re-search with (-INFINITY, alpha + 1) failed high.
And so on, and so on, and so on ...
Anything you write needs to prevent this.

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