Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Comments on delta pruning

Author: Robert Hyatt

Date: 11:02:41 10/06/99

Go up one level in this thread


On October 06, 1999 at 10:54:49, Bas Hamstra wrote:

>On October 06, 1999 at 09:51:50, Robert Hyatt wrote:
>
>>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.
>
>You say it  yourself: "unless the value < alpha".
>
>But that is exactly the only case that is relevant here! Because if Eval was
>greater or equal than alpha, *zero* captures will be thrown out. There simply
>*is* no "gap" if Eval > alpha.

totally wrong...  I still cull captures if the capture itself seems to lose
material...  And if there is no 'gap' then this 'delta-pruning' (not my name
for it) doesn't apply anyway... the point is that if the material score is
too low for the positional score to pull it up, no need to try captures that
have no chance to pull the material score up enough to give the positional
score a chance to bring it back in the window...




>
>Relevant is only the case where Eval is bigtime < alpha. Then there is hopefully
>something to prune.

you do realize just how often that is the case in a full-width search?  IE
it is one of the reasons null-move works so well...  one side is so far behind
nothing he can do, including making two moves in a row, can get him back to
anywhere near equality...




>
>If you agree on that point, then why not simply substract Eval, which you have
>computed already, in stead of material?


because that would be more aggressive than what I am doing now...  I take the
larger of eval and alpha, and use that to prune against.  if eval < alpha, and
you use eval to prune against, you are getting more pessimistic results.  I want
the speed...  and continue to take it until I see a clear place where this hurts
results...



>
>BTW what does YMMV mean?

Your Milage May Vary...  or you may get different results on different programs.

>
>
>Regards,
>Bas Hamstra.
>
>
>>>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...



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.