Dots and Boxes

You drew the grid on the back of a notebook. Players take turns adding one edge between two adjacent dots; whoever closes the fourth side of a box claims it, writes their initial inside, and moves again. Most boxes win.

It feels like a children's game, and for a few moves it is. But there is a moment — when the board fills up and only long chains of boxes remain — where the obvious move becomes a trap. Greedily grabbing every box you can will lose you the game against anyone who knows the secret.

That secret is real combinatorial game theory, and the question "what is the optimal move here?" turns out to be as hard as some of the most stubborn problems in computer science.

Here is the endgame everyone gets wrong. The board is carved into a few long chains of boxes, and it is your turn to open one. The greedy instinct says: take every box you can reach. The expert says: take all but the last two, then hand them over.

<p class="hint">{{hint}}</p>
<div class="chains" id="chains"></div>
<div class="score" id="score">{{score_you}}: 0 &nbsp; {{score_opp}}: 0</div>
<div class="status" id="status">{{status_initial}}</div>
<div class="btns">
  <button id="greedy" type="button">{{btn_greedy}}</button>
  <button id="cross" type="button">{{btn_cross}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.chains { display: flex; flex-direction: column; gap: 8px; margin: .4rem 0; }
.chain { display: flex; gap: 4px; flex-wrap: wrap; align-items: center; }
.chain .label { font: 600 12px system-ui; color: #555; width: 64px; }
.box { width: 28px; height: 28px; border-radius: 6px; display: flex; align-items: center;
       justify-content: center; font: 700 13px ui-monospace, monospace;
       background: #dfe5ec; border: 1px solid #c4cdd8; color: #1d3557; }
.box.you { background: #1d3557; border-color: #142844; color: #fff; }
.box.opp { background: #e63946; border-color: #c92f3c; color: #fff; }
.score { font: 700 1rem system-ui; margin: .6rem 0 .2rem; }
.status { font-size: .95rem; font-weight: 600; margin: .3rem 0 .6rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Play Greedy and watch yourself win the early chains — then get forced to open the final, biggest chain and lose. Play Double-cross and you sacrifice two boxes in each chain to keep handing the move back to your opponent, so they are the one forced to open the next chain. Two given-away boxes buy you a whole chain. This is the chain rule, and counting the chains decides the winner before a single box is closed.

How hard is Dots and Boxes, really? Not the drawing — the deciding.

• Checking a finished game is trivial: count whose initials fill more boxes.
• Playing well is governed by deep theory. Elwyn Berlekamp built a whole combinatorial-game-theory analysis of the endgame, where positions get nimber values and the chain rule ("the player who makes the number of long chains the right parity wins") tells you who has control.
• It's NP-hard. Deciding optimal play in generalized Dots-and-Boxes was shown NP-hard (Demaine, Demaine, Fleischer, Hearn and collaborators). Even just figuring out the best move on an arbitrary board is as hard as the toughest problems in P vs NP.
• So the simple-looking grid packs a decision problem that no known efficient algorithm can crack in general — the same wall you meet in SAT and other classic hard problems.

That is the punchline: the move that feels obvious — close the box — is often exactly wrong, and proving which move is right is computationally intractable. The double-cross is intractability you can play with a pencil.

"Give something up now to control what your opponent is forced to do later" is a pattern that runs far past the schoolyard, and Dots and Boxes is its clearest demo:

• Combinatorial game theory: Dots and Boxes is the textbook case for nimbers, parity and the sum-of-games machinery that analyzes Nash equilibria and other strategic settings.
• Game-playing AI: the double-cross is a "tempo sacrifice" — the same idea engines use in checkers and chess to keep the initiative.
• Adversarial scheduling: forcing an opponent to act first, at a cost to yourself, is a real tactic in auctions, negotiation and turn-based planning.
• Teaching hardness: because everyone has played it, Dots and Boxes is a vivid on-ramp to what "NP-hard" even means.

Learn why Dots and Boxes is hard and you've met the parity-and-control reasoning that underlies adversarial search everywhere.

Dots and Boxes hides a beautiful inversion: the move that looks like winning — closing a box — is often the move that loses, and the path to victory is to deliberately hand your opponent free boxes so they are forced to open the next chain. Berlekamp turned that intuition into a precise theory of chains and nimbers, and deciding the best move in general is NP-hard.

So the next time a game comes down to who has to open the last chain, remember: the right play might be to give two boxes away. You're not being generous — you're staring at P vs NP hiding behind a doodle, and the clever-looking move is the losing one.