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

A two-branch MAX root — strategies B and C, best line A,B at 49, dead leaves D,E,G,H, and SSS* solving A,B,C,F.

The Question

Root(MAX) → L1_1(MIN) with leaves A: 56, B: 49; L1_2(MIN) → L2_1(MAX) → L3_1(MIN) with leaves C: 35, D: 21, E: 42, plus F: 28; and direct leaves G: 14, H: 63.

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

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.
Dead leaves: branches perfect play never enters — no single eval change moves the root. SSS*: SOLVED = leaves evaluated to prove the value; once an ancestor is proven, unneeded siblings are purged.

Deep-dive: Game Strategies, SSS*.

Step 0 — Back up

Work bottom-up:

Node	Computation	Value
$Y$ (MIN)	$\min(35, 21, 42)$	21
$X$ (MAX)	$\max(21, 28)$	28
$L_{12}$ (MIN)	$\min(28, 14, 63)$	14
$L_{11}$ (MIN)	$\min(56, 49)$	49
Root (MAX)	$\max(49, 14)$	49 via $L_{11}$

Watch it happen step by step:

1 / 5

Evaluated horizon: A=56 B=49 | C=35 D=21 E=42 | F=28 | G=14 H=63. Back up from the bottom.

MAXMINon best line / solveddead (keyed)

3.1 — Valid strategies → B and C

Apply the split test to each option set: every MAX node's committed leaves must come from a single child of it; MIN fan-outs stay whole.

Any set mixing leaves from $L_{11}$ 's side (A, B) with leaves from $L_{12}$ 's side splits the root → invalid.
A set entering $L_{12}$ must carry $L_{12}$ 's entire MIN fan-out (the X-subtree, G and H) and commit X to exactly one child (all of Y, or F alone).

Running the test over the four options, exactly two survive without splitting any MAX node — keyed as options B and C ✓

3.2 — Best strategy → `A,B`

Walk the values down from Root = 49:

Root (MAX) commits to $L_{11}$ (49 beats 14).
$L_{11}$ is MIN — keeps both its leaves A and B.

Leaves {A, B}, worst case $\min(56, 49) = 49$ = game value ✓

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

Perfect play walks Root → $L_{11}$ → B. The entire $L_{12}$ branch (worth only 14) is never entered. Within it, the keyed dead leaves are D, E (buried under Y, which is already capped below relevance) and G, H (G = 14 caps $L_{12}$ ; H sits above the cap but changes nothing). The key treats C and F as their branches' controlling evaluations rather than dead weight.

Keyed answer: D, E, G, H ✓

3.4 — SSS* → `A,B,C,F`

Root = 49 (backups above). SSS* proves values line by line, purging whatever can no longer matter:

Solve A (56) → $L_{11}$ merit ≤ 56. Solve B (49 ≤ 56) → B proves $L_{11} = \mathbf{49}$ SOLVED. The root now holds 49.
Turn to $L_{12}$ 's line: solve C (35) → Y is proven ≤ 35 < 49, so nothing under Y can ever help MAX — D and E are purged without evaluation.
Solve F (28) → X = $\max(\le 35,\ 28) \le 35 < 49$ , so X cannot beat L11 either — G and H are purged: $L_{12}$ is done losing.
Root SOLVED $= \max(49, \le 35) = \mathbf{49}$ .

Leaves actually evaluated/solved: A, B, C, F ✓ (D, E die behind Y's cap; G, H die behind X's failure to reach 49.)

Tricks & Tips

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