Author: Omid David Tabibi
Date: 14:20:30 11/20/02
Go up one level in this thread
On November 20, 2002 at 16:36:08, Vincent Diepeveen wrote: > >Omid i have 3 points > a) in my draughtsprogram around 1997,1998 i had already > the same algorithm as you describe in my 10x10 checkersprogram > which then was called dr initially later called Napoleon. > > I didn't invent it myself however, it was already published in some > article back then if i remember well. Hopefully for you not an ICCA > article but only RGCC, if memory serves well however it was also > published in ICCA journal. > > How can you claim it is a 'new algorithm' anyway? This trick has > been described over the years already everywhere and no one could > use it because overhead was too big. > A verification method used for detecting zugzwangs was described by Plenkner (1995), and was most probably in use even before that. However, a verification search to enhance the tactical strength has never been used before. The greater tactical strength comes from the detection of some of the tactical problems that wouldn't have been detected by the standard null-move pruning due to the horizon effect. > b) how can you claim it works? "It is impossible, because I couldn't do it." --Vincent Diepeveen > Even for draughts it doesn't work, > not to mention chess. R=3 as you show is giving like 40% to 50% > reduction even in your own experiments. Unless your qsearch is idiotic, > that means that you will see of course more tactics without that > reduced search. Your claim is based upon showing the depths that > solve positions. This is not fair. Time counts, not the searchdepth. > If you get 12 ply with R=3 within 3 minutes and you get 9 ply with > your 'verified nullmove' in 3 minutes, then you must compare that > 9 ply search versus the 12 ply search, not compare the 2 searches of > 9 ply. That's what i call misinformation. > The simpler your quiescence search is, the better will be the total gain from verified null-move pruning. If your quiescence is huge, then you might end up with a search tree, greater than standard R = 2 on occasions. However, even then, starting from a certain depth, the tree constructed by verified null-move pruning will be smaller than that of the standard one. > c) I miss the comparision with double nullmove. In fact double nullmove > is the same thing in a smarter way implemented and with a smaller > verificiation depth. Like depth-2-2R instead of depth-1. > The implementation of double nullmove is more > elegant though and its implementation is correct where your implementation > is assuming a lot. > 1. Double null-move is intended mainly for detecting zugzwangs; whilst verified null-move constructs a smaller search tree with greater tactical strength in middle games (in addition to detecting zugzwangs). 2. There is no published article regarding your double null-move, so I couldn't even mention it in my references! > d) you reduce the depth only 1 ply. How the HELL can it be better than > even R=2. If i do a verification search of depthleft-1, then > i search like 3 ply less than i do now. So that's worse than even > R=2 for nullmove. I cannot imagine that there is strong programs > which can afford a depthleft-1 reduction search. For singular extensions > *after* nullmove (so the cutoff of nullmove has been given already) > i do R=3 reduction, even that is too costly already at bigger search > depths (11+). > That's right, it is costly. But as the presented figures show, the cost of R = 3 plus verification is less than the cost of R = 2. > Perhaps you can enlighten us a little. and show some outputs of your > program. I need outputs simply on positions. with node counts there > for each ply. Let's compare things. I do not understand. How can you > afford to search with depthleft-1 in a node where i already have > done a cutoff? > > If i do it, i'm nearly searching fullwidth then. > One final remark: You use standard R = 3 in DIEP. So the search tree constructed by your program will definitely be smaller than that of verified R = 3. Many people find standard R = 3 as too risky; but if you are happy with its overall tactical strength, then I don't recommend you to shift to another method. But for those who'd like to get greater tactical strength than standard R = 2, and a smaller search tree than R = 2, I recommend to try verified null-move pruning. Best, Omid. >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
This page took 0.06 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.