The game in every exercise book

More people have played Dots and Boxes than have played every other game on this site put together. It needs a scrap of paper and nothing else, it takes about a minute to explain, and almost everybody who plays it has been taught the same rule.

Take every box available.

That rule is wrong, and not marginally. On a board of six boxes it changes the result of two thousand positions. On an endgame of a few chains it loses most of them. And the move that beats it is one a beginner would never make: hand the opponent two boxes on purpose.

The rules, and the one word that does the damage #

Dots on a grid. A move draws a line between two adjacent dots. A player who completes the fourth side of a box scores it and must move again. When no lines remain, the higher score wins.

That last sentence is the whole difficulty. Every other game on this site is normal play — the player who cannot move loses — and the theory of who moves last is built on that convention and no other. Dots and Boxes keeps a score. Nobody is ever unable to move until the lines run out, so the normal-play question has a trivial answer that no player cares about, and the question players do care about is one the machinery here does not directly answer.

The graph on the right is called strings and coins, and it is Berlekamp’s translation of the game into something with structure. It matters because it makes the two games on the same position visible at once: the scoring game, and the impartial game underneath it in which no score is kept and the last cut wins.

That second game has a name — Nimstring — and it is what decides the first. This essay stays with the scoring game and the rule beginners are taught.

What the rule costs, measured #

The way to find out what a rule costs is to build a player that follows it and one that does not, and let them play the same positions.

The comparison only means anything if the two differ in exactly the thing under test. So the greedy player here is not a heuristic and is not weak: it is the solver, searching to the end of the game and playing perfectly, with one constraint added — when a capture is available it must take one. Whatever gap opens between the two is the price of that constraint and of nothing else.

Three rows and three different answers.

On a four-box board the rule costs nothing. Both players bound to it reach exactly the same score as both players free. This is not a failure of the experiment; it is the reason the rule survives. A board that small has no chain long enough to be worth declining, so a beginner playing it can be told “take every box” and will never be punished.

On a six-box board it costs the game 2,032 times. Over every one of the 131,071 positions of a 2 × 3 board, solved twice, the constrained player’s outcome differs from the free player’s on 2,032 — and every difference is an outcome flip rather than a shaved margin. The worst case gives away four boxes.

On endgames it is a rout. Over every endgame of at most four chains of at most eight boxes, the rule changes the score on 277 of 494 positions, turns the outcome round on 266 of them, and gives away as many as 28 boxes.

The move that gives away two boxes #

Here is what the rule forbids and why forbidding it is fatal.

Late in a game the position is a collection of chains: runs of boxes joined so that opening one hands the whole run to the opponent. Somebody has to open a chain — every remaining line does — and the player who is forced to open is the one in trouble, because opening gives boxes away.

So a player who has just been handed a chain has a choice. Take the whole thing, and then be the one who must open the next chain. Or take all but the last two, and stop: the opponent pockets those two and is then the one who must open.

That second move is the loony move, or the double-cross, and it is the whole of what separates a beginner from a player. It looks like a mistake in the most literal way possible: it gives the opponent two boxes that were available for the taking.

What it buys is the move. Whoever holds the obligation to open holds a losing obligation, and two boxes is a low price for passing it back.

The arithmetic in that figure is four numbers and it is worth reading rather than trusting. Two chains of three, six boxes in all, and one of them opened. Taking the whole opened chain scores three — and then the taker must open the other chain, which the opponent takes entire, so the taker’s three are matched by the opponent’s three and the net is nothing. Declining scores one, hands two boxes over, and leaves the opponent holding the obligation: the opponent opens the last chain and the decliner takes all three of it. One plus three against two is a net of two.

The whole difference is who has to open last, and the two boxes are the fee.

That row of squares is a drawing of a component structure rather than of a game, and it is fair to ask whether any real board reaches it. One does, and the two solvers can be set against each other on it.

Why the position turns into chains at all #

Nothing in the rules mentions chains. They appear because of what a box is: a coin held by four strings, of which every move cuts one.

Early on, cutting a string is almost always safe — the coin it belonged to still has two or three others. The moment a coin is down to one string, cutting that string pockets it, and cutting the string of a coin that has two left hands the opponent a coin with one. So a player avoids reducing any coin to two strings for as long as possible, both players avoid it, and the position drifts toward the state where every remaining coin has exactly two strings.

A graph in which every vertex has degree two is a disjoint union of paths and cycles. That is not a fact about Dots and Boxes; it is a fact about graphs. The paths are the chains and the cycles are the loops, and they appear in every game because the players’ shared reluctance drives the position there.

That is the sense in which the endgame recursion is not a special-purpose trick. It is what the game turns into, by a mechanism that has nothing to do with the players’ cleverness, and it is the reason a rule about chains can be stated for boards of any size at all.

The opposite mistake is easy to make once the first one has been corrected, and the recursion makes it immediately. Add a third chain — three, three and five, with the five opened — and taking all five comes out exactly as good as declining it, because the parity of the list has changed and the obligation lands on the same player either way. Declining is not a rule any more than taking is. It is a branch, and the recursion that chooses between them is short enough to read: the opener picks a chain, the opponent picks a branch, and both sides play the whole thing out.

Where the rule loses a whole game #

A cost in boxes is a weaker claim than a cost in games. A player who wins by four instead of six has lost nothing that matters.

So the sharper measurement is the one that counts positions where the outcome changes. On the six-box board every single difference is an outcome flip, and the smallest endgame where it happens has five boxes in it.

Five boxes. That is smaller than most games children play, and it is the reason the rule is not merely inelegant: it is a rule that fails on positions that occur constantly, taught to people who then lose games without ever finding out why.

The move has a price, and it is always the same price #

Reading the two worked positions side by side — one where declining wins and one where it does not — suggests the decision is delicate. It is not. The fee is fixed and only the thing being bought varies, which is a much easier rule to hold.

Declining a chain always costs exactly two boxes. Take all but the last two, stop, and the opponent pockets those two. It does not matter whether the chain is three boxes long or thirty: the surrender is two, every time, because two is what a chain’s tail holds after the rest has been eaten.

What the two boxes buy is also always the same thing: the obligation to open moves to the opponent. So every decline in the game is one transaction at one price, and the only question a player ever faces is whether the move is worth two boxes in this position.

That is why the threshold is a chain of three. A chain of two cannot be declined at all if the opener does not allow it: cutting the middle string leaves both boxes at three sides, so every remaining move in that component captures and the responder has nothing to decline with. That opening is called hard-hearted, and it is the reason a two is not a long chain rather than merely an unprofitable one. A chain of one has no tail to leave. Three is the shortest chain with something left over after the fee, which is exactly where the long-chain rule puts its boundary, and why a four-box board — too small to hold one — is a board the beginner’s rule survives.

Which makes it the same decision the rest of this site is about #

A fixed price paid for the right to move next is not a Dots and Boxes idea. It is what is at stake with the units filled in.

Everywhere else on this site, the question here or there is settled by comparing what moving is worth against what it costs to move elsewhere, and the currency is the temperature. Here the currency is boxes, the fee is two, and the question is whether holding the move is worth more than two boxes — which depends entirely on what else is on the table, and on nothing about the chain being declined.

Read that way the two worked positions stop being a puzzle. Two chains of three: the move is worth three boxes, the fee is two, so decline. Three chains including a five: the parities work out so that the move is worth two or less, so the fee is not worth paying and taking everything is as good. The loony move is not a mantra because two boxes is a price and prices are compared, not obeyed.

It also says why the beginner’s rule is the wrong shape rather than merely the wrong answer. Take every box is a rule with no price in it at all — it never compares anything, so it cannot be right except by accident, and the accident is exactly the class of boards too small to hold a chain worth three.

The fee is not always two #

One qualification, because the fixed price is fixed per kind of component and there are two kinds.

A loop — a cycle of coins rather than a path — has to be declined four boxes at a time rather than two, because a cycle opened and eaten down to its last four cannot be left with two: taking two more would open the rest. So a loop’s fee is double a chain’s, for a reason about the shape of the graph rather than about the game.

Loops are not a hypothetical component invented to make that point. The same six-box board reaches them, and the smallest one it holds is the whole of what is left.

That makes the endgame a board of components with two different prices on it, which is the ordinary situation everywhere else on this site and is why the recursion has to be run rather than replaced by a rule. A player facing a chain and a loop is choosing between two purchases of the same thing at different prices, and the cheaper one is not always the one to make — the loop is worth declining when what the move buys exceeds four, and the chain when it exceeds two, and the two conditions can point at different components.

What the theory contributes, and what it does not #

It is worth being exact about which parts of this essay came from combinatorial game theory and which came from a search.

The search supplied the numbers: 2,032 flipped outcomes, four boxes in the worst case, five boxes in the smallest failure. Nothing in the theory produced any of them and nothing in the theory needed to.

The theory supplied the shape of the answer. The idea that a late position is a sum of independent chains, that the parts can be evaluated separately and combined, that the obligation to move is itself a quantity worth paying for — those are the disjunctive sum, the components of a decomposed board, and tempo, and without them the endgame recursion above would be a special-purpose trick rather than an instance of something.

What the theory does not supply is the answer itself. A normal-play position falls into one of four outcome classes — first player, second player, Left, Right — and every one of them is a statement about who wins and not about by how much. A scoring game asks a question with a number for an answer, and four classes have no way to hold a number.

This is the honest position and it is worth stating plainly, because a field called out in the world invites the opposite. Combinatorial game theory does not solve Dots and Boxes. It gives a vocabulary in which the endgame is a sum, and then somebody has to do the arithmetic.

There is one further contribution and it is the surprising one. The quantity a good player is fighting over is not boxes. It is the obligation to move — and that obligation has no size, no units and no place in a score. It is the thing a value leaves out when it says who wins and by how much, promoted here to the only thing that matters. A game that keeps score turns out to be decided by the one quantity a score cannot hold, which is as neat an argument for the theory as this field contains.

The other rule, and why it is nearly right #

Beginners are taught one rule and slightly better players are taught a second: whoever has to open the first long chain loses.

That one is nearly true, and how nearly is measurable. Over every endgame of chains in range, positions made entirely of long chains — three boxes or more — go to the opener’s opponent every single time, with no exceptions at all. Allow short chains in and the rule starts to have exceptions, because a chain of one or two cannot be declined and is therefore a gift rather than an obligation.

The next essay is about where that rule comes from, and the answer is the impartial game underneath: the chains decide it before the boxes do.

What the picture cannot show #

Every figure here draws a position and none of them draws a game. That gap is the reason the essay leans on counts rather than on examples.

A reader looking at a chain of three cannot see that declining it is right; the two branches differ by a number that depends on everything else still on the board. Change the rest of the position and the same chain wants the opposite treatment, and the drawing is identical. The figures above therefore print both totals rather than marking the good move, because marking it would be showing the conclusion where the choice belongs.

The other thing no picture here shows is scale. Everything solved from empty in this essay has at most six boxes. The board on the back of an exercise book has twenty-five or more, and its state space is past what any of this machinery touches. What holds at six boxes is asserted at twenty-five on the strength of the endgame recursion, which is a claim about chains rather than about board size — and it is a claim, stated as one.

The convention, named #

Everything above keeps score, which is the opposite of the convention the rest of this site uses.

Under normal play the loser is the player who cannot move, and Dots and Boxes never reaches that state until the last line is drawn. Its normal-play skeleton is therefore decided by the parity of the number of lines and by nothing else — which is a real answer to a question nobody asked. What counting at the end does to the theory is a field of its own, and the coin row there is the cleanest place to watch it happen.

The simplest form of the same disease is a row of coins taken from either end: two different rows can have different scoring answers and the same normal-play answer, because in neither of them is anybody ever stuck. A scoring game and its normal-play skeleton are different objects, and the second can be entirely silent about the first.

Where the ladder goes next #

This anchor has two rungs and they are the two halves of the same object.

This one is the scoring game: what the rules of thumb cost, measured against a solver on positions small enough to solve. The next is the impartial game hiding inside it — the same position with the score thrown away — and the reason it is worth looking at is that it answers the question the scoring game keeps asking. Who ends up having to open?

That question has nothing to do with points, and everything on this site applies to it.