Fail soft vs fail hard

[Sergei S. Markoff]

For pure iterative deepening + depth-first search framework without pruning fail-soft obviously outperforms fail-hard — due to better ordering provided by shallow search that returned value < alpha, because this search near the leaf nodes distinguishes different failed branches. Here is simple example: let's consider depth = 1 search. It tries each move and then goes to static eval (for the simplicity let's say that there are no checks/captures in leaf nodes, only static eval; also let's consider that there are no lazy eval). So each search with depth 0 simply returns -eval. In the case of each shallow search returned value <= alpha, we shoud fail low. But in the case of fail-soft we will have best move (with max -eval) and some best value <= alpha. That's why at next iteration we will have transposition move that have more chances to pruduce cut-off in the case if error at the previous iteration. Moreover, we will sometimes have value < alpha, so it can help us to modify window a little bit better (count aspiration from returned value, not from alpha).

But in the case of search with forward pruning/pruning/razoring there are two problems:
1) we will miss some moves that are able, theoretically, return value > best_value, so final node value will not be accurate.
2) we will have more TT moves; usually TT move is move that is excluded from pruning; but much of TT moves in the case of fail low are useless — these nodes will remain all-nodes, so our TT move will simply lead to less pruning and, consequently, to tree growth.

The first problem is easy to deal. Just set node value to alpha if you pruned any move. Or you can use max(best_value, alpha – C) — there are a plenty of alternatives here to test.

The second one is worse. The first way is to threat TT move from node with value <= alpha as usual move but with highest priority. Prune it if it's a prune node and so on. Add it to quiet moves processed count for forward pruning and so on. The second way is to use best_eval = alpha – C instead of best_eval = -infinity at the beginning of the node processing. In this case you will have TT moves only for "promising" nodes and it's worth to try them w/o pruning.

Do you have any test results/additional considerations?

[bob]

For pure iterative deepening + depth-first search framework without pruning fail-soft obviously outperforms fail-hard — due to better ordering provided by shallow search that returned value < alpha, because this search near the leaf nodes distinguishes different failed branches. Here is simple example: let's consider depth = 1 search. It tries each move and then goes to static eval (for the simplicity let's say that there are no checks/captures in leaf nodes, only static eval; also let's consider that there are no lazy eval). So each search with depth 0 simply returns -eval. In the case of each shallow search returned value <= alpha, we shoud fail low. But in the case of fail-soft we will have best move (with max -eval) and some best value <= alpha. That's why at next iteration we will have transposition move that have more chances to pruduce cut-off in the case if error at the previous iteration. Moreover, we will sometimes have value < alpha, so it can help us to modify window a little bit better (count aspiration from returned value, not from alpha).

But in the case of search with forward pruning/pruning/razoring there are two problems:
1) we will miss some moves that are able, theoretically, return value > best_value, so final node value will not be accurate.
2) we will have more TT moves; usually TT move is move that is excluded from pruning; but much of TT moves in the case of fail low are useless — these nodes will remain all-nodes, so our TT move will simply lead to less pruning and, consequently, to tree growth.

The first problem is easy to deal. Just set node value to alpha if you pruned any move. Or you can use max(best_value, alpha – C) — there are a plenty of alternatives here to test.

The second one is worse. The first way is to threat TT move from node with value <= alpha as usual move but with highest priority. Prune it if it's a prune node and so on. Add it to quiet moves processed count for forward pruning and so on. The second way is to use best_eval = alpha – C instead of best_eval = -infinity at the beginning of the node processing. In this case you will have TT moves only for "promising" nodes and it's worth to try them w/o pruning.

Do you have any test results/additional considerations?

I've tested fail-soft many times. I have yet to see any gain or loss whatsoever from using it or not using it. PVS searches almost all nodes on a zero-width window, so whether the result is < alpha or = alpha really doesn't change a thing. The only place I have seen it useful is in the context of something like mtd(f) where you can use a clue as to how far off your initial aspiration window actually is.

[hgm]

The second one is worse. The first way is to threat TT move from node with value <= alpha as usual move but with highest priority. Prune it if it's a prune node and so on. Add it to quiet moves processed count for forward pruning and so on. The second way is to use best_eval = alpha – C instead of best_eval = -infinity at the beginning of the node processing. In this case you will have TT moves only for "promising" nodes and it's worth to try them w/o pruning.

I raised this problem before, and think it is much more general than just a fail-hard/soft issue. Even with fail-hard you can stumble on a TT move with a lower-bound < alpha. E.g. one from a previous iteration, where the root score was lower. But when in the current iteration a so-far-underestimated other branch has "raised the bar", the stored lower-bound is no longer good enough to effect a cutoff.

Would you now still want to treat that move as a valid TT move, and give it all perks you normally give to TT moves? Like suppressing IID, and immediately searching it (before any others) at the now-requested depth? And when you do, and it fails low, because it cannot meet the raised demands, would you then start to search for an alternative at full depth with nothing to go on but the static move ordering, for moves that likely never have been touched before? When alpha was still low you picked this TT move not because it was the best, but because life was easy and you were lazy. So you took the first one that met the modest demands. It could very well be there is a much better one amongst the remaining moves, but it is rather unlikely you would pick that first, and very expensive (because of the large deoth) when you pick one that also will fail low.

Intuitively it seems attractive to not trust such a hash move before you verified that it is likely it can also meet the new demands, and start searching for a viable alternative at lower depth (IID).