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.