Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 22:48:06 11/21/02

Go up one level in this thread


On November 21, 2002 at 23:33:53, Vincent Diepeveen wrote:

>On November 21, 2002 at 22:42:37, Robert Hyatt wrote:
>
>>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.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>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
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>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
>>>>>>>>>>>plies).
>>>>>>>>>>>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.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>Martin
>>>>>>>>>>
>>>>>>>>>>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%
>>>>>>>>>>slower!
>>>>>>>>>>
>>>>>>>>>>Martin
>>>>>>>>
>>>>>>>>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?
>>>>
>>>>Martin
>>>>>
>>>>>>Martin
>>>>>>
>>>>>>>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.
>>>>>>>
>>>>>>>
>>>>>>>>Martin
>>>
>>>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.
>>
>>Etc.
>>
>>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...
>
>bob his verification search is a depthleft-1 search.
>
>at a 10 ply search that's 9 ply.
>
>he claims it is using *way* less nodes than
>a R=2 which is a 7 ply search.
>
>That's *impossible* of course.


It isn't what he is claiming.  He claims that R=3 + verification is close to
R=2 in nodes, and has fewer null-move failures.  His data seems to support that.
R=3 with a depth-1 verification ought to be fairly close to R=2, just based on
pure math.  I'll leave it to you to figure out why...



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