Introduction

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.

Try It: The Double-Cross

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">The endgame is a set of long <b>chains</b> of boxes. It's <b>your</b>
turn to open the first chain. <b>Greedy</b> takes every box it can reach.
<b>Double-cross</b> takes all but the last two of each chain and hands them back —
keeping the opponent on the hook to open the next chain.</p>
<div class="chains" id="chains"></div>
<div class="score" id="score">You: 0 &nbsp; Opponent: 0</div>
<div class="status" id="status">Pick a strategy and watch the chains fall.</div>
<div class="btns">
  <button id="greedy" type="button">Play Greedy</button>
  <button id="cross" type="button">Play Double-cross</button>
  <button id="reset" type="button" class="ghost">Reset chains</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Dots-and-Boxes endgame. The board is reduced to long CHAINS of boxes and it is
    // YOU who must open the first one. Whoever opens a chain lets the other player
    // take it. The double-cross: when you take a chain, leave the LAST TWO boxes and
    // hand them to the opponent, who is then forced to open the next chain for you.
    // This "all-but-two" sacrifice is the chain rule that decides the whole endgame.
const CHAINS = [3, 4, 6]; // chain lengths (boxes)
let anim = null;

function render(state){
  const c = document.getElementById('chains'); c.innerHTML = '';
  CHAINS.forEach((len, ci) => {
    const row = document.createElement('div'); row.className = 'chain';
    const lab = document.createElement('div'); lab.className = 'label';
    lab.textContent = fmt('chain %ci%%v% (%len%)', { ci: ci, v: 1, len: len }); row.appendChild(lab);
    for (let i=0;i<len;i++){
      const b = document.createElement('div'); b.className = 'box';
      const owner = state && state[ci] ? state[ci][i] : null;
      if (owner==='you'){ b.classList.add('you'); b.textContent='Y'; }
      else if (owner==='opp'){ b.classList.add('opp'); b.textContent='O'; }
      row.appendChild(b);
    }
    c.appendChild(row);
  });
}
function setScore(y,o){ document.getElementById('score').textContent =
  fmt('You: %y%   Opponent: %o%', { y: y, o: o }); }
function setStatus(t,cls){ const s=document.getElementById('status');
  s.textContent=t; s.className='status '+cls; }

// Pure simulation: returns {you, opp, owners} for a strategy.
    // YOU are forced to open the first chain — the losing seat for a greedy player.
    // opener = who must open the current chain. The OTHER player (the "taker") eats
    // it. Greedy taker eats every box, then must open the next chain. With the
    // double-cross, when YOU are the taker you eat all but the last two and give
    // those two to the opener, so the opener stays stuck opening the next chain.
    // On the last chain there is nothing left to give back, so you simply take it.
function simulate(strategy){
  let opener = 'you', you = 0, opp = 0;
  const owners = CHAINS.map(len => Array(len).fill(null));
  CHAINS.forEach((len, ci) => {
    const taker = opener === 'you' ? 'opp' : 'you';
    const last = ci === CHAINS.length - 1;
    if (strategy === 'cross' && taker === 'you' && !last){
      // double-cross: you eat len-2, hand the last two back to the opener.
      for (let i=0;i<len-2;i++) owners[ci][i] = 'you';
      owners[ci][len-2] = opener; owners[ci][len-1] = opener;
      you += len - 2;
      if (opener === 'you') you += 2; else opp += 2;
      // opener keeps the move (forced) and must open the next chain.
    } else {
      // taker eats the whole chain, then must open next (or game ends).
      for (let i=0;i<len;i++) owners[ci][i] = taker;
      if (taker === 'you') you += len; else opp += len;
      opener = taker;
    }
  });
  return { you, opp, owners };
}

function animate(strategy){
  if (anim) clearInterval(anim);
  const res = simulate(strategy);
  const flat = [];
  res.owners.forEach((arr,ci)=>arr.forEach((o,i)=>flat.push([ci,i,o])));
  const shown = CHAINS.map(len=>Array(len).fill(null));
  let y=0,o=0,k=0;
  render(shown); setScore(0,0);
  anim = setInterval(()=>{
    if (k>=flat.length){ clearInterval(anim); anim=null; finish(strategy,res); return; }
    const [ci,i,owner]=flat[k++]; shown[ci][i]=owner;
    if (owner==='you') y++; else o++;
    render(shown); setScore(y,o);
  }, 90);
}
function finish(strategy,res){
  const win = res.you > res.opp;
  if (strategy==='greedy')
    setStatus(fmt('Greedy: You %you%, Opponent %opp%. %v%', { you: res.you, opp: res.opp, v: win?'(rare)':'You grabbed early boxes but were forced to open the last big chain — you lose.' }),
      win?'ok':'bad');
  else
    setStatus(fmt('Double-cross: You %you%, Opponent %opp%. %v%', { you: res.you, opp: res.opp, v: win?'You sacrificed two boxes per chain to keep control — you win!':'tie/loss' }),
      win?'ok':'bad');
  console.log(strategy, res.you, 'vs', res.opp);
}

document.getElementById('greedy').addEventListener('click',()=>animate('greedy'));
document.getElementById('cross').addEventListener('click',()=>animate('cross'));
document.getElementById('reset').addEventListener('click',()=>{
  if(anim){clearInterval(anim);anim=null;} render(null); setScore(0,0);
  setStatus('Pick a strategy and watch the chains fall.',''); });
render(null); setScore(0,0);
Result
Console

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.

The Real Complexity

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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/dots-and-boxes/Content licensed under CC BY-NC 4.0.