= Solution
Use <utilities> from A's viewpoint, with A maximizing and B minimizing. The following <alpha-beta pruning> code assumes a finite horizon or terminating <game tree>; leaf evaluation uses terminal <utility> when available and a specified horizon estimate otherwise.
``
ALPHABETA(state, depth, alpha, beta, maximizing):
if state is terminal or depth == 0:
return EVALUATE(state)
if maximizing:
value := -infinity
for child in SUCCESSORS(state):
value := max(value, ALPHABETA(child, depth-1, alpha, beta, false))
alpha := max(alpha, value)
if alpha >= beta: break
return value
else:
value := +infinity
for child in SUCCESSORS(state):
value := min(value, ALPHABETA(child, depth-1, alpha, beta, true))
beta := min(beta, value)
if alpha >= beta: break
return value
``
Call the root with $(-\infty,+\infty)$ and record the child giving the greatest root value. In a nonterminal game state, SUCCESSORS must supply the game's legal moves, including any mandatory pass; a player with no moves must be handled according to the rules rather than left as an accidental empty loop.
The bound $\alpha$ records an outcome already available to MAX on the active ancestor path; $\beta$ records one already available to MIN. At a MIN node, once a child gives value at most $\alpha$, further children can only decrease the node's minimum, so MAX need not choose that branch. The dual argument applies at MAX when its current value is at least $\beta$. Returned values from cut-off subtrees can be bounds rather than exact local <minimax search> values, while the unrestricted root value is exact. Equal-value pruning preserves that value; retaining the first best root action gives a fixed tie rule.<CS 188 minimax notes>[§3.2.1, Alpha-Beta Pruning: ancestor alternatives and cutoffs]{ref}
Back to article page
