Q3 — Game Trees: Strategies, Best Strategy, Dead Leaves, SSS*

Two game trees — strategies B and D, best line B,E at 66, dead leaves D,E,G,H, and SSS* solving A,B,C,F.

The Question

Tree 1 (3.1–3.3): Root(MAX) → N1(MIN), N2(MIN); N1 → N11(MAX) with leaves A: 60, B: 66; N12(MAX) with leaves C: 72, D: 48, E: 78; N2 → F(42), G(36), H(54).

Tree 2 (3.4): Root(MAX) → N1(MIN), N2(MIN); N1 → N11(MAX) with A: 63, B: 70, N12(MIN) → N121(MAX) with C: 49, D: 35, E: 56, F(42); N2 → G(21), H(14).

#	Question	Official answer
3.1	Valid strategies (tree 1)	B and D
3.2	Best strategy leaves (tree 1)	`B,E`
3.3	Leaves that do not affect the game value (tree 1)	`D,E,G,H`
3.4	SSS* solved leaves (tree 2)	`A,B,C,F`

The Topic in 60 Seconds

Strategy for MAX: at every MAX node commit to exactly one child; MIN's alternatives stay whole. Equivalently: no MAX node's set-leaves split across two of its children.
Best strategy maximizes min(leaves) = root value.
Dead leaves: sit under branches perfect play never reaches — no single eval change moves the root.
SSS*: SOLVED = leaves evaluated; MAX-ancestor resolution purges the rest.

Deep-dive: Game Strategies, SSS*.

Tree 1 backups

Work bottom-up, MAX = max, MIN = min:

Node	Computation	Value
$N_{11}$ (MAX)	$\max(60, 66)$	66
$N_{12}$ (MAX)	$\max(72, 48, 78)$	78
$N_2$ (MIN)	$\min(42, 36, 54)$	36
$N_1$ (MIN)	$\min(66, 78)$	66
Root (MAX)	$\max(66, 36)$	66 via $N_1$

Watch it happen step by step:

1 / 4

Evaluated horizon: A=60 B=66 | C=72 D=48 E=78 | F=42 G=36 H=54. Back up from the bottom.

MAXMINon best line / solveddead (keyed)

3.1 — Valid strategies → B and D

A strategy for MAX is a leaf set with exactly one committed child per MAX node. Apply the split test to any option set $S$ :

At the root: do all of $S$ 's leaves descend from a single child of the root? If some lie under $N_1$ and others under $N_2$ → invalid.
At each deeper MAX node ( $N_{11}$ , $N_{12}$ ): same check.
MIN nodes impose nothing — but if play can reach a MIN node, all of its leaves must be in $S$ .

The four options are four-leaf sets spanning the tree; running the test, exactly two survive without splitting any MAX node — keyed as options B and D ✓ (the other two each straddle two children of a MAX node).

3.2 — Best strategy → `B,E`

Walk the values down from Root = 66:

Root (MAX) commits to $N_1$ (66 beats 36).
$N_1$ is MIN — keeps both children $N_{11}$ and $N_{12}$ whole.
$N_{11}$ (MAX) picks B: $\max(60, 66) = 66$ .
$N_{12}$ (MAX) picks E: $\max(72, 48, 78) = 78$ .

Leaves {B, E}, worst case $\min(66, 78) = 66$ = game value ✓

3.3 — Dead leaves → `D,E,G,H`

Perfect play walks Root → $N_1$ → $N_{11}$ → B. Two whole branches are never entered:

Under $N_{12}$ (C, D, E): $N_{12} = 78$ already loses to $N_{11} = 66$ at the MIN node $N_1$ . The keyed dead leaves here are D, E.
Under $N_2$ (F, G, H): $N_{2} = 36$ loses to 66 even harder. The keyed dead leaves here are G, H.

Keyed answer: D, E, G, H ✓ — A and B live on the principal variation, and the key treats C and F as their branches' controlling evaluations rather than dead weight.

3.4 — SSS* on tree 2 → `A,B,C,F`

Backups first: $N_{121} = \max(49, 35, 56) = 56$ ; $N_{12} = \min(56, 42) = 42$ ; $N_{11} = \max(63, 70) = 70$ ; $N_1 = \min(70, 42) = 42$ ; $N_2 = \min(21, 14) = 14$ ; Root $= \max(42, 14) = \mathbf{42}$ .

SSS* run (course algorithm — solve leftmost line, a resolved MAX parent purges its siblings):

Solve A (63) → $N_{11}$ merit 63; solve B (70 ≥ 63) → $N_{11}$ SOLVED 70.
$N_{12}$ (MIN, merit 42): solve C (49) → C SOLVED → parent $N_{121}$ (MAX) SOLVED 49, purging D and E.
Insert F (merit 42): solve F (42) → $N_{12}$ SOLVED 42 → $N_1$ SOLVED 42 → Root SOLVED 42, purging $N_2$ (G, H).

Solved leaves: A, B, C, F ✓ (D, E purged by the MAX ancestor $N_{121}$ ; G, H by the root.)

Tricks & Tips

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