Computer Chess Club Archives


Search

Terms

Messages

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

Author: Vincent Diepeveen

Date: 19:05:15 11/21/02

Go up one level in this thread


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