Chan Rasjid wrote:Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.
I agree that using fail-soft may give a hint in this case. I'm not so sure whether so many programs actually use fail-soft. But I disagree on your description of fail-soft: it does not "always return the exact score", at least this can be misunderstood. On failing low or high it returns bounds the same way as fail-hard does, the only difference is that these bounds can be < alpha or > beta.
You can rewrite fail-hard and fail-soft alphabeta to fully equivalent code such that there is only one line of difference between both, and that is the initialization of the best score (initialized to alpha vs. -INF) prior to the move loop. This is done by always passing [-beta, -Max(alpha, bestScore)] to the next level, and by always returning bestScore.
Sven
Hi all,
I think I have a fail-soft framework already:
search(alpha,beta)
gen_moves();
for each move
make
if (first_move)
score = -search(-beta, -alpha);
else
{
score = -search(-alpha - 1, -alpha);
if (score > alpha && score < beta) // research only if non pv nodes
score = -search(-beta, -alpha);
}
unmake
if (score >= beta)
return score;
if (score > alpha)
alpha = score;
end for
// mate or stalemale?
if (moves_tried == 0)
{
if (in check) return LOST+ply; else return DRAW;
}
return alpha;
end search
I'm still debugging this problem, but as far as I can see, I can tell the research code works as expected, as tracing to the mate position at ply 14 it backup to ply 13 a -mate_score_in_x, so ply 13 fails-high with score +mate_score_in_x to ply 12, but then ply 12 tries next move and improves alpha from -mate to -6.00, so score backed-up to ply 11 is not -matescore_in_x but is -6.00, which will be flip-flopped by negasearch until root is reached with positive sign, hence the score of +6.00. Still investigating why it fails-high at ply 14. A lot of nodes to look through... Maybe the problem is here and not in the research. Problem is that research is fair easy to trace because I already know the search will follow PV... the search before, instead, have a complete different move ordering....... I'm trying also to investigate this problem on other positions where depths are less than 14...
Generally speaking, more cut-offs "for free" means less nodes to search, AKA less time spent on unuseful part of the tree space. So I think search quality is better.
well, at least what you posted is not a "complete" fail-soft implementation.
You return score instead of beta bound when getting a cut, which is like it
should be in FS. But on the other hand, you return the hard alpha bound if you have a fail-lo at a node.
It should look like this...
int search(PARAMS)
{
int bestScore = NO_VALUE;
...
while( moves )
{
if( firstMove )
{
value = -search(-beta,-alpha,...);
}
else
{
value = -search(-alpha-1,-alpha,...);
...
}
if( value > bestScore ) bestScore = value;
if( value > alpha ) alpha = value;
if( value >= beta ) return value; // (or simply bestScore ) may be a score above beta
}
...
// This way you will also return values below alpha
return bestScore; // may be a value below alpha
}
I agree, in case it is really free and really helps.
From the Wiki
Fail-Soft has the reputation for searching less nodes than Fail-Hard, but might also require some care regarding to search instability issues in conjunction with transposition tables and various pruning-, reduction- and extension techniques.
The general recommendation I think for a beginner was to at least start with fail hard, as it is easier to catch bugs. I still use it.
Sven Schüle wrote:I'm not so sure whether so many programs actually use fail-soft.
Because in combination with hashing it is an improvement without any trade-offs. You will see hash hits causing a cutoff that otherwise would not have been possible because the score bound was too high (or low), just because when storing it you carelessly rounded the bound to alpha or beta. And there is no downside.
I did not ask "why" ... No need to convince me of fail-soft since I am using it as well for a very long time (I think I never used fail-hard in any serious engine). I was just curious how many other engines actually use it.
Chan Rasjid wrote:Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.
I agree that using fail-soft may give a hint in this case. I'm not so sure whether so many programs actually use fail-soft. But I disagree on your description of fail-soft: it does not "always return the exact score", at least this can be misunderstood. On failing low or high it returns bounds the same way as fail-hard does, the only difference is that these bounds can be < alpha or > beta.
You can rewrite fail-hard and fail-soft alphabeta to fully equivalent code such that there is only one line of difference between both, and that is the initialization of the best score (initialized to alpha vs. -INF) prior to the move loop. This is done by always passing [-beta, -Max(alpha, bestScore)] to the next level, and by always returning bestScore.
Sven
Hi all,
I think I have a fail-soft framework already:
search(alpha,beta)
gen_moves();
for each move
make
if (first_move)
score = -search(-beta, -alpha);
else
{
score = -search(-alpha - 1, -alpha);
if (score > alpha && score < beta) // research only if non pv nodes
score = -search(-beta, -alpha);
}
unmake
if (score >= beta)
return score;
if (score > alpha)
alpha = score;
end for
// mate or stalemale?
if (moves_tried == 0)
{
if (in check) return LOST+ply; else return DRAW;
}
return alpha;
end search
I'm still debugging this problem, but as far as I can see, I can tell the research code works as expected, as tracing to the mate position at ply 14 it backup to ply 13 a -mate_score_in_x, so ply 13 fails-high with score +mate_score_in_x to ply 12, but then ply 12 tries next move and improves alpha from -mate to -6.00, so score backed-up to ply 11 is not -matescore_in_x but is -6.00, which will be flip-flopped by negasearch until root is reached with positive sign, hence the score of +6.00. Still investigating why it fails-high at ply 14. A lot of nodes to look through... Maybe the problem is here and not in the research. Problem is that research is fair easy to trace because I already know the search will follow PV... the search before, instead, have a complete different move ordering....... I'm trying also to investigate this problem on other positions where depths are less than 14...
I even do not understand why
score = -search(-beta, -score);
makes the search gets worse when you do not have any extensions
or pruning except for quiescence search.
tpetzke wrote:I agree, in case it is really free and really helps.
From the Wiki
Fail-Soft has the reputation for searching less nodes than Fail-Hard, but might also require some care regarding to search instability issues in conjunction with transposition tables and various pruning-, reduction- and extension techniques.
The general recommendation I think for a beginner was to at least start with fail hard, as it is easier to catch bugs. I still use it.
Thomas...
Fail soft is really free. The fail high and soft score x > beta is as theoretically sound as an lower bound as beta itself. It just mean that x, as well as beta, is a lower bound to the exact score of optimal play. The only reason Bob gave why Crafty uses fail hard is that it was easier for him to debug his (must be very buggy !!!) SMP search.
I think using fail soft should not pose much a a problem once we are aware when we need to be careful. There are only few cases where we may need to be careful:
1) when search() returns with a concocted "artificial" score that is outside of [alpha, beta] that is not from recursive search() itself, not from eval() and also not from the TT. I don't recall now any situation it may happen. There may come a time when we have a great idea about aborting search with failing low or high when it would be better just to fail with the bounds alpha or beta.
2) nullmove; I think it is safer to fail high on a nullmove success with beta rather than any search() score > beta. Nullmove is an unusual search where we trust beta as the only acceptable lower bound.
So what to do when search() returns with a concocted "artificial" score that is outside of [alpha, beta] that is not from recursive search() itself, not from eval() and also not from the TT ?
Chan Rasjid wrote:Almost all decent chess programs use fail-soft; ie search() always returns the exact score:
1) on fail low, do not return alpha, but the score (<= alpha).
2) on fail high, return score (>= beta), not beta.
I agree that using fail-soft may give a hint in this case. I'm not so sure whether so many programs actually use fail-soft. But I disagree on your description of fail-soft: it does not "always return the exact score", at least this can be misunderstood. On failing low or high it returns bounds the same way as fail-hard does, the only difference is that these bounds can be < alpha or > beta.
You can rewrite fail-hard and fail-soft alphabeta to fully equivalent code such that there is only one line of difference between both, and that is the initialization of the best score (initialized to alpha vs. -INF) prior to the move loop. This is done by always passing [-beta, -Max(alpha, bestScore)] to the next level, and by always returning bestScore.
Sven
Hi all,
I think I have a fail-soft framework already:
search(alpha,beta)
gen_moves();
for each move
make
if (first_move)
score = -search(-beta, -alpha);
else
{
score = -search(-alpha - 1, -alpha);
if (score > alpha && score < beta) // research only if non pv nodes
score = -search(-beta, -alpha);
}
unmake
if (score >= beta)
return score;
if (score > alpha)
alpha = score;
end for
// mate or stalemale?
if (moves_tried == 0)
{
if (in check) return LOST+ply; else return DRAW;
}
return alpha;
end search
I'm still debugging this problem, but as far as I can see, I can tell the research code works as expected, as tracing to the mate position at ply 14 it backup to ply 13 a -mate_score_in_x, so ply 13 fails-high with score +mate_score_in_x to ply 12, but then ply 12 tries next move and improves alpha from -mate to -6.00, so score backed-up to ply 11 is not -matescore_in_x but is -6.00, which will be flip-flopped by negasearch until root is reached with positive sign, hence the score of +6.00. Still investigating why it fails-high at ply 14. A lot of nodes to look through... Maybe the problem is here and not in the research. Problem is that research is fair easy to trace because I already know the search will follow PV... the search before, instead, have a complete different move ordering....... I'm trying also to investigate this problem on other positions where depths are less than 14...
I even do not understand why
score = -search(-beta, -score);
makes the search gets worse when you do not have any extensions
or pruning except for quiescence search.
Correction:
I do not know if score = -search(-beta, -score);
makes the search gets worse when you do not have any extensions
or pruning except for quiescence search.
But this is a theoretical question. Every clone uses null move pruning.
search(alpha,beta)
gen_moves();
for each move
make
if (first_move)
score = -search(-beta, -alpha);
else
{
score = -search(-alpha - 1, -alpha);
if (score > alpha && score < beta) // research only if non pv nodes
score = -search(-beta, -alpha);
}
unmake
if (score >= beta)
return score;
if (score > alpha)
alpha = score;
end for
// mate or stalemale?
if (moves_tried == 0)
{
if (in check) return LOST+ply; else return DRAW;
}
return alpha;
end search
This is almost pure fail-hard The only deviation was already mentioned by Michael: you return "score" instead of "beta" in case of a beta cutoff (and additionally you possibly return a mate or draw score even if it is outside the alpha-beta window). But this won't make any difference in my opinion since the parent will simply not improve his "alpha" anyway, so the return value goes fully unnoticed. Even if you use the same algorithm at root I think it should not matter. But you can try whether I am right or wrong by replacing the "return score" by "return beta", of course
The only deviation was already mentioned by Michael: you return "score" instead of "beta" in case of a beta cutoff (and additionally you possibly return a mate or draw score even if it is outside the alpha-beta window). But this won't make any difference in my opinion since the parent will simply not improve his "alpha" anyway, so the return value goes fully unnoticed. Even if you use the same algorithm at root I think it should not matter. But you can try whether I am right or wrong by replacing the "return score" by "return beta", of course