Dots and Boxes — the series · Combinatorial Game Theory

A 2 × 3 board of boxes, 6 still on the table. A Dots and Boxes position drawn as dots and lines, and — where the figure asks for it — the same position as a strings-and-coins graph: one coin per box, one string per line, and the border lines running to the ground. Lines already played are solid, lines still available are dashed, and a box with no strings left has been pocketed. The footer carries the exact net score the solver computes from here and the normal-play verdict on the same position.

The game in every exercise book

Dots and Boxes is played by more people than every game in this collection put together, and everybody is taught the same rule — take every box available. The rule is wrong. Establishing that takes a solver rather than an opinion, and the solver says how wrong, on which boards, and by how many boxes.

part 1 · applied

The impartial game inside the scoring one. For every position of a Dots and Boxes board, two questions asked separately: who wins the scoring game, and who wins Nimstring — the same position under the normal-play convention, with no score kept. The bars show how often the two answers agree, grouped by how many boxes are still on the table. Agreement is near-total when there is enough left to be worth controlling and falls away when there is not.

The chains decide it before the boxes do

Under every game of Dots and Boxes there is an impartial game with no score in it, and it settles the question the scoring game keeps asking — who ends up having to open. The rule players learn as folklore falls out of it, and so do the exceptions nobody mentions.

part 2 · applied

Every part on its own is worth nothing. The Grundy value of each chain and loop considered as a game by itself, and three real Dots and Boxes boards used to check the turn-by-turn walk against the win-or-lose solver already used here. Every component alone is a second-player win, which is exactly what makes the nim-sum useless.

The parts are worth nothing and the sum is not

Every chain and every loop in Nimstring, taken alone, has Grundy value nought. So the Sprague–Grundy theorem predicts that every position built from them is worth nought — and ninety-six of the two hundred and seven positions checked here are not. The theorem is not being misapplied; it does not apply, because a capture keeps the turn. What replaces it is smaller and sharper: count the short chains, and one long component of any kind reverses the parity.

part 3 · applied

The endgame theory arrives late

Every component the chain-and-loop theory names has coins of degree two, so a position it can read is one where every surviving coin holds exactly two strings. Over a six-box board that is 1,033 of the 28,028 positions with no free box on the table — 3.7 per cent — and more than half of them only after twelve of the board's seventeen strings have been cut.

part 4 · applied

The law, on a board rather than in a bag. The parity law applied to every position of a real board that has fallen into chains and loops, with the verdict computed independently from the board's own strings. The components are the ones the geometry produces rather than the ones a sweep constructs.

A thousand positions and no exception

The parity law was fitted to constructed bags of chains and loops inside a string budget. A board's positions are a different population — the sizes are what the geometry allows, the components come correlated, and a six-box board holds exactly one position that is a loop of six. Tested on all 1,032 of them and all 160 of the four-box board's, the law is right every time, against a verdict computed from the strings by a walk that has never heard of a component.

part 5 · applied

The components the theory does not name. Grundy values of strings-and-coins components with a branching coin, grouped by the value. A chain or a loop is worth nothing on its own whatever its size; a coin with three strings takes four different values depending on its arms, and a coin with four strings is back to nothing.

A coin with three strings is worth something

Every chain and every loop is worth nought on its own, whatever its size, and that is exactly what makes their nim-sum useless. A coin with three strings on it is worth nought, one, two or three depending on its arms — 31 of the 35 measured are not nought, and the four that are are the ones whose arms are all long. A coin with four strings is back to nought every time.

part 6 · applied

What control is worth, to a box. The margin the player who does not have to open nets, beside the formula that predicts it: the total less four boxes for every long chain after the first. Computed against the solver on every endgame of long chains in range.

Four boxes for every chain after the first

Nimstring answers who is forced to open and says nothing about the score. The margin has a formula: the controller nets the total less four boxes for every long chain after the first — two surrendered and two not taken, each time control is kept. Checked against the solver on 175 endgames it is exact on 172, never too generous, and exact wherever it promises the controller anything at all. The three it misses are the three where it promises nothing.

part 7 · applied

Two and four are not conventions

Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.

part 8 · applied