Author: Vincent Diepeveen
Date: 13:36:08 11/20/02
Go up one level in this thread
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.
b) how can you claim it works? 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.
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.
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+).
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.
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.32 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.