Computer Chess Club Archives




Subject: Re: Verified Null-Move Pruning, ICGA 25(3)

Author: Robert Hyatt

Date: 19:27:27 11/21/02

Go up one level in this thread

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...

>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.
>>I am working on this.  I'll certainly post the results when I get it to work
>>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.
>>>>zipped pdf:
>>>>gzipped postscript:

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.