AI Search · Exam notes
One games comprehension per paper, three to four sub-questions on one tree: strategy for MAX? best strategy leaves? pruned or unaffected leaves? SSS* solved leaves? One chain answers all of them: solve minimax first, then read everything else off those values.
| Shape | Player | Rule (bottom-up) |
|---|---|---|
| Square | MAX, wants large values | write the max of the children |
| Circle | MIN, wants small values | write the min of the children |
Fill values bottom-up before answering anything else. Example: MAX over 68 and 30 gives 68; MIN over 48 and 68 gives 48. Root is always MAX here.
Strategy: a subtree where MAX keeps one child and MIN keeps all children. Test each option and kill it if a MAX node keeps two children, a MIN node drops one, or it spans two root branches.
Best strategy: walk down from the root carrying its minimax value. MAX takes the max child, MIN takes everything. Example: root 56 comes from the right child; right MIN keeps I and the J/K node; that MAX picks J (78 beats 22). Leaves: I, J.
Walk left to right, depth first, carrying alpha (best MAX is guaranteed) and beta (best MIN is guaranteed). The moment alpha ≥ beta, cut the remaining children. Their leaves are never inspected.
Example: MIN has beta 48 from leaf A. Its MAX child returns 68 from leaf B, so 68 ≥ 48 cuts leaf C.
SSS* searches partial strategies best-first and marks examined leaves SOLVED. The exam asks only for the final SOLVED set. Tie-breaker: deepest node first, then leftmost.
Cross-check from the 2024T3 tree: leaves called unaffected by perfect play are exactly the ones SSS* never marks SOLVED.
5a. The tree as a table (solve from this, then check the animation)
| Node | Type | Children | Minimax value |
|---|---|---|---|
| R | MAX (root) | M1, M2, M3 | 56 |
| M1 | MIN | A=48, X1 | 48 |
| X1 | MAX | B=68, C=30 | 68 |
| M2 | MIN | D=20, X2 | 20 |
| X2 | MAX | N1, N2 | 88 |
| N1 | MIN | E=42, F=76 | 42 |
| N2 | MIN | G=88, H=98 | 88 |
| M3 | MIN | I=56, X3 | 56 |
| X3 | MAX | J=78, K=22 | 78 |
Cover the animation. First fill the minimax column yourself, then derive strategy, pruning, and solved sets. Official answers: strategy: A,B and D,G,H; best: I,J; pruned: C,E,F,G,H,K; SSS* solved: A,D,I,J.
5b. Animation: one tree, four modes
Why this step
Status at this step
5c. The four questions
Leaves A to K with values in the table above. Tie-breaker: same best cost goes to the deepest node, then the leftmost of the deepest.
5d. Solution
Fill minimax values yourself, then answer with a pen before opening the answer.
| Node | Type | Children | Minimax value |
|---|---|---|---|
| R | MAX (root) | M1, M2, M3 | 54 |
| M1 | MIN | A=18, X1 | 18 |
| X1 | MAX | B=98, C=70 | 98 |
| M2 | MIN | D=54, X2 | 54 |
| X2 | MAX | E=80, N | 80 |
| N | MIN | F=92, G=62 | 62 |
| M3 | MIN | H=32, X3 | 32 |
| X3 | MAX | I=50, J=74 | 74 |
Q: Strategy? Options: A,C / A,D,H / D,F,G / E,I,J. Best strategy? Pruned by Alpha-Beta? SOLVED by SSS*?
Why this step
Tracker
Strategy: A,C and D,F,G. A,D,H and E,I,J span branches, dead. Best: D,E (R takes M2 at 54, X2 takes E at 80). Pruned: C,F,G,I,J (C cut at X1; F,G cut at X2 entry; I,J cut at X3 entry). SSS*: A,D,E,H (official).
| Node | Type | Children | Minimax value |
|---|---|---|---|
| R | MAX (root) | M1, M2 | 49 |
| M1 | MIN | A=56, B=49 | 49 |
| M2 | MIN | X4, G=14, H=63 | 14 |
| X4 | MAX | N3, F=28 | 28 |
| N3 | MIN | C=35, D=21, E=42 | 21 |
Q: Strategy? Options: A,C,F / C,D,E,G,H / F,G,H / G,H. Best strategy? Leaves not affecting the value with perfect play? SOLVED by SSS*?
Why this step
Tracker
Strategy: C,D,E,G,H and F,G,H. A,C,F spans branches, dead. G,H drops a MIN child, dead. Best: A,B (R takes M1 at 49). Unaffected: D,E,G,H (official, equals the complement of the SSS* set). SSS*: A,B,C,F (official).
A path from the MAX root reaches a small subtree. Leaves A to D take distinct evals from \(\{1,2,3,4\}\). Pick the assignment that prunes the most leaves, then report minimax value, cut counts, and pruned leaves. Two real variants below; their subtree shapes differ, so read the root shape first.
| Variant | Subtree shape | Entry bounds |
|---|---|---|
| FN (Q8 to Q11) | MIN root (circle), two MAX children (squares); A,B left, C,D right | alpha = 1, beta = 3 |
| AN (Q8 to Q11) | MAX root (square), two MIN children (circles); A,B left, C,D right | alpha = 2, beta = 4 |
Cut rule used on both: the first leaf under each middle node is always inspected. At a MAX child, a leaf at or above beta triggers a beta-cut and its sibling is pruned. At a MIN child, a leaf at or below alpha triggers an alpha-cut and its sibling is pruned. Exhausting all 24 assignments by script gives exactly 4 optimal ones per variant, matching the official keys.
FN walk: assignment 4,2,3,1, alpha = 1, beta = 3
AN walk: assignment 1,3,2,4, alpha = 2, beta = 4
FN assignments: 3,1,4,2 and 3,2,4,1 and 4,1,3,2 and 4,2,3,1. Take 4,2,3,1: left MAX sees A = 4, which is at or above beta 3, so beta-cut, B pruned. Root MIN tightens beta to 3. Right MAX sees C = 3, at or above 3, so beta-cut, D pruned. Minimax 3, cuts 0 alpha and 2 beta, pruned B,D. All four assignments give the same triple.
AN assignments: 1,3,2,4 and 1,4,2,3 and 2,3,1,4 and 2,4,1,3. Take 1,3,2,4: left MIN sees A = 1, at or below alpha 2, so alpha-cut, B pruned. Right MIN sees C = 2, at or below 2, so alpha-cut, D pruned. Minimax 2, cuts 2 alpha and 0 beta, pruned B,D. All four assignments give the same triple.
Exam trap: the two variants prune the same leaves (B,D) but with opposite cut types, because the middle layer flips from MAX to MIN. Always mark squares MAX and circles MIN before simulating.
Older papers ask a shorter variant: alpha-beta is mid-flight down a path from the MAX root, and you pick the eval of the frontier node N (from a fixed parity set) that prunes N's siblings, then name the cut type. Rule: read the operative bound off the path (MAX ancestors set alpha, MIN ancestors set beta). N at a MAX node needs an eval at or above beta (beta-cut); N at a MIN node needs an eval at or below alpha (alpha-cut). Only in-range values of the right parity count.
Why this step
Tracker
Odd variant (path 5,17,7,11,9,N; odd evals below 15): N = 11 or 13, Beta Cutoff. The MIN ancestor holds beta at 11, so N at its MAX node cuts iff N is at or above 11; the odd in-range values doing that are exactly 11 and 13.
Even variant (path 2,14,4,10,N; even evals below 15): N = 2 or 4, Alpha Cutoff. The MAX ancestor holds alpha at 4, so N at its MIN node cuts iff N is at or below 4; the even in-range values doing that are exactly 2 and 4.