Let's assume a fail-soft framework (fail-hard will be similar) and the following code:
Code: Select all
int score = rootSearch(position, alpha, beta, maxDepth);
if (score <= alpha) {
score = rootSearch(position, -INF, NEW_BETA, maxDepth);
} else
if (score >= beta) {
score = rootSearch(position, NEW_ALPHA, +INF, maxDepth);
}
1) NEW_BETA = score, NEW_ALPHA = score
2) NEW_BETA = score+1, NEW_ALPHA = score-1
(fail-hard: replace 'score' by 'alpha' and 'beta', respectively.)
My question arises since I am not quite sure what happens if the true minimax value of the search for the given 'maxDepth' is equal to 'score'. (In other cases there should not be any problem, I hope.)
- With solution 1), the re-search after failing low will immediately fail high since the best move returns 'score'. Is this cutoff o.k. or not?
- With solution 1), the re-search after failing high might fail to produce a PV since none of the moves improves over NEW_ALPHA. Is this o.k. or not? Note that I don't assume that the PVS algorithm is used; it might actually depend on the search algorithm.
- With solution 2), both seems to be corrected but at least the re-search after failing low will often need more nodes than solution 1).
Solution 1) is what can be read everywhere, so my guess is that it is the right solution. But I'd like to understand why. Any suggestions are welcome.
Sven