Computer Chess Club Archives




Subject: Re: Zero-width Window Null Move Search

Author: Guido Schimmels

Date: 08:01:24 06/18/98

Go up one level in this thread

On June 17, 1998 at 22:25:12, Roberto Waldteufel wrote:

>On June 15, 1998 at 12:41:26, Ren Wu wrote:
>>I used to use PVS but switch to NegaScout some time ago, but after that
>Please would you explain what is the difference? I was under the impression that
>PVS and Negascout were one and the same algorithm, namely search first move with
>window [alpha,beta], then search remaining moves with window [alpha, alpha+1]
>with a research if necessary. If this is wrong, I would like to know.
>Best wishes,

Well, *almost* the same.
PVS comes from Schaeffer et al., NegaScout is from Reinefeld.

value = PVS(-(alpha+1),-alpha)
if(value > alpha && value < beta) {
  value = PVS(-beta,-alpha);

value = NegaScout(-(alpha+1),-alpha)
if(value > alpha && value < beta && depth > 1) {
 value2 = NegaScout(-beta,-value)
 value = max(value,value2);

The difference is how they handle researches:
PVS passes alpha/beta while NegaScout passes the value returned by the
null window search instead of alpha. But then you can get a fail-low on
the research due to search anonomalies. If that happens NegaScout returns
the value from the first search. That means you will have a crippled PV :-(
Then there is a refinement Reinefeld suggests which is to ommit the
research at the last two plies (depth > 1)- but that won't work in a real
program because of search extensions...
NegaScout is slightly an ivory tower variant of PVS (IMHO).

Look at
for the whole story.
You will  also find there a link to Reinefeld's
ICCA Journal article, ready for download.

- Guido

This page took 0.01 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.