# Computer Chess Club Archives

## Messages

### Subject: Re: Negascout == PVS (with references)

Author: Tony Werten

Date: 01:00:19 08/03/04

Go up one level in this thread

```On August 02, 2004 at 03:33:55, Dennis Breuker wrote:

>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).

In the negascout algo "OR (depth >= d-2)" the 2 should be a 1, as wel as in the
PVS " AND (depth > 2)"

The original writers assumed that a failsoft will always return the true score
for the last 2 ply, which in principle is true, but because of extensions, you
never know if there really are only 2 plies afterwards.

With 1 ply remaining you go straight into quiescence wich will give you the real
score ( so no need to research )

Tony

>[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

```