Author: Dieter Buerssner
Date: 05:15:05 08/24/00
Go up one level in this thread
On August 23, 2000 at 12:15:22, Ernst A. Heinz wrote:
>>Both use zero window searches with -alpha-1, -alpha for the recursive call.
>>If the score returned from the recursive call is > alpha and < beta, Negascout
>>will research with -beta, -score while PVS will research with -beta, -alpha.
>
>There might be some confusion in the literature, but I am quite
>sure that the distinction you describe relates to the so-called
>"fail-hard" and "fail-soft" versions of alpha-beta search.
Sorry, I probably confused two matters here. In my notes, I have a PVS
algorithm, that researches with -beta, -alpha (ignoring the score returned
by the null window search, but updating alpha at the end of the loop:
alpha = max(score,alpha)). Perhaps, I have written it down wrong.
BTW. I have experimented with both, and didn't seem to detect any significant
difference.
Are the papers by Marseland and Campbell, describing the original PVS
algorithm, abailable online?
>The fail-soft variant "raises" the upper bound of recursive
>search calls to "-max(alpha, score)" and the upper bound of
>PVS researches to "-score + 1".
I had to think quite some while about the upper bound of the research, and
it seems correct to me. But I wonder, if it is really needed. (Practically
it probably won't make a difference).
If I rewrite the pseudo-Pascal to pseudo-C and renaming variables to fit the
discussion:
/* Comments are mine, if wrong, please correct.
Position updating is omitted. */
int negascout(alpha, beta, depth)
{
if (depth > d)
return eval();
m = -infinity;
n = beta;
for (i = 0; i < nmoves; i++)
{
score = -negascout(-n, -max(alpha,m), depth+1);
if (score > m)
{
if (n == beta || depth == d-2) /* first move, or we were allready called
with zero window, or the
discussed "trick" */
m = score;
else /* need to research with larger window */
m = -negascout(-beta, -score, depth+1);
}
if (m >= beta)
return m; /* fail-soft, fail hard: return beta; */
n = max(alpha,m)+1;
}
return m; /* fail-hard: return max(m,alpha); */
}
The +1 is missing form the -score in the research. If I understand correctly,
all we know from the first search is, that the real score is score or larger.
If the real score is not smaller than score, the research will fail again!
This time, it will fail low. But it seems, that the recursive call must return
exactly -score, independant of the fact, that the bound is -score + 1 or
-score.
Also, isn't there missing an important optimization in the else clause,
namely only research if score < beta?
About the fail-hard variant. I could never see why anybody would want to
implement a fail-hard variant (in the sense of my comments above, not
necessarily in the sense of the bounds in the research - or is my terminoligy
wrong again?). Are there any advantages?
As far as I can see, when using hash tables, most entries will just happen
to be filled with very tight bounds - the score of the PV. Chances are high,
that when searching the next depth, the bounds will be a little bit different.
When hitting a position, that was searched with enough depth in the
previous iteration, a hash table fail high or fail low might not be possible,
just because of this. (Practically I wouldn't expect a large difference, though)
One last remark, to the "trick". I think, this trick will not only fail, when
there is a qsearch, but also when the eval is "lazy".
Regards,
Dieter
This page took 0.05 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.