Author: Ernst A. Heinz
Date: 05:00:01 06/23/98
Go up one level in this thread
On June 23, 1998 at 07:05:39, Guido Schimmels wrote:
>
>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 -
Guido,
For the best of my knowledge of the published literature your explanations
w.r.t. the differences between PVS and NegaScout are totally correct.
My practical experiences with "DarkThought" slightly favor pure PVS over
NegaScout (1%-2% less nodes) starting at search depths >= 10 plies. At
higher depths I presume PVS to make more effective use of the transposition
table due to the always identical alpha bounds.
=Ernst=
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.