Alpha-beta pruning: Fail-hard VS. Fail-soft

Question

Analyzing the Alpha-beta pruning algorithm in its fail-hard and fail-soft versions, I cannot find the difference in its behavior:

Fail-hard

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            if value ≥ β then
                break (* β cutoff *)
            α := max(α, value)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            if value ≤ α then
                break (* α cutoff *)
            β := min(β, value)
        return value

Fail-soft

function alphabeta(node, depth, α, β, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
            α := max(α, value)
            if value ≥ β then
                break (* β cutoff *)
        return value
    else
        value := +∞
        for each child of node do
            value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
            β := min(β, value)
            if value ≤ α then
                break (* α cutoff *)
        return value

I understand that in fail-soft, both alpha and beta are determined before evaluating break de for-loop (branch), but:

In the event that the analysis in the branch must end, the value of alpha and beta determined have no effect on the analyzes carried out in the rest of the other branches that will be found above it. am I not understanding the pseudocode correctly?

Thank you very much!

user_952648 · Answer

You are correct, the two code snippets have identical behaviour – both of them are actually the "fail-soft" variant. (The code is from Wikipedia, and was added to the Alpha–beta pruning article on 5 June 2021.)

The real "fail-hard" variant (which is older of the two) initialises value to α when maximising and to β when minimising, rather than to -∞ and +∞.

The "fail-soft" variant was introduced by John Fishburn in his 1983 article "Another optimization of alpha-beta search" (SIGART Bull., 84 (April 1983): 37–38. DOI [paywalled]). Here is an extract:

We assume the reader is familiar with the alpha-beta search algorithm:[1]
ab(p,alpha,beta)
position p; int alpha,beta;
{
    int m,d;
    if p is a leaf return(staticvalue(p));
    let p[1]...p[d] be the successors of p;
    m = alpha;
    for(i=1;i<=d;i++){
        m = max(m, -ab(p[i],-beta,-m));
        if(m >= beta) return(m);
    }
    return(m);
}
The value ab returned by the function ab(p,alpha,beta) gives the following information about the true negamax value, nm, of p:

if ab <= alpha then nm <= alpha
if ab >= beta then nm >= beta
if alpha < ab < beta then nm = ab

If we initialize the variable m to -∞ instead of alpha, and take care not to change the values passed to recursive calls of the procedure, we get the following routine, called fab for fail-soft alpha-beta search:
fab(p,alpha,beta)
position p; int alpha,beta;
{
    int m,d;
    if p is a leaf return(staticvalue(p));
    let p[1]...p[d] be the successors of p;
    m = -∞;
    for(i=1;i<=d;i++){
            m = max(m, -fab(p[i],-beta,-max(m,alpha)));
            if(m >= beta) return(m);
    }
    return(m);
}
The value fab returned by fab(p,alpha,beta) sometimes bounds nm more tightly than ab when the search fails high or low: [emphasis added]

if fab <= alpha then nm <= fab
if fab >= beta then nm >= fab
if alpha < fab < beta then nm = fab

The optimization itself seems obvious enough, and the above inequalities are not difficult to prove. The hard part is to find a use for fab. Unfortunately, the algorithm as it stands searches exactly the same nodes as ab. Fab seems to be a solution in search of a problem. A little thought, however, suggests the following possible applications:

Several infinitesimal window schemes [2,3] have been found to be more efficient than normal alpha-beta in practical game-playing programs. When a search with one of these windows fails high, the node must be searched again with a normal window. A tighter bound provided by fab could be used to make this normal window smaller.

...

References:

D.E. Knuth and R.W. Moore, "An analysis of alpha-beta pruning," Artificial Intelligence, col. 6(4), pp. 293-326 (Winter 1975).

J.P. Fishburn, Three optimizations of alpha-beta search, Computer Science Department, University of Wisconsin - Madison (May 1981). Appendix to Ph.D. thesis.

J. Pearl, "Asymptotic Properties of Minimax Trees and Game-Searching Procedures," Artificial Intelligence, col. 14(2), pp. 113-13

user_13379473 · Answer

The main difference between fail-hard and fail-soft is that fail-hard limits the return value ranged in alpha and beta, while fail-soft doesn't.

You may check if the initial value should be set alpha/beta instead of negative_infinity/infinity in the fail-hard version.

As shown in your pseudocode of fail-soft, alpha and beta are updated before checking whether pruning. Thus, fail-soft returns a tighter bound, giving more information.

If you use a transposition table, next time you look up an existing state, its tighter bound will improve your search.

Alpha-beta pruning: Fail-hard VS. Fail-soft

2 Answers