Author: Omid David Tabibi
Date: 16:36:45 08/07/03
Go up one level in this thread
On August 07, 2003 at 19:25:38, Dieter Buerssner wrote:
>Another interesting thing there, I cite the code from the URL:
>
>
>int PrincipalVariation (pos, depth, alpha, beta)
>{
> if (depth == 0) return Evaluate(pos);
> succ = Successors(pos);
> pos = RemoveOne(succ);
> best = -PrincipalVariation(pos, depth-1, -beta, -alpha);
> while (not Empty(succ) && best < beta)
> {
> pos = RemoveOne(succ);
> if (best > alpha) alpha = best;
> value = -PrincipalVariation(pos, depth-1, -alpha-1, -alpha);
> if (value > alpha && value < beta)
> best = -PrincipalVariation(pos, depth-1, -beta, -value);
> /* ^^^^^^ */
> else if (value > best)
> best = value;
> }
> return best;
>}
>
>I think, Reinefeld formulated his Negascout similarily. The research with
>-value can leave you without a PV (even in the cases of a search without
>qsearch/extensions/pruning). Often programs only update the PV, when it is
>inside the window. But it might be the case, that the correct score is just
>value. This is a bound in the research (and so not inside the window). In this
>case, many typical engines would come up with no PV at at all. Using -value+1
>instead would fix it.
I think due to the search instability, the best thing is to use the full window
upon re-search, i.e., in the example above:
if (value > alpha && value < beta)
best = -PrincipalVariation(pos, depth-1, -beta, -alpha);
/* ^^^^^^ */
Another thing I find interesting is the two different implementations of PVS:
I) Use full window for the first child, and minimal window (alpha, alpha + 1) in
all other childs (like the pseudo-code above. This is the PVS version used in
Crafty).
II) Use full window for all childs until you find a PV, then use minimal window
for all other childs (see Bruce Moreland's pseudo-code).
I use the latter (although the difference is negligible).
>
>Regards,
>Dieter
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.