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

Three MIN branches under MAX — valid strategies A and C, best line D,E at 56, and six pruned leaves.

The Question

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

#	Question	Official answer
3.1	Valid strategies (A: A,C · B: A,D,G · C: G,J,K · D: D,E,F)	A and C
3.2	Best strategy leaves	`D,E`
3.3	Alpha-Beta pruned	`C,F,H,I,J,K`
3.4	SSS* solved	`A,D,E,G`

The Topic in 60 Seconds

Strategy for MAX: no MAX node's set-leaves split across two children; MIN's alternatives stay whole.
Best strategy maximizes min(leaves) = root value.
α-β: cutoff when α ≥ β. SSS*: solves leaves line-by-line.

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

Step 0 — Back up

$X_1 = \max(68, 30) = 68$ ; $M_1 = \min(48, 68) = 48$
$X_2 = \max(78, 22) = 78$ ; $M_2 = \min(56, 78) = 56$
$Y_3 = \min(42, 76) = 42$ ; $Z_3 = \min(88, 98) = 88$ ; $X_3 = \max(42, 88) = 88$ ; $M_3 = \min(20, 88) = 20$
$\text{Root} = \max(48, 56, 20) = \mathbf{56}$ via $M_2$

3.1 — Valid strategies → A (A,C) and C (G,J,K)

A strategy must commit to ONE child at every MAX node; MIN nodes contribute all their children.

Option	Check	Verdict
A: A,C	Root→ $M_1$ ✓; $M_1$ (MIN) keeps both children: A and $X_1$ ; $X_1$ (MAX) commits to C only ✓	Valid
B: A,D,G	Root (MAX) would need $M_1$ , $M_2$ and $M_3$ — split!	Invalid
C: G,J,K	Root→ $M_3$ ✓; $M_3$ keeps G, $X_3$ ; $X_3$ commits to $Z_3$ (dropping $Y_3$ : no H, I); $Z_3$ keeps J, K ✓	Valid
D: D,E,F	Root→ $M_2$ ✓; $M_2$ keeps D, $X_2$ ; but E and F are the two children of MAX node $X_2$ — it can't take both. Split!	Invalid

Note the trap in option D: unlike the FN-24t1 tree, here E and F hang directly off a MAX node, so {D,E,F} is impossible while {D,E} would have been fine.

3.2 — Best strategy → `D,E`

Root → $M_2$ (56). $M_2$ keeps D and $X_2$ ; $X_2$ picks E (78 beats 22). Leaves {D, E}, guarantee min(56, 78) = 56 = game value ✓

3.3 — Alpha-Beta prunes → `C,F,H,I,J,K`

Node	Window	Happening
$M_1$ (MIN)	$(-\infty, \infty)$	A = 48 → β = 48
$X_1$ (MAX)	$(-\infty, 48)$	B = 68 ≥ 48 → β-cutoff — C pruned!
Root	α = 48
$M_2$ (MIN)	$(48, \infty)$	D = 56 → β = 56
$X_2$ (MAX)	$(48, 56)$	E = 78 ≥ 56 → β-cutoff — F pruned!
Root	α = 56
$M_3$ (MIN)	$(56, \infty)$	G = 20 ≤ 56 → α-cutoff — $X_3$ (H, I, J, K) pruned!

Pruned: C, F, H, I, J, K ✓ — only A, B, D, E, G inspected.

1 / 5

M1 (MIN): A = 48 -> beta = 48.

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

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

A solved (48) → $M_1 \le 48$ ; $X_1$ live merit 48: B solved (68 ≥ 48) → $X_1$ proven → C never expanded. $M_1$ solved 48.
$M_2$ line (∞): D solved (56) → $X_2$ live merit 56: E solved (78 ≥ 56) → $X_2$ proven → F never expanded. $M_2$ solved 56.
$M_3$ line (merit 56): G solved (20 ≤ 56) → $M_3 = 20$ ; $X_3$ (H, I, J, K) never needed.
Root = 56. Solved: A, D, E, G ✓ (the paper also accepted A,D,G,E — same set, different order.)

Tricks & Tips

Answers: 3.1 A, C · 3.2 D,E · 3.3 C,F,H,I,J,K · 3.4 A,D,E,G