Minimax and Alpha-Beta Pruning

In a two-player, zero-sum, perfect-information game, both players know everything and one player's gain is the other's loss. MAX wants a large final utility; MIN wants a small one. Optimal play against a perfect opponent has an exact definition, and it is computed bottom-up.

The minimax value

$$\text{MINIMAX}(s) = \begin{cases} \text{UTILITY}(s) & \text{if } s \text{ is terminal},\\ \max_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MAX moves at } s,\\ \min_{a} \text{MINIMAX}(\text{RESULT}(s,a)) & \text{if MIN moves at } s. \end{cases}$$

Read it as an assumption about the opponent: MAX assumes MIN will always reply with the worst move for MAX. The value is what MAX can guarantee even against perfect play - a lower bound you cannot be argued out of, not a prediction of what a weak opponent will do.

Worked example

The standard two-ply tree. A MAX root has three MIN children, whose leaves are

$$B: (3, 12, 8) , \qquad C: (2, 4, 6) , \qquad D: (14, 5, 2) .$$

Back up the MIN nodes. Each takes the minimum of its leaves:

$$B = \min(3,12,8) = 3 , \quad C = \min(2,4,6) = 2 , \quad D = \min(14,5,2) = 2 .$$

Back up the MAX root. It takes the maximum of its children:

$$\text{root} = \max(3, 2, 2) = 3 .$$

The minimax value is $\mathbf{3}$, and the optimal move is the one leading to $B$.

Note the trap in node $D$: it contains the largest leaf in the entire tree, $14$. It is worth $2$, because MAX does not get to choose which leaf of $D$ is reached - MIN does, and MIN will take the $2$. A branch is worth what your opponent will allow, not what it contains.

Alpha-beta pruning

Minimax examines every node, which is $O(b^m)$ and hopeless for real games. But you do not need to see every node to know the root value.

Suppose MAX has already established that $B$ guarantees $3$. Now examine $C$ and find its first leaf is $2$. Node $C$ is a MIN node, so its final value is at most $2$ - MIN can always take that $2$, and further leaves can only lower it. Since $2 < 3$, MAX will never choose $C$. The remaining leaves of $C$ cannot change the root value, so they need not be examined at all.

That is the entire idea, tracked with two bounds: $\alpha$, the best value MAX can already guarantee, and $\beta$, the best MIN can already guarantee.

What pruning changes. Applied to a standard minimax tree, alpha-beta returns the same move as minimax would, while pruning away branches that cannot possibly influence the final decision. It is exact, not approximate: the value is identical, only the work differs. Anyone describing it as a faster approximation has misunderstood it.

Move ordering

Pruning depends entirely on examining good moves early. If the best move is searched first, $\alpha$ rises immediately and later branches are cut quickly. With perfect ordering the effective branching factor falls from $b$ to about $\sqrt{b}$, letting a search go roughly twice as deep in the same time. With worst-case ordering nothing is pruned and you have paid minimax's full cost.

This is why real engines invest heavily in ordering heuristics before deepening the search.

Before the quiz

Be able to back values up a small tree, state that alpha-beta returns the identical value while examining fewer nodes, and explain why $D$ is worth $2$ despite containing $14$. See Adversarial Search and Minimax.