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

A deep MIN-heavy tree — strategies A and C, best line I,J at 56, and six pruned leaves.

The Question

Root = MAX; circles = MIN, squares = MAX. Leaves A–K.

#QuestionOfficial answer
3.1Valid strategies (A: A,B · B: A,D,I · C: D,G,H · D: C,H,K)A and C
3.2Best strategy leavesI,J
3.3Alpha-Beta prunedC,E,F,G,H,K
3.4SSS* solvedA,D,I,J

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

  • N1=max⁡(68,30)=68N_1 = \max(68, 30) = 68; L1=min⁡(48,68)=48L_1 = \min(48, 68) = 48
  • N3=min⁡(42,76)=42N_3 = \min(42, 76) = 42; N4=min⁡(88,98)=88N_4 = \min(88, 98) = 88; N2=max⁡(42,88)=88N_2 = \max(42, 88) = 88; L2=min⁡(20,88)=20L_2 = \min(20, 88) = 20
  • N5=max⁡(78,22)=78N_5 = \max(78, 22) = 78; L3=min⁡(56,78)=56L_3 = \min(56, 78) = 56
  • Root=max⁡(48,20,56)=56\text{Root} = \max(48, 20, 56) = \mathbf{56} via L3L_3

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

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

OptionCheckVerdict
A: A,BRoot→L1L_1 ✓; L1L_1 (MIN) keeps both children: A and N1N_1; N1N_1 (MAX) commits to B only ✓Valid
B: A,D,IRoot (MAX) would need L1L_1, L2L_2 and L3L_3 — split!Invalid
C: D,G,HRoot→L2L_2 ✓; L2L_2 keeps D, N2N_2; N2N_2 commits to N4N_4 only (dropping N3N_3: no E, F); N4N_4 keeps G, H ✓Valid
D: C,H,KC lives under L1L_1, H under L2L_2, K under L3L_3 — root split!Invalid

3.2 — Best strategy → I,J

Root → L3L_3 (56). L3L_3 keeps I and N5N_5; N5N_5 picks J (78 beats 22). Leaves {I, J}, guarantee min(56, 78) = 56 = game value ✓

3.3 — Alpha-Beta prunes → C,E,F,G,H,K

NodeWindowHappening
L1L_1 (MIN)(−∞,∞)(-\infty, \infty)A = 48 → β = 48
N1N_1 (MAX)(−∞,48)(-\infty, 48)B = 68 ≥ 48 → β-cutoff — C pruned!
Rootα = 48
L2L_2 (MIN)(48,∞)(48, \infty)D = 20 ≤ 48 → α-cutoff — N2N_2 (E,F,G,H) pruned!
Rootα = 48
L3L_3 (MIN)(48,∞)(48, \infty)I = 56 → β = 56
N5N_5 (MAX)(48,56)(48, 56)J = 78 ≥ 56 → β-cutoff — K pruned!

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

1 / 5
L1 (MIN): A = 48 -> beta = 48.
MAX (square)MIN (circle)inspected / value pathpruned

3.4 — SSS* solves → A,D,I,J

  1. A solved (48) → L1≤48L_1 \le 48; N1N_1 live merit 48: B solved (68 ≥ 48) → N1N_1 proven → C pruned; B discarded (can't improve 48). L1L_1 solved 48.
  2. L2L_2 line (∞): D solved (20 ≤ 48) → L2L_2 solved 20; N2N_2 (E–H) pruned (merit 20).
  3. L3L_3 line: I solved (56) → N5N_5 live merit 56: J solved (78 ≥ 56) → N5N_5 proven → K pruned. L3L_3 solved 56.
  4. Root = 56. Solved: A, D, I, J ✓

Tricks & Tips

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