Sixty-six days of engines that look ahead from a position. Cops and Robbers cannot be one of them, because the robber's win condition is an infinite play. Search a thousand plies deep and all you know is that the cop has not won yet.
First pursuit game and first graph game in the series, with the tablebase shading every vertex: https://dev48.infy.uk/game/day67-cops-and-robbers.html
The solver runs backwards, and "unresolved" is the proof
Every state is a triple: cops, robber, whose turn. One cop on n vertices is 2*n*² states — 72 on a six-vertex graph. Small enough to hold all of them and work backwards from capture, exactly how a chess endgame tablebase is built.
a COP-to-move state is won as soon as ONE of its moves reaches a won state
a ROBBER-to-move state is won only when the LAST of its moves has been shown won
Some for the cop, all for the robber — that asymmetry is the entire solver. And the states still unresolved when the queue empties are not "unknown" or "too deep". They are proved robber wins, which is the verdict no forward search can hand you.
// need[p] counts the CLOSED neighbourhood - staying put is a legal move.
if (--need[p] === 0){ dist[p] = d + 1; push(p); } // ALL escapes now closed
A second algorithm that never plays a move
Nowakowski–Winkler / Quilliot, 1983: a connected reflexive graph is cop-win iff deleting corners collapses it to one vertex, where u is a corner when some v has N[u] ⊆ N[v]. Pure graph surgery, sharing no line of code with the solver.
if ((N[u] & live & ~(N[v] & live)) === 0) remove(u);
Both programs run over every connected graph up to six vertices — 27,476 of them, the enumeration itself checked against OEIS A001187. Disagreements: 0. Two unrelated programs agreeing 27,476 times is worth more than quoting the theorem.
Then the policy race, which is where the article went
| robber policy | positions lost, n = 6 |
|---|---|
| tablebase (optimal) | 0% |
| greedy, ties last | 5.05% |
| greedy, ties first | 8.24% |
| greedy + most room behind | 14.40% |
| random legal move | 100% |
Flee-the-nearest-cop is not a rough approximation of the tablebase. Up to five vertices it is perfect — 1,160 surviving positions, 0 losses. At six it loses 8.24%, concentrated on 1,902 graphs.
The smallest counterexample is a square with a two-edge tail. The robber survives by circling the square; greedy runs up the tail, because its far end is further from the cop than anywhere on the square, and gets cornered. But at the junction, round the square and up the tail are both distance 2. The heuristic has nothing to say, so neighbour storage order picks.
So the page runs that graph under all 720 numberings. 240 survive all 11 positions, 240 are caught in every position, 240 lose exactly one. Identical graph, identical policy — the labels decide. The tablebase verdict is the same in all 720.
Two things that contradicted what I set out to write
I wanted a 4×4 grid as the friendly cop-win example. A grid has no corner at all, so nothing dismantles and one cop chases forever; its cop number is 2. assert(copNumber(grid(4,4)) === 2) is in the suite because the engine computed it and I had remembered otherwise.
And the natural repair — break ties toward the vertex with more room behind it — measures worse: 14.40% against 8.24%. Flipping the tie-break gives 5.05%. None of those numbers is a property of the policy. They are properties of an arbitrary choice made where the policy is silent, which is far more uncomfortable than "it is a bit weak".
Part of a from-scratch series — one game a day, vanilla JS, one file, offline: https://dev48.infy.uk/gamefromzero.php
Top comments (0)