Author: Dennis Breuker
Date: 00:33:55 08/02/04
Go up one level in this thread
On July 28, 2004 at 08:50:15, Fabien Letouzey wrote:
>On July 28, 2004 at 08:47:01, Fabien Letouzey wrote:
>
>>Can you confirm that PVS re-searches with window (value,beta), and not
>>(alpha,beta) as I claim, in Marsland's article?
>
>^^^
>
>This can be misinterpreted.
>
>Another way of looking at it is that, according to me, in NegaScout alpha is
>updated after the null-window search but not in PVS.
>
>Fabien.
Here are the two algorithms.
NegaScout as given here is less readable than PVS (I think)
because the loop searches all moves (and testing "IF (n = beta)",
meaning "if this was the first move") instead of searching
the first move separately.
Anyway, here they are:
Note that there are some small errors in the Negascout algorithm
given here, and the correct version is in Reinefeld's thesis
(but I could not find that in my attic).
[Source: ICCA Journal, Vol. 6, No. 4, p. 7]
FUNCTION negascout (p:POSITION; alpha, beta, depth: INTEGER) : INTEGER;
VAR i,t,m,n: INTEGER;
BEGIN
IF depth = d THEN RETURN (evaluate(p))
ELSE
BEGIN m := -infinity
n := beta
FOR i := 1 to b DO
BEGIN t := -negascout (p.i, -n, -max(alpha,m), depth+1);
IF t > m THEN
IF (n = beta) OR (depth >= d-2)
THEN m := t
ELSE m := -negascout (p.i, -beta, -t, depth+1);
IF m >= beta THEN RETURN (m);
n := max (alpha,m) +1;
END;
RETURN (m);
END;
END;
[Source: ICCA Journal, Vol. 9, No. 1, p. 10]
FUNCTION PVS (p : position; alpha, beta, depth : integer ) : integer;
{ p is pointer to the current node }
{ alpha and beta are window bounds }
{ depth is the remaining search length }
{ the value of the subtree is returned }
VAR score, j, value : integer;
posn : ARRAY [1..MXWIDTH] OF position;
{ Note: depth must be positive }
BEGIN
IF depth = 0 THEN { horizon node, maximum depth? }
Return(Evaluate(p));
posn := Generate(p); { point to successor positions }
IF empty(posn) THEN { leaf, no moves? }
Return(Evaluate(p));
{ principal variation? }
score :- -PVS (posn[1], -beta, -alpha, depth-1 );
FOR j := 2 TO sizeof(posn) DO BEGIN
IF (score >= beta) THEN { cutoff? }
GOTO done;
alpha := max(score, alpha); { fail-soft condition }
{ zero-width minimal-window search }
value := -PVS (posn[j], -alpha-1, -alpha, depth-1);
IF (value > score) THEN { re-search, if "fail-high" }
IF (alpha < value) AND (value < beta) AND (depth > 2) THEN
score := -PVS (posn[j], -beta, -value, depth-1);
ELSE score := value;
END ;
done:
Return(score);
END;
As for your question, both algorithms re-search with window
(value,beta).
Dennis
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.