Computer Chess Club Archives


Search

Terms

Messages

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,
>
>Roberto

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

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

NegaScout:
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
http://www.uni-paderborn.de/pc2/people/homes/ar/r_nsc.htm
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.06 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.