Computer Chess Club Archives


Search

Terms

Messages

Subject: Verified nullmove is BS

Author: Vincent Diepeveen

Date: 18:36:31 11/21/02

Go up one level in this thread


On November 20, 2002 at 17:20:30, Omid David Tabibi wrote:

>On November 20, 2002 at 16:36:08, Vincent Diepeveen wrote:
>
>>
>>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.
>>
>
>A verification method used for detecting zugzwangs was described by Plenkner
>(1995), and was most probably in use even before that. However, a verification
>search to enhance the tactical strength has never been used before.

Very clearly what you write here.

There is no difference algorithmically seen between

  a = 1;
  if( x )
    a = 3;

and:

  if( !x )
    a = 1;
  else
    a = 3;

Same is true for 'your' algorithm which is a rewrite of
an older zugzwang finding algorithm:

Your implementation goes schematically like:
if( conditionsfornullmove allowed ) {
  score = -alfabeta(..,depthleft-ReductieFactor-1);
  if( score >= beta ) {
    depthleft--;
    ..
  }

  again:
  for all moves( .. )
    score = -alfabeta(..,depthleft-1);

  if( bestscore >= beta ) {
    ..
    goto again;
  }

  return bestscore;
}

That's no difference with the already published:

// nullmove code
if( conditionsfornullmove allowed ) {
  score = -alfabeta(..,depthleft-ReductieFactor-1);
  if( score >= beta ) {
    // verificatie eerst
    score = -alfabeta(..,depthleft-1-R);
    if( score >= beta )
      return score;
  }

  for all moves
    score = -alfabeta(..,depthleft-1);

  return bestscore;
}

That's no algorithmic difference.

Also just 1 ply reduction is just too expensive for a 'verification'
search.

That's too costly for any decent chess program.

Even in my draughtsprogram where i also experimented with
i needed 2 ply reduction. 1 was too expensive.

Of course nullmoving is not a good idea in draughts. I removed it
later obviously that algorithm.

But now *show* me what your theory is why it would be tactical
stronger to search more fullwidth?

Of course, you compare depth tables with each other.

Of course a 12 ply fullwidth search is tactical sometimes
better than a 12 ply search with nullmove.

That's what you proof. that's no proof. Proof me you
get that 12 ply FASTER with fullwidth. You didn't do that.

Your results compare depths not search times to find positions.

This is trivial crap what you write.

>The greater tactical strength comes from the detection of some of the tactical
>problems that wouldn't have been detected by the standard null-move pruning due
>to the horizon effect.
>
>
>>  b) how can you claim it works?
>
>"It is impossible, because I couldn't do it." --Vincent Diepeveen
>
>>     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.
>>
>
>The simpler your quiescence search is, the better will be the total gain from
>verified null-move pruning. If your quiescence is huge, then you might end up
>with a search tree, greater than standard R = 2 on occasions. However, even
>then, starting from a certain depth, the tree constructed by verified null-move
>pruning will be smaller than that of the standard one.
>
>
>>  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.
>>
>
>1. Double null-move is intended mainly for detecting zugzwangs; whilst verified
>null-move constructs a smaller search tree with greater tactical strength in
>middle games (in addition to detecting zugzwangs).
>
>2. There is no published article regarding your double null-move, so I couldn't
>even mention it in my references!
>
>>  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+).
>>
>
>That's right, it is costly. But as the presented figures show, the cost of R = 3
>plus verification is less than the cost of R = 2.
>
>>     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.
>>
>
>One final remark: You use standard R = 3 in DIEP. So the search tree constructed
>by your program will definitely be smaller than that of verified R = 3. Many
>people find standard R = 3 as too risky; but if you are happy with its overall
>tactical strength, then I don't recommend you to shift to another method. But
>for those who'd like to get greater tactical strength than standard R = 2, and a
>smaller search tree than R = 2, I recommend to try verified null-move pruning.
>
>Best,
>
>Omid.
>
>
>>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.21 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.