Q3 — Games: Alpha-Beta Pruning Puzzle

The Question

Consider a game tree with the root node as MAX, where an arbitrary path from the root reaches the subtree shown in the figure.

Each leaf node A to D takes a UNIQUE EVAL VALUE from the set $\{1, 2, 3, 4\}$. Alpha-Beta algorithm is entering the subtree with $\alpha=1$ and $\beta=3$; find an optimal eval assignment (for nodes A to D) that maximizes the number of leaves pruned; find the minimax value, the type of cuts and the leaves pruned for that assignment.

The Topic in 60 Seconds

Structure read off the figure: the subtree root is a MIN node (it inherits bounds $\alpha=1, \beta=3$ from its MAX ancestors); its two square children are MAX nodes over leaf pairs.

• MAX cutoff: a MAX child stops once its running value reaches $\beta$ — remaining leaves die.
• After a child returns $v$, the MIN root raises $\alpha \leftarrow \max(\alpha, v)$ before opening the next child; an empty window still evaluates one leaf (to learn the bound) but cuts the rest.

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

Designing the assignment

Goals: prune as many of the four leaves as possible while keeping every value distinct from $\{1,2,3,4\}$.

Left square: call it first with window $(\alpha{=}1, \beta{=}3)$. If its FIRST leaf already reads $\ge 3$, the MAX cutoff fires immediately and the sibling is never read:

$A \in \{3, 4\} \Rightarrow \text{cutoff} \Rightarrow B \text{ pruned}$

Right square: root's $\alpha$ has risen to $\max(1, A) = A \ge 3$, so the window handed down is $(A, 3)$ — empty or razor-thin. The first leaf must still be read (to learn the bound), and it too will sit $\ge 3 = \beta$:

$C \in \{3, 4\} \Rightarrow D \text{ pruned}$

Constraints assembled:

$\{A, C\} = \{3, 4\}, \qquad \{B, D\} = \{1, 2\} \quad (\text{either order inside each pair})$

That yields exactly $2 \times 2 = 4$ assignments — the four keyed answers:

$`\,3,1,4,2\,` \quad `3,2,4,1` \quad `4,1,3,2` \quad `4,2,3,1`$

Any assignment with $A < 3$ reads both left leaves (no cut); any with $C < 3$ reads both right leaves. Two cuts is the maximum — you can never prune the FIRST leaf under a freshly opened child because its parent's value is still unknown.

3.2 — Minimax value → 3

Take the representative assignment $(A,B,C,D) = (3,1,4,2)$:

$\text{Left} = \max(3,1) = 3 \qquad \text{Right} = \max(4,2) = 4 \qquad \text{Root(MIN)} = \min(3,4) = \mathbf{3}$

All four keyed assignments give Root $= \min(A, C)$ where $\min(A,C) = 3$ ✓.

3.3 — Cut types → 0, 2

Counting by the bound that did the cutting:

Zero alpha-type cuts (no MIN-node cutoff ever fires here — the root never lowers below $\beta$), two beta-type cuts → 0, 2.

3.4 — Leaves pruned → B, D

As derived: the second leaf under each square dies unread. First leaves are indispensable — they establish their parent's value.

Interactive trace

Tricks & Tips

Answers: 3.1 3,1,4,2 / 3,2,4,1 / 4,1,3,2 / 4,2,3,1 · 3.2 3 · 3.3 0,2 · 3.4 B,D