Author: Robert Hyatt
Date: 20:27:12 10/26/02
Go up one level in this thread
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).
Just a note. This can happen in _any_ search that uses a transposition
table. Searches get grafted from one point in the tree to another, and it
is easy to see cases where you have a >= beta type position where beta is
something like .1, and when you re-search with beta=+infinity, you can't use
that fail-high table entry and the search might not go deep enough down this
path to see how to win...
We saw this occasionally in Cray Blitz, even before we did null-move and
PVS...
>
>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?
>
>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.