Q3 — Games: Alpha-Beta Pruning Puzzle

The Question

A subtree reached from the root's path, entered with window $\alpha = 1$, $\beta = 3$; leaves take unique values from $\{1,2,3,4\}$. Structure: MIN subtree-root over two MAX squares? — the FN sheet flips the polarities of the AN variant; the keyed data pins the reading:

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

Deriving the assignment family

Both keyed cut counts and pruned leaves say: two alpha-type cutoffs, killing B and D. Alpha-cuts fire at MIN nodes whose running value drops to $\le \alpha$. That forces:

• Left square (MIN): first leaf $A \le \alpha_{\text{in}} = 1 \Rightarrow A = 1$... more generally $A \le 1$ triggers instantly; with the entering window's $\alpha = 1$: $A = 1$, B never read.
• After the left child returns its capped value, the parent MAX raises the passing bound so the right square's window opens at $\alpha' \ge 2$:
• Right square (MIN): first leaf $C \le \alpha' \Rightarrow C = 2$ kills D before it is read.

Partition constraint over unique values:

$\{A\} = \{1\}\text{-slot},\quad \{C\} = \{2\}\text{-slot},\quad \{B, D\} = \{3, 4\}\ \text{(either order)}$

giving exactly four assignments:

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

Any placement with a big value in A's slot reads both left leaves; any small value in C's slot leaves D alive. Two cuts is again the ceiling — first leaves are indispensable.

3.2 — Minimax value → 2

Representative $(A,B,C,D) = (1,3,2,4)$:

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

All four assignments yield Root = 2 ✓.

3.3 → 2,0 · 3.4 → B, D

Both cutoffs fired on the $\alpha$ side (MIN nodes hitting the lower bound), none on $\beta$ — hence 2,0; the unread second leaves are B and D.

Interactive trace

Tricks & Tips

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