Author: Guido Schimmels
Date: 04:05:39 06/23/98
Go up one level in this thread
On June 22, 1998 at 13:35:02, Roberto Waldteufel wrote:
>
>Hi Guido,
>
>It seems I had misinterpreted Negascaout. Perhaps my misinterpretation even
>constitutes a new variant of this family of search algorithms. My metod on each
>iteration is as follows:
>
>At each node, I search the first move with window {alpha,beta):
>
>value=-Search(-beta,-alpha,depth-1)
>If value>alpha then
> If value>=beta then
> Search=value
> Exit
> End If
> Alpha=value
>End if
>
>
>
>Then, if I did not get a beta cut-off, for each subsequent move from that node I
>do a null width search, with a research if necessary,like this
>
>value=-Search(-alpha-1,-alpha,depth-1)
>If (value>alpha) and (value value=Search(-value,beta,depth-1)
>End if
>
>If value>alpha then
> If value>=beta then
> Search=value
> Exit
> End If
> Alpha=value
>End if
>
>This was my interpretation (or misinterpretation) of Reinfeld's pseudo-code. To
>be more precise, I search to depth instead of depth-1 if the side to move is in
>check. Compared to classical alpha beta with infinite window, it was a great
>improvement. I'll have to look at Reinfeld's code again a bit more closely, but
>my method seems to work so well that I would need to be really convinced before
>recoding it all over again. Do you think I could improve my speed with a proper
>PVS? Maybe I waste a lot of time searching the first move to full width instead
>of with a null window.
>
>Best Wishes,
>
>Roberto
Sorry, my lazyness obviously left a totally confused Roberto :-(
What you are doing is definitely NegaScout as Reinefeld suggested it.
The code I gave was only the part where I thought PVS and NegaScout
are different. The pv itself of course will be searched with the normal
alpha/beta window.
int PVS(int alpha, int beta, int depth)
int best;
{
Getmove();MakeMove();
best = -PVS(-beta,-alpha);
while(Getmove()) {
MakeMove()
value = -PVS(-(alpha+1),-alpha)
if(value > alpha && value < beta) {
value = -PVS(-beta,-alpha);
}
UnMake();
if(value > best) {
best = value;
if(best > alpha) {
if(best >= beta) return(best);
alpha = best;
}
}
}
return(best);
}
int NegaScout(int alpha, int beta, int depth)
{
int best;
Getmove();
MakeMove();
best = -NegaScout(-beta,-alpha);
UnMake();
while(Getmove()) {
MakeMove();
value = -NegaScout(-(alpha+1),-alpha)
if(value > alpha && value < beta && depth > 1) {
value2 = -NegaScout(-beta,-value)
value = max(value,value2);
}
UnMake();
if(value > best) {
best = value;
if(best > alpha) {
if(best >= beta) return(best);
alpha = best;
}
}
}
return(best);
}
As I explained in my original post, the difference between PVS and
NegaScout is the way they handle the research. My sources are
the Reinefeld ICCA article and Crafty. So I haven't read the original text
about PVS, I looked at the Crafty source and Bob says he does PVS.
- 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.