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

- Re: Negascout == PVS (with references)
**Stuart Cracraft***07:05:48 08/03/04* - Re: Negascout == PVS (with references)
**Tony Werten***01:00:19 08/03/04*

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.