Q3 — Games: Strategy + Alpha-Beta
Three MIN children at the root: alpha-beta with running bounds kills C,E,F,I, and SSS* dismisses exactly the same five without a glance.
The Question
The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to I. 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.
Based on the above data, answer the given subquestions.
| # | Question | Official answer |
|---|---|---|
| 3.1 | Which of the following is a strategy for the MAX player? | B |
| 3.2 | List the horizon nodes in the best strategy for MAX. Enter the node labels in al | G,H |
| 3.3 | List the horizon nodes pruned by Alpha-Beta. | C,E,F,I |
| 3.4 | List the horizon nodes not processed (neither LIVE nor SOLVED) by SSS*. | B,C,E,F,I |
The Topic in 60 Seconds
Root has THREE MIN children; MAX picks the largest. With the course's aggressive bound-passing (a node's running value is passed to its children as their second window bound), cutoffs fire early and often.
Deep-dive: browse the Concepts section for Games, Alpha-Beta, SSS*.
Step 0 — Full minimax backup
| Node | Children | Value |
|---|---|---|
| X1 (MAX) | B 80, C 60 | |
| M1 (MIN) | A 40, X1 | |
| X2 (MAX) | E 10, F 90 | |
| M2 (MIN) | D 30, X2 | |
| X3 (MAX) | H 70, I 50 | |
| M3 (MIN) | G 60, X3 | |
| R (MAX) | M1, M2, M3 |
3.1 — Strategy → B
A strategy = one choice per MAX node (R, X1, X2, X3), leaves all under ONE root child. Option B is the listed set meeting the shape rules — e.g., committing R→M3 with one leaf per branch beneath. Options mixing leaves across different M-children are auto-invalid.
Answer: B
3.2 — Best strategy's leaves → G,H
Root value 60 flows through M3: opponent takes , touching exactly G, H.
Answer: G,H
3.3 — Alpha-Beta prunes → C,E,F,I
Left-to-right DFS passing RUNNING bounds down:
| Event | Window logic | Cut |
|---|---|---|
| M1: A = 40 → M1 running min 40 | X1 called with β = 40 | |
| X1: B = 80 ≥ β=40 → MAX cutoff | C never read | C |
| X1 returns 80 → M1 = 40; Root α = 40 | M2 window α=40 | |
| M2: D = 30 ≤ α=40 → MIN cutoff | X2 never opened | E, F |
| M2 returns 30; Root α stays 40 | M3 window α=40 | |
| M3: G = 60 > 40 continue; running min 60 | X3 called with β = 60 | |
| X3: H = 70 ≥ β=60 → MAX cutoff | I never read | I |
| M3 = min(60, 70) = 60 → Root = 60 ✓ |
Pruned horizon nodes in order: C, E, F, I — exact key. Same root value as full minimax, four leaves saved.
3.4 — SSS*: not processed → B,C,E,F,I
SSS* resolves (node, bound) PROBLEM entries until the root is SOLVED:
- Establish M3 = 60 exactly: solve G (60), solve H (70) ⇒ M3 = 60.
- M1 side needs only a witness < 60: solve A (40) ⇒ M1 ≤ 40; X1's subtree becomes irrelevant.
- M2 side likewise: solve D (30) ⇒ M2 ≤ 30; E, F dismissed.
Processed/solved horizon nodes: A, D, G, H. Never processed (neither LIVE nor SOLVED): B, C, E, F, I — the exact key, mirroring alpha-beta's prune set plus B (which αβ evaluated but SSS*'s proof never needed).
Interactive trace
Tricks & Tips
Answers: 3.1 B · 3.2 G,H · 3.3 C,E,F,I · 3.4 B,C,E,F,I