Author: Robert Hyatt
Date: 22:48:06 11/21/02
Go up one level in this thread
On November 21, 2002 at 23:33:53, Vincent Diepeveen wrote: >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. 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... > >bob his verification search is a depthleft-1 search. > >at a 10 ply search that's 9 ply. > >he claims it is using *way* less nodes than >a R=2 which is a 7 ply search. > >That's *impossible* of course. It isn't what he is claiming. He claims that R=3 + verification is close to R=2 in nodes, and has fewer null-move failures. His data seems to support that. R=3 with a depth-1 verification ought to be fairly close to R=2, just based on pure math. I'll leave it to you to figure out why...
This page took 0.07 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.