Author: Omid David Tabibi
Date: 15:49:15 11/20/02
Go up one level in this thread
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. 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.09 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.