Author: Vincent Diepeveen
Date: 06:08:56 06/20/05
Go up one level in this thread
On June 20, 2005 at 08:22:17, Ricardo Gibert wrote:
>On June 20, 2005 at 05:31:17, Vasik Rajlich wrote:
>
>...
>>
>>I don't understand why that would be the case. Can you explain?
>
>To understand the reason, it is necessary to explain no progress pruning. Here
>is an illustration of no progress pruning:
a - b - c - d - ... - e - f - g
\ \
h h
Probably small typo in your very good explanation further.
You probably mean to say:
"If in position c we can reach a position h by means of a move c',
whereas we also can reach h from position e playing move e' going to position h
possibly at a smaller search depth than h is when playing c' in c. If that
condition is fullfilled that we find 2 moves for which this condition is true,
then move e' can get pruned.
The assumption is of course that if move e' gives a cutoff for going to position
h then we will already earlier in the tree get that cutoff by playing move c'
anyway".
There is a huge number of problems with no progress pruning apart from the
transposition table cutoffs.
a) making a fast datastructure is not so easy. Its overhead is *huge*.
I used a redblack-tree implementation to implement it. There are faster ways to
do it of course, but i just wanted a quick 1 day implementation. That turned out
to take a week of coding & testing to get it decently to work (the redblack tree
code i already use for diep's datastructures so that code was already bugfree
lucky and ready to be used).
b) It is possible that move e' gives a cutoff in position e which takes care you
don't have to search any other move.
c) by searching move e' anyway you create a kind of IID (internal iterative
deepending) which helps you quicker for position h after move c' to get the best
move there. So that reduces a LITTLE BIT of the overhead.
d) the bug no progress pruning introduces into the hashtable is huge.
Please note there is ways to repair that, but the overhead of that is HUGE.
e) the actual reduction in treesize no progress pruning gives is very small.
Basically it reduces in 'shuffle positions' with pawns at unmovable spots.
This where we get already 20 ply anyway in that rook endgame and we would like
to get our search depth bigger in the MIDDLEGAME, whereas thanks to the huge
overhead of implementing no progress, we just get slower in that middlegame
f) no progress pruning just messes up your move ordering everywhere.
g) no progress pruning prunes interesting numbers of branches at nodes where we
already get a huge increased number of transposition table cutoffs. So the very
thing that no progress pruning doesn't work with, is already giving an
exponential speedup there. If you have to choose between hashtable or no
progress, then obviously no progress can leave.
h) todays top engines are non stop busy progressing in complex positions. The
odds for getting in positions with numerous repetitions is therefore utmost
tiny. Usually not before move 30 no progress pruning could reduce the tree size
some. Even then the savings are smaller than the huge overhead it costs.
Please keep in mind that the DEEPER you search the BIGGER the overhead. For
every node, no progress pruning has a cost of (n log n).
Using a small hashtable for no progress pruning is possible of course, but very
risky and tricky to implement. Hashtables are slow things.
In short you run huge risks with no progress, for the price of huge costs.
Frans Morsch showed 1 position where it worked for him. But he also concluded
that it was too expensive to be used for normal games and most importantly he
started to lose games by means of bad moves.
If you think very long about it, you will find a way to fix the hashtable, which
could in theory repair the problem of no progress pruning.
But do you want to do all that effort, for some *possible* reduction in tree
size around move 40?
>Let the letters a thru g represent successive moves in a line being analyzed. No
>progress pruning says that if the position after move i instead of move f leads
>to the same position as move instead d, then move i can be pruned from
>consideration, because it could have been reached earlier.
>
>Where this gets you in trouble is if move h turns out to be quite a good move.
>The positions after moves from d to e will not reflect this fact, since move i
>was pruned. The positions after moves from d to e will get stored in the HT with
>the wrong score and if a subsequent line should get a HT hit that uses these
>scores, the search will get fooled as to the true value of the positions after
>the moves from d to e. This is not good.
>
>One solution to this is to store the hash moves but not the hash scores for
>positions dependent (d thru e) on a no progress prune. Another idea is to keep
>the hash scores, but associate a reduced draft for the scores. Yet another idea
>is to chuck no progress pruning as being more trouble than it is worth. The
>latter idea is attractive, since it is not a big win.
>
>>
>>The interaction of no progress pruning with HT will cause you some problems
>>because the pruning is path-dependent, while the positions in the HT are not.
>>You'll store in the HT a position which was later pruned (actually reduced)
>>because of lack of progress, and then you'll come to that same position via a
>>different path where this pruning (actually reducing) shouldn't be done.
>>
>>The question not everybody agrees about is how of much of a problem this is.
>>
>>Vas
>>
>...
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.