Computer Chess Club Archives




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

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.

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;
  IF depth = d THEN RETURN (evaluate(p))
  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;
         RETURN (m);

[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 }
  IF depth = 0 THEN                         { horizon node, maximum depth? }

  posn := Generate(p);                      { point to successor positions }
  IF empty(posn) THEN                                    { leaf, no moves? }
                                                    { 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 ;

As for your question, both algorithms re-search with window


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.