Author: Omid David Tabibi
Date: 21:48:41 12/20/02
Go up one level in this thread
I didn't compare to Adaptive Null-Move Pruning, and neither drew any conclusions as to which one is better. It is up to you -- the programmer -- to test both Verified and Adaptive schemes, and find out which one performs better in your program. Although as I've said before, I believe that starting from a certain depth (threshold), Verified Null-Move Pruning will always be superior to the Adaptive one (since unlike the Adaptive version, Verified's backbone is pure R=3). This depth threshold varies from one program to another (one programmer reported the threshold to be 12 plies in his programs, i.e., Verified Null-Move Pruning performed better only after depth 12). So you have to test this algorithm in longer time controls and deeper searches. BTW, you quoted from Section 4 of Heinz' paper. In Section 3, Heinz describes that R=2 is superior to R=2. Quote from second paragraph of Section 3, Adaptive Null-Move Pruning, 1999: "Regarding the depth reduction of null-move searches, the accepted standard recommended the usage of a constant depth-reduction factor R=2. Independent studies by several researchers confirmed that recursive null-move pruning with R=2 behaved markedly better than both the too conservative R=1 and the too aggressive R=3." On December 20, 2002 at 17:18:54, Vincent Diepeveen wrote: >On December 19, 2002 at 12:13:46, Omid David Tabibi wrote: > >I assume Heinz doesn't mind i quote his summary and part of his >conclusion that is relevant to this issue. If so then >apologies for Heinz for quoting his research litterary. > >Page 123 september 1999 issue. > >".. To this end, we extend standard null-move pruning by a variable >depth reduction and introduce what we call adaptive null-move pruning. >Quantitative experiments with our chess program Darkthought show that >adaptive null-move adds a new member to the collection of successful >forward-pruning techniques in computer chess. It preserves the tactical >strength of Darkthought while reducing its search effort by 10 to 30% >on average in comparision with standard nullmove pruning at search >depths 8 to 12 plies. ..." > >So where is your compare to adaptive nullmove? Heinz concludes >adaptive nullmove is better for his program that is doing a lot of >forward pruning at the leafs and no checks in the qsearch i assume. > >Then the conclusion of Heinz. The *entire* conclusion. All sentences. >Nothing is left out: > >"Our brief historical overview of search paradigms in computer chess argued that >the pure brute-force searchers lost their traditional dominance of the field >around 1990. Since then selective forward-pruning techniques have again taken >the lead, guided by the spectacular achievemens of the null move in >microcomputer practice. Today, nearly all the world-class chess programs apply >various clever forward-pruning schemes with good success. > >This article adds adaptive null-move pruning to the collection of succesful >forward pruning methods in computer chess. Extensive experiments show that >adaptive null-move pruning preserves the tactical strength of our sophisticated >and tournament-proven chess program Darkthought while reducing its search effort >by 10 to 30% on average in comparision with standard R=2 null-move pruning at >search depths of 8 to 12 plies. Furthermore, adaptive null-move pruning and its >savings in search effort scale equally well with search depth as those of the >extremely risky R=3 scheme. Overall, our fine-tuned implementation of adaptive >null-move pruning in darkthought combines the merits of both standard R=2 and >aggressive R=3 nullmove pruning in a convincing way. In view of its tactical >safety and the neatly reduced search effort, we deem it quite remarkable that >adaptive null-move pruning is very easy to implement. > >During the course of our research on adaptive null-move pruning we also >discovered an important distinction between dynamic and static forward-pruning >schemes regarding their preferred degrees of selectivity in different parts of >the full-width search. While static forward pruning generally thrives on low >selectivity in the upper parts and the increased selectivity in the lower ones, >dynamic forward pruning excels with the exact opposite. Hence, dynamic forward >pruning rather prefers high remaining search depths for the application of >aggressive selectivity. Their specific preferences allow both styles of forward >pruning to sustain the desired degrees of tactical safety." > >NOW EVERYONE CAN READ THAT AND DRAW THEIR OWN CONCLUSIONS. > >First of all: > - Ernst A. Heinz says nowhere that R=2 is better than R=3. He just > side comments R=3 is risky because it is aggressively pruning. > - Ernst A. Heinz DOES conclude that adaptive nullmove pruning is better > for darkthought at the search depths 8-12. > >Now where todays software programs are above that 12 and tend to go more >to R=3 especially when having checks in qsearch, still the vaste majority >of software programs is having adaptive nullmove and many concluded that it >was best for them. > >You researched depths 9 and 10 and didn't compare with adaptive nullmove >*despite* saying you know the article. > >Explain that please. > >>On December 19, 2002 at 09:53:21, Vincent Diepeveen wrote: >> >>>Your own data shows that R=3 produces a far smaller tree >>>and you didn't compare time to solution in any of the >>>tests performed. >>> >>>So you cannot claim anything about verified nullmove. >>> >>>The tactics you solve easily with checks in qsearch. >>> >>>Heinz concluded a combination of R=3 + R=2 is better, >>>*not* that R=2 is better than R=3 in itself. >>> >> >>Vincent, it seems that you have neither read Heinz' article. Read Section 3 of >>Adaptive Null-Move Pruning, Heinz 1999. >> >> >> >>>On December 18, 2002 at 22:50:56, Omid David Tabibi wrote: >>> >>>>On December 18, 2002 at 22:36:38, Andrew Dados wrote: >>>> >>>>>On December 18, 2002 at 22:12:43, Omid David Tabibi wrote: >>>>> >>>>>>On December 18, 2002 at 22:08:39, Andrew Dados wrote: >>>>>> >>>>>>>On December 18, 2002 at 22:00:08, Omid David Tabibi wrote: >>>>>>> >>>>>>>>On December 18, 2002 at 21:48:03, Andrew Dados wrote: >>>>>>>> >>>>>>>>>On December 18, 2002 at 18:56:21, Omid David Tabibi wrote: >>>>>>>>> >>>>>>>>>>On December 18, 2002 at 18:12:22, Bruce Moreland wrote: >>>>>>>>>> >>>>>>>>>>>On December 18, 2002 at 16:59:10, Omid David Tabibi wrote: >>>>>>>>>>> >>>>>>>>>>>>You take two numbers and draw a very general conclusion. Look at other tables >>>>>>>>>>>>and depths, which show a more significant superiority of std R=2 over std R=3. >>>>>>>>>>>> >>>>>>>>>>>>Look at Tables 2 and 6. Vrfd R=3 solved almost the same number of positions as >>>>>>>>>>>>std R=1 !!! Does it leave any room for doubt as for vrfd R=3's superiority over >>>>>>>>>>>>std R=3 ? >>>>>>>>>>> >>>>>>>>>>>I don't see anything that shows demonstrated superiority of R=2 over R=3. You >>>>>>>>>>>say to look at table 2 -- so do I. It shows that R=2 gets one more correct >>>>>>>>>>>through ply 10, but takes over twice as long to do it. I suggest that if R=3 >>>>>>>>>>>were allowed to continue until R=2 is finished, that it would have found >>>>>>>>>>>significantly more than 1 solution in the mean time. >>>>>>>>>>> >>>>>>>>>>>Table 6 has no node counts, so I don't know how much faster R=3 is than R=2. It >>>>>>>>>>>gets 286 as opposed to 292. Fine. How much less time did it take to get it? >>>>>>>>>>> >>>>>>>>>>>Maybe VR=3 is better than R=3. The paper should allow me to draw this >>>>>>>>>>>conclusion. >>>>>>>>>>> >>>>>>>>>>>A reason that I bring up the comparison between R=3 and R=2, is if you are >>>>>>>>>>>proving that R=3 is better than R=2, and you don't think that R=3 is better than >>>>>>>>>>>R=2, then maybe your other results are flawed. >>>>>>>>>>> >>>>>>>>>>>You are writing a paper on some aspect of biological science, and your data is >>>>>>>>>>>suddenly implying that evolution doesn't take place. Doesn't *that* seem worth >>>>>>>>>>>investigating? >>>>>>>>>>> >>>>>>>>>>>Either you are on the verge of a serious breakthrough, or your testing process >>>>>>>>>>>is wrong. You need to figure out which. >>>>>>>>>>>bruce >>>>>>>>>> >>>>>>>>>>Bruce, >>>>>>>>>> >>>>>>>>>>Apparently we are not looking at the data from the same perspective. As I told >>>>>>>>>>you before, I conducted self-play matches, and their results showed that std R=2 >>>>>>>>>>is superior to std R=3. Although I still think that this finding is not worth >>>>>>>>>>publishing, as it is an already known fact. >>>>>>>>>> >>>>>>>>>>I understand your criticism of the fixed depth method, which is the standard >>>>>>>>>>scientific comparison in computer chess. But I'm afraid your case against fixed >>>>>>>>>>depth is not strong enough to convince the whole computer chess research >>>>>>>>>>community to opt for fixed time comparisons instead. >>>>>>>>>> >>>>>>>>>>Mentioning some fixed time experiments in a footnote or appendix could have been >>>>>>>>>>interesting; but even without them, my experiments took more than 6 months >>>>>>>>>>24h/d, 7d/w. >>>>>>>>>> >>>>>>>>>>If you have a specific experiment in mind, I would be glad to conduct whenever I >>>>>>>>>>get the time, but besides that, I would like the implemented algorithm in your >>>>>>>>>>program to speak for its own. >>>>>>>>>> >>>>>>>>>>In our discussion today, I didn't get into details and kept my replies short, >>>>>>>>>>because none of your points were new, and I have already discussed all these in >>>>>>>>>>detail a few weeks ago. I'm sure anyone who followed those discussions could >>>>>>>>>>have answered all your questions. >>>>>>>>>> >>>>>>>>>>Based on the programmers' feedbacks I additionally posted several implementation >>>>>>>>>>suggestions for the various variants of this algorithm, which I'm sure you'll >>>>>>>>>>find helpful. >>>>>>>>>> >>>>>>>>>>Now you will have to excuse me for not being able to continue the discussion, >>>>>>>>>>for I am up to my ears busy working on another paper (on Blockage Detection) >>>>>>>>>>which I hope to be ready soon. >>>>>>>>> >>>>>>>>>Please, refrain... >>>>>>>>> >>>>>>>> >>>>>>>>Sorry Andrew, I didn't understand what you meant. >>>>>>> >>>>>>>I meant refrain from producing tons of 'scientific' papers with wrong or >>>>>>>unjustified conclusions. Instead of vr=3 and 80% more nodes overhead simply >>>>>>>implement checks in q-search and get more tests right with 10-15% overhead. >>>>>>> >>>>>>>Btw.. try self-playing vr=3 versus r=2 or 3 + checks in qsearch :) >>>>>>> >>>>>> >>>>>>And why do you think that vrfd R=3 won't be superior to std R=2 if they both use >>>>>>checks in q-search? >>>>> >>>>>Then what do you need to verify? Biggest problem with null move is when it drops >>>>>you right into qsearch and you don't do checks after that. >>>>> >>>> >>>>Based on the feedback I've received from other programmers, verified null-move >>>>pruning usually yielded a considerable tactical improvement even in programs >>>>using checks in q-search and other extensions. >>>> >>>>The idea of verified null-move pruning will work fine on almost every program; >>>>on some after 10 minutes of implementation, on others after several days of fine >>>>tuning. The main issue is to find the suitable reduction value after a fail-high >>>>report. In my experiments I used a reduction of 1 after a fail-high report, but >>>>programs with more sophisticated extensions might achieve good results with a >>>>value of 2; or even an adaptive value. >>>> >>>>After a certain depth (a threshold), vrfd R=3 will always create a smaller tree >>>>than std R=2. For some programs that threshold might be higher (one programmer >>>>reported the depth 12 to be the threshold in his program!), so the experiments >>>>should be conducted on higher depths. It is quite natural that for example until >>>>depth 10, vrfd R=3 constructs a larger tree than std R=2, and starting from >>>>depth 11, the tree will be smaller. The key issue is to find the threshold. >>>> >>>> >>>>>Another (much smaller) problem is when a piece is trapped. Here you may try >>>>>improving on verification search: When null fails low (I know, you do >>>>>verification when null fails high) and is refuted with direct capture: either >>>>>suppress null move in subtrees, or supress it only when you try evasions of >>>>>piece en-prise. Or extend. Lots of options, most of us tried those some time >>>>>ago. This is all old stuff.... >>>>> >>>>>But I don't think bloating tree by 80% to get null problems right is a good >>>>>idea. >>>>> >>>> >>>>80% ?!? >>>> >>>> >>>>>> >>>>>>>> >>>>>>>>BTW, are you still working on Rookie?! >>>>>>>No, I stopped like 1 year ago. >>>>>>> >>>>>>>> >>>>>>>> >>>>>>>>>-Andrew-
This page took 0.02 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.