iterative deepening: keep alpha/beta?

[flok]

Hi,

I'm implementing iterative deepening in my chess engine.
e.g.:

Code: Select all

   depth=1
   while(! time_is_up())
   {
        alpha = ...
        beta = ...
        score = alphaBeta(alpha, beta, depth);
        // do something with score
        depth++
    }

What I'm wondering now is: should I indeed each time reset alpha/beta to their initial values when I'm trying a deeper depth?


Thanks.

[tpetzke]

Unless you introduce yet another technique called "aspirations windows", the answer is yes, Reset them to the full window.

With aspiration windows you set them to some margin around the last value (alpha = last score - margin, beta = last score + margin) but must be prepared that if the returned score is not inside your assumed window you have to widen the window and do a research.

Thomas...

[ZirconiumX]

The classical iterative deepening driver has

(code from Bruce Moreland)

Code: Select all

for (depth = 1;; depth++) {
    val = AlphaBeta(depth, -INFINITY, INFINITY);
    if (TimedOut())
        break;
}

I think you are getting confused with Aspiration Windows, which is implemented like this:

(code from Bruce Moreland)

Code: Select all

#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++;
}

This allows you to get cut-offs quicker than with an open window, where beta-cutoffs are impossible.

Matthew:out

[bob]

Hi,

I'm implementing iterative deepening in my chess engine.
e.g.:

Code: Select all

   depth=1
   while(! time_is_up())
   {
        alpha = ...
        beta = ...
        score = alphaBeta(alpha, beta, depth);
        // do something with score
        depth++
    }

What I'm wondering now is: should I indeed each time reset alpha/beta to their initial values when I'm trying a deeper depth?


Thanks.

Most use the last iteration's score +/- some delta value that prevents excessive re-searching. For example, +/- 1/3 of a pawn works pretty well...

[Sven]

This allows you to get cut-offs quicker than with an open window, where beta-cutoffs are impossible.

Not quite: with an open window, beta-cutoffs are impossible at the root node but not necessarily down the tree.

Sven