Double Cross

The game every child plays on the back of a worksheet, and the one where being good looks, from the outside, like throwing boxes away. Take every box you are offered and you will lose to someone who doesn’t — 176 games out of 200, by an average of six boxes out of sixteen. The move that beats you gives you two free boxes in a single move — a double-cross — and the reason it works is not psychology or depth of search. It is a counting identity you can prove in four lines.

The one line it all comes from

Let d be dots, b boxes, e edges, on an R×C grid of boxes:

e = (R+1)C + R(C+1) = 2RC + R + C
b + d − 1 = RC + (R+1)(C+1) − 1 = 2RC + R + C

so e = b + d − 1, always. Now count turns, where a turn is a maximal run of moves by one player — you move again after completing a box, so a turn ends on the move that completes nothing.

Every turn but the last ends on a non-scoring move, and the final move of the game always scores (the last edge drawn has all three of its box’s other edges already there). So with S scoring moves and T turns:

e = S + (T − 1)

Let D be the number of moves completing two boxes at once. Every box is completed by exactly one move, so b = S + D, giving S = b − D. Substitute, and use e = b + d − 1:

b + d − 1 = (b − D) + T − 1

T  =  d + D

The number of turns in a game of Dots and Boxes is the number of dots plus the number of double-crosses. Nothing about skill, board shape, or play order survives into that statement. Twenty-five dots means twenty-five turns, plus one for every time somebody hands over two boxes with one move.

Nine thousand games — random, greedy and chain players in every pairing — and T = d + D in every single one. scripts/measure.mjs fails if it ever isn’t.

Which means the last turn is not something you play for

Players alternate turns, so turn k belongs to the first player exactly when k is odd. The last turn is turn T:

The last turn of the game belongs to the first player if and only if d + D is odd.

Measured over 480 games on four board sizes: zero mismatches. That is not a model of the game, it is arithmetic about it.

The long chain rule is that identity with one substitution

Here is the received wisdom, the thing good players actually say: count the long chains; the first player wants dots + long chains to be even. It is usually presented as folklore. It isn’t — it is the identity above with one assumption dropped in.

Once the board is nothing but chains and loops, whoever runs out of safe moves must open one, and the other player eats it. The eater then declines the last two boxes to stay off the hook, and each decline is exactly one double-cross — until the final chain, which gets eaten whole because there is nothing left to stay off the hook for. So with c long chains:

D = c − 1        →        T = d + c − 1

and the last turn — the one where the controller eats the final chain — goes to the first player iff d + c − 1 is odd, i.e. iff d + c is even. That is the rule, derived rather than remembered.

And the rule is exactly as good as that one substitution, never better. Games played out by the chain player, with c read off the board the moment it decomposes:

Look at the last two columns rather than the middle one. Where the assumption holds the rule is essentially never wrong; where it fails the rule is worse than a coin flip, because the way it fails is a parity flip — an extra double-cross, or one that never happened, moves T by one and swaps who is holding the short straw. A heuristic that degrades to 50% is unreliable. This one degrades to 29%, which means it is still carrying information, just with the sign reversed.

The other thing the rule quietly needs is that control be worth having:

Control of four boxes is not control. The rule is a statement about who wins the long chains, and it only predicts the game when the long chains are the game.

The bribe costs four, not two

This is the part that is easy to get wrong, and I did get it wrong: I wrote the endgame solver with declining priced at two boxes, and it disagreed with brute force on 265 of 400 positions.

Declining two boxes does not cost you two. The two boxes you leave are two your opponent scores, so the difference moves by four. Write EV(S) for the net boxes of the player who must open into a multiset S of chains and loops. Handed an open component of length L with S left behind:

take it all    L + EV(S)              — and then you are the one opening
decline        L − 2·bribe − EV(S)    — bribe is 2 for a chain, 4 for a loop

With that sign, the multiset DP and an exhaustive bitmask search over the real edges — no shared algebra, one works on integers and the other on the board — agree on 400 of 400 decomposed positions.

What an opened chain is worth, net, to the player holding it:

The whole top row says take everything: with nothing behind it, control buys nothing, so a bribe is a pure loss. Every other row says decline, from a 3-chain upward — and the length of the chain in your hand does not enter the decision at all. Subtract the two lines above:

decline − take it all  =  −2·bribe − 2·EV(S)

No L in it. So the rule is decline exactly when −EV(S) exceeds the bribe — when being the one who opens into what’s left costs more than two boxes (four, for a loop). The chain you are being handed is irrelevant to whether you should eat it; only what is standing behind it matters.

Loops are the same argument at double the price, and it shows:

A four-box bribe is not worth paying for one 3-chain, and is worth paying for one 5-chain. That single row is why loops are worth building when you are losing the parity fight: they are the expensive thing to hand over.

Two cases the DP treats specially, both verified by the agreement above rather than asserted: a 1-chain cannot be declined at all, and a 2-chain can be declined only if its opener lets it be. Open a 2-chain at the end and one move gives both boxes away; open it in the middle and there is no such move left — the taker must eat both and then open next. So the opener’s choice of where to open is itself a real move, and openMove() makes it.

Where runs actually go wrong, which is not at the chain count

The demo prices every move you make against perfect play, exactly, once the position fits in a bitmask. Six hundred positions with a box on offer:

In 68% of positions, greed is free. That is the trap: the habit is correct almost all of the time, which is how it survives to the 32% where it is worth −22 boxes on a sixteen-box board. You cannot learn this by playing badly and noticing; the feedback is too sparse and arrives too late.

And every cost in that table is even. So is every one of the 47 mistakes the demo’s own meter priced in-browser — a mistake in this game is always an even number of boxes, because what a mistake does is hand over a bribe, and bribes are paid in twos.

What the chain player is worth, and what it isn’t

Two hundred games per matchup on 4×4 boxes, each bot playing both seats:

The middle rows are the honest framing of the trap: greed beats thoughtlessness by fourteen boxes out of sixteen. It is an enormous improvement over nothing, and it is precisely the thing that loses.

The last row is a null result I am keeping in. I wrote a midgame heuristic that steers the long-chain count toward the parity it wants, on the theory that the rule says parity is everything. It is worth nothing — very slightly less than nothing. Safe moves early rarely decide whether a region becomes one long chain or two; the structure is settled much later, by moves that are not safe at all. So the module ships with it off by default and the flag left in, since the measurement is more interesting than the feature. All of the strength in this engine lives in the endgame, and that is not a shortcut, it is where the game is.

Perfect play, where it fits

A plain memo table over edge subsets runs out at about twenty free edges — 2^20 entries, a second of work — so 3×3 boxes (24 edges) is already past it and the 4×4 board the demo defaults to is far past it. That is exactly why the chain decomposition matters: it replaces sixteen boxes and forty edges with a multiset like {9, 5, 2}, on which the same question is answered instantly and provably identically.

The skeleton is the drawing

Every undrawn edge is an arc: between the two boxes it separates, or between a box and the ground outside the board. When no box has more than two arcs left, the position is its chains and loops, and the demo draws them as ribbons with their lengths written on them — because the lengths are the entire remaining state, and nobody draws them.

The classifier has a hard invariant. A loop is a cycle, and the dual of a grid is bipartite, so every loop has even length and at least four boxes. My first version called a component a loop whenever it touched no ground, which quietly mislabelled the most important position in the game — the last two boxes of an opened chain, joined by one edge, touching nothing — as a 2-loop, and priced its bribe at four. measure.mjs now classifies 43,480 components on every run and fails if a single loop comes back odd or shorter than four.

What is derived here and what isn’t

• Derived: e = b + d − 1; T = d + D; the last-turn parity; the long chain rule as a corollary with D = c − 1; the bribe costing 2·bribe in margin; the chain/loop endgame values; every number in every table above. node scripts/measure.mjs reprints all of it and exits non-zero if any of it stops being true.
• A modelling choice: the engine plays exactly below eighteen free edges and heuristically above it. That is a compute budget, not a claim about the game. The “perfect play from here” readout is exact whenever it appears — by bitmask search when the position fits in one, by the chain DP when the board has decomposed, which is why it can still quote an exact number with twenty edges left — and it simply goes away when neither route applies rather than guessing.
• A game, not a claim: the 340 ms the engine waits before moving, the board sizes on offer, and the fact that the greedy opponent exists at all.
• Deliberately not done: no opening book and no midgame search. The engine will lose to a strong human in the first half of a 5×5 game. It will not lose the endgame, which is the part this piece is about.

Reuse

src/double-cross.mjs is framework-free and has no canvas in it. createGame(), play(), captureMoves() and safeMoves() are the rules; structure() is the chain decomposition; endgameValue(), takerValue() and endgameAdvice() are the multiset solver; exactSolve() is the bitmask search with two-box moves forced (never wrong, and it prunes most of the tree); controller() is the parity rule; greedyMove(), randomMove() and chainMove() are the players, and openMove() and declineMove() are the two moves that carry the whole idea.

The demo is demo/index.html with its own copy of the module (ADR-0002), pointer input, a window.__demo hook the screenshot rig drives, and a blunder meter that prices your last move in boxes after the repaint rather than in front of it. node scripts/screenshot-demo.mjs regenerates the thumb and media and doubles as the smoke test: it checks in a real browser that a click draws exactly one edge, that thirty finished games all satisfy T = d + D, that the blunder meter finds real mistakes and that none of them costs an odd number, and that the chain player still beats the greedy one over the same code path a visitor plays against.