Dots and Boxes history

From la pipopipette to the long-chain rule

The History of Dots and Boxes

In 1883, a Paris mathematics teacher gave two short paragraphs to a new game his former students were playing on squared paper. Six years later he sold it as a boxed set with thirty-six pegs. The game then spent most of a century in schoolrooms before a mathematician who had learned it in first grade showed how much was hiding in it.

Juno points with her bionic hand to show where a rail goes.

The game of the École Polytechnique

The earliest description we could find is in the second volume of Édouard Lucas’s Récréations mathématiques, published in Paris in 1883. On pages 90 and 91, in a chapter on board games, Lucas adds a short entry called “Le jeu de l’École Polytechnique.” He writes that students of the École Polytechnique had come up with it “for some years” before. That is as close to a date of invention as the record gets, and no inventor is named.

The rules he gives are the ones you know. Two players draw a square of twenty-five, thirty-six or forty-nine cells on squared paper. Each in turn inks one side of a small square. Whoever draws the last side of a square marks it with an initial and plays again. Two details differ from the modern game. The outer border is inked before play starts, and the game is over as soon as one player holds more than half the squares.

Lucas had little to add. He says the game seemed curious enough to describe, and that he knew of no observations about it important enough to report. Most short histories start the story in 1889. The 1883 volume shows the game was already in print six years earlier, under a different name.

Thirty-six pegs and sixty bars

On May 5, 1889, Lucas signed a booklet titled La Pipopipette and subtitled a new game of combinations. It came with a boxed set, one of six in his series Jeux scientifiques, which also included the Tower of Hanoi. The games were shown at the 1889 Universal Exposition in Paris. The booklet is dedicated to the students of the École Polytechnique, and Pipo was school slang for Polytechnique. Lucas says the game was invented there by several of his own former students.

The set had thirty-six pegs in a square and sixty small bars to hang between them, enough to close twenty-five squares. That is the same board LarkSpark uses. Two, three or four people could play. A player who closed a square scored a point and placed another bar. Because moving first matters, a match for two was two games, with each player starting once.

Lucas admits that the theory of the game “is not known.” He offers one tip, which is to stop your opponent from building lines in zigzags or stair steps. Players now call those shapes chains. He also counts the possible orders of play as the product of every number from one to sixty, a figure eighty-two digits long. The booklet survives because his editors reprinted it in L’Arithmétique amusante in 1895, four years after his death. One of them adds a guess that the second player should mirror the first.

The teacher who wrote it down

Édouard Lucas was born in Amiens in 1842 and died in Paris in 1891. He worked at the Paris Observatory, served as an artillery officer in the Franco-Prussian War, and then taught mathematics at two Paris schools, the Lycée Saint-Louis and the Lycée Charlemagne. The students he credits with the game were his own former pupils, from the advanced mathematics classes that prepared candidates for the École Polytechnique.

He is better known for other things. In 1876 he proved that the number 2¹²⁷ − 1 is prime. The Lucas sequence carries his name. In 1883 he published the Tower of Hanoi puzzle under the name Claus, an anagram of Lucas. His four volumes of Récréations mathématiques collected puzzles and games with the mathematics behind them. The pencil game from the Polytechnique was one small entry among many, and he never claimed to have invented it.

A century on scrap paper

The boxed set did not last, and the pencil game did. All it needs is a sheet of paper, so it spread without a publisher or a rule book. That also means it left few records. We found no reliable account of how the game traveled from Paris classrooms to schoolrooms in other countries, and stories that fill the gap should be read with care.

What the record does show is a pile of names. English-language sources list boxes, dots and dashes, the game of dots, and pigs in a pen alongside Dots and Boxes. German players call it Käsekästchen. In French it is still la pipopipette. By the 1990s, mathematicians could describe it as a game popular with children in many countries under various names, and as a traditional children’s pencil-and-paper game.

A first grader who kept playing

Elwyn Berlekamp was born in Dover, Ohio, in 1940, and learned Dots and Boxes in first grade in 1946. By the University of California’s account, he took it up at age six and his progress “plateaued in junior high.” He went on to a career in coding theory at Berkeley, where his error-correcting codes helped spacecraft send clear pictures home. He kept coming back to the game.

What he found was a theorem. On his Berkeley page he wrote that the game can be played on at least four levels, and that players at each level beat those below because they understand a theorem the others have not yet discovered. He first presented his result at a symposium at the University of Calgary in the late 1960s. It became the long-chain rule, a way to tell from a count of dots and chains which player is headed for control of the endgame.

Berlekamp died at his home in Piedmont, California, on April 9, 2019, at the age of seventy-eight. Berkeley’s obituary called Dots and Boxes the simplest example of the games he studied and said it had fascinated him since first grade.

Chapter 16 and a $500 final

In 1982, Berlekamp, John Conway and Richard Guy published Winning Ways for Your Mathematical Plays in two volumes with Academic Press. Chapter 16 is called Dots-and-Boxes. It lays out the steps to becoming an expert. Give up greedy play in favor of the double-dealing move. Learn the parity rule for long chains. Then study two related games, Strings-and-Coins and Nimstring. The chapter also shows that a version of the game played on general graphs is NP-hard.

The theory was tested over the board at a games meeting at the Mathematical Sciences Research Institute. A knockout tournament with a $500 purse came down to Daniel Allcock and Martin Weber, playing on six dots by six, the same size as the LarkSpark board. Julian West’s report on the final appeared in 1996. Allcock won as first player and as second player. In one game both players gave up boxes to fight over control. It came down to a hard-hearted handout, a four-box chain and a six-box loop, and finished 13–12.

Sophisticated child’s play

In 2000, Berlekamp gave the game a book of its own, The Dots and Boxes Game: Sophisticated Child’s Play, published by A K Peters. It is short and built around problems. The chapters move from Strings-and-Coins to elementary and advanced chain counting, then to Nimstring, then to games with very close scores. It ends with a list of unsolved problems.

The book’s best-known idea starts from a piece of bookkeeping. In any game, the number of dots plus the number of doublecrosses equals the number of turns. A doublecross is one line that takes two boxes. In a simple endgame there is one fewer doublecross than there are long chains. Put together, the first player should try to make the dots plus the long chains come out even, and the second player should try to make that total odd.

Later work kept refining the endgame. In 2002, Berlekamp and Katherine Scott published a paper on positions where every available move opens a long chain or a loop. They showed when the player in control does best by simply staying in control, and gave a formula for what that is worth.

What computers have solved

In 2012, Joseph Barker and Richard Korf of UCLA presented a paper called Solving Dots-And-Boxes at the AAAI conference. Before them, the largest board with a known result was 4×4 boxes, worked out by a program written by David Wilson. Wilson’s program had also settled a set of half-finished 5×5 positions from Berlekamp’s book. Barker and Korf’s search ran for ten days and showed that a board of 4×5 boxes is a tie when both sides play perfectly. They called it the largest game solved to date.

LarkSpark’s board is 5×5 boxes, and we found no published solution for it. The numbers explain why. A 4×5 board has forty-nine lines, and every line doubles the count of possible arrangements. A 5×5 board has sixty, which makes the problem about two thousand times larger. A full 5×5 game can’t end in a tie, since there are twenty-five boxes, so perfect play must favor one side. Nobody has shown which.

There is also a proof that the game is hard in general. In 2021, Kevin Buchin, Mart Hagedoorn, Irina Kostitsyna and Max van Mulken showed that Dots and Boxes is PSPACE-complete, settling a question Erik Demaine had posed twenty years earlier. The result is about boards of any size. It means no shortcut is expected to solve every position quickly as boards grow.

Sources