Minimax & Alpha–Beta Pruning

Games as trees

In a two-player game like tic-tac-toe or chess, every position has possible moves; each move leads to a new position with the opponent’s possible replies, and so on. Drawn out, this is a game tree:

• the root is the current position,
• each level alternates between MAX (you) and MIN (the opponent),
• the leaves are final (or far-enough) positions with a score — high is good for MAX.

Minimax

Assume both players play perfectly:

• at a MAX node, pick the child with the highest value,
• at a MIN node, pick the child with the lowest value,
• at a leaf, use its score.

Values are computed bottom-up (with a depth-first search), and the root’s value tells MAX the best guaranteed outcome. The move leading to it is the best move.

In the textbook example of the model: the three MIN nodes get values min(3,12,8) = 3, min(2,4,6) = 2 and min(14,5,2) = 2, so MAX picks the first move with value 3.

Alpha–beta pruning

Minimax looks at every leaf — impossible for chess, which has about 35 moves per position. Alpha–beta gets the same answer while skipping branches that cannot matter. It carries two numbers down the tree:

• α — the best score MAX can already guarantee (starts at −∞, only goes up),
• β — the best score MIN can already guarantee (starts at +∞, only goes down).

Whenever β ≤ α at a node, its remaining children are pruned: one player already has a better option elsewhere and will never let the game reach this point.

Example: after the first MIN node, α = 3 at the root. In the second MIN node, the first leaf is 2 — so MIN can force ≤ 2 here. MAX already has 3 elsewhere, so MAX will never choose this branch: the leaves 4 and 6 don’t need to be looked at.

With good move ordering (best moves first), alpha-beta searches twice as deep as plain minimax in the same time.

Code

import math

def alphabeta(node, alpha, beta, maximizing):
    if isinstance(node, (int, float)):          # leaf: a score
        return node
    if maximizing:
        best = -math.inf
        for child in node:
            best = max(best, alphabeta(child, alpha, beta, False))
            alpha = max(alpha, best)
            if beta <= alpha:
                break                           # β cut-off: prune
        return best
    else:
        best = math.inf
        for child in node:
            best = min(best, alphabeta(child, alpha, beta, True))
            beta = min(beta, best)
            if beta <= alpha:
                break                           # α cut-off: prune
        return best

tree = [[3, 12, 8], [2, 4, 6], [14, 5, 2]]      # MAX root, three MIN nodes
print(alphabeta(tree, -math.inf, math.inf, True))   # 3

Real game engines add…

• Depth limits + evaluation functions: stop at a fixed depth and estimate the score (material, mobility, king safety…).
• Move ordering and iterative deepening to prune more.
• Transposition tables (hash tables) to remember positions already searched.
• Modern engines like AlphaZero and Stockfish NNUE combine search with neural networks.

Common mistakes

• Swapping max and min at the wrong levels.
• Forgetting that pruning depends on the order children are visited.
• Thinking alpha-beta is an approximation — it gives exactly the minimax value.