Forcing the Minimax Value — One-Leaf Tweaks
Change ONE horizon eval to force the root to a target value — the inverse problem from 23T1 papers, solved with backup arithmetic
The Simplest Explanation
The papers' other inverse question (alongside maximize-pruning):
"Force the MinMax value of the tree to X by changing the eval of only one horizon node. Pick that node, and give the smallest/largest possible new value."
The tool is pure backup arithmetic: root = max of MIN children; each MIN = min of its MAX children; each MAX = max of its leaves. Change one leaf → recompute upward.
To RAISE the root: find a MIN node already equal to the current root value and raise its ceiling — but every sibling under it must also rise. To LOWER the root: shrink the single MIN branch that currently controls it.
Interactive Demo
Target: force Root to 98 by changing exactly one leaf. Click a leaf and tweak:
Click a leaf node to select it, then use the buttons above to change its eval. Currently Root = max(53, 27, 37) = 53.
What the Demo Shows
Original backups:
- N1 = min(max(18,69), max(30,53)) = min(69,53) = 53
- N2 = min(max(15,27), max(98,14)) = min(27,98) = 27
- N3 = min(max(19,37), max(61,68)) = min(37,68) = 37
- Root = max(53,27,37) = 53
Why only leaf E works for target 98:
- Raising N1 or N3 to 98 needs both their MAX children ≥ 98 — two leaves. Not allowed.
- N2's second child M22 = max(98,14) = 98 already. So raising E (in M21) to ≥ 98 makes M21 = 98, then N2 = min(98,98) = 98, then Root = max(53,98,37) = 98 ✓ — one leaf!
- Smallest value for E that achieves it: exactly 98 (any less leaves N2 < 98).
Worked Example 2 — Lowering the Root (23T1 AN)
Tree: Root(MAX) → three MINs with pairs (A29,B46), (C75,D96), (E13,F36), (G99,H28), (I33,J26), (K37,L18).
Backups: N1 = min(46,96) = 46; N2 = min(36,99) = 36; N3 = min(33,37) = 33; Root = 46.
Task: force Root to 36, choosing the largest possible new value.
- Root = 46 comes solely from N1. Lowering N2/N3 changes nothing (they're already ≤ 46).
- Reduce B (46): M11 = max(29, x). Need N1 = min(M11, 96) ≤ 36 → M11 ≤ 36 → x ≤ 36.
- Largest feasible x = 36 → answer
B,36✓ (official key)
The General Recipe
- Back up the whole tree; identify which MIN child equals the current root value
- To change root to T:
- Raise: find a MIN node where a single leaf-change can lift its min to T (needs its other MAX child already ≥ T); else impossible with one change
- Lower: reduce a leaf in the controlling MIN branch so its backed-up value hits T
- Compute the boundary value algebraically; pick smallest/largest per the question
- Verify no other branch exceeds T after your change (for lower-targets) or that root actually reaches T (for raise-targets)
Properties
| Aspect | Rule |
|---|---|
| Changes allowed | Exactly one leaf |
| Raise root | Some MIN must reach T with one leaf tweak (its sibling MAX ≥ T already) |
| Lower root | Controlling MIN's leaf reduced so its min = T |
| Answer style | Leaf,Value e.g. E,98, B,36 |
| Boundary logic | "smallest/largest possible" = solve the backup inequality at equality |