Q3 — SSS* on a Deep Narrow Tree
A single MIN child under the root means SSS* walks the whole tree — every leaf gets SOLVED, nothing is pruned.
The Question
Squares = MAX, circles = MIN. Horizon nodes A–D. Tie-breaker: deepest, then leftmost.
| # | Question | Official answer |
|---|---|---|
| 3.1 | Horizon nodes assigned SOLVED | A,B,C,D |
| 3.2 | Horizon nodes pruned (removed from queue by a MAX-ancestor) | NIL |
The Topic in 60 Seconds
The course's SSS* loop: process the highest-merit node —
- LIVE leaf → mark SOLVED with its eval.
- LIVE MAX → insert all children; LIVE MIN → insert first child only.
- SOLVED node: MAX parent → parent SOLVED once all its children are solved (purge any leftover siblings from OPEN); MIN parent → update merit and insert the next sibling.
Deep-dive: SSS*, Game Strategies.
The trace — everyone gets solved
Backups first (MIN circles take minima, MAX squares take maxima):
| Step | Processed | Effect |
|---|---|---|
| 1 | Root (LIVE MAX, ∞) | insert N (∞). OPEN = { N(∞) } |
| 2 | N (LIVE MIN, ∞) | insert first child SQ1 (∞). OPEN = { SQ1(∞) } |
| 3 | SQ1 (LIVE MAX, ∞) | insert all children → C1 (∞). OPEN = { C1(∞) } |
| 4 | C1 (LIVE MIN, ∞) | insert first child A (∞). OPEN = { A(∞) } |
| 5 | A (leaf) | A SOLVED = 11 |
| 6 | A SOLVED → C1 (MIN parent) | merit ← min(∞, 11) = 11; insert next sibling B (LIVE, 11). OPEN = { B(11) } |
| 7 | B (leaf, merit 11 — highest in OPEN) | B SOLVED = 70 |
| 8 | B SOLVED → C1 (MIN) | both children solved → C₁ SOLVED = min(11, 70) = 11 |
| 9 | C1 SOLVED → SQ1 (MAX) | only child → SQ₁ SOLVED = 11, nothing to purge |
| 10 | SQ1 SOLVED → N (MIN) | merit ← 11; insert next child SQ2 (LIVE, 11). OPEN = { SQ2(11) } |
| 11 | SQ2 (LIVE MAX, 11) | insert all children → C2 (LIVE, 11) |
| 12 | C2 (LIVE MIN, 11) | insert first child C (LIVE, 11) |
| 13 | C (leaf) | C SOLVED = 48 |
| 14 | C SOLVED → C2 (MIN) | merit stays 11; insert sibling D (LIVE, 11) |
| 15 | D (leaf, 11) | D SOLVED = 54 |
| 16 | D SOLVED → C2 (MIN) | both solved → C₂ SOLVED = min(48, 54) = 48 |
| 17 | C2 SOLVED → SQ2 (MAX) | only child → SQ₂ SOLVED = 48 |
| 18 | SQ2 SOLVED → N (MIN) | both children solved → N SOLVED = min(11, 48) = 11 |
| 19 | N SOLVED → Root (MAX) | only child → Root SOLVED = 11. Done |
The key structural fact: N and both SQ nodes are only children, so SSS* simply walks the chain — left line first (A at step 5, B at step 7), across to the right line once N demands its second subtree (steps 10–15), then back up. Nothing is ever pruned because no MAX node ever has a second branch sitting in OPEN when it resolves. Every leaf is assigned SOLVED: A, B, C, D ✓
Interactive trace — watch the queue walk the chain (squares = MAX, circles = MIN):
3.2 — Pruned → NIL
A MAX-ancestor purge happens when a MAX node is solved while siblings still sit in OPEN. Here: SQ1 and SQ2 are only children; N is an only child. Nobody gets purged → NIL ✓
The tree is a single chain of only-children — there are no alternative branches for a MAX node to discard. Compare with the FN paper's version of this question, where the root has two MIN children and the cheap left line lets MAX purge the other side.
Tricks & Tips
Answers: 3.1 A,B,C,D · 3.2 NIL