Q7 — GAMES

Minimax backs up 59 through the left subtree while alpha-beta silently kills G, H, J, L and all of M, N, O, P without reading them.

The Question

The figure shows a 4-ply game tree with evaluation function values at the horizon. The nodes in the horizon are assigned labels A, B, C, ..., P. Use these labels when asked to enter a horizon node or a list of horizon nodes.

Tie-breaker: when several nodes qualify then select the left most node, if tie persists then select the deepest node among the left most nodes.

#	Question	Official answer
7.1	Which of the following are strategies for MAX?	A, B
7.2	List the horizon nodes in the best strategy for MAX. Enter the nodes in the ascending order of node labels.	`C,D,E,F`
7.3	List the first five horizon nodes pruned by Alpha-Beta.	`G,H,J,L,M`

The Topic in 60 Seconds

Layer	Nodes	Rule
Ply 3 (horizon parents)	$L3_1 \dots L3_8$	MIN takes the smaller child value
Ply 2	$L2_1 \dots L2_4$	MAX takes the larger child value
Ply 1	$L1_1, L1_2$	MIN takes the smaller child value
Root	MAX	takes the larger child value

Alpha-Beta = minimax plus two windows: $\alpha$ (best MAX can already force) and $\beta$ (best MIN can already force). Prune the moment $\beta \le \alpha$ at a node — remaining children there can never influence the root decision.

Deep-dive: browse the Concepts section for minimax and alpha-beta.

Solutions

Static minimax values (bottom-up)

Node	Type	Computation	Value
$L3_1$	MIN	$\min(45, 82)$	45
$L3_2$	MIN	$\min(81, 59)$	59
$L3_3$	MIN	$\min(99, 99)$	99
$L3_4$	MIN	$\min(30, 57)$	30
$L3_5$	MIN	$\min(37, 54)$	37
$L3_6$	MIN	$\min(55, 93)$	55
$L3_7$	MIN	$\min(76, 34)$	34
$L3_8$	MIN	$\min(43, 87)$	43
$L2_1$	MAX	$\max(45, 59)$	59
$L2_2$	MAX	$\max(99, 30)$	99
$L2_3$	MAX	$\max(37, 55)$	55
$L2_4$	MAX	$\max(34, 43)$	43
$L1_1$	MIN	$\min(59, 99)$	59
$L1_2$	MIN	$\min(55, 43)$	43
Root	MAX	$\max(59, 43)$	59

7.1 — Which of the following are strategies for MAX?

A strategy must commit to ONE child at the root and cover both of MAX's later choices with complete sibling pairs:

Option	Leaves	Spans root child	Verdict
A — A,B,E,F	both pairs of $L1_1$ ( $L3_1$ , $L3_3$ )	left only ( $L1_1$ )	Valid strategy, guarantees $\min(45, 99) = 45$
B — C,D,G,H	both pairs of $L1_1$ ( $L3_2$ , $L3_4$ )	left only ( $L1_1$ )	Valid strategy, guarantees $\min(59, 30) = 30$
C — A,C,I,J	A,C both sit under $L2_1$ (MAX cannot take both), I,J under $L1_2$	both sides	Invalid — MAX would need to choose left AND right at the root
D — B,D,J,L	B,D both under $L2_1$ ; J,L both under $L2_3$	both sides	Invalid for the same reason

Answer: A, B

7.2 — Horizon nodes of the BEST strategy → C,D,E,F

Enumerate the four legal left-subtree strategies: $\{A,B\}$ + $\{E,F\}$ gives 45, $\{A,B\}$ + $\{G,H\}$ gives $\min(45,30)=30$ , $\{C,D\}$ + $\{E,F\}$ gives $\min(59,99)=59$ , $\{C,D\}$ + $\{G,H\}$ gives 30. No right-subtree strategy beats 43 ( $L1_2 = 43 < 59$ ). Best guarantee = 59 via $L2_1 \to L3_2$ (leaves C, D) and $L2_2 \to L3_3$ (leaves E, F):

$\text{value} = \min\big(\max(\underbrace{\min(81,59)}_{59}, \underbrace{\min(99,99)}_{99})\big)\text{-branch} = 59$

Answer: C,D,E,F

7.3 — First five horizon nodes pruned by Alpha-Beta → G,H,J,L,M

Left-to-right DFS, passing $\alpha, \beta$ down:

Event	Node visited	Window $(\alpha, \beta)$	What happens
1	A = 45	$(-\infty, +\infty)$ at $L3_1$	$\beta_{L3_1} = 45$
2	B = 82	same	$L3_1$ returns $\min(45,82) = 45$ ; $\alpha_{L2_1} = 45$
3	C = 81	$(45, +\infty)$ at $L3_2$	$\beta_{L3_2} = 81 > \alpha$ , continue
4	D = 59	same	$L3_2$ returns 59; $L2_1 = \max(45,59) = 59$ ; $\beta_{L1_1} = 59$
5	E = 99, F = 99	$(-\infty, 59)$ at $L3_3$	$L3_3$ returns 99; $\alpha_{L2_2} = 99 \ge \beta_{L1_1} = 59$ → CUT: subtree of $L3_4$ skipped → G, H pruned
6	—	$L1_1$ completes at 59	Root updates $\alpha = 59$
7	I = 37	$(59, +\infty)$ at $L3_5$	$\beta_{L3_5} = 37 \le \alpha = 59$ → CUT: J pruned; $L3_5$ returns 37
8	K = 55	$(59, +\infty)$ at $L3_6$	$\beta_{L3_6} = 55 \le 59$ → CUT: L pruned; $L3_6$ returns 55; $L2_3 = \max(37,55) = 55$
9	—	$\beta_{L1_2} = 55 \le \alpha_{root} = 59$ → CUT	entire $L2_4$ skipped → M, N, O, P pruned

Pruning order of horizon nodes: G, H, then J, then L, then M, N, O, P — the first five are G,H,J,L,M.

Answer: G,H,J,L,M

Interactive alpha-beta trace

Each step shows the window state, exact min/max arithmetic, and what got pruned.

1 / 6

MIN(L3_1): min(A=45, B=82) = 45 alpha(L2_1) = 45. Waiting for second child.

evaluating nowbacked upnot yet reachedpruned (never examined)best strategy / root value

Tricks & Tips

Answers: 7.1 A, B · 7.2 C,D,E,F · 7.3 G,H,J,L,M