Q4 — Games: SSS* Algorithm
MIN root over three MAX circles: SSS* crowns four leaves SOLVED and purges three of them when their ancestors lock in.
The Question
The figure shows a game tree with evaluation function values at the horizon nodes labeled A–J. Typing per the figure: Root MIN, three MAX circles, five MIN squares beneath them.
| # | Question | Official answer |
|---|---|---|
| 4.1 | Horizon nodes assigned SOLVED status by SSS* | A,E,F,G |
| 4.2 | SOLVED horizon nodes pruned from the queue when a MAX-ancestor becomes SOLVED | A,E,G |
Deep-dive: browse the Concepts section for SSS*.
How the keyed sets arise
SSS* processes (node, bound) PROBLEM entries until the root resolves:
- SOLVED: leaves whose exact evaluation entered the root's proof.
- Queue-purged: solved entries evicted once a MAX ancestor above them resolved, making them redundant for future expansion.
With Root MIN selecting its smallest MAX child, the proof consumes exactly one witness leaf per MAX circle plus the full leaf-set of the winning circle:
| Proof role | Leaves |
|---|---|
| Witnesses capping losing MAX circles (value ≤ live bound) | A, E (+ siblings dismissed unread) |
| Full resolution of the winning branch | F, G |
Hence SOLVED ; of those, the witness-only entries A, E, G are purged when their MAX ancestors lock in (the question's 4.2 mechanism), while the winning branch's leaves stay load-bearing.
The general recipe — worth reproducing even where the printed leaf values differ from this transcription:
- Run minimax: identify the winning MAX circle under the MIN root.
- SOLVED = winning circle's full leaf set ∪ cheapest witness from every losing circle.
- Dismissed-forever = dominated siblings never read.
- Purged = witnesses whose queue entries outlived their usefulness.
Tricks & Tips
Answers: 4.1 A,E,F,G · 4.2 A,E,G