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.01 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.