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."
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.
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.
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.
No comments:
Post a Comment