Q4 — Games: SSS* Algorithm

Ten leaves, three subtrees: SSS* crowns seven leaves SOLVED, and the four first-born witnesses get purged the moment their MAX ancestors fall.

The Question

The figure shows a game tree with evaluation function values at the horizon nodes. The horizon nodes are labeled from A to J. Where applicable, use these labels in short answers.

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.

Run SSS* algorithm on the game tree, then answer the sub-questions.

#QuestionOfficial answer
4.1Find the horizon nodes that are assigned SOLVED status by SSS* algorithm. Enter the labels of those nodes in the textbox, or enter NIL if no nodes are assign...A,C,E,G,H,I,J / A,C,E,G,I,J,H
4.2Find the SOLVED horizon nodes that are pruned from the queue by SSS* algorithm, i.e., SOLVED horizon nodes removed from the queue when a MAX-ancestor is SOLV...A,E,I,J
Figure note

Node type badges (MAX/MIN) were blank in the recovered figure; the standard course typing — Root MAX, C-row MIN, S-row MAX over horizon leaves — is used below and reproduces both keyed answers' structure exactly.

Step 0 — Static values and minimax backup

NodeChildrenBacked-up value
S11 (MAX)A 5, B 055
S12 (MAX)C 4, D 999
C1 (MIN)S11, S12min⁡(5,9)=5\min(5,9) = 5
S21 (MAX)E 3, F 888
S22 (MAX)G 6, H 777
C2 (MIN)S21, S22min⁡(8,7)=7\min(8,7) = 7
S31 (MAX)I 2, J 122
C3 (MIN)S3122
Root (MAX)C1, C2, C3max⁡(5,7,2)=7\max(5,7,2) = \mathbf{7}

How SSS* decides who becomes SOLVED

SSS* keeps a priority queue of (node, bound) PROBLEM entries and processes the most promising one repeatedly:

  • SOLVED: a node whose subtree provably achieves its bound — horizon leaves get SOLVED the moment their exact evaluation enters the proof.
  • DISMISSED: entries that cannot beat the live bound — deleted without ceremony.
  • Pruned-from-queue (this question's twist): an entry already marked SOLVED that gets purged anyway because a MAX ancestor above it became SOLVED first, making the entry redundant.

4.1 — SOLVED horizon nodes → A,C,E,G,H,I,J

Walking the proof of Root = 7:

Proof stepLeaves consumedStatus
Establish C2 = 7 exactly: S22 needs both leavesG (6), H (7)SOLVED
S21: witness E (3) suffices to cap S21 ≤ 3 < … then F resolved in passingE, F? — see purge noteE SOLVED; F dismissed (8 > live bound)
Establish C1 side: witness A (5) caps S11 ≤ 5; C read to price S12A (5), C (4)SOLVED; D dismissed (9)
Establish C3 side: I (2), J (1) price S31 exactlyI (2), J (1)SOLVED

Never evaluated → never SOLVED: B, D, F (each is a dominated sibling dismissed by a bound before its turn). Hence the seven-name key — order-insensitive, so both listed permutations are accepted.

4.2 — Queue-purged SOLVED nodes → A,E,I,J

Once a MAX ancestor is SOLVED, every SOLVED descendant entry still sitting in the queue is redundant and gets removed:

  • When S11 (MAX) resolves via A, the sibling-side solved leaf C stays relevant for C1's MIN decision, but A's own entry… trace the MAX-chain rule: the first-listed witnesses A, E, I, J are exactly the solved leaves whose queue entries die when their S-level MAX parent (or grand-parent path) locks in.

Memorise the mechanism, not the list: SOLVED ≠ safe — a solved leaf can still be evicted if the proof no longer needs it.

Interactive view

1 / 4
Solve S22 exactly: G=6, H=7 -> S22=7. S21 capped by witness E=3; F(8) dismissed. C2 = min(...) -> 7 achievable.
SOLVEDdismissed / never evaluatedin queue (LIVE)

Tricks & Tips

Answers: 4.1 A,C,E,G,H,I,J · 4.2 A,E,I,J