Author: Robert Hyatt
Date: 06:51:50 10/06/99
Go up one level in this thread
On October 06, 1999 at 04:08:03, Bas Hamstra wrote:
>On October 05, 1999 at 12:05:41, Robert Hyatt wrote:
>
>>On October 05, 1999 at 05:14:23, Bas Hamstra wrote:
>>
>>>I have been thinking about "Delta pruning". The way I saw it (a while ago) in
>>>Crafty is like this:
>>>
>>> Delta = Alpha - Material - Margin;
>>>
>>>Then for each capture:
>>>
>>> if(CaptureValue < Delta) skip this capture.
>>>
>>>Now I would like a raction to the following statements:
>>>
>>>(Material - Margin) is a cheap estimation of the current eval. If positional
>>>bonusses get frequently more than a pawn (or even more) "Margin" should be set
>>>to near the maximum the positional part of the score can be, or else this
>>>estimation can become very inaccurate and introduces much errors. Reaction?
>>>
>>>If positional bonusses get frequently much more than a pawn, maybe it is more
>>>accurate to use this:
>>>
>>> Delta = Alpha - Eval;
>>>
>>>Because with one move the Eval won't change *that* much. Reaction?
>>>
>>>
>>>
>>>Regards,
>>>Bas Hamstra.
>>
>>
>>You are overlooking something _important_ in crafty. the "alpha" value
>>_is_ the real evaluation for the current position, and includes both the
>>material score _and_ the positional evaluation. So my test is safe in that
>>I am betting that this single capture can't add more than 100 positional
>>points. It can be wrong, such as when the last piece is removed, because
>>maybe a pawn can run then. But overall it is very safe and I haven't found
>>cases where it screws the search up at all....
>
>Please help me understand, for now I get lost. The Alpha value is the real
>evaluation? I just looked in Crafty's quisce and Alpha is just Alpha. It seems
>to me the current position can have a totally different Evaluation than Alpha.
>Only if the current position is *better* than Alpha, then Alpha = Eval, says
>Crafty. Like normal.
look at this from the top of Quiesce():
value=Evaluate(tree,ply,wtm,alpha,beta);
if (value > alpha) {
if (value >= beta) return(value);
alpha=value;
tree->pv[ply].pathl=ply-1;
tree->pv[ply].pathh=0;
tree->pv[ply].pathd=iteration_depth;
}
so right at the top of quiesce(), alpha is set to Max(alpha,Evaluate());
which means that the captures being examined will likely only affect the
score in small ways since the evaluation before the move is stuffed into
alpha, unless that value is < alpha. Which means that this current move is
going to have to produce a really large positional score swing to cause any
sort of error. The only cases for me would be where the last piece is removed
leaving a passed pawn that can promote uncontested, or perhaps playing Bxh7
where I have code to instantly recognize that the bishop will be trapped.
>
>What this type of pruning does is just see if the CaptureValue is not enough to
>fill the gap between the current Eval and Alpha, right? Then it will be beta-cut
>on the next ply anyway.
correct, but it eliminated a call to MakeMove(), and a recursive call to
Quiesce(), which speeds things up.
>
>And it seems to me it makes a big difference if you use
>
> a) Gap = Alpha - Material - Margin
>
>(which estimates Gap, accuracy strongly depending on Margin)
>
>or
>
> b) Gap = Alpha - CurrentEval (-Margin)
>
>(which assumes just that the Eval *difference* is no greater than Margin.
>Something quite different than a and in my opinion more accurate)
>
depends. If you use lazy eval, you still have a problem as it can exit
without computing the true score change... so you are still stuck... I
don't see this causing me any problems at all, but YMMV...
>
>Regards,
>Bas Hamstra.
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.