Author: Russell Reagan
Date: 19:38:09 01/28/04
I was reading a newsgroup post, and now I'm confused. The whole post can be
found here (the first search result):
http://groups.google.com/groups?q=%22The+meaning+of+Alpha+and+Beta%22
The part that confused me is regarding aspiration search. Dr. Hyatt is
describing the situation where the aspiration search fails high.
Dr. Hyatt writes:
>This score will be >= beta in the above case and that particular move will
>return a score of beta (or >= beta) which means beta was too low. You have
>to increase beta and search the move _again_ to get the true score..."
To me this says that if your aspiration search of AlphaBeta(depth, alpha, beta)
fails high, you can find the real score by re-searching with AlphaBeta(depth,
beta-1, INFINITY).
So now let's go to Bruce Moreland's webpages.
http://www.brucemo.com/compchess/programming/aspiration.htm
Bruce writes:
>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!
Then he gives this bit of code as an example of what is not supposed to work
(basically an iterative deepening search with aspiration search at the root):
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++;
}
Bruce writes:
>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:
>
>1. The search with (alpha, beta) failed high.
>2. The re-search with (beta - 1, INFINITY) failed low.
>3. The re-search with (-INFINITY, alpha + 1) failed high.
>4. And so on, and so on, and so on ..."
The writings of Dr. Hyatt and Bruce seem to conflict. So what's the true story
here? I have a feeling I'm misunderstanding something.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.