Author: José Carlos
Date: 14:00:03 10/27/02
Go up one level in this thread
On October 27, 2002 at 14:48:58, Dieter Buerssner wrote:
>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?
Surely you have thought deeper than me about this. I find your arguments very
interesting and worth a longer thought before I can properly reply.
I simplified things in my mind considering scores outside the alpha-beta
window as the source of errors. That's why null-move (which might give cutoffs,
apart from reducing the depth) is the worst enemy of accuracy. Also hash table
hits are an enemy here.
To fight the problem, I don't allow null moves in the pv, and only use it in
refutation lines. I have two search functions:
- what I call AlphaBetaPV searches the pv nodes. I don't do null moves there
and search always open windows.
- my AlphaBeta only receives alpha (and has a local beta = alpha + 1) and does
all kind of dubious prunning.
When a move "appears" to be good enough, it's researched with AlphaBetaPV and
an open window. If I still find it good, I trust it.
>> * 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.
Another difference is that we can't do anything else to be safer. Totally open
window is the limit; it gives a true score and searches everything we actually
can search.
>> 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.
But I guess we can't avoid that. We have to make a choice there, an "act of
faith" for one option or the other. So we should take the one that is right most
of the time, even if it's wrong a few times.
>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.
It might be.
Or it might be that they have found something we both miss about the artifact,
about how it works (most probably).
Maybe they choose not to research, search the other moves with null windows,
allocate more time and then jump to the next iteration in order to validate the
score there.
Or they might use not a null window but something like [alpha-5,alpha+1] and
then trust the fail high there.
Anyway, it's an interesting thing to think about. There're surely many
"secrets" there waiting to be discovered...
>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.
So the window must be open, not a null window artifact...
>If you now adjust alpha, this can avoid a following fail low in a
>research situation, that would have be seen, without adjusting alpha.
By adjusting alpha you mean changing my current alpha for the found lower
bound, right?
I don't do that. If I raise alpha because of that lower bound, I still need to
search so, if null move fails high on the next ply for this lowered beta, what
information do I really have? I was searching a window and now I find myslef
with an upper bound that is actually inside my original window! Possibly this
has an easy solution, but I preferred not to deal with that.
>Similar for upper bound hits.
Same problem. If I lower beta, search and fail high for the new beta... well,
I guess I'd need to research with the original window, right?
>Regards,
>Dieter
Regards,
José C.
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.