Author: Dieter Buerssner
Date: 11:48:58 10/27/02
Go up one level in this thread
On October 27, 2002 at 04:18:58, José Carlos wrote:
>On October 26, 2002 at 20:10:38, Dieter Buerssner wrote:
>
>>On October 25, 2002 at 21:27:18, Nagendra Singh Tomar wrote:
>>
>>>score = -alphabeta(board, -alpha-1, -alpha, depth-1);
>>>
>>>if(score > alpha && score < beta)
>>>{
>>> score = -alphabeta(board, -beta, -score, depth-1);
>>> OR
>>> score = -alphabeta(board, -beta, -score+1, depth-1);
>>>}
>>>
>>>since the zero window search failed high and it returns
>>> score, this means that the true score is >= score.
>>> Now when we do a wide window search, if we want to store the PV
>>>properly we have to pass alpha value less than the possible
>>> score, else PV will not get updated (Note: PV gets updated only
>>> for nodes where score > alpha.). So we pass -score+1
>>>
>>>Am I right ?
>>
>>Yes.
>>
>>Using -score instead of -score+1 would also be correct in another sense. For a
>>"pure" alpha-beta algorithm (including PVS) it would calculate the correct
>>score, allways. But, as you noted, you will miss the PV now and then. IIRC the
>>original paper of Reinfeld about the Negascout algorithm used -score as bound.
>>
>>With typically used enhancements of alpha-beta (extensions, pruning, HTs),
>>unfortunately things get a bit more complicated - as others have mentioned. To
>>me, it is not clear what is best to do, when you get a score > alpha and < beta
>>in the first call (the zero window search), and receive a score <= result of the
>>first call in the research (something that will never happen with a "pure"
>>alpha-beta search).
>>
>>Jose Carlos thinks, it is better to trust the research (actually I am currently
>>doing this). But why should the research be more trustful than the original
>>search?
>
> * Here's my reason (please correct me if I'm mistaken):
I think, nothing wrong - just debatable :-)
> * We're at the root. We've searched the pv with an aspiration window or
>whatever, and we have a true score, which I'll call pvscore.
You have read more carefully than me. I thought we were not necessarily at the
root. This doesn't make much of a difference for the argumentation, however (if
it makes a difference at all).
> * We search second move with a null window [pvscore,pvscore + 1] or, as beta
>has been the subject of some confusing discussion, we can do:
> alpha = pvscore;
> beta = pvscore + 1;
> newscore = -search(-beta,-alpha)
> * So there's no way to get a newscore between alpha an beta ;)
> * We get a fail high, shall we trust it? Well, we could, but we want to be
>safer here
Ok - I think here we are at point, where we really do not know, what safer is.
We both agree, that we have two contradicting search results. One says, that the
we have proven, that the score > pvscore. The next says that the score <=
pvscore (assuming we kept the "old" alpha for the reasearch, as in your example
below).
If you only look at that bound, and consider for example null move pruning as a
source of error. To prove that the score is > pvscore, we let the side to move
do some null moves, to get some beta cutoffs. Some of those beta cutoffs may be
wrong (a search without allowing null move would have given no cutoff, for
example because some deep tactics is over the horizont now after the depth
reduction for the null move, or because of some Zugzwang. A research with a
higher beta for might not give those null move cutoffs, and we find that
actually a score is returned, that is <= the pvscore without this wrong cutoff).
To prove that the score <= pvscore, the other side could have done some null
moves to get beta cutoffs (which are for "my" side now fail lows). The same
situation. Now, which is safer?
> * We research. Now we try:
> alpha = pvscore;
> beta = pvscore + 30;
> newscore = -search(-beta,-alpha);
> * Three things can happen:
> a. We fail low. Shall we accept this move as a good improvement over the pv?
>Certainly not yet. We should decide, search is with [-INFINITY,+INFINITY] or
>other wide open window, or just forget it.
Even in the case of the research with totally open window, the situations
described above can happen somewhere in the tree (alpha and beta get adjusted
while doing the search). But of course a difference is, that we now cannot see
those obvious artifacts anymore - they are hidden in a more subtle way.
> b. We get a score between alpha and beta. I trust it because it is a true
>score that I got in an open window search after a previous search. I guess
>there's enough information, and both searches seem to agree that the move is
>good.
> c. We fail high again. I definetly trust the move. I only need to decide
>whther to open the window now and get a true score or search the other moves
>hoping they're allo bad.
Another thing that can happen - for the first search (that failed high) we had a
"lucky hit" in the transposition table, that perhaps shows, that the position is
won, while the normal search (or the eval, when the hit is in qsearch) would not
have seen this. At research time, that TT entry might have gotten overwritten. I
have seen my engine failing high to a mate score, but the research for the same
move failed low again. In all cases I investigated, the mate score was a correct
lower bound. Typically one depth later it will be seen. Also, in test positions,
I see now and then a fail high for the correct move, that fails low again
immediately after the research. At deeper depth, it is found again.
Sure, also counter examples can be found, and explained with very similar
reasoning. After I always thought, that not trusting that first fail high,
without getting a score inside a window was "safer", I am no doubting that this
is best. But I am not sure yet. One observation of Shredder 5. The GUI shows
"lower bound scores". So, I know, when the Shredder engine fails high in zero
window (after a score of say +1.00 a score of +1.01++ will follow). I have never
seen, a fallback to the last best move at the same iteration depth in such a
situation (or my memory or observation is bad ...) So, it seems, that he trusts
the first fail high more.
Also, I cannot remember, that I have seen such a pattern from other commercial
engines in analysis posted here. But of course, it may be the case, that they
just don't display a fail high in zero window search.
BTW. Some perhaps at the first look not too related things can influence the
occurence of fail high/low pattern. Assume you have a lower bound hit with
enough draft in TTs, but the score is not >= beta, it is > alpha however. If you
now adjust alpha, this can avoid a following fail low in a research situation,
that would have be seen, without adjusting alpha. Similar for upper bound hits.
Regards,
Dieter
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.