Dots and Boxes

The familiar pencil-and-paper game of Dots-and-Boxes sounds exceedingly simple.

Given a square or rectangular array of dots, two players take turns joining two adjacent dots with a horizontal or vertical line. When such a move adds the fourth side of a box, the player who did the deed claims the box (marking it with his or her initial) and must take an extra turn. If the same move closes two boxes, the player claims both boxes but still gets only one bonus move. A player who can complete a box is not obliged to do so. The game ends when all the boxes are taken. The player who closed more boxes wins.

Despite the simplicity of its rules, the game can be played on several different levels of sophistication.

"Like many other children, I learned to play the game of Dots-and-Boxes soon after I entered grade school," mathematician Elwyn R. Berlekamp of the University of California, Berkeley, notes in the preface to his new book, The Dots-and-Boxes Game: Sophisticated Child's Play. "That was in 1946."

BOOK

"Ever since then I have enjoyed recurrent spurts of fascination with this game," he continues. "During several of those bursts of interest, my playing proficiency broke through to a new and higher plateau."

In Dots-and-Boxes, "each advance can be associated with a new mathematical insight," Berlekamp claims. Indeed, "a surprisingly large amount of mathematics is very relevant to this game."

Berlekamp posits that the game can be played on at least four different levels. "Players at any level consistently beat players at lower levels, and do so because they understand a theorem which less sophisticated players have not yet discovered," he says. Berlekamp's book serves as a useful guide to Dots-and-Boxes strategies and an introduction to mathematical game theory.

Novice players tend to play at random. Before long, however, they typically begin to adopt rudimentary strategies to improve outcomes.

Initially, the idea is to keep adding lines while ensuring that no square in the grid has three filled-in edges. The result is a kind of maze with a number of chains, or sequences of connected boxes. You and your opponent then trade the rights to different chains of squares. Here's how to proceed:

Make sure there are several long chains (three or more squares in length) and try to force your opponent to be the first to open one.
When you have control by forcing your opponent to open a long chain, make sure you keep it by declining two boxes of every long chain except the last.
To take control, the first player tries to make the sum of the number of dots in the array plus the number of moves in which a single stroke completes two boxes (a doublecrossed move) odd. The second player tries to make the sum even.

In simple games, the number of doublecrosses will be one less than the number of long chains. This leads to the "long chain rule": Try to make the number of initial dots plus the number of eventual long chains even if you play first, odd if you play second. Such a strategy leaves the doublecrossed moves to your opponent.

The rule also ensures that an alert player starting second can always win a nine-box game.

Berlekamp's book presents a number of elementary chain-counting problems (with solutions), then proceeds to advanced chain counting, nimstring graphs, and other mathematical theory for expert play. He concludes his book with a set of unsolved problems--game situations on 5 by 5 grids that have so far escaped definitive solution.

Challenge: Find a move that will win this game.

Dots and boxes is the sort of game for which it is relatively easy to find simple, effective strategies for improved play. At the same time, important aspects of the game continue to elude analysis. There are so many possible moves on even a 5 by 5 grid of squares that no computer can try all the possibilities to find a path to a guaranteed win and play a perfect game.

In fact, a 5 by 5 playing field is an ideal venue for testing strategies. A game on such a grid offers plenty of challenge yet can be played in a reasonably short time.

References:

Berlekamp, E.R. 2000. The Dots-and-Boxes Game: Sophisticated Child's Play. Natick, Mass.: A.K. Peters (http://www.akpeters.com/).

Berlekamp, E.R., J.H. Conway, and R.K. Guy. 1982. Winning Ways for Your Mathematical Plays. San Diego, Calif.: Academic Press.

Weaver, L., and T. Bossomaier. Preprint. Evolution of neural networks to play the game of Dots-and-Boxes. Available at http://xxx.lanl.gov/abs/cs.NE/9809111.

West. J. 1996. Championship-level play of Dots-and-Boxes. In Games of No Chance. Berkeley, Calif.: Mathematical Sciences Research Institute.

Elwyn Berlekamp has a dots-and-boxes Web page at http://www.math.berkeley.edu/~berlek/cgt/dots.html. His lecture on "a mathematical view of the children's game Dots-and-Boxes" is available at http://www.msri.org/activities/events/9900/Berlekamp/index.html.

A lecture by Katherine Scott on a "loony Dots-and-Boxes endgame" can be found at http://www.msri.org/publications/ln/msri/2000/gametheory/scott/1/index.html.

The Mathematical Sciences Research Institute's Puzzle Corner can be found at http://www.msri.org/publications/news/puzzlepage.html.

Comments are welcome. Please send messages to Ivars Peterson at ip@sciserv.org.

Ivars Peterson is the mathematics/computer writer and online editor at Science News (http://www.sciencenews.org). He is the author of The Mathematical Tourist, Islands of Truth, Newton's Clock, Fatal Defect, and The Jungles of Randomness. He also writes for the children's magazine Muse (http://www.musemag.com) and is working on a book about math and art.

Ivars Peterson will present "A Kaleidoscope of Mathematics and Art" at the Joint Mathematics Meetings in New Orleans on Jan. 13, 2001, at 10:05 a.m.