Q7 — GAMES

A 4-ply tree worth 49 at the root: two legal strategies survive scrutiny, the best one touches A,B,E,F, and Alpha-Beta kills D before anyone else.

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.

Based on the above data, answer the given subquestions.

#	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.	`A,B,E,F`
7.3	List the first five horizon nodes pruned by Alpha-Beta.	`D,G,H,J,L`

The Topic in 60 Seconds

Ply	Nodes	Rule
3 (horizon parents)	C1…C8	MIN picks the smaller leaf
2	M1…M4	MAX picks the larger MIN
1	N1, N2	MIN picks the smaller MAX
0	R	MAX picks the larger MIN

A strategy for MAX = one committed choice at every MAX node, covering all opponent replies — so its leaves may span siblings but never cross the root's two subtrees.

Deep-dive: browse the Concepts section for Minimax and Alpha-Beta.

Step 0 — Full minimax backup (no pruning)

Node	Children (values)	Backed-up value
C1	A 99, B 49	$\min = 49$
C2	C 21, D 62	$\min = 21$
C3	E 88, F 86	$\min = 86$
C4	G 23, H 83	$\min = 23$
C5	I 14, J 75	$\min = 14$
C6	K 19, L 13	$\min = 13$
C7	M 17, N 48	$\min = 17$
C8	O 80, P 82	$\min = 80$
M1	C1, C2	$\max(49,21) = 49$
M2	C3, C4	$\max(86,23) = 86$
M3	C5, C6	$\max(14,13) = 14$
M4	C7, C8	$\max(17,80) = 80$
N1	M1, M2	$\min(49,86) = 49$
N2	M3, M4	$\min(14,80) = 14$
R	N1, N2	$\max(49,14) = \mathbf{49}$

7.1 — Strategies for MAX → A, B

A strategy fixes ONE move per MAX node (R, M1…M4) and must answer every opponent reply:

Option	Leaves	Reads as	Verdict
A	C,D,E,F	R→N1 · M1→C2 · M2→C3	Valid (value 21)
B	C,D,G,H	R→N1 · M1→C2 · M2→C4	Valid (value 21)
C	A,C,I,J	spans C1/C2 under N1 and C5 under N2 → two different root moves	Not one strategy
D	B,D,J,L	B lives under N1 while J,L live under N2	Not one strategy

Options C and D mix leaves from both sides of the root — impossible after MAX commits to his first move.

7.2 — Best strategy's horizon nodes → `A,B,E,F`

The optimal play is worth 49 through the left subtree: R→N1. Opponent may then pick M1 or M2:

vs M1: MAX answers C1 (49 beats C2's 21); opponent takes $\min(99,49) = 49$ → leaves A, B
vs M2: MAX answers C3 (86 beats C4's 23); opponent takes $\min(88,86) = 86$ → leaves E, F

Union, ascending: A,B,E,F — exactly the leaves reachable when both sides play optimally inside MAX's best strategy.

7.3 — First five prunes → `D,G,H,J,L`

Alpha-Beta, left-to-right DFS with the window passed down:

#	Event	Window logic	Pruned
1	C1 = min(99,49) = 49	—	—
2	C2 sees C = 21	$21 \le \alpha_{M1}=49$ → stop	D
3	M1 = 49 → N1 explores M2; C3 = min(88,86) = 86	$86 \ge \beta_{M2}=49$ → MAX cutoff	G, H
4	N1 = min(49,86) = 49 → root α = 49	—	—
5	C5 sees I = 14	$14 \le \alpha=49$ → stop	J
6	C6 sees K = 19	$19 \le 49$ → stop	L
7	M3 = 19 → N2 holds 19	$19 \le \alpha_R=49$ → cutoff	O, P (sixth+)

First five horizon prunes, in order: D, G, H, J, L.

Interactive traces

Minimax backup

1 / 4

Static evaluation of all 16 horizon leaves. Backup bottom-up, MIN rows first.

node being backed upchildren knownevaluatedprincipal variation

Alpha-Beta with pruning

1 / 8

Left-to-right DFS. C1: A=99, B=49 -> C1 = 49.

currently evaluatingprunedfinal value / PVdone

Tricks & Tips

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