Author: Bruce Moreland
Date: 09:52:01 03/26/98
Go up one level in this thread
On March 26, 1998 at 10:32:51, KyoJin Kim wrote:
>Hi, Bob!
>
>I try to understand source code of Crafty.
>I KNOW BASIC deep alpha beta pruning of negamax searh algorithm.
>I have question about this this part of code in search.c.
>
> if (first_move) {
> value=-ABSearch(-beta,-alpha,ChangeSide(wtm),
> depth+extensions,ply+1,DO_NULL);
> }
> else {
> value=-ABSearch(-alpha-1,-alpha,ChangeSide(wtm), <=== ????
> depth+extensions,ply+1,DO_NULL);
> if (value>alpha && value value=-ABSearch(-beta,-alpha,ChangeSide(wtm),
> depth+extensions,ply+1,DO_NULL);
> }
> }
>
>Could you explain to me this part?
>Is there any book or document which explanin about this (windows ?) ?
What he is doing is the basis for several alpha-beta optimizations. I
believe that the one Bob is using is called PVS, which stands for
"Principle Variation Search".
The idea is that for the first move you search, you do it normally. You
pass it the full window: alpha, beta.
For moves other than this first move, you assume that they are going to
stink.
If you are right, they won't exceed alpha. So you trim the window down
so that rather than searching with alpha, beta, you are searching with
alpha, alpha+1. Most of the time the move will come back with a value
under alpha, so you save time because you don't give it the full window
to search.
If it turns you you were wrong, that the move didn't stinck, you have to
admit you were wrong and go back and search the move with alpha, beta.
This is exactly what is happening in the above code, although it is a
little hard to understand, because alpha and beta are reversed and
negated before they are passed to the recursive "search" call.
This supposedly saves approximately 10% of search overhead. In my own
experiments it has alwas been a measurable savings, but I don't have an
exact number.
Example:
Assume that the first move you search is 1. e4, and you pass it a window
of -40, +40. This comes back with a value of +20. So now alpha is 20
and beta is 40.
The second move you search is 1. d4. You could search this with a
window of +20, +40, but you know that because you have a good hash table
and good move ordering, usually the first move is the best one, so you
expect to get a value of <= +20. So you search instead with +20, +21.
If you were right, and 1. d4 was worse than 1. e4, you'll get something
<= +20 back, and you can discard this move like normal.
If you were wrong, you'll get something >= +21, and you need to research
with +20, +40 again.
bruce
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.