Author: Robert Hyatt
Date: 19:50:05 01/28/04
Go up one level in this thread
On January 28, 2004 at 22:38:09, Russell Reagan wrote:
>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.
Both are right.
Technically, what happens is that it is possible for you to do a very deep
search at the root, say when pondering, and you store a hash table entry for
position "P" that says score >= .60, depth=15. Now after that long ponder, your
opponent plays a different move. Each time you hit position P, you can use that
>= .60 score because of the extreme draft stored in the table. And if your
current beta value is (say) .3, then you will fail high since the table entry
says >= .6. But when you relax beta, and re-search, now when you hit table
entry P, you get sufficient draft, but the flag says "LOWER" which means that
the .6 value stored is the LOWER bound. That is useless here since our UPPER
bound (beta) is +infinity. You can't use it. And you are not searching deep
enough to see the reason for the fail high, so now you fail low.
That won't cause a problem if you implement it correctly, and the fail high _is_
the correct result for the best move. But you have to take care that the
fail-low doesn't cause a re-search when you fail high again. And you have to be
sure that you realize that after the fail-high, _that_ is the move you want to
play even if it fails low on the re-search.
Bruce's case is a pathological problem that will happen. But it is caused by an
extreme happening. In a normal search this won't/can't happen (assuming you are
not using null-move). But in reality it can. However, 99.9% of the time,
re-searching with beta,+infinity after a fail high on alpha,beta will produce a
score as expected...
This page took 0.01 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.