Minimax / α-β Pruning Demo

A demonstration of Minimax with α-β pruning for a turn-based game between two players, MAX and MIN. Terminal nodes mark the end of the game with a utility value for MAX. Interior nodes are either MAX nodes or MIN nodes, indicating whose turn it is. The value of an interior node depends on the values of its children and whether it is a MAX or MIN node.

Both players are assumed rational: MAX always picks the branch that maximizes utility, and MIN always picks the branch that minimizes it. Minimax computes the utility of every node in the tree via depth-first search. α-β pruning tracks the best values found so far for MAX (α) and MIN (β) to skip branches that can't affect the final decision. The pseudocode below is adapted from Russell & Norvig, AI: A Modern Approach (4e).

function ALPHA-BETA-SEARCH(game, state) returns an action
    player←game.TO-MOVE(state)
    value, move←MAX-VALUE(game, state,−∞,+∞)
    return move

function MAX-VALUE(game, state,α, β) returns a (utility, move) pair
    if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null
    v←−∞
    for each a in game.ACTIONS(state) do
        v2, a2←MIN-VALUE(game, game.RESULT(state, a),α, β)
        if v2 > v then
            v, move←v2, a
            α←MAX(α, v)
        if v ≥ β then return v, move
    return v, move

function MIN-VALUE(game, state,α, β) returns a (utility, move) pair
    if game.IS-TERMINAL(state) then return game.UTILITY(state, player), null
    v←+∞
    for each a in game.ACTIONS(state) do
        v2, a2←MAX-VALUE(game, game.RESULT(state, a),α, β)
        if v2 < v then
            v, move←v2, a
            β←MIN(β, v)
        if v ≤ α then return v, move
    return v, move

Step through the algorithm below. Each step reveals exactly what α-β does at that point — entering a node, examining a leaf, updating α/β/v after a child returns, or pruning a subtree — and the message line explains it in words.