The Mathematics of Dots and Boxes: Combinatorial Game Theory in Plain English

Dots and boxes looks like a children's game, but for serious mathematicians it is an object of real interest. Combinatorial game theorists have been studying it for forty years. It sits in the same theoretical world as Nim, Go, and hundreds of other games, and the mathematical tools used to analyze it are fundamental to a branch of modern mathematics.

This post is an introduction to the mathematics of dots and boxes for people who like strategy games and are curious about the theory behind them. You do not need a mathematics degree to follow it — just patience and a willingness to think carefully about what "value" means in a game.

The central question

When mathematicians look at a position in dots and boxes — or any two-player game with perfect information — they ask: who should win, assuming both players play perfectly? For most positions the answer is not obvious. The challenge of combinatorial game theory is to develop tools that answer that question efficiently for any position, without having to search every possible move.

For dots and boxes specifically, this question has been answered for small boards (up to 5×5 box grids, maybe 5×6) and remains open for larger boards. The tools developed along the way are interesting in their own right.

Sprague-Grundy theory: the foundation

The core tool of combinatorial game theory is Sprague-Grundy theory, developed in the 1930s. It applies to a specific class of games called impartial games — games where both players have the same available moves and the only difference is who moves next.

In an impartial game, every position can be assigned a number called its Grundy value (or nimber). These numbers have a beautiful property: if you break a complicated game into independent subgames, the Grundy value of the whole game is the XOR (exclusive-or) of the Grundy values of the subgames. This turns game analysis into arithmetic.

Dots and boxes is not quite impartial — it is a partisan game, meaning the two players have different stakes because each player wants to claim their own boxes. Partisan games need a more general framework called surreal number theory, developed by John Conway.

Why dots and boxes is partisan (and weird)

In a fully impartial game, the only thing that matters is who is forced to make the last move. Whoever has the Grundy value 0 on their turn loses.

Dots and boxes is partisan because the outcome depends not only on who makes the last move but on who claims which boxes. A player can "lose the last move" but "win on box count" if they collected more total boxes.

This mixed structure makes dots and boxes harder to analyze than pure impartial games. The theory for it was developed in the 1980s and 1990s, primarily by Elwyn Berlekamp, and forms the mathematical core of his 2000 book The Dots and Boxes Game: Sophisticated Child's Play.

The concept of a "loony" position

One of the most useful ideas in the theory of dots and boxes is the notion of a loony position. A position is loony if there is a move that gives your opponent a chain of some specific length without other options — essentially, a gift.

Loony positions are important because they are dominated. No matter what your opponent does in response, the game has a predictable structure. This predictability lets mathematicians prove theorems like "if the game reaches position X with player A to move, player A loses under perfect play."

The practical player does not need to know the formal definition of loony, but the intuition — that some positions force specific structural outcomes — is worth having.

Chain values and the long chain rule

The long chain rule (the chain rule we have discussed elsewhere on this blog) falls out of combinatorial game theory as a consequence of analyzing chain positions. The rule says that the parity of long chains plus loops determines, in most endgames, which player wins under perfect play.

The mathematical reason the rule works is:

1. Each long chain has a specific "value" in combinatorial game terms — roughly, it gives the receiver $N - 2$ boxes and gives the opener $2$ boxes (on a double-cross).
2. Each loop gives the receiver $N - 4$ boxes and gives the opener $4$.
3. The parity of chain counts determines who is forced to "open" first.
4. Summing the values across all chains determines the final score, and the parity determines who gets the favorable side of each sum.

Writing this out rigorously takes a few pages of algebra, but the intuition is clear: chains have values that depend on who opens them, and counting chains correctly tells you the total value of the game.

Sprague-Grundy theory applied to short chains

For short chains (1 or 2 boxes) in dots and boxes, Sprague-Grundy theory gives specific values:

• A single opened box has a trivial analysis — the opener loses 1 box, and that is it.
• A short chain of 2 has a Grundy-like value of 0 in the endgame, meaning neither player gains significant tempo from it.

These values are small and straightforward because short chains do not admit the double-cross technique — you cannot sacrifice anything meaningful in a chain of 2.

Long chains and loops are where the analysis gets interesting, because their values depend on the chain length and on whether a double-cross is available.

The middlegame is harder than the endgame

A surprising fact: the endgame of dots and boxes is mathematically tractable, but the middlegame is not. Once the chain structure is established and we are in the long chain phase, combinatorial game theory gives clean answers about who wins. But during the middlegame — when players are still shaping chains and deciding which regions will become long chains — the analysis is combinatorially explosive.

This is why small-board dots and boxes has been solved by computer (the computer can search all positions and work out the values) but large-board dots and boxes is still open. The middlegame search space grows too fast.

In 2007, Joe K. Wilson solved the 5×5 box grid with a distributed computer search. The 5×6 was analyzed a few years later. Boards of 6×6 or larger remain unsolved because the middlegame branching is intractable for current computer analysis.

The double-cross as a mathematical result

The double-cross — taking all but two boxes from a long chain and sacrificing the last two — is not just a clever technique. It is the optimal move in a wide class of positions, and the proof comes from combinatorial game theory.

The proof sketch:

1. Compute the value of receiving a long chain of $N$ boxes and then being forced to move.
2. Compute the value of receiving $N - 2$ boxes and forcing the opponent to move.
3. Show that (2) beats (1) whenever there is at least one more opening region available.

This is an inequality you can work out for specific chain lengths. The double-cross is optimal for chains of length 3 or more, except when it is the last chain (in which case the "forcing the opponent to move" part buys nothing because there is nothing to move into). The theorem matches the practical rule of thumb exactly.

Why dots and boxes is not a solved game

For a game to be solved in the game-theory sense, we need to know the value of every position under perfect play. For dots and boxes, we know this for small boards (up to 5×6 or so). For larger boards, we do not.

The reasons larger boards are hard:

• Exponential state space. A 10×10 box grid has a game tree with roughly $10^250$ positions. Computers cannot search this directly.
• No known polynomial-time algorithm. Unlike some games (Nim, for example) that have efficient solutions, dots and boxes has no known efficient algorithm for finding perfect play.
• PSPACE-hard in general. A paper by Buro and later work showed that generalized dots and boxes is PSPACE-hard, meaning the game is as hard as any problem in the class PSPACE. This places a theoretical lower bound on how hard perfect play can be to compute.

This PSPACE-hardness result is not surprising — many popular games are PSPACE-hard or harder — but it formalizes the intuition that the game is genuinely difficult.

Practical implications

So what does any of this theory mean for someone who just wants to win more games?

Not much, directly. The math does not give you specific move recommendations in specific positions. It gives you the conceptual framework — chain counting, the double-cross, parity — that organizes your thinking.

Indirectly, quite a lot. The practical rules of thumb we use — "count long chains and loops," "double-cross unless it's the last," "force your opponent to open the biggest region first" — are all consequences of the mathematical analysis. They are shortcuts that capture what the theory would tell you if you did the computation.

If you want the math to make you better at the game, the path is: learn the practical rules first, play many games, and then read Berlekamp's book for the theoretical justification. The math will deepen your understanding of moves you were already making intuitively.

Related mathematical games

If you enjoy the mathematical side of dots and boxes, there is a whole world of related games to explore:

• Nim. The simplest impartial game, and the starting point for Sprague-Grundy theory. Also provably solvable by a very simple XOR-based strategy.
• Hackenbush. A partisan game that Conway used to develop surreal number theory.
• Sprouts. A topological game invented by Conway and Paterson that has its own deep theory.
• Go. The deepest combinatorial game theorists can analyze at all, though full-board Go is beyond current techniques.

Each of these has a slightly different character, and studying several gives you a broader sense of what game theory is.

Resources for going deeper

For the mathematically curious:

• Elwyn Berlekamp, The Dots and Boxes Game: Sophisticated Child's Play. The canonical reference. Written accessibly but requires some mathematical patience.
• Berlekamp, Conway, Guy, Winning Ways for Your Mathematical Plays (4 volumes). The encyclopedic treatment of combinatorial game theory. Volume 3 covers dots and boxes specifically.
• Aaron Siegel, Combinatorial Game Theory. A more modern textbook, rigorous and thorough.

For computer search and solving:

• Joe K. Wilson's papers on solving small dots-and-boxes boards. Available through academic databases.
• Papers on alpha-beta search applied to dots and boxes — classical AI territory.

The takeaway

Dots and boxes is mathematically deep. The depth is partly hidden behind rules so simple that a child can learn them, but the theory underneath is genuinely sophisticated — the same theoretical framework used to analyze Go, chess endgames, and a wide variety of other games.

You do not need the theory to enjoy the game. But knowing that the theory exists, and that the rules of thumb you use are consequences of real mathematics, adds a dimension to your play. The chain rule is not a heuristic — it is a theorem. The double-cross is not a trick — it is an optimal strategy in a well-defined class of positions. The game is worth your time precisely because the simplicity of the rules conceals real complexity.

If you want to take the practical strategy further, read the chain rule post and the double-cross post. If you want to play and apply the ideas in real time, Dot Clash runs in the browser and uses many of the same strategic principles. Either way, the mathematical depth is there when you are ready to dig in.