Author: Vincent Diepeveen
Date: 19:36:25 11/21/02
Go up one level in this thread
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.