Computer Chess Club Archives


Search

Terms

Messages

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

Author: Omid David Tabibi

Date: 03:19:55 11/22/02

Go up one level in this thread


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.

I tried verified null-move in my other program which is still nameless. It has
about 2600 performance and is a damn complicated one. The idea worked very well
there (after a lot of tuning of course).

Why didn't I publish the results on that "strong" program?

Because it is using many extensions and different pruning methods that not every
program necessarily uses. While Genesis uses only the algorithms I described in
the paper, and so the results are generic enough for publication. Besides, since
Genesis' structure is far simpler, I trust it more to be bug-free.



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