Computer Chess Club Archives




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

Author: Robert Hyatt

Date: 19:42:37 11/21/02

Go up one level in this thread

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

>On November 20, 2002 at 19:59:24, Martin Giepmans wrote:
>>On November 20, 2002 at 19:31:30, Omid David Tabibi wrote:
>>>On November 20, 2002 at 19:25:28, Martin Giepmans wrote:
>>>>On November 20, 2002 at 18:49:15, Omid David Tabibi wrote:
>>>>>On November 20, 2002 at 18:39:13, Martin Giepmans wrote:
>>>>>>On November 20, 2002 at 17:45:02, Omid David Tabibi wrote:
>>>>>>>On November 20, 2002 at 17:39:26, Martin Giepmans wrote:
>>>>>>>>On November 20, 2002 at 16:19:29, Omid David Tabibi wrote:
>>>>>>>>>On November 20, 2002 at 16:04:50, Martin Giepmans wrote:
>>>>>>>>>>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:
>>>>>>>>>>If I'm not mistaken this is the well known "verification search" with
>>>>>>>>>>one modification: no verification in the verification search.
>>>>>>>>>>Am I right?
>>>>>>>>>The classical verification search as introduced by Plenkner comes to detect
>>>>>>>>>zugzwangs. Verifeid null-move pruning as presented in the paper, constructs a
>>>>>>>>>smaller search tree with greater tactical strength in middle games (in addition
>>>>>>>>>to detecting zugzwangs).
>>>>>>>>>>Another question:
>>>>>>>>>>your results in table 5 seem convincing, but what about table 4?
>>>>>>>>>>Are these results statistically significant? (my guess is no ..)
>>>>>>>>>For a good estimate of the growth of the search tree as we go deeper, see Table
>>>>>>>>>3 and Figure 4 (which present ECM test positions searched to a depth of 11
>>>>>>>>>The WCS test positions were mainly used for testing the tactical strength
>>>>>>>>>(results in Table 5). Table 4 was provided just for the sake of completeness.
>>>>>>>>I see that I reduced the numbers of the tables (R=1 ;))
>>>>>>>>What I wanted to write is that table 6 is convincing while table 5 is IMO not.
>>>>>>>>Combining table 4 and 5 my impression is that - from a time perspective -
>>>>>>>>R=3 might be better than verified R=2.
>>>>>>>(you mean verified R = 3, don't you?!)
>>>>>>>Even though standard R = 3 constructs a smaller search tree, the problem with
>>>>>>>it, is that it is too risky. Except DIEP which uses a fixed R = 3, I don't know
>>>>>>>of any program that uses that value due to its high risk.
>>>>>>>>Compared to R=3 verified R=2 solves about 3% more positions but is about 40%
>>>>>>Yes, of course I mean verified R=3 (I did it again ;)).
>>>>>>What about my last remark (the percentages)?
>>>>>>From a time perspective your results may indicate that vrfd R=3 is actually
>>>>>>_worse_ than R=3.
>>>>>>OK, R=3 is risky, but for the prize of an occasional oversight (3%) you get
>>>>>>a speedup of about 40% (according to your tables).
>>>>>>The prize for 40% speedup is 1 or 2 extra plies in 3% of the positions ...
>>>>>>I think if you do the math you will see that that is very cheap.
>>>>>>In a tournament game with clocks R=3 is indeed risky. One oversight is often
>>>>>>enough to lose a game. The question is how a (less risky) combination of R=2 and
>>>>>>R=3 compares to your method.
>>>>>By "combination of R=2 and R=3" you mean adaptive null-move pruning, don't you?
>>>>>Verified version has a greater average tactical strength than standard R=2 (and
>>>>>thus greater than adaptive R=2~3), and its tree size is smaller using simple
>>>>>quiescence search.
>>>>Is adaptive R=2/3 tactically stronger if you include the time factor?
>>>>As I allready pointed out: your tables seem to indicate that pure R=3
>>>>is stronger that vrfd R=3.
>>>>If if if you include the time factor.
>>>>Adaptive nullmove migth also be stronger if if if ...
>>>>Do we agree that time matters?
>>>>Of course if you like we can continue this conversation in heaven :)
>>>Usually people don't get good results with standard R=3 due to its great
>>>tactical weaknesses. But you have to try all the algorithms and choose the one
>>>that yields the best performance for _your_program_!
>>To be sure, I don't use R=3 myself. Until recently I didn't even use
>>nullmove at all. Now I use something that vaguely resembles nullmove R=2
>>together with a few other tricks. Seems OK.
>>A problem is that it is usually difficult to find out what is best.
>>A trick that works well tactically may turn out to be a disaster in quiet
>>positions. What helps in bullet games may not help at all in tournament
>>games with more time. And so on.
>>Finding out what really works (in all or most circumstances) is a very time
>>consuming business.
>>That brings me to the question you didn't answer: how about the time factor?
>>>>>And don't forget that using verified null-move pruning, you detect the zugzwangs
>>>>>and end up with the correct result, while in standard version you don't.
>this is a nonsense discussion martin from you and omid.
>Of course R=2 also outperforms his algorithm if he bugfixes his
>nullmove implementation.

I _really_ wish you would look at what you write.  And the opinion it
causes others to have about you.

If you can't do it, it can't be done.

If you didn't do it, it is no good, inefficient, rude, or has bugs.

If you can't understand it, it is obviously no good.


He used R=3 + verification.  Note that he does _not_ do verification after
every null-move search that fails high.  So his conclusion that R=3 with his
verification does better than R=2 without seems reasonable.

I prefer to take the scientific approach and try it a bit before I conclude that
it works for me or it doesn't.  However it _obviously_ works for him.  To make
these "bugs" statements makes you look like a you-know-what...

>R=2 is always going to outperform a verification search where you
>do an additional near to fullwidth search of depthleft-1.

You do realize it isn't done in most cases?

>That tree is *always* bigger than the whole nullmove with R=2.

Can you "proof" that?  Without knowing anything about how often the
verification search is even done?  Didn't think so.  Experimentation is
the best way as math won't work.

>Only bugs will make verification search look better and forgetting
>the time factor.

I've told you the same thing many times.  Only bugs will make a parallel
search consistently produce speedups > 2.  You argued for years, but now I
notice you no longer claim that nonsense.  You should practice what you
preach now and then...

This page took 0.11 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.