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.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.