Alpha-beta pruning

Speed up search with alpha-beta pruning.

Alpha-beta pruning

Alpha-beta pruning is a faster version of minimax. It prunes branches that cannot affect the final decision; the result is unchanged.

Alpha is the lowest value the max player can secure; beta is the highest value the min player can secure.

When alpha >= beta at a node, the remaining children are skipped. With good ordering, complexity drops to O(b^(d/2)).

Pruning condition

In the max branch, after evaluating each child, alpha is updated with alpha = max(alpha, value). If alpha >= beta, the loop breaks and remaining children are skipped.

In the min branch, beta is updated with beta = min(beta, value) and pruning occurs when beta <= alpha.

Pruning never changes the final minimax value; it only avoids unnecessary computation.

Exercise alphabeta function

Write alphabeta(node, alpha, beta, is_max). Return the minimax value with pruning. Print 3 with print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True)).

Show example solution

def alphabeta(node, alpha, beta, is_max):
    # Minimax with alpha-beta pruning
    if not isinstance(node, list):
        return node
    if is_max:
        value = float('-inf')
        for child in node:
            value = max(value, alphabeta(child, alpha, beta, False))
            alpha = max(alpha, value)
            if alpha >= beta:
                break
        return value
    value = float('inf')
    for child in node:
        value = min(value, alphabeta(child, alpha, beta, True))
        beta = min(beta, value)
        if beta <= alpha:
            break
    return value
print(alphabeta([[3, 5], [2, 9]], float('-inf'), float('inf'), True))

Test yourself

alpha update

alpha = max(alpha, ____)

Show answer

alpha = max(alpha, value)

When is pruning done in the max branch?
```
if alpha >= beta:
    break
```
- When alpha is greater than or equal to beta
- When alpha is zero
- When beta is zero
- When all children are scanned
Show answer

When alpha is greater than or equal to beta — When alpha >= beta, remaining children are pruned.
Alpha-beta concepts

alpha

Max lower bound
beta

Min upper bound
pruning

Cut unnecessary branches
O(b^(d/2))

Good ordering

Next lesson: Nash equilibrium

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies