Author: Vincent Diepeveen
Date: 19:50:53 11/21/02
Go up one level in this thread
On November 21, 2002 at 22:36:25, Vincent Diepeveen wrote: hi, you need another parameter. If in nullmove section the near to fullwidth search is < beta, then in fact a parameter always turned on false, now becomes true and that's that you need a complete fullwidth search. that's a small addition to the 'verification search' which is complete useless and very inefficient IMHO. but it will make it perform even worse of course at ECM. Best regards, Vincent >On November 21, 2002 at 22:27:27, Robert Hyatt wrote: > >>On November 21, 2002 at 22:05:15, Vincent Diepeveen wrote: >> >>>On November 21, 2002 at 11:14:24, Robert Hyatt wrote: >>> >>>Just go for a 2 minute single cpu implementation. >>> >>>But of course you will find that R=2 always will outperform >>>already his verification search with 1 ply reduction. >>> >>>You can implement it quicker his algorithm by doing next >>>after nullmove: >>> >>>int Search(alfa,beta,depthleft,allowingnull) { >>> .. >>> >>> if( !allowingnull && nullmoveok ) { >>> .. try nullmove >>> if( score >= beta ) { // score returned by nullmove >>> score = Search(alfa,beta,depthleft-1,true); >>> // last parameter to prevent another reduction next position >>> if( score >= beta ) { >>> StoreInHashtableAndKillerTable(..); >>> return score; >>> } >>> } >>> } >>> .. >>> >>>This is a more elegant way to implement it, and it was already done >>>years ago and published in ICCA journal. >> >>That's the way I did it. No goto's in Crafty except for one >> >>However there is much more to it than that, in terms of passing the >>nonull/noverify flag down thru the search calls... > >if you try to get it to work in parallel obviously that's true. >basically that flag is true only when you do a research from >nullmove area and otherwise false. > >Also don't fall for a hashtable trap here. > >Still both implementation methods will obviously have the >Fail High reduction hashtable bug when it is possible to get >to positions with transpositions which matter for the root. > >So in positions where there is many sequences it suffers >from the same bugs. In that respects of course both verification >search and the zugzwang detection (which both is the same >algorithm implemented in 2 different ways) suffer from it. > >I have played for years with the zugzwang detection code as above >in my draughts program (checkers international 10x10). Until i >found out that nullmoving is a very good move there actually :) > >But it was great to find tactics. Forcings they are called in >international checkers. > >That's why i happen to know the price of doing a fullwidth search >nearly as a method to detect whether a nullmove is allowed to cutoff. > >That whole depthleft-1 search you are basically doing to detect >a zugzwang happening or whether the extra depth helps to find tactics. > >That's a *very* expensive way to nullmove :) > >Basically double nullmove doesn't suffer from the Fail High reduction >problem, but of course it is reducing the depth so drastically for the >research that it's really another implementation of it, for sure more >elegant, and also bugfree :) > >> >>> >>>That's pretty quickly done in crafty Bob :) >>> >>>>On November 21, 2002 at 10:15:47, Bernhard Bauer wrote: >>>> >>>>>Hi Omid, >>>>> >>>>>would you implement your pruning technique in crafty so the benefits could be >>>>>tested by everybody? >>>>>That way we would have the best comparison. >>>>>regards >>>>>Bernhard >>>> >>>>I am working on this. I'll certainly post the results when I get it to work >>>>right. >>>>It is a bit tricky if you try to do it cleanly... >>>> >>>> >>>>> >>>>>On November 20, 2002 at 11:43:10, Omid David Tabibi wrote: >>>>> >>>>>> >>>>>> ICGA Journal, Vol. 25, No. 3, pp. 153-161, September 2003 >>>>>> >>>>>> >>>>>> Verified Null-Move Pruning >>>>>> >>>>>> Omid David Tabibi and Nathan S. Netanyahu >>>>>> >>>>>> >>>>>> Abstract >>>>>> >>>>>>In this article we review standard null-move pruning and introduce our extended >>>>>>version of it, which we call verified null-move pruning. In verified null-move >>>>>>pruning, whenever the shallow null-move search indicates a fail-high, instead of >>>>>>cutting off the search from the current node, the search is continued with >>>>>>reduced depth. >>>>>> >>>>>>Our experiments with verified null-move pruning show that on average, it >>>>>>constructs a smaller search tree with greater tactical strength in comparison to >>>>>>standard null-move pruning. Moreover, unlike standard null-move pruning, which >>>>>>fails badly in zugzwang positions, verified null-move pruning manages to detect >>>>>>most zugzwangs and in such cases conducts a re-search to obtain the correct >>>>>>result. In addition, verified null-move pruning is very easy to implement, and >>>>>>any standard null-move pruning program can use verified null-move pruning by >>>>>>modifying only a few lines of code. >>>>>> >>>>>> >>>>>>pdf: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.pdf >>>>>>zipped pdf: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.pdf.zip >>>>>>gzipped postscript: http://www.cs.biu.ac.il/~davoudo/pubs/vrfd_null.ps.gz
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.