21. Alpha-Beta Pruned Minimax over a Game Tree

Problem

DeepMind's game-playing research lineage, from early Atari agents through AlphaGo-style self-play, leans on minimax search with alpha-beta pruning as the classical baseline a new search algorithm gets compared against.

Given a game tree where each leaf is a terminal utility value and each internal node is a list of its children, with players alternating between maximizing and minimizing at each depth, compute the game-theoretic value of the root under optimal play — using alpha-beta pruning so that branches which cannot possibly change the final decision are skipped rather than fully explored.

Source: src/21_alpha_beta_minimax.py

def alpha_beta_value(node: int | list, maximizing: bool = True) -> int:
    ...

Examples:
>>> alpha_beta_value([[3, 5], [6, 9]])
6

>>> alpha_beta_value([[[3, 5], [6, 9]], [[1, 2], [0, -1]]])
5

Step-by-Step Approach

1. Write plain minimax first: recursively evaluate a node, returning it directly if it's a leaf (int), otherwise taking the max of its children's values if it's a maximizing level or the min if it's a minimizing level, flipping the level on each recursive call.
2. Add two running bounds, alpha and beta, threaded through the recursion: alpha is the best value the maximizer can already guarantee somewhere above this node; beta is the best the minimizer can already guarantee.
3. At a maximizing node, after evaluating each child, update alpha to the best value seen so far. If alpha ever reaches or exceeds beta, stop evaluating remaining children immediately — the minimizer above will never let play reach this branch anyway.
4. At a minimizing node, do the symmetric thing with beta: update it after each child, and cut off remaining children the moment alpha >= beta.
5. The final value returned is identical to plain minimax — pruning only skips branches that are provably irrelevant to the final decision, it never changes the answer.
6. Handle the trivial base case where the root itself is a leaf (an int, no children to search at all).

The key insight is that alpha and beta represent "the best outcome each side can already guarantee elsewhere" — the moment a branch could only produce a result that one side would never let happen, exploring it further is provably wasted work, regardless of what values are actually hiding deeper in that branch.

Reference solution

def alpha_beta_value(node, maximizing: bool = True) -> int:
    def search(n, alpha, beta, is_maximizing):
        if isinstance(n, int):
            return n  # leaf: terminal utility
        if is_maximizing:
            value = float("-inf")
            for child in n:
                value = max(value, search(child, alpha, beta, False))
                alpha = max(alpha, value)
                if alpha >= beta:
                    break  # beta cutoff: the minimizer above already has a better option
            return value
        else:
            value = float("inf")
            for child in n:
                value = min(value, search(child, alpha, beta, True))
                beta = min(beta, value)
                if alpha >= beta:
                    break  # alpha cutoff: the maximizer above already has a better option
            return value

    return search(node, float("-inf"), float("inf"), maximizing)

Key Functions & Tricks

• isinstance(n, int) — distinguishes a leaf (terminal utility) from an internal node (list of children)
• alpha = max(alpha, value) / beta = min(beta, value) — tightens each side's guaranteed bound as children are explored
• if alpha >= beta: break — the pruning cutoff itself; stops exploring children that cannot affect the parent's decision
• Alternating is_maximizing flag threaded through recursive calls — encodes whose turn it is without extra state
• float("-inf") / float("inf") initial bounds — start with no constraint on either side before any child has been seen

How to Recognize This Pattern