Author: Bas Hamstra
Date: 13:38:32 10/06/99
Go up one level in this thread
On October 06, 1999 at 14:02:41, Robert Hyatt wrote:
>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...
I'll think about it and get back. But I want to say this:
Suppose Eval > alpha. Now what is the chance "this capture can't bring us
anywhere near alpha", as I quote from memory? We are at alpha *already* even
before the capture is added... Do I understand correctly that you still throw
captures out in that situation?
If I want to test if this capture can bring me near alpha, I intuitively say:
take the last eval, add the material capture value and see if it is near alpha.
Which is nonsense in the case Eval > alpha, because then you can hardly end up
far below alpha.
What am I missing...?
Regards,
Bas Hamstra.
Regards,
Bas Hamstra.
>>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.