Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Verified nullmove is BS

Author: Omid David Tabibi

Date: 03:07:49 11/22/02

Go up one level in this thread


You haven't read the article at all, and haven't got a clue what you are talking
about.

You even don't know that node comparison at fixed depth is a far better method
that a fixed time which can't be reproduced, is not accurate at all, and is too
dependent on your system and program.

Instead of trying to find out why a certain innovation doesn't work, trying
finding something that *does* work, and contribute to the computer chess
community you claim to be part of.




On November 21, 2002 at 21:36:31, Vincent Diepeveen wrote:

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