Author: Vincent Diepeveen
Date: 10:41:15 12/21/02
Go up one level in this thread
On December 21, 2002 at 00:48:41, Omid David Tabibi wrote: >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 So in short your whole article proofs *nothing* other than that you implemented in a buggy way a zugzwang detection and didn't even know how to show your verification search. With the usual hashtable transposition bug (all beginners seem to miss that, including Rainer Feldmann for his FHR implementation) which also makes sure that you have no garantuee that you can detect a single zugzwang. >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 That is a false claim not backed up by any scientific evidence from your side. All we know is that you have a bug in your implementation and that for Darkthought adaptive was the best implementation, whereas R=3 is never *concluded* to be bad. Just mentionned that it is *aggressive*. Also limited by the domain 8-12 ply whereas todays programs go > 12 ply at tournament level. >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: I quoted the entire conclusion. You quote some in between murmuring from Heinz which is not backed up by evidence. Therefore Heinz didn't use it in his conclusion either. All Heinz does is proof that Adaptive nullmove works for darkthought; the rest is not relevant at all. However he even goes that far in saying that it is an interesting implementation of using nullmove, not even claiming that adaptive nullmove is the best. A very careful statement from Heinz therefore! >"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 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.