Author: Vincent Diepeveen
Date: 18:50:36 11/21/02
Go up one level in this thread
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. R=2 is always going to outperform a verification search where you do an additional near to fullwidth search of depthleft-1. That tree is *always* bigger than the whole nullmove with R=2. Only bugs will make verification search look better and forgetting the time factor.
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.