Author: Vincent Diepeveen
Date: 03:18:45 12/08/00
Go up one level in this thread
On December 07, 2000 at 13:56:31, Bert van den Akker wrote:
>In a previous question about Futility pruning Vincent Diepeveen mentioned:
>
>>Futility pruning is very dubious. It sure speeds you up, but it's
>>dubious and tends to give you slight positional
>>differences that make a program play positional
>>a lot weaker.
>
>Can sombody explain me why Futility pruning tends to give slight positional
>differences?
First of all it heavily relies on the positional evaluation of
a program. If you have a very simple evaluation with small scores
then the problem is a lot smaller when you have huge scores (no matter
the size of the evaluation).
Suppose i am in a position X where evaluation of the position is
0.055
Now suppose alfa is 0.500
Suppose i use a value 0.400 to create a region but that
a move i delivers after making a move an evaluation of 0.700:
So for move i the rule:
if( eval(X)-region <= alfa )
prune move i
Obviously this way of pruning is HEAVILY dependant upon what
a move positional can deliver to me. Is it a huge score, then
you have a major problem because the smaller the value 'region'
in the above example the more one can prune. The bigger i make
the value 'region' the less one can prune.
Not to mention that a move can place down a tactical trick, like
threatening mate, and as i do checks in the qsearch,
i see the completion of it in the qsearch.
On average the move in the root surprisingly is largely dependant upon
huge positional scores.
Now if we go prune *everywhere* at the tips then obviously *everything*
is getting influenced, as we nowhere get the chance to maximize scores.
Basically also next applies: if i make a very strong move, delivering
me a lot of positional scoring, then my opponent is no longer allowed
to refute that as score is a lot smaller than alfa next move!
This hurts bigtime.
If i can get the score in this position a LOT above beta
positionally, then most likely there is a pretty big chance in critical
positions for the root that next move of my opponent is positionally
going to influence a lot too!
These for chessplayers logical things are usual forgotten by pruning
designers.
Only nullmove which prunes on beta seems to do a good job. Pruning on
alpha, whether it's in qsearch or whether it's last few ply or even only
last ply, for DIEP i figured out it's extremely dubious.
Note that for my draughtsprogram it also doesn't work at all, despite
that its evaluation is not delivering too many huge scores, the whole
game is completely dependant upon a programs positional insight nowadays.
You can't afford to prune away knowledge in your evaluation in a time
where nowadays games only get decided on the wellness of an evaluation.
Analyze games of the world champs in london, even single cpu you won't
see many games decided on tactics anymore.
Before 1990 programs doing best pruning and extensions won with induction
from other programs. This has slowly been changing over the years.
Nowadays everyone can search at tournament levels above 10 ply, pruning
on alpha with reasonable small values is simply something you can't
afford.
Obviously i'm not talking here about the theoretic possibility that you
know IN ADVANCE that your evaluation is going to deliver at most 0.200
positional score so you prune on 0.250 which is a safe assumption.
Of course i don't go prune at 40 pawns in DIEP, pruning on 40 pawns
is so insane stupid that it removes all advantages of pruning.
In my experiments in the last ply pruning i tried margins which
delivered me about a 5 to 15% node reduction. I tried values between
1.5 and 5 pawns and didn't include 'tactical' moves in the pruning.
>BvdA
Vincent
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.