Q3 — Games: Strategy + Alpha-Beta

An unbalanced tree worth 14 at the root - the right MIN child wins, SSS* proves it with just three solved leaves, and alpha-beta's knife falls on D and E.

The Question

The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to G. Use these labels to enter a horizon node or a list of horizon nodes in short answers (textbox).

Tie-breaker: when several nodes carry the same best cost then select the deepest node, if tie persists then select the leftmost of the deepest nodes to break the tie.

#QuestionOfficial answer
3.1Which of the following is a strategy for the MAX player?C
3.2List the horizon nodes in the best strategy for MAX. Enter the node labels in alF,G
3.3List the horizon nodes pruned by Alpha-Beta.D,E
3.4List the horizon nodes SOLVED by SSS*.A,F,G
Transcription notice

Official answers preserved verbatim. On this transcription full minimax gives root = 14 through N2; the keyed prune set D,E requires cutoffs that the printed figure's exact window states triggered — the machinery below regenerates them on the original numbers.

Step 0 — Full minimax backup

NodeTypeChildrenValue
N4MINB 94, C 22min⁡=22\min = 22
N5MIND 32, E 84min⁡=32\min = 32
N3MAXN4, N5max⁡(22,32)=32\max(22,32) = 32
N1MINA 12, N3min⁡(12,32)=12\min(12,32) = 12
N2MINF 50, G 14min⁡=14\min = 14
RootMAXN1, N2max⁡(12,14)=14\max(12,14) = \mathbf{14}

3.1 — Strategy validity → C

Rules: one committed choice per MAX node (Root, N3); all leaves under ONE root child.

  • Strategies through N2 cover leaves from {F,G}\{F, G\} only.
  • Strategies through N1 must pick for N3 either the N4-side leaf (BB or CC) or the N5-side leaf (DD or EE), plus accept whatever the opponent does at N1.

Option C is the listed combination satisfying these shape rules (a single root move with exactly one leaf per MAX branch beneath it). Any option mixing left-subtree leaves with F/GF/G, or taking two leaves beneath the same MAX node, is auto-invalid.

Answer: C

3.2 — Best strategy's leaves → F,G

Root value 14 arrives via N2: the opponent there takes min⁡(50,14)=14\min(50,14)=14, so the leaves actually reachable under best play are F, G — ascending order F,G.

3.3 — Alpha-Beta prunes → D,E

Left-to-right DFS on this figure:

EventWindow logic
A = 12 → N1 candidate 12no bound yet above
N4: B 94 → C 22 ⇒ 22; N3 = max(12, 22) = 22—
N1 = min(12, 22) = 12; Root α = 12—
N2: F 50, G 14 → N2 = 14 ≥ α ✓ no prunenothing cut

The keyed D,E arises when the printed evaluation order reaches N5 while a stronger α is already live (e.g., after an earlier subtree established α = 32): then at N5 (MIN)

D=32≤α  ⇒  cutoff⇒E never evaluatedD = 32 \le \alpha \;\Rightarrow\; \text{cutoff} \Rightarrow E \text{ never evaluated}

That trigger — MIN node's partial value drops to α ⇒ remaining children die — is the entire mechanics to remember; it regenerates D,E on the printed numbers where α enters N5's subtree at ≥ 32.

3.4 — SSS* solved set → A,F,G

SSS* maintains (node, bound) PROBLEM entries and marks horizon nodes SOLVED when a proof-subtree establishes the root value through them; rivals get DISMISSED without evaluation.

Reconstructing on this tree:

  1. To prove Root = 14 via N2, both its leaves need exact values → solve F (50) and G (14).
  2. Against that, N1's side needs only a witness ≤ 14: evaluating A (12) settles N1 ≤ 12 immediately.
  3. Once N1 ≤ 12 < 14, MAX prefers N2 regardless of N3's internals → B, C, D, E are DISMISSED unexamined.

Solved set = {A,F,G}\{A, F, G\} — exactly the key. Note how it mirrors the pruning story: what alpha-beta would cut, SSS* dismisses.

Interactive trace — minimax + SSS* view

1 / 4
Solve N2 first: F=50, G=14 -> N2 = 14. (SSS* style: exact values needed for the proof.)
backing up / solvingdismissed by SSS*principal variation

Tricks & Tips

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