bob wrote:The question is, where is the improvement? We get a fail high. Or a fail low. How does knowing a more accurate bound help?
Take the root search function for example. After searching the first move (YBW) you spawn a search of the second root move with a null window, i.e. alpha = best_score, beta = best_score + 1. This search returns a score of best_score + 10 (i.e. a fail-soft fail high). Then you're gonna do the full window search to find the actual score of this move, now you spawn a new search with a window of [best_score + 10, +INFINITY] instead of getting a score of best_score + 1 and doing the new search with a window of [best_score + 1, + INFINITY].
The latter is what would happen with fail-hard, the former is what you can do if you use fail-soft. Smaller window, faster search.
That's not to mention the more accurate entries in the TT which can cause some additional hash hits.
I don't understand why performance would be the same. With fail-soft you propagate tighter bounds, and store tighter bounds in the hash table. When you do a re-search with shifted null-window that should come in really useful. You will get lots of hash cuts where with fail hard the bound was guaranteed to be useless.
I don't think fail soft is anymore bug prone than fail hard. With fail hard you tend to notice bugs more quickly, though.
rbarreira wrote:There are two ways of implementing alpha-beta: fail-soft and fail-hard.
Fail-hard means you never return a score out of the expected bounds ( alpha <= x <= beta ). Fail-soft means you can return any score.
To qualify as fully fail-soft, a search algorithm must always return scores which are as high or as low as possible. It's not enough to return scores above beta, as an ALL node above would turn it into a fail-hard score (i.e. = alpha). This means that you need an extra variable in the search function, which records the best score found so far even if it's below alpha.
They are exactly equivalent from an alpha-beta point of view, since alpha-beta only checks if the score is >= beta, <= alpha or in between alpha and beta. But when you add transposition tables into the mix, fail soft records more accurate bounds than fail-hard which should somewhat improve performance.
In a PVS-type search, fail soft can also return more accurate scores that you can use to better choose the window of a subsequent confirmation search.
Hi Ricardo, thanks for the response.
Ok I read that on chess programming wiki.
PS: I don't see the sense of option 3... if you have a better bound to return, why not return it?
That's why I'm asking, I use PVS + ZWS in my engine and it always is doing worse in tests if I return the score backed up by the search. It might be a bug though...
Correct. When in doubt, fail hard. Fail soft is a source of potential bugs if you are not aware of certain things. If you are aware of those, then it is ok but the performance should be the same. Then the question is, why not fail hard . Fail soft may help you if you use the return scores as a hint for something. For instance, threats. If you do not do that, the performance should be identical.
BE CAREFUL: if you search every single node in an ALL node, there is no risk to return score as a bound. But if you do not search every node, you cannot know with certainty whether that bound was correct. It is possible that another move you did not search may improve it. What "ALL" nodes do you not search completely? quies nodes, when you do delta pruning, leaf nodes when you do futility pruning.
The problem is when you return to this node, with different alpha and betas, and take the score+bound from the hash table. Now, that wrong bound may be able to give a wrong cutoff. The combination of careless fail-soft with hash table could give you very nasty and difficult to trace bugs.
The solution in those cases (delta pruning, futility nodes) is NOT to return the score, but to take into account the safety margin you were using. Even safer, if you do not even want to think about it, return alpha and fail hard.
You can still fail hard in certain place and soft in others (checkmates and stalemates) if you could use that information. It is very interesting to check the same program with fail hard and fail soft as you do. If there is a huge discrepancy, there is a bug somewhere.
Miguel
After reading all replies of this thread it seems to me that fail-hard is a more "conservative" way of backing up beta cutoffs values.
It appears that most top engines, for instance Stockfish and Robbolito (Rybka), are developed with the only goal of improving playing performance.
They are succeeding a lot in this regard. And from what I could understand most of its success was accomplished abusing a lot of "leaps of faith" by using agressive pruning, reductions and even fail softs everywhere.
The only place in Stockfish's source I can see a fail hard is when doing null move in the only situation where the search returns a mate score.
I guess taking all these risks is really worth it depending on what you are aiming at: perfect analyses, playing performance, etc.
I'm not sure that it's fair to say Stockfish and others are taking leaps of faith in using things like fail soft.
I actually see it the opposite way... If you need to use fail-hard to eliminate bugs in your search, you are taking a leap of faith that fail hard will "fix" those problems. Fail hard essentially means throwing away information that you computed earlier, which of course will hide problems with those computations.
Could it be instead that Stockfish and those other strong programs can use fail soft because they eliminated most other search bugs that fail hard would hide?
By the way, a suggestion for your debugging... Try to disable all the pruning tricks you're using, and see if fail soft results in an improvement then. If it does, start gradually adding back the pruning tricks until fail soft starts playing worse. Maybe you can identify the pruning problems this way.
There is no reason anyone who have done some thinking on the meaning of fail-soft would implement fail-hard. If one is unsure how to implement fail-soft with confidence, then one is also likely not too certain how to fail hard. - Indecision too is a source of bugs.
May be you should remember what a poster mentioned earlier, that with fail-soft, one has to keep another int variable "best_score" initialized to -infinity to start with and not make changes to the backup bounds alpha, beta.
However one fails, bugs in chess programming would not fail .
bob wrote:The question is, where is the improvement? We get a fail high. Or a fail low. How does knowing a more accurate bound help?
Take the root search function for example. After searching the first move (YBW) you spawn a search of the second root move with a null window, i.e. alpha = best_score, beta = best_score + 1. This search returns a score of best_score + 10 (i.e. a fail-soft fail high). Then you're gonna do the full window search to find the actual score of this move, now you spawn a new search with a window of [best_score + 10, +INFINITY] instead of getting a score of best_score + 1 and doing the new search with a window of [best_score + 1, + INFINITY].
The latter is what would happen with fail-hard, the former is what you can do if you use fail-soft. Smaller window, faster search.
That's not to mention the more accurate entries in the TT which can cause some additional hash hits.
How does this not help?
The extra information you have in fail soft it is based on guesses if futility pruning and/or delta pruning is used. They are not real bounds, they are estimated based on safety margins. That's where the danger lies. You may be trusting those not to do re-searches. That is ok in one iteration, but if they get stuck in the HT after being propagated, search could be seriously misled.
As you said, with fail soft you have extra information, the problem is that if you are not _really_ careful you extra information that is not reliable.
bob wrote:The question is, where is the improvement? We get a fail high. Or a fail low. How does knowing a more accurate bound help?
Take the root search function for example. After searching the first move (YBW) you spawn a search of the second root move with a null window, i.e. alpha = best_score, beta = best_score + 1. This search returns a score of best_score + 10 (i.e. a fail-soft fail high). Then you're gonna do the full window search to find the actual score of this move, now you spawn a new search with a window of [best_score + 10, +INFINITY] instead of getting a score of best_score + 1 and doing the new search with a window of [best_score + 1, + INFINITY].
The latter is what would happen with fail-hard, the former is what you can do if you use fail-soft. Smaller window, faster search.
That's not to mention the more accurate entries in the TT which can cause some additional hash hits.
How does this not help?
The extra information you have in fail soft it is based on guesses if futility pruning and/or delta pruning is used. They are not real bounds, they are estimated based on safety margins. That's where the danger lies. You may be trusting those not to do re-searches. That is ok in one iteration, but if they get stuck in the HT after being propagated, search could be seriously misled.
As you said, with fail soft you have extra information, the problem is that if you are not _really_ careful you extra information that is not reliable.
Miguel
Stockfish uses both futility pruning and fail-soft according to a quick look I just took there, and it seems to be doing fine for itself...
bob wrote:The question is, where is the improvement? We get a fail high. Or a fail low. How does knowing a more accurate bound help?
Take the root search function for example. After searching the first move (YBW) you spawn a search of the second root move with a null window, i.e. alpha = best_score, beta = best_score + 1. This search returns a score of best_score + 10 (i.e. a fail-soft fail high). Then you're gonna do the full window search to find the actual score of this move, now you spawn a new search with a window of [best_score + 10, +INFINITY] instead of getting a score of best_score + 1 and doing the new search with a window of [best_score + 1, + INFINITY].
The latter is what would happen with fail-hard, the former is what you can do if you use fail-soft. Smaller window, faster search.
That's not to mention the more accurate entries in the TT which can cause some additional hash hits.
How does this not help?
The extra information you have in fail soft it is based on guesses if futility pruning and/or delta pruning is used. They are not real bounds, they are estimated based on safety margins. That's where the danger lies. You may be trusting those not to do re-searches. That is ok in one iteration, but if they get stuck in the HT after being propagated, search could be seriously misled.
As you said, with fail soft you have extra information, the problem is that if you are not _really_ careful you extra information that is not reliable.
Miguel
Stockfish uses both futility pruning and fail-soft according to a quick look I just took there, and it seems to be doing fine for itself...
All I will add here is that this is _far_ more complicated than you realize. For just one example, out of many (in addition to what MB just posted) is what do you do with lazy evaluation? If the score is way outside the window, and you decide to return before doing the full eval, what do you return? Surely not just alpha or beta if you want fail-soft to work at all? Do you return the estimated score which can be way off the final mark? When you do a futility prune, what do you return? Reduced depth searches? Null-move searches? fail-soft is not as simple as it seems, and most end up implementing it in a flawed way to work around some of those issues. I've not looked at stockfish, but will try to do so later today when I have time, just to see what they are doing...
bob wrote:
All I will add here is that this is _far_ more complicated than you realize. For just one example, out of many (in addition to what MB just posted) is what do you do with lazy evaluation? If the score is way outside the window, and you decide to return before doing the full eval, what do you return? Surely not just alpha or beta if you want fail-soft to work at all? Do you return the estimated score which can be way off the final mark? When you do a futility prune, what do you return? Reduced depth searches? Null-move searches? fail-soft is not as simple as it seems, and most end up implementing it in a flawed way to work around some of those issues. I've not looked at stockfish, but will try to do so later today when I have time, just to see what they are doing...
As I said earlier in the thread: you return as high or as low a score as you know to be accurate. No more and no less.
If your lazy evaluation doesn't make mistakes that means you know the safety margin, so use it to get the maximum / minimum possible score, it's just a subtraction. If it makes mistakes then that's out of the scope of fail-soft. But if you're really afraid of what would happen here, you can still use a half-assed fail-soft and return beta or alpha when you do lazy evaluation. That wouldn't negate all the benefit of fail-soft, just some of it.
bob wrote:
All I will add here is that this is _far_ more complicated than you realize. For just one example, out of many (in addition to what MB just posted) is what do you do with lazy evaluation? If the score is way outside the window, and you decide to return before doing the full eval, what do you return?
...
One reason why chess programming is such "addictive" fun is it offers a challenge to get a bug free program.Whether it is fail soft or hard will not make a chess engine less bug free.
Your example of lazy-evaluation has no proper treatment as, in itself, it is a great risk if the instance depends on the current a-b bounds and will be corrupt if used in other revisits to the same node (cannot put into the TT). So only the programmer knows what risks to take and it has nothing to do with fail hard/soft. It is the same with all the other issues that can cause problems.
The only time chess programming is clear is when there is no pruning, no depth extension/reduction, etc... , just plain alpha-beta as you are well aware of.
. Fail soft may help you if you use the return scores as a hint for something. For instance, threats. If you do not do that, the performance should be identical.
- Indecision too is a source of bugs. 
