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

A three-branch MAX root with nested MIN choices — valid strategies, the 56-value best line, and two pruning stories that agree.

The Question

Squares = MAX, circles = MIN. Leaves A–K. Tie-breaker: deepest, then leftmost.

#	Question	Official answer
3.1	Valid strategies for MAX (A: I,K · B: E,F,G · C: E,F · D: I,J,K)	A and C
3.2	Leaves in MAX's best strategy	`A,C,D`
3.3	Leaves inspected by Alpha-Beta	`A,B,E,I`
3.4	Leaves SOLVED by SSS*	`A,B,E,I`

The Topic in 60 Seconds

Backups: MAX takes max, MIN takes min.
Strategy for MAX: at every MAX node the set-leaves must descend from one single child; MIN's alternatives all stay in the set.
Best strategy = valid set maximizing $\min(\text{leaf evals})$ ; its guarantee equals the root's minimax value.
Alpha-Beta: prune the moment $\alpha \ge \beta$ (β-cutoff at MAX, α-cutoff at MIN).
SSS*: proves values line-by-line; unneeded leaves are never expanded.

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

Step 0 — Back up the tree

$Y_1 = \min(77, 70) = 70$ ; $\quad Y_2 = \min(42, 14) = 14$
$X_1 = \max(56, 70) = 70$ ; $\quad X_2 = \max(84, 14) = 84$ ; $\quad X_3 = \max(28, 21) = 28$
$M_1 = \min(56, 70) = 56$ ; $\quad M_2 = \min(49, 84) = 49$ ; $\quad M_3 = \min(35, 28) = 28$
$\text{Root} = \max(56, 49, 28) = \mathbf{56}$ via $M_1$

3.1 — Valid strategies → A (I,K) and C (E,F)

Option	Split test at MAX nodes	Verdict
A: I,K	Root: all via $M_3$ ✓. $X_3$ : K via one child ✓. $M_3$ keeps I and the $X_3$ branch ✓	Valid
B: E,F,G	$X_2$ has F (direct) and G (via $Y_2$ ) — split!	Invalid
C: E,F	Root: via $M_2$ ✓. $X_2$ → F only ✓	Valid
D: I,J,K	$X_3$ has both J and K as children — split!	Invalid

3.2 — Best strategy → `A,C,D`

Root commits to $M_1$ (56). $M_1$ (MIN) keeps all: A and the $X_1$ subtree. $X_1$ (MAX) picks $Y_1$ (70 beats 63). $Y_1$ (MIN) keeps C and D.

Horizon set: A, C, D — guarantee $\min(56, 77, 70) = 56$ = game value ✓

3.3 — Alpha-Beta inspects → `A,B,E,I`

Node	Window	Happening
$M_1$ (MIN)	$(-\infty, +\infty)$	A = 56 → $\beta = 56$
$X_1$ (MAX)	$(-\infty, 56)$	B = 63 ≥ 56 → β-cutoff — $Y_1$ (C, D) pruned!
Root	$\alpha = 56$
$M_2$ (MIN)	$(56, +\infty)$	E = 49 ≤ 56 → α-cutoff — $X_2$ (F, G, H) pruned
$M_3$ (MIN)	$(56, +\infty)$	I = 35 ≤ 56 → α-cutoff — $X_3$ (J, K) pruned

Inspected: A, B, E, I ✓ (only 4 of 11 leaves!). Pruned: C, D, F, G, H, J, K.

3.4 — SSS* solves → `A,B,E,I`

A solved (56) → $M_1 \le 56$ .
$X_1$ live with bound 56 → solve B (63 ≥ 56 ✓) → $X_1$ proven ≥ 56 → $Y_1$ (C, D) never expanded.
$M_1$ solved = 56. $M_2$ : solve E (49 < 56) → $M_2 = 49$ . $M_3$ : solve I (35) → $M_3 = 35$ .
Root = 56.

Solved leaves: A, B, E, I ✓ — identical to α-β's inspected set here.

Interactive α-β trace (the cutoffs are the whole story):

1 / 4

Root MAX (−∞,+∞) → M1 (MIN). A = 56 → β(M1) = 56.

MAX (square)MIN (circle)inspected / value pathpruned

Why SSS* matches α-β here

SSS* proves A (56) → M1 ≤ 56; then B (63 ≥ 56) proves X1 without touching Y1 — the same cutoff α-β found. Then E and I solve M2, M3 cheaply. Solved = A, B, E, I — identical to the inspected set.

Tricks & Tips

Answers: 3.1 A, C · 3.2 A,C,D · 3.3 A,B,E,I · 3.4 A,B,E,I