Evert wrote:bob wrote:
When you recurse with those values, you can never do the "if (value > alpha && value < beta) because beta = alpha+1 99+% of the time, and therefore if value > alpha, then it is at least == beta and for fail-soft it could be even higher.
But along the PV, where beta != alpha+1, you search the first move at such a node with the normal alpha/beta window, then you search the remainder of the moves at that ply with alpha, alpha+1. On occasion, here, you CAN get the value > alpha & value < beta, because the window you just failed high on was alpha, alpha+1, and you want to re-search with alpha,beta to see if it still fails high or if you get a real score back.
I'm not entirely sure I understand the < beta in that test.
Without it, any move that improves alpha (against expectations) with a null-window is subjected to a research - in other words, we don't necessarily trust the result. Seems fair.
With that addition, we're saying that we want an exact score if possible - but if the returned score suggests that the move will cause a cut-off, we don't bother and simply trust the score as given. In that sense, the <beta should be a simple speed optimisation that prevents an unnecessary research that is going to fail high. Is that the idea?
If my understanding is correct, in a fail-hard environment the returned score can never be larger than alpha+1, so the condition alpha < score < beta is equivalent to score>alpha && beta !=alpha+1, right?
Yes, but this is not sufficient to say whether the "&& score < beta" part of the PVS re-search condition is
1) correct and required for the algorithm to work at all,
2) correct and required for efficiency,
3) correct but redundant, or
4) incorrect.
Now I could write a lot of text again but instead I prefer to show some code (see below). After everyone has read it carefully, I would really like to see a well-written answer to my "1, 2, 3, or 4?" question above ... (My preferred answer is "2" but currently I refrain from another textual explanation of it.)
Please note, the context of my code example below is fail-hard. After clarifying the topic for fail-hard we can move on to fail-soft, or to a generalized answer. My feeling is that the answer for fail-soft is "2" as well but I did not dig into it yet.
Depending on the level of agreement on this issue it might be necessary to change the code example in the CPW article about PVS, or not ...
So here are my two functions "A" (without score < beta) and "B" (with score < beta added). So which statement 1, 2, 3, 4 of the list above applies to "B"?
Code: Select all
int PVS_FailHard_A(int alpha, int beta, ...) {
...
ASSERT(alpha < beta);
bool isZeroWindow = (beta == alpha+1); // not part of algorithm
bool isFirstMove = true;
for (all moves) {
int score;
make();
if (isFirstMove) {
isFirstMove = false;
score = -PVS_FailHard_A(-beta, -alpha, ...);
} else {
score = -PVS_FailHard_A(-(alpha+1), -alpha, ...);
if (score > alpha) {
ASSERT(score == alpha+1);
ASSERT(!isZeroWindow || score == beta);
//
// !!!!!! Note 1: If "!isZeroWindow" then score < beta. This will
// !!!!!! implicitly avoid a useless re-search which would occur in
// !!!!!! case of score >= beta (the latter would fail high the same
// !!!!!! way as the original search did).
//
// !!!!!! Note 2: If "isZeroWindow" then score == beta so here we
// !!!!!! perform a useless re-search with the same bounds as before
// !!!!!! since beta == alpha+1.
//
score = -PVS_FailHard_A(-beta, -alpha, ...);
}
}
unmake();
if (score >= beta) {
return beta;
}
if (score > alpha) {
alpha = score;
}
}
return alpha;
}
int PVS_FailHard_B(int alpha, int beta, ...) {
...
ASSERT(alpha < beta);
bool isZeroWindow = (beta == alpha+1); // not part of algorithm
bool isFirstMove = true;
for (all moves) {
int score;
make();
if (isFirstMove) {
isFirstMove = false;
score = -PVS_FailHard_B(-beta, -alpha, ...);
} else {
score = -PVS_FailHard_B(-(alpha+1), -alpha, ...);
if (score > alpha && score < beta) {
ASSERT(score == alpha+1);
ASSERT(!isZeroWindow);
//
// !!!!!! Note 1: Here we explicitly avoid a useless re-search,
// !!!!!! see note 1 in PVS_FailHard_A().
//
// !!!!!! Note 2: A re-search will only be performed with bounds
// !!!!!! different from the previous ones.
//
score = -PVS_FailHard_B(-beta, -alpha, ...);
}
}
unmake();
if (score >= beta) {
return beta;
}
if (score > alpha) {
alpha = score;
}
}
return alpha;
}
