Computer Chess Club Archives




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

Author: Vincent Diepeveen

Date: 13:36:08 11/20/02

Go up one level in this thread

Omid i have 3 points
  a) in my draughtsprogram around 1997,1998 i had already
     the same algorithm as you describe in my 10x10 checkersprogram
     which then was called dr initially later called Napoleon.

     I didn't invent it myself however, it was already published in some
     article back then if i remember well. Hopefully for you not an ICCA
     article but only RGCC, if memory serves well however it was also
     published in ICCA journal.

     How can you claim it is a 'new algorithm' anyway? This trick has
     been described over the years already everywhere and no one could
     use it because overhead was too big.

  b) how can you claim it works? Even for draughts it doesn't work,
     not to mention chess. R=3 as you show is giving like 40% to 50%
     reduction even in your own experiments. Unless your qsearch is idiotic,
     that means that you will see of course more tactics without that
     reduced search. Your claim is based upon showing the depths that
     solve positions. This is not fair. Time counts, not the searchdepth.
     If you get 12 ply with R=3 within 3 minutes and you get 9 ply with
     your 'verified nullmove' in 3 minutes, then you must compare that
     9 ply search versus the 12 ply search, not compare the 2 searches of
     9 ply. That's what i call misinformation.

  c) I miss the comparision with double nullmove. In fact double nullmove
     is the same thing in a smarter way implemented and with a smaller
     verificiation depth. Like depth-2-2R instead of depth-1.
     The implementation of double nullmove is more
     elegant though and its implementation is correct where your implementation
     is assuming a lot.

  d) you reduce the depth only 1 ply. How the HELL can it be better than
     even R=2. If i do a verification search of depthleft-1, then
     i search like 3 ply less than i do now. So that's worse than even
     R=2 for nullmove. I cannot imagine that there is strong programs
     which can afford a depthleft-1 reduction search. For singular extensions
     *after* nullmove (so the cutoff of nullmove has been given already)
     i do R=3 reduction, even that is too costly already at bigger search
     depths (11+).

     Perhaps you can enlighten us a little. and show some outputs of your
     program. I need outputs simply on positions. with node counts there
     for each ply. Let's compare things. I do not understand. How can you
     afford to search with depthleft-1 in a node where i already have
     done a cutoff?

     If i do it, i'm nearly searching fullwidth then.

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