bob wrote:
No, because if ANY move exceeds alpha, it normally is >= beta since most searches have a null-window passed in. Only on PV-type nodes do you have a non-null-window, and only on those nodes can value be > alpha AND < beta, because on most nodes if it is > alpha it is = to beta thanks to the null-window.
I'm not sure how that's different from what I said?
This is what was not so clear to me:
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?
-don't do null move in the PV nodes
-don't do cutoff from the hash table in the PV nodes, just use the hash move
-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already
Seemed to me he was describing a problem trying to construct the PV from the hash table. The above don't help that at all. Perhaps I misunderstood his question?
I think his problem is incomplete PV. He tried various ways to collect the PV (one of them is using the exact nodes from the main TT, others are triangular array, etc) but still fails to display the PV at it's full length from time to time. I'm suggesting ways on how it can be solved. That's what we've been doing in our engine and we don't have that truncated PV issue.
Yes, but your "fix" is not so good. You ignore any hash hit in the PV that would stop the search. Why throw out good information like that, it hurts efficiency?
My solution uses all available information, and doesn't return short PVs either. There is no measurable overhead in my PV storing approach, and I don't give up any search efficiency by not honoring TT entries with sufficient depth, when at a PV node.
You can actually eliminate ALL search instability by throwing the TT out completely, or else just using it to store a best move, but no bound/score/draft, etc.
bob wrote:
No, because if ANY move exceeds alpha, it normally is >= beta since most searches have a null-window passed in. Only on PV-type nodes do you have a non-null-window, and only on those nodes can value be > alpha AND < beta, because on most nodes if it is > alpha it is = to beta thanks to the null-window.
I'm not sure how that's different from what I said?
This is what was not so clear to me:
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?
Ah, I see. My default mode of thinking is in terms of fail-soft.
In a fail-hard framework, the score > alpha && score < beta condition simply says to to a re-search on a PV node on any move that improves alpha (we now need to know if it fails high, and we need to update the search bound). However, it will never happen that the score > beta.
In fail soft, that can happen, and then that condition seems to say "don't trust the score, do a re-search with an open window, unless the returned score is a cut-off in which case, take the cut-off and skip the verification." This seems oddly in two minds: should you not either always accept the returned score (in which case you don't need the verification search), or never (in which case the < beta condition is not needed)?
Evert wrote:In a fail-hard framework, the score > alpha && score < beta condition simply says to to a re-search on a PV node on any move that improves alpha (we now need to know if it fails high, and we need to update the search bound). However, it will never happen that the score > beta.
No. The "score > alpha && score < beta" condition says that
a) you do a re-search on a PV node on any move that improves alpha, where we know that this means "score == alpha+1" and therefore "score < beta" (PV node!), and
b) you avoid a re-search in all other cases, including all zero-window (non-PV) nodes since *there* "score > alpha && score < beta" can never happen, and also including those PV nodes where the score of a move fails high.
In a fail-hard framework, the score > alpha && score < beta condition simply says to to a re-search on a PV node on any move that improves alpha (we now need to know if it fails high, and we need to update the search bound). However, it will never happen that the score > beta.
In fail soft, that can happen, and then that condition seems to say "don't trust the score, do a re-search with an open window, unless the returned score is a cut-off in which case, take the cut-off and skip the verification." This seems oddly in two minds: should you not either always accept the returned score (in which case you don't need the verification search), or never (in which case the < beta condition is not needed)?
I would always summarize as "The condition says to not research a score that is for sure a fail-high/low."
In non PV nodes, I see no problem. You can have only FH/FL. In PV nodes, instead, in a FH we know the score must between alpha/beta but we need to research to discover exactly where it is, and we have no information about it. In FS, we do have an indication of where the (real) score is, but this can be misleading, as the search usually back-ups a score as soon as it finds a move that produce a cut-off. A research can give a different score.
-don't do null move in the PV nodes
-don't do cutoff from the hash table in the PV nodes, just use the hash move
-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already
Seemed to me he was describing a problem trying to construct the PV from the hash table. The above don't help that at all. Perhaps I misunderstood his question?
I think his problem is incomplete PV. He tried various ways to collect the PV (one of them is using the exact nodes from the main TT, others are triangular array, etc) but still fails to display the PV at it's full length from time to time. I'm suggesting ways on how it can be solved. That's what we've been doing in our engine and we don't have that truncated PV issue.
Yes, but your "fix" is not so good. You ignore any hash hit in the PV that would stop the search. Why throw out good information like that, it hurts efficiency?
The answer, based on measurements in my program, would be because 1. it is very simple and 2. the perceived efficiency loss (just a hand full of nodes, far fewer than 1 ms worth of them) doesn't translate into an observable strength loss. The extra nodes are just the immediate cut-offs in the siblings of PV nodes. Therefore 1 prevails. In my case I maintain the PV separate from the hash table, in a variable size array, not only in the transposition table. I believe, but I haven't measured, that that might be important, because you don't want to lose PV moves ever. (It is easy to test with Fruit if that is true: remove the is_pv condition for exact matches and compare elo.)
Last edited by mvk on Tue Feb 25, 2014 7:31 pm, edited 1 time in total.
Evert wrote:In a fail-hard framework, the score > alpha && score < beta condition simply says to to a re-search on a PV node on any move that improves alpha (we now need to know if it fails high, and we need to update the search bound). However, it will never happen that the score > beta.
No. The "score > alpha && score < beta" condition says that
a) you do a re-search on a PV node on any move that improves alpha, where we know that this means "score == alpha+1" and therefore "score < beta" (PV node!), and
b) you avoid a re-search in all other cases, including all zero-window (non-PV) nodes since *there* "score > alpha && score < beta" can never happen, and also including those PV nodes where the score of a move fails high.
Once again, I never said anything different.
Let my try to rephrase it again: why do you avoid the research if the return indicates a fail high (> beta, which can only happen in a fail soft framework), but not when the score falls within the window? In the first case you trust the returned score, in the second, not. Why though?
Clearly this only ever applies to PV nodes.
xmas79 wrote:I would always summarize as "The condition says to not research a score that is for sure a fail-high/low."
Well, I don't think you'd ever research a fail low. There clearly is no point in doing a research if you know it will fail high. See below.
In non PV nodes, I see no problem. You can have only FH/FL.
Yes, I've already said several times I'm only talking about PV nodes (all other nodes having a null-window).
In PV nodes, instead, in a FH we know the score must between alpha/beta but we need to research to discover exactly where it is, and we have no information about it.
Yes.
In FS, we do have an indication of where the (real) score is, but this can be misleading, as the search usually back-ups a score as soon as it finds a move that produce a cut-off. A research can give a different score.
Yes, and that was my original question: you take the cut-off when the returned score indicates a fail high (you trust the score), but you don't when it falls within the window (you don't trust the score). Can you always trust the fail high in this case?
In FS, we do have an indication of where the (real) score is, but this can be misleading, as the search usually back-ups a score as soon as it finds a move that produce a cut-off. A research can give a different score.
Yes, and that was my original question: you take the cut-off when the returned score indicates a fail high (you trust the score), but you don't when it falls within the window (you don't trust the score). Can you always trust the fail high in this case?
I think we can't trust a score that fails high (score >= beta) in fail-soft if it results from a zero-window search (alpha, alpha+1) resp. (newAlpha, newAlpha+1). See the code example below for an explanation what I mean by "newAlpha".
So in case of fail-soft I currently get the impression that variant B that includes "&& score < beta" is incorrect (answer 4), unlike fail-hard where it is good for a tiny improvement of efficiency (answer 2). But I am not 100% sure yet ...
int PVS_FailSoft_A(int alpha, int beta, ...) {
...
ASSERT(alpha < beta);
bool isZeroWindow = (beta == alpha+1); // not part of algorithm
bool isFirstMove = true;
int bestScore = -INF;
for (all moves) {
int score;
make();
int newAlpha = Max(alpha, bestScore);
if (isFirstMove) {
isFirstMove = false;
score = -PVS_FailSoft_A(-beta, -newAlpha, ...);
} else {
score = -PVS_FailSoft_A(-(newAlpha+1), -newAlpha, ...);
if (score > newAlpha) {
ASSERT(score > alpha);
ASSERT(score > bestScore);
//
// can be either PV node or zero-window (non-PV) node
//
// Q: would it be correct to avoid a re-search for "score >= beta" in fail soft?
// If so, in which of the two cases (PV or non-PV node)?
//
score = -PVS_FailSoft_A(-beta, -newAlpha, ...);
}
}
unmake();
if (score >= beta) {
return score;
}
if (score > bestScore) {
bestScore = score;
}
}
return bestScore;
}
Sven Schüle wrote:So in case of fail-soft I currently get the impression that variant B that includes "&& score < beta" is incorrect (answer 4), unlike fail-hard where it is good for a tiny improvement of efficiency (answer 2). But I am not 100% sure yet ...
I (also) have the impression that the second one is correct in a fail-soft framework, but the first may not be.
Should be easy to test in principle, but I don't expect the difference to be very big. Either way, for readability I think I prefer the second condition...
