Q3 — Game Tree: Strategies, Alpha-Beta and SSS*

One game tree, four questions — what a strategy really is, where Alpha-Beta cuts, and which leaves SSS* actually solves.

The Question

A game tree with evaluation values at the horizon nodes A–G. Squares = MAX to move, circles = MIN to move. Tie-breaker: deepest node first, then leftmost.

Rectangles = MAX to move, circles = MIN to move.

#	Question	Official answer
3.1	Which of the following is a strategy for MAX? (A: C,D,E · B: A,C · C: A,B · D: A,D,F)	A and C
3.2	Horizon nodes in MAX's best strategy	`C,F,G`
3.3	Horizon nodes pruned by Alpha-Beta	`F,G`
3.4	Horizon nodes SOLVED by SSS*	`A,C,D,E`

The Topic in 60 Seconds

Minimax backup: MAX nodes take the max of their children, MIN nodes take the min. Leaves already hold their evals.

Strategy for MAX = a complete plan: at every MAX node pick exactly one child; the set must not split across two children of any MAX node. MIN's replies stay inside the set — every leaf the opponent can force lands in it.

Best strategy = the valid strategy whose worst leaf is best: $\text{value(strategy)} = \min(\text{evals of its leaves}), \qquad \text{best strategy maximizes this}$ Its guarantee equals the minimax value of the root.

Alpha-Beta prunes with a window $(\alpha, \beta)$ : cut the remaining children the moment $\alpha \ge \beta$ (β-cutoff at a MAX node, α-cutoff at a MIN node).

SSS* solves leaves by proving values top-down; leaves it never needs to touch are never solved.

Deep-dive: Minimax, Game Strategies, Alpha-Beta Pruning, SSS*.

Step 0 — Back up the tree

Work bottom-up:

$N_1 = \min(A, B) = \min(24, 34) = 24$
$P_1 = \min(52, 54) = 52$ , $\quad P_2 = \min(62, 64) = 62$
$M = \max(P_1, P_2) = 62$
$N_2 = \min(C, M) = \min(26, 62) = 26$
$\text{Root} = \max(N_1, N_2) = \max(24, 26) = \mathbf{26}$ (via $N_2$ , then $C$ )

3.1 — Valid strategies → A (C,D,E) and C (A,B)

Apply the split test — leaves under any MAX node must come from a single child of it:

Option	Check	Verdict
A: C,D,E	Root: C via N₂, D,E via N₂ ✓ (all one child). M: D,E via P₁ only ✓	Valid
B: A,C	Root: A via N₁ but C via N₂ — split!	Invalid
C: A,B	Root: both via N₁ ✓. N₁ is MIN — both its leaves included ✓	Valid
D: A,D,F	Root: A via N₁, D,F via N₂ — split!	Invalid

Reading a strategy set

A legal set = one committed choice per MAX node, with MIN's alternatives kept whole. A,B = "MAX goes left at the root" (MIN may pick A or B). C,D,E = "MAX goes right at the root, and if MIN hands over M, MAX commits to P₁" (C, or the pair D/E).

3.2 — Best strategy → `C,F,G`

The root value 26 is achieved through $N_2$ :

Root (MAX) commits to $N_2$ .
$N_2$ (MIN) keeps all its children: C and the M subtree.
M (MAX) commits to $P_2$ (62 beats 52).
$P_2$ (MIN) keeps all: F and G.

Horizon set: C, F, G — guarantee $\min(26, 62, 64) = 26$ = the minimax value ✓.

3.3 — Alpha-Beta prunes → `F,G`

Left-to-right, depth-first. Root MAX starts with $\alpha = -\infty$ .

Node	Window	Result
$N_1$ (MIN)	$(-\infty, +\infty)$	A: 24 → $\beta_{N_1}=24$ ; B: 34 no change. Returns 24
Root	$\alpha = 24$	—
$N_2$ (MIN)	$(24, +\infty)$	C: 26 → $\beta_{N_2}=26$ ; continue (24 < 26)
$M$ (MAX)	$(24, 26)$	$P_1$ (MIN): D=52, E=54 → 52; $\alpha_M = \max(24, 52) = 52 \ge \beta_M = 26$ → β-cutoff!
$P_2$	pruned	F, G never inspected ✓

$M$ already has 52, which its MIN parent $N_2$ will never take (26 is smaller) — so $P_2$ 's whole subtree is irrelevant. Pruned: F, G.

Step through the full α-β trace — the window $(\alpha, \beta)$ is written at every node, exactly as you'd annotate the exam paper:

1 / 7

Root MAX: α = −∞, β = +∞. Descend left into N1 (MIN), window inherited.

MAX (square)MIN (circle)inspected leafprunedvalue flows to root

3.4 — SSS* solves → `A,C,D,E`

SSS* processes the most promising line first, proving values:

A solved with 24 → $N_1$ can do no worse than… wait, MIN wants low: B (34) is LIVE with bound 24 but 34 > 24 can't improve → B discarded.
$N_1$ solved at 24. Root's other child $N_2$ (bound ∞) is now the only hope for MAX.
C solved with 26 → $N_2 \le 26$ . M is LIVE with bound 26 (MAX needs to prove ≥ 26).
$P_1$ 's leaves: D solved (52 ≥ 26, proves its point), E solved (54, same).
$P_1 = 52 \ge 26$ ⟹ $M \ge 26$ proven — $P_2$ (F, G) is never expanded.

Solved horizon nodes: A, C, D, E ✓ — B was discarded, F and G were never needed.

SSS* processes the most promising line first, proving values top-down. Step through it:

1 / 6

Merit order → leftmost line first. A SOLVED with 24 → N1 ≤ 24.

MAX (square)MIN (circle)SOLVEDdiscarded / never expanded

Tricks & Tips for This Question Family

Answers: 3.1 A, C · 3.2 C,F,G · 3.3 F,G · 3.4 A,C,D,E