Q3 — Games: Strategy + Alpha-Beta

Game tree strategies and pruning

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.

#	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 alphabetical order	`G,I`
3.3	List the horizon nodes pruned by Alpha-Beta.	`C,E,F`
3.4	List the horizon nodes not processed (neither LIVE nor SOLVED) by SSS*.	`B,C,E,F`

The Topic in 60 Seconds

Backed-up values: MAX nodes take the max of children, MIN nodes the min. Static values: $N12 = \max(B,C)$ , $N1 = \min(A, N12)$ , root $= \max(N1, N2, N3)$ .
Alpha-Beta: pass $\alpha$ (best MAX guarantee so far) down; a MIN node cutoffs when its $\beta \le \alpha$ ; a MAX node cutoffs when its value $\ge \beta$ . Pruned leaves are never evaluated.
Strategy for MAX: a move at every MAX node reachable under that plan — root choice plus choices at any deeper MAX nodes. Value = the leaf reached when MIN answers optimally.
SSS*: best-first over strategies; a subtree whose parent MIN already holds a value $\le$ the incumbent can never beat it, so its unexpanded leaves are neither LIVE nor SOLVED.

Deep-dive: Minimax, Alpha-Beta, SSS*.

Backed-up values (needed everywhere)

Node	Computation	Value
N12 (MAX)	$\max(70, 80)$	80
N1 (MIN)	$\min(30, 80)$	30
N22 (MAX)	$\max(10, 90)$	90
N2 (MIN)	$\min(20, 90)$	20
N32 (MAX)	$\max(40, 50)$	50
N3 (MIN)	$\min(60, 50)$	50
Root (MAX)	$\max(30, 20, 50)$	50

3.1 — A strategy for MAX → `B`

A strategy is not a single move — it must name MAX's reply at every MAX node the play could reach: the root choice plus choices at N12 / N22 / N32 if that branch is entered. The winning plan is: go to MIN 3 at the root, and if play reaches N32, pick I (50 over 40) — guaranteed value 50 regardless of MIN's replies. Option B is the option describing exactly this complete plan ✓. Options naming a bare root move ("go to N1"), or plans that omit the second-level MAX choice, are not strategies at all — that is the discriminator being tested.

3.2 — Horizon nodes of the best strategy → `G,I`

Follow the principal variation with backed-up values:

Root picks the best MIN child: $\max(30, 20, 50) = 50$ → MIN 3.
At N3, MIN compares $G = 60$ against the N32 side $= \max(H{=}40, I{=}50) = 50$ → MIN plays toward N32.
At N32, MAX picks $I = 50$ over $H = 40$ .

The leaves the strategy realizes/tests along this line: G and I → G,I ✓ (already alphabetical).

3.3 — Alpha-Beta pruned horizon nodes → `C,E,F`

Left-to-right depth-first with $\alpha$ / $\beta$ :

Phase	State	Result
N1 starts ( $\alpha = -\infty$ , $\beta = +\infty$ )	evaluate A = 30	$\beta(\text{N1}) = 30$
N12 (MAX, $\beta = 30$ )	evaluate B = 70	value $\ge 70 > \beta = 30$ → cutoff: C pruned, N12 returns ≥ 70
N1 returns	$\min(30, \ge 70) = 30$	root $\alpha = 30$
N2 starts ( $\alpha = 30$ )	evaluate D = 20	$\beta(\text{N2}) = 20 \le \alpha = 30$ → cutoff: N22 never opened → E, F pruned
N3 starts ( $\alpha = 30$ )	evaluate G = 60	$\beta(\text{N3}) = 60$ , continue
N32 (MAX, $\alpha = 30$ , $\beta = 60$ )	evaluate H = 40, then I = 50	returns 50, no cutoff
N3 returns 50, root returns	$\max(30, 20, 50) = 50$	done

Pruned horizon nodes: C, E, F ✓ — C died to the $\beta$ -cutoff inside N12; E and F died wholesale with N22's $\beta \le \alpha$ cutoff.

3.4 — SSS* unprocessed horizon nodes → `B,C,E,F`

SSS* grows strategies best-first and dismisses any subtree that can no longer beat the incumbent:

Event	Why
Solve A = 30	leftmost strategy gives root a guaranteed 30
N12's leaves (B, C) never generated	N1 is a MIN holding 30 from A: $N1 = \min(30, \cdot) \le 30$ forever — no strategy through N1 can beat 30, so expanding N12 is pointless
Solve D = 20	any strategy through N2 is worth $\le 20 < 30$ → N2 dismissed
E, F never generated	killed with the N2 dismissal — same set alpha-beta pruned
Solve H = 40, I = 50, evaluate G = 60	N3 side is the only one that can raise the bound
N3 = 50 > 30 → root solved at 50	stop

Processed leaves: A, D, G, H, I. Not processed (neither LIVE nor SOLVED): B, C, E, F ✓.

Note the subtlety: alpha-beta did evaluate B (=70) to prove N12 ≥ 30; SSS* gets the same conclusion for free from N1's MIN property and skips B entirely.

Interactive trace — alpha-beta on this tree

1 / 8

Root MAX, children MIN 1..3. Horizon values: A30 B70 C80 D20 E10 F90 G60 H40 I50

being evaluatedpruned (never evaluated)value settledbest line (value 50)

Tricks & Tips

Answers: 3.1 B · 3.2 G,I · 3.3 C,E,F · 3.4 B,C,E,F

The Question

The Topic in 60 Seconds

Backed-up values (needed everywhere)

3.1 — A strategy for MAX → B

3.2 — Horizon nodes of the best strategy → G,I