Game Strategies and the Best Strategy

The Simplest Explanation

A strategy for MAX = a complete plan that says what MAX will do at every one of its decision points, and accounts for every possible MIN reply.

Think of it as a subtree, not a single path:

• At each MAX node: pick exactly one child (your choice)
• At each MIN node: include all children (you must handle every opponent reply)

Formal Definition (Lecture 77)

Given a game tree with horizon evals:

• Cluster of a node = horizon nodes under it (grouped by MAX-strategy)
• Strategy = union of clusters corresponding to MAX's choices

If MAX commits S1→A and S2→C, the strategy's horizon leaves are exactly A and C — one leaf per committed MAX node. MIN's freedom is already baked in: S1 vs S2 was MIN's choice, so both branches stay in the set.

What Papers Actually Ask

Papers ask two things every year:

Q1: "Which of the following is a strategy for MAX?"

The validity test: for every MAX node in the tree, all set-leaves descending from it must come from one single child of that MAX node. If leaves split across two children of any MAX node → invalid.

Worked example (22T3 FN Q7) — 4-ply tree, Root(MAX) → N1,N2 (MIN) → M1–M4 (MAX) → C1–C8 (MIN) → leaves A–P:

Q2: "List the horizon nodes in the best strategy"

Key insight: once MAX fixes its commitments, the opponent (MIN) can steer play to any leaf in the resulting set. So:

$\text{value(strategy)} = \min(\text{evals of all horizon leaves in the set})$

Best strategy = the valid strategy maximizing this minimum — it equals the minimax value of the root.

Worked example (22T3 FN): back up the full tree: C1=49, C2=21, M1=49; C3=86, C4=23, M2=86; N1=49; C5=14, C6=13, M3=14; C7=17, C8=80, M4=80; N2=14; Root = max(49,14) = 49 via N1.

Candidates under N1 (root→N1 forced):

• A,B,E,F: guarantee = min(99,49,88,86) = 49 ← best
• C,D,E,F: min(21,62,88,86) = 21
• A,B,G,H: min(99,49,23,83) = 23

Under N2 nothing beats 14 (best: M3→C5 gives 14). So best strategy horizon = A,B,E,F, matching the exam answer.

Smaller example (23T1 FN Q4): Root(MAX) → 3 MINs → 6 MAX nodes → leaves A–L in pairs. Back up: N1 = min(max(18,69), max(30,53)) = min(69,53) = 53. Best strategy: root→N1, first MAX commits to B (69), second to D (53) → horizon B,D, guarantee min(69,53)=53 ✓ exam answer.

Clusters (SSS* Prep)

A cluster = all horizon nodes that share the same MAX-choice pattern up to that point. SSS* refines clusters by merit. If you understand strategies, you understand what SSS* is searching over.

"Leaves Not Affecting the Game Value" (24T3 variant)

A related ask: "List the horizon nodes that do not affect the game value under perfect play."

These are leaves that could never influence the root's minimax value — they sit in branches that optimal play never reaches or that α-β proves irrelevant:

1. Back up the tree; find the root value and the optimal strategy
2. Any leaf outside every branch MIN would steer into (given MAX's strategy) cannot change the value
3. Concretely: leaves in subtrees whose backed-up value loses at some MIN node above them are dead — even huge eval changes there leave the root untouched

24T3 example (answer D,E,G,H): those four leaves live under branches whose MIN parents already lose to a sibling — no single eval change among them alters the root.

Distinguish from Alpha-Beta pruned sets: "not affecting game value" is a game-theoretic property (about perfect play), while pruning is an algorithmic property (about what α-β happens to skip). They usually overlap but need not be identical.