Description

Alpha-Beta Pruning is an optimization technique for the Minimax algorithm. It eliminates branches in the game tree that don't need to be explored because they cannot influence the final decision. This helps reduce the number of nodes evaluated and improves efficiency without affecting the result.

• Alpha (α): The best (highest) value that the maximizer currently can guarantee.
• Beta (β): The best (lowest) value that the minimizer currently can guarantee.
• If at any point β ≤ α, the algorithm prunes that branch (ignores it).

Examples (Code)

Below is a simple example(Python Pseudocode)

def alpha_beta(node, depth, alpha, beta, maximizingPlayer):
    if depth == 0 or is_terminal(node):
        return evaluate(node)

    if maximizingPlayer:
        maxEval = -float('inf')
        for child in node.children:
            eval = alpha_beta(child, depth - 1, alpha, beta, False)
            maxEval = max(maxEval, eval)
            alpha = max(alpha, eval)
            if beta <= alpha:
                break  # Beta cutoff
        return maxEval
    else:
        minEval = float('inf')
        for child in node.children:
            eval = alpha_beta(child, depth - 1, alpha, beta, True)
            minEval = min(minEval, eval)
            beta = min(beta, eval)
            if beta <= alpha:
                break  # Alpha cutoff
        return minEval

Real-World Applications

Where the Topic Is Applied

Resources

Interview Questions with Answers