Sixty-nine engines in this series, and every one of them has had a side to move. Minimax alternates on it, alpha-beta prunes against it, a tablebase indexes by it. Colonel Blotto deletes it. Both armies are committed at the same instant, neither side sees the other's orders, and there is no "position after my move" to evaluate because no move happens first.
So there is no best move either. Six soldiers, three fields: 4–1–1 beats 3–3–0, which beats 2–2–2, which beats 4–1–1, and the page counts 180 such triangles among the 28 allocations. Every one of the 28 has something that beats it outright.
max over my allocations, min over theirs = -1
min over their allocations, max over mine = +1
the value of the game = 0
A gap of 2, and only randomising closes it. Play it, with every shape's exploitability printed as a fraction: https://dev48.infy.uk/game/day69-colonel-blotto.html
The engine is a linear program, and duality is the theorem
min 1'w s.t. A'w >= 1, w >= 0 the row player
max 1'z s.t. A'z <= 1, z >= 0 the column player
Those are an LP dual pair, and strong duality restated in the game's terms is von Neumann's minimax theorem. It is not proved using linear programming here; in this formulation it is linear programming.
The values come out as 4/9, 13/21, 53/115, and which strategies sit in the support is decided by sign tests on a system of equalities — so one rounded comparison does not shift the answer slightly, it returns a different strategy. Every comparison is a ratio of BigInts settled by cross-multiplication. Payoffs are only −1/0/+1, so equal ratios are the rule rather than the exception and the default game reports a degenerate pivot on nearly every iteration; the leaving row is chosen lexicographically over the slack columns, which are the rows of B⁻¹ and therefore independent, so the tie always resolves.
Then the simplex is thrown away. What it emits is a certificate — two distributions plus a value — re-checked over the full matrix by arithmetic that has never heard of a pivot. A symmetry quotient does the heavy lifting: four fields and twelve soldiers is 455 allocations and 34 shapes, solved in under a tenth of a second and lifted back for certification against the full 455×455 matrix.
A draw against a strong bot is no evidence at all
| six on three fields | vs the exact equilibrium | if watched | counter |
|---|---|---|---|
| spread evenly 2–2–2 | 0 | −1 | 3–3–0 |
| two fronts 3–3–0 | 0 | −1/3 | 4–1–1 |
| 4–1–1 | 0 | −1 | 2–2–2 |
| all on one 6–0–0 | −5/7 | −1 | 4–1–1 |
| uniform over all 28 | −27/196 | −9/28 | 2–2–2 |
Spreading evenly scores exactly the value of the game against the equilibrium — indistinguishable from perfect play — and loses every single battle to a bot that has only watched its distribution. An equilibrium opponent does not punish you. It declines to lose.
What the measurement contradicted
My draft had the beat-chain the wrong way round, and the engine's counter column settled it. The "you need twice the army" threshold is also wrong: measured on three fields it is ⌈1.5·S⌉ for S = 1..7, confirmed twice over — nine soldiers beat six, not fourteen. And three test failures were test-side, including support enumeration, which is exponential in the support rather than the matrix and hung on 28×28.
Two smaller corrections landed too: 4–2–0 shuffled is already unbeatable alone, exploitability exactly 0, from a shape the LP put no weight on — 40 reorderings returned 3 different supports at the same value. And regret matching after 100,000 iterations is still 0.0035 exploitable against an LP that returned 0 exactly.
139,317 in-page assertions; 61 verifier checks and 1,000,232 assertions against independent support enumeration on all 19,683 3×3 matrices, the 2×2 closed form on all 625 over −2..2, a Brown–Robinson bracket and a 1/18 brute-force grid.
Part of a from-scratch series — one game a day, vanilla JS, one file, dependency-free engine: https://dev48.infy.uk/gamefromzero.php
Top comments (0)