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

A three-branch MAX root with nested MAX/MIN pairs — strategies A and C, best line D,E, and five pruned leaves.

The Question

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

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

The Topic in 60 Seconds

Strategy for MAX: no MAX node's set-leaves may split across two of its children; MIN's alternatives stay whole.
Best strategy maximizes $\min(\text{leaves})$ = root minimax value.
α-β: cutoff when $\alpha \ge \beta$ . SSS*: solves leaves line-by-line; unneeded leaves are discarded or pruned.

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

Step 0 — Back up

$X_1 = \max(98, 70) = 98$ ; $M_1 = \min(18, 98) = 18$
$Y_2 = \min(92, 62) = 62$ ; $X_2 = \max(80, 62) = 80$ ; $M_2 = \min(54, 80) = 54$
$X_3 = \max(50, 74) = 74$ ; $M_3 = \min(32, 74) = 32$
$\text{Root} = \max(18, 54, 32) = \mathbf{54}$ via $M_2$

3.1 — Valid strategies → A (A,C) and C (D,F,G)

Option	Check	Verdict
A: A,C	Root→ $M_1$ ✓; $M_1$ keeps A and $X_1$ ; $X_1$ → C only ✓	Valid
B: A,D,H	Root: A via $M_1$ , D,H via $M_2$ — split!	Invalid
C: D,F,G	Root→ $M_2$ ✓; $M_2$ keeps D, $X_2$ ; $X_2$ → $Y_2$ only; $Y_2$ keeps F,G ✓	Valid
D: E,I,J	Root: E via $M_2$ , I,J via $M_3$ — split!	Invalid

3.2 — Best strategy → `D,E`

Root → $M_2$ (54). $M_2$ keeps D and $X_2$ ; $X_2$ picks E (80 beats 62); leaves {D, E}, guarantee $\min(54, 80) = 54$ = game value ✓

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

Node	Window	Happening
$M_1$ (MIN)	$(-\infty, \infty)$	A = 18 → $\beta = 18$
$X_1$ (MAX)	$(-\infty, 18)$	B = 98 ≥ 18 → β-cutoff — C pruned!
Root	$\alpha = 18$
$M_2$ (MIN)	$(18, \infty)$	D = 54 → $\beta = 54$
$X_2$ (MAX)	$(18, 54)$	E = 80 ≥ 54 → β-cutoff — F, G pruned!
Root	$\alpha = 54$
$M_3$ (MIN)	$(54, \infty)$	H = 32 ≤ 54 → α-cutoff — I, J pruned!

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

1 / 5

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

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

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

A solved (18) → $M_1 \le 18$ . $X_1$ live merit 18: solve B (98 ≥ 18) → $X_1$ proven ≥ 18 → C never expanded. $M_1$ solved 18.
$M_2$ line (∞): D solved (54) → $M_2 \le 54$ ; $X_2$ live merit 54: E solved (80 ≥ 54) → $X_2$ proven → F, G never expanded. $M_2$ solved 54.
$M_3$ line (merit 54): H solved (32 ≤ 54) → $M_3 = 32$ ; $X_3$ (I, J) never needed.
Root = 54. Solved leaves: A, D, E, H ✓ — B was evaluated but discarded (98 can't improve 18), the rest pruned.

The pattern

Every MIN node's first leaf is low (18, 54, 32) — each one is a scissors: β-cutoff inside its own MAX child, α-cutoff across its siblings. α-β and SSS* end up inspecting the same five leaves; only B is evaluated-but-discarded by SSS*.

Tricks & Tips

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