Minimax/α-β Pruning Demo

A demonstration of Minimax wth α-β pruning. This shows a game tree for a turn-based game with two players, MAX and MIN. Terminal nodes indicate the end of the game with an associated utility value for MAX. Interior nodes are either MAX nodes or MIN nodes, indicating whose turn it is. The value of an interior node is dependent on the value of its children and whether it is a MAX node or a MIN node.

It is assumed that both players are rational. When it's MAX's turn, MAX chooses the branch of the tree which will maximize the utility value. Similarly MIN chooses a branch which minimizes the utility.

The Minimax algorithm calculates the utility of each node in the entire game tree (the tree is traversed in a depth-first fashion). α-β Pruning is a variation of Minimax in which two variables α and β, which record the best values encountered on a path for both MAX and MIN, are used to prune away portions of the game tree. The version of the α-β search algorithm shown below is taken from Russell \amp Norvig's 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

The demonstration allows one to step through the algorithm, showing the values for v, α, and β on entry and exit from a function call. The drawn tree indicates which portions of the subtree will be pruned away by the algorithm.