COMP338 · Artificial Intelligence · Chapter 5

Games and adversarial search

Planning when the world fights back: minimax, alpha–beta pruning, and evaluation functions.

Based on lecture material by Prof. Mustafa Jarrar (Birzeit University) and Russell & Norvig, AIMA 3rd ed., Ch. 5.

The setting

Search, but an opponent moves too

In ordinary search you make every move and the world stays still. In a game, an opponent moves between your moves, and wants the opposite of what you want.

  • Two players, called MAX (us) and MIN (the opponent), taking turns.
  • Deterministic and perfect information: no dice, nothing hidden. (Chess, checkers, tic-tac-toe.)
  • Zero-sum: one player's gain is the other's loss, so a single number describes the outcome, read from MAX's view.
We start here because this clean case already contains the two big ideas: minimax and alpha–beta pruning. Cards and backgammon (hidden info, chance) need extra machinery.
Why it is hard

The tree is astronomically large

  • Playing a game is a search: my moves, your replies, my replies…
  • Chess: branching factor b ≈ 35, depth m ≈ 100 ply.
  • Full tree ≈ 35100 ≈ 10154 nodes. We can never build it.
So the real questions are:
  • Best move against a perfect opponent? That is minimax.
  • Skip work that cannot matter? That is alpha–beta.
  • Stop early but still judge well? That is an evaluation function.
Representation

The game tree

MAX MIN leaves +10 −1+1 0−1

MAX chooses at ▲ levels, MIN at ▼; one move is a ply. Leaves are terminal, scored by UTILITY from MAX's view (here +1 / 0 / −1).

PLAYER(s)
whose turn it is
ACTIONS(s)
legal moves
RESULT(s,a)
the next state
TERMINAL?(s)
is the game over?
UTILITY(s)
outcome at a terminal state
Zero-sum lets us use one number: high is good for MAX, low is good for MIN. MAX climbs, MIN drags down.
The core algorithm

Minimax: assume a perfect opponent

Whatever move MAX makes, MIN will then steer to the worst leaf for MAX. So MAX should pick the move whose forced-worst outcome is the least bad.

MINIMAX(s) =
  UTILITY(s)  if s is terminal
  max a MINIMAX(RESULT(s,a))  if MAX to move
  min a MINIMAX(RESULT(s,a))  if MIN to move
Read it as a recipe: (1) build the tree, (2) evaluate the leaves, (3) back up (min at MIN nodes, max at MAX nodes), (4) at the root, MAX takes the move with the highest backed-up value.
Worked example · press Step to advance

Backing values up the tree

▲ MAX keeps the largest child  ·  ▼ MIN keeps the smallest  ·  each node's backed-up value sits above it.
Cost

Correct and optimal, but too slow

Complete
Yes
if the tree is finite
Optimal
Yes
vs an optimal opponent
Time
bm
visits every node
Space
b·m
depth-first
For chess, bm ≈ 35100: exact minimax is completely infeasible. Two escapes follow: prune the tree (alpha–beta) and stop early with an evaluation function.
Pruning

Alpha–beta: same answer, far less work

Most leaves cannot change the root value. Alpha–beta proves a branch is irrelevant mid-search and skips it, returning exactly what minimax would.

α
best value MAX can already guarantee on this path (starts −∞, only rises)
β
best value MIN can already guarantee on this path (starts +∞, only falls)
  • At a MAX node: if value ≥ β, stop (β-cut). MIN above will never allow it.
  • At a MIN node: if value ≤ α, stop (α-cut). MAX above already has better.
Same tree, now pruned · press Step to advance

Watch the window, watch the cuts

value sits above each node  ·  the [α, β] window sits below it  ·  ✂ cut = the rest of that branch is skipped.
leaves read: 0 / 8leaves pruned: 0root: –
Efficiency

Move ordering doubles your depth

Ordering does not change the answer, only the cost. Trying strong moves first tightens the window sooner, so more branches cut. (leaf counts below: one sample tree)

best-first
5 / 9 leaves
as drawn
7 / 9 leaves
worst-first
9 / 9 leaves
Perfect ordering takes alpha–beta from O(bm) to O(bm/2): the exponent halves, so in the same time you can search twice as deep.
Real time

Stop early, then judge the position

  • We cannot reach true terminals in chess, so replace the terminal test with a cut-off test (search to depth d).
  • Nodes at the cut-off depth become the new leaves; an evaluation function estimates their value, and minimax backs those up as usual.
Thought experiment: a perfect evaluation function would let you search just one level deep. You cannot build one (that would solve the game), but it shows the evaluator is approximating the true minimax value.
Heuristics

Evaluation functions

  • Game-specific; encode human knowledge.
  • Usually a weighted linear sum of features:
EVAL(s) = w₁f₁(s) + w₂f₂(s) + … + wₙfₙ(s)
  • Chess: material (my pieces − yours), queen/rook advantage, …
  • Only the relative order matters, not the absolute value.
Tic-tac-toe, a real one:
E(s) = (open lines for X)
    − (open lines for O)
A line is open for X if it holds no O. The position favouring X scores positive (good for MAX).
In practice

Where these ideas run

  • Checkers: E(s) = (5x₁+x₂) − (5r₁+r₂), a king worth five singles; minimax/alpha–beta over the moves.
  • Chinook became checkers world champion; the game was later solved.
  • Deep Blue beat Kasparov (1997): alpha–beta to great depth + a hand-tuned evaluation + special hardware.
  • AlphaGo (2016): Go's huge branching needed a different search (Monte-Carlo tree search + learned evaluation), but the framing is the same.
Takeaways

A working game engine, in five parts

  • Minimax: MAX maximises, MIN minimises; back up from the leaves.
  • Alpha–beta: carry α, β down the path; cut branches that cannot matter. Same answer, less work.
  • Cut-off + evaluation: stop at depth d and estimate the value there.
  • Move ordering: best-first prunes hardest, toward bm/2.
The durable lesson: search the tree, evaluate where you must stop, and assume a strong opponent.

Practice the full interactive walkthrough and Jarrar's exercise tree in the Games companion.

Arrow keys or Space to move · F for fullscreen