So far our agents have been alone in the world. Today an adversary enters the room. In chess, draughts or tic-tac-toe, the opponent's moves are chosen to minimise your outcome. Planning under such opposition is called adversarial search, and it produced some of AI's most famous triumphs — from Deep Blue to AlphaZero.
Games as search problems#
We model a two-player, zero-sum, perfect-information game with:
- $s_0$: the initial position;
- $\text{ToMove}(s)$: whose turn it is (MAX or MIN);
- $\text{Actions}(s)$ and $\text{Result}(s, a)$;
- $\text{IsTerminal}(s)$;
- $\text{Utility}(s, p)$: the final payoff for player $p$ (e.g. +1 win, 0 draw, −1 loss).
"Zero-sum" means one player's gain is the other's loss, so a single number describes the outcome.
The minimax value#
Assume both players play optimally. The minimax value of a state is
MAX chooses the move leading to the highest minimax value. This recursion is a depth-first exploration of the whole game tree, with time $O(b^m)$ and space $O(bm)$. For chess ($b \approx 35$, $m \approx 80$ plies) that is about $10^{123}$ nodes — utterly infeasible. We need two ideas: pruning and evaluation functions.
Alpha–beta pruning#
Alpha–beta computes exactly the same decision as minimax while ignoring branches that cannot influence it. It carries two bounds:
- $\alpha$: the best value MAX can already guarantee on the current path;
- $\beta$: the best value MIN can already guarantee on the current path.
Whenever $\alpha \ge \beta$, the current node cannot affect the final decision, so we stop exploring it.
import math
def alphabeta(state, depth, alpha, beta, maximizing, game):
if depth == 0 or game.is_terminal(state):
return game.evaluate(state)
if maximizing:
value = -math.inf
for move in game.ordered_moves(state):
value = max(value, alphabeta(game.result(state, move), depth - 1,
alpha, beta, False, game))
alpha = max(alpha, value)
if alpha >= beta:
break # beta cut-off: MIN will never allow this line
return value
else:
value = math.inf
for move in game.ordered_moves(state):
value = min(value, alphabeta(game.result(state, move), depth - 1,
alpha, beta, True, game))
beta = min(beta, value)
if alpha >= beta:
break # alpha cut-off: MAX already has a better option
return valueWhy pruning is safe — an intuition#
Suppose MAX has already found a move worth 5. Exploring a second move, MIN's first reply gives 3. MIN will choose at most 3 at that node, which is already worse for MAX than 5. Whatever the remaining replies are, MAX will not choose this move, so we prune them.
How much does it help?#
The effectiveness depends on move ordering. With perfect ordering alpha–beta examines about $O(b^{m/2})$ nodes — the effective branching factor drops from $b$ to $\sqrt{b}$, letting you search roughly twice as deep in the same time. With random ordering it is about $O(b^{3m/4})$.
Imperfect real-time decisions#
Since we cannot reach terminal states, we cut off search at a depth limit and apply a heuristic evaluation function $\text{Eval}(s)$ estimating the expected utility. Classical chess engines used weighted linear features:
where $f_1$ might be material balance (queen = 9, rook = 5, …), $f_2$ mobility, $f_3$ king safety, and so on. Modern engines replace this hand-crafted function with a neural network trained on millions of positions — a beautiful meeting of search and learning.
Two pitfalls arise with cut-offs:
- The horizon effect: a bad event (losing a queen) can be pushed just beyond the search depth by delaying moves.
- Non-quiescent positions: evaluating in the middle of a capture sequence is misleading. Quiescence search extends the search on such positions until they are "quiet".
Beyond two-player deterministic games#
- Stochastic games (backgammon) use expectiminimax, with chance nodes averaging over dice outcomes.
- Imperfect information (poker) requires reasoning over belief states and game-theoretic equilibria.
- Monte Carlo Tree Search, covered in a later lecture, replaces exhaustive search with random simulations and powers Go programs.