Computer Chess Club Archives




Subject: Re: negascout and PVS?

Author: Fabien Letouzey

Date: 03:34:54 07/27/04

Go up one level in this thread

On July 26, 2004 at 19:47:21, Peter Alloysius wrote:

>What's the different between negascout and PVS ? They look like the same
>algorithm to me.

Somebody who has the two original articles can correct me if I'm wrong:

PVS was published first.  It combines the scout idea by Pearl with alpha-beta
pruning.  The definition uses two functions: PVS() for the PV nodes and TEST()
for the scout searches.

I am not sure about the TEST part, which comes from the original SCOUT.
Algorithmically, TEST is equivallent to a fail-hard NWS (AlphaBeta with null
window, as used in the MTD framework).  NWS is sometimes called MWS or even ZWS
in on-line documents.

NegaScout re-formulates PVS with only one function.  TEST is replaced with
AlphaBeta, which enables the use of known improvements such as fail-soft.  The
re-search window is reduced as I mention in  There is also a "trick"
near the leaves which can (should!) be ignored.  It can only avoid re-searching
a handful of nodes at best, and is anyway incompatible with most refinements
used in real-world programs such as quiescence search, lazy eval, etc ...

Knowledgeable readers, please correct me as I tried to guess from references

Also among those differences, I am not sure which distinguishes PVS and
NegaScout the most.  If it is the two-function vs. one-function property, it
could be argued that most scout-based chess programs use some form of NegaScout.

I prefer to think in terms of algorithms (as in the tree that is actually
searched) rather than implementation, and the re-search window strikes me as the
main characteristic.


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.