Elwyn Berlekamp (1940-2019)

Elwyn R. Berlekamp, who died on April 9, 2019, was an accomplished computer scientist and an expert in combinatorial game theory. In 2000, I wrote about his book on the seemingly simple game of Dots and Boxes.

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, noted in the preface to his book The Dots and Boxes Game: Sophisticated Child's Play (CRC Press, 2000). "That was in 1946."

"Ever since then I have enjoyed recurrent spurts of fascination with this game," he continued. "During several of these 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 claimed. Indeed, "a surprisingly large amount of mathematics is very relevant to this game."

Berlekamp posited 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 said.

Berlekamp's book serves as an eye-opening 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 layer 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.

Originally posted October 30, 2000.