Author: Martin Giepmans
Date: 16:59:24 11/20/02
Go up one level in this thread
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 page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.