Author: Yngvi Bjornsson
Date: 15:40:15 01/28/00
Go up one level in this thread
On January 28, 2000 at 17:51:45, Tim wrote:
>I know what principal variation search is.
>But I don't understand returned value when window size so small.
>This is principal variation search algorithm.
>
> if (Firstmove) {
> value=-Search(-beta,-alpha);
> Firstmove=0;
> }
> else {
> value=-Search(-alpha-1,-alpha);
> if ((value > alpha) && (value < beta))
> value=-Search(-beta,-alpha);
> }
>
>Above code says:
>If it is not the first move, search with window size 1.
>if value <= alpha or value >= beta, we don't have to search again.
>if value > alpha and value < beta, search again with normal window size.
>
>But how can we sure value is always correct when value <= alpha or value >=
>beta?
The value returned is not the correct value, its a bound: if < alpha then an
upper-bound, if >= alpha then a lower-bound. If the value is less than alpha, we
know that the correct value must also less than alpha (because the value
returned is an upper-bound). In that case we are simply not interested in
knowing the correct value, because it cannot possibly improve on the currently
best-move found. Similarly, if the value returned exceeds beta (or same), we
know that the correct value is also greater than beta. However, how much greater
doesn't really matter, because the returned value is already good enough to
cause a cutoff. In that case, the value returned by PVS will not be a correct
value, but a lower-bound.
>And how can we sure value is always incorrect when value > alpha and value <
>beta?
It's not necessarily incorrect, the point is, you don't know. If the value
returned by the minimal-window search is > alpha you only know that the value
is a lower-bound on the correct value. The lower-bound could could be the
same as the correct value, however, you don't know; that's why you have to
re-search to get the correct value.
-Yngvi
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.