CSE 4355 · W5 C1 · Minimax and alpha

01 Cold open 0–4 min

Do you need to look at every leaf?

Last class's tree. Minimax read all 9 leaves to find A = 3.

Think deeper

You have finished B (= 3). Under C, the first leaf is 2. Do you need to look at C's other two leaves?

Argue it in pairs for two minutes. There may be more than one defensible answer.

02 Concept 4–10 min

Alpha and beta: what each side already has

α = the best (highest) value MAX can already guarantee on the path to this node. Starts at −∞, only goes up.
β = the best (lowest) value MIN can already guarantee on that path. Starts at +∞, only goes down.
The true value that matters lies in the window [α, β]. When the window closes, α ≥ β, the rest of the node's children cannot matter: prune.

\text{MIN node: cut when } v \le \alpha \qquad \text{MAX node: cut when } v \ge \beta

Read it as a conversation

MAX at the root: "I already have a move worth 3." MIN at C: "Here I can hold you to 2." MAX: "Then I'm not coming to C. Stop looking."

Pro tip

α and β travel down the tree as arguments; values come back up. A child's window is its parent's current window.

03 Concept 10–14 min

Alpha–beta in fifteen lines

function MAX-VALUE(s, α, β):
  if TERMINAL(s): return UTILITY(s)
  v ← −∞
  for each a in ACTIONS(s):
    v ← max(v, MIN-VALUE(RESULT(s, a), α, β))
    if v ≥ β: return v        // MIN above will avoid this node
    α ← max(α, v)
  return v

function MIN-VALUE(s, α, β):
  if TERMINAL(s): return UTILITY(s)
  v ← +∞
  for each a in ACTIONS(s):
    v ← min(v, MAX-VALUE(RESULT(s, a), α, β))
    if v ≤ α: return v        // MAX above will avoid this node
    β ← min(β, v)
  return v

Call MAX-VALUE(s₀, −∞, +∞) and keep the action with the best value.

Gotcha

Values returned from a cut node are bounds, not exact: C returns "2", meaning "≤ 2". Only the root's value is guaranteed exact.

Pro tip

It is minimax plus two lines per function. Still depth-first: O(bm) memory.

04 Worked example 14–20 min

Worked example: pruning by hand

Given

Last class's tree (Russell & Norvig): MAX root, leaves 3 12 8 | 2 4 6 | 14 5 2.

Find

The root value, each node's [α, β] window, the pruned leaves.

Leaves evaluated 0 / 9

Start at the root with the window [α, β] = [−∞, +∞].

Method: ALPHA-BETA-SEARCH (Russell & Norvig)

Solution

Predict the answer first. Then reveal one step at a time.

05 Live lab 20–27 min

Live lab: pruning, and why order matters

Leaves evaluated 0 / 27

Start at the root with the window [α, β] = [−∞, +∞].

06 Your turn 27–33 min

Your turn · 1: alpha–beta on a three-ply tree

05:00

1 Exam CQ

Run alpha–beta left to right. Give the [α, β] window of every node when it is visited, and list the pruned leaves.

Work it out first.
Press Solve when the class has an answer.

07 Concept 33–38 min

Move ordering decides everything

Ordering	Nodes examined	Effective b
Worst first	b^m (no pruning)	b
Random	≈ b^3m/4	b^3/4
Best first (perfect)	≈ b^m/2	√b

Chess: b ≈ 35 becomes ≈ 6 with perfect ordering. We cannot know the best move in advance (that is the search), but cheap guesses come close:

try captures and checks first; then killer moves (moves that caused cuts elsewhere at this depth);
iterative deepening: the best move from depth d − 1 is searched first at depth d;
transposition table: a hash table of positions already evaluated (different move orders reach the same position).

Pro tip

Iterative deepening (Week 3) looks wasteful, but here it pays for itself: the shallow searches produce the move ordering for the deep one.

08 Worked example 38–42 min

Worked example: how deep can it see?

Given

Chess, b ≈ 35. The computer can examine 10⁹ positions per move.

Find

The search depth for minimax, for alpha–beta with perfect ordering, and with random ordering.

Method: complexity of alpha–beta (Russell & Norvig; Knuth & Moore)

Solution

Predict the answer first. Then reveal one step at a time.

09 Think deeper 42–46 min

Critical thinking · what does pruning cost?

Think deeper

Alpha–beta skipped leaf 3 under F. Suppose that leaf was actually 100. Would MAX have played differently?

Argue it in pairs for two minutes. There may be more than one defensible answer.

Think deeper

Then why do some engines also use forward pruning (skipping moves that merely look bad), which can be wrong?

Argue it in pairs for two minutes. There may be more than one defensible answer.

10 Concept 46–51 min

Dice and cards: expectiminimax

In Ludo, backgammon or any game with dice, the tree has a third kind of node: chance, whose children are the outcomes of the roll, each with a probability.

\text{EMM}(s) = \begin{cases} \text{UTILITY}(s) & \text{terminal} \\ \max_a \text{EMM}(\text{RESULT}(s,a)) & \text{MAX} \\ \min_a \text{EMM}(\text{RESULT}(s,a)) & \text{MIN} \\ \sum_r P(r)\,\text{EMM}(\text{RESULT}(s,r)) & \text{CHANCE} \end{cases}

Scale matters now

Minimax only compares values, so any order-preserving change of EVAL gives the same move. An average is different: EVAL must be proportional to the expected payoff (e.g. a win probability), not just ranked correctly.

Pro tip

Time grows to O(b^m n^m) for n dice outcomes: a Ludo die adds a factor of 6 per turn. Alpha–beta pruning works only weakly on chance nodes.

11 Worked example 51–56 min

Worked example: safe move or race?

Given

Ludo. (a₁) Move to a safe square: utility 2 or 6, probability ½ each (the opponent's roll). (a₂) Race ahead: utility 6 with probability 0.8, −5 if the opponent rolls the capture (0.2).

Find

The expectiminimax value of each move and the best move.

Method: EXPECTIMINIMAX (Russell & Norvig)

Solution

Predict the answer first. Then reveal one step at a time.

12 Your turn 56–61 min

Your turn · 2: same order, different move

04:00

2 Critical thinking

relabel leaves (1→1, 2→20, 3→30, 4→400)

Find MAX's best move. Then relabel the leaves 1 → 1, 2 → 20, 3 → 30, 4 → 400 (the order is unchanged) and find it again. What does this tell you about evaluation functions?

Work it out first.
Press Solve when the class has an answer.

13 Real world 61–65 min

Real world: what engines actually do

Stockfish

The strongest open-source chess engine: alpha–beta with iterative deepening, transposition tables, killer moves, late-move reductions and quiescence search, with a small neural network (NNUE) as EVAL. Tens of millions of positions per second on a laptop.

AlphaZero (2017)

Replaced alpha–beta by Monte Carlo tree search guided by a deep network, trained only by self-play. It examined about 1,000× fewer positions than Stockfish and still beat it.

Ludo on your phone

Mobile Ludo bots run expectiminimax a few plies deep (or simple rules). Sholo Guti has no dice, so a minimax player with alpha–beta and a material-count EVAL is a weekend project: a good presentation topic.

14 Pop quiz 65–70 min

Pop quiz

Score 0

Question 1 / 5

Alpha–beta pruning, compared with minimax on the same tree, returns…

15 Recap 70–80 min

Three things to remember

01

Alpha–beta: carry [α, β] down; cut a MIN node when v ≤ α, a MAX node when v ≥ β. Same root value as minimax.

02

Ordering: worst b^m, random ≈ b^3m/4, best ≈ b^m/2: twice the depth. Iterative deepening, killer moves and transposition tables get close to the best case.

03

Chance nodes average: Σ P(r)·value. EVAL must then have a meaningful scale, not just the right order.

HW Before next class

(a) Run alpha–beta on [[3, 2, 1], [4, 8, 9], [5, 6, 7]] (MAX root, three MIN children). Which leaves are pruned? (b) Reorder the children (not the values within a leaf set) so that alpha–beta prunes as much as possible. Check both in the lab.

Assignment 2 is due next class. The midterm (Weeks 1–5, CQ only) follows this week.

Work it out first.
Press Solve when the class has an answer.

Minimax and alpha–beta pruning

Do you need to look at every leaf?

Alpha and beta: what each side already has

Read it as a conversation

Alpha–beta in fifteen lines

Worked example: pruning by hand

Given

Find

Solution

Live lab: pruning, and why order matters

Your turn · 1: alpha–beta on a three-ply tree

Move ordering decides everything

Worked example: how deep can it see?

Given

Find

Solution

Critical thinking · what does pruning cost?

Dice and cards: expectiminimax

Worked example: safe move or race?

Given

Find

Solution

Your turn · 2: same order, different move

Real world: what engines actually do

Pop quiz

Three things to remember