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

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.