Computer Chess Club Archives


Search

Terms

Messages

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

Author: Omid David Tabibi

Date: 16:31:30 11/20/02

Go up one level in this thread


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_!


>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 page took 0.2 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.