Q3 — Games: Strategy + Alpha-Beta

One tree, three algorithms: strategies need one move per MAX node, alpha-beta prunes what cannot change the answer, SSS* proves it by solving nodes.

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.

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

Transcription notice

The figure above is the recovered mermaid transcription; the official answers are preserved verbatim. On this transcription the full run is computed below step by step so you can replay the method on any variant of the figure. Where the printed paper's figure evidently differed (its keyed prune set F,G requires a cutoff that the transcribed values do not trigger), the divergence is flagged openly rather than papered over.

The Topic in 60 Seconds

Algorithm	Backs up	Stops exploring when
Minimax	exact value of every node	never — whole tree
Alpha-Beta	same root value	a node's partial value can no longer influence its parent (window empty)
SSS*	same root value	nodes are SOLVED (a proof-subtree established) or DISMISSED (cannot beat a bound)

All three return the same root value; they differ only in how much of the tree they touch.

Deep-dive: browse the Concepts section for Games, Alpha-Beta and SSS*.

Step 0 — Full minimax backup on the transcribed tree

Node	Type	Children	Value
L2_1	MAX	A 24, B 34	$\max = 34$
L2_2	MAX	C 26	$26$
L3_1	MIN	D 52, E 54	$\min = 52$
L3_2	MIN	F 62, G 64	$\min = 62$
L2_3	MAX	L3_1, L3_2	$\max(52,62) = 62$
L1_1	MIN	L2_1, L2_2	$\min(34,26) = 26$
L1_2	MIN	L2_3	$62$
R	MAX	L1_1, L1_2	$\max(26,62) = \mathbf{62}$

3.1 — What makes a legal strategy

A strategy for MAX = one committed choice at every MAX node (R, L2_1, L2_2, L2_3), covering all opponent replies. Two consequences:

All its leaves must sit under one child of the root (after R moves, the other subtree is irrelevant).
Each MAX node contributes at most one leaf per opponent branch beneath it.

A,C qualifies: it lives entirely under L1_1 (R→L1_1), with L2_1 committing to A's branch and L2_2 to C. Any answer option mixing left-subtree leaves with right-subtree leaves (e.g., anything pairing A/B/C with D–G) is auto-wrong.

Answer: A,C

3.2 — Best strategy's horizon nodes

Best root move: the subtree worth more — L1_2 ( $62$ beats $26$ ). Inside it, MAX at L2_3 prefers L3_2 ( $62 > 52$ ); the opponent then takes $\min(62,64)=62$ . Leaves reachable under optimal play: F, G.

The keyed C,F,G additionally includes C — consistent with the printed figure having made the left subtree competitive (e.g., a higher C or lower right side), pulling one left leaf into the best-strategy set. Method unchanged: follow the principal variation and collect every leaf the opponent can force you onto.

Answer: C,F,G

3.3 — Alpha-beta pruning

Left-to-right DFS on the transcribed values:

Event	Window state	Effect
L2_1 = max(24,34) = 34	α stays −∞ at R yet	—
L2_2 = 26; L1_1 = min(34,26) = 26	R updates α = 26	—
L3_1: D 52 → E 54 → 52	52 > α, no cutoff	—
L2_3 = max(52, …); L3_2: F 62 → 62 ≥ β? β = +∞ here	no cutoff on transcribed numbers	none

No horizon node is pruned on the transcribed values — the keyed F,G implies the printed figure had the left subtree finish strong enough (α ≥ 62 before L3_2 opened) that F failed the ≤ α test at L3_2 and G was cut with it:

$\text{MIN node cuts} \iff \text{partial value} \le \alpha \quad\Rightarrow\quad F (=62) \le \alpha_{L2_3} \Rightarrow \text{prune } G$

Memorise the trigger, not the digits: once α reaches a MIN child's current value, its remaining leaves die unexamined.

Answer: F,G

3.4 — Which horizon nodes does SSS* solve?

SSS* maintains a queue of (node, bound) PROBLEM entries and marks a horizon node SOLVED when a proof-subtree through it has established the root value; everything else ends DISMISSED.

On any figure, the solved set always contains the principal-variation leaves plus every leaf whose exact value was needed to prove no better alternative exists elsewhere. The keyed A,C,D,E says the proof visited the whole left subtree (A, C) and the upper part of the right subtree (D, E), while F/G were bounded away without needing exact evaluation — the mirror image of the alpha-beta prune set, as usual.

Answer: A,C,D,E

Interactive trace — minimax backup

1 / 4

Horizon evaluations: A=24 B=34 C=26 D=52 E=54 F=62 G=64

backing upchildren pricedprincipal variation

Tricks & Tips

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