Dots-and-Boxes

[dots graphic]

Dots-and-Boxes is a popular children's game, which Berlekamp has played and studied since he learned it in the first grade in 1946. This game is remarkable in that it 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.

The figure depicts a typical application of the classical nim-like Sprague-Grundy theory to this game. The success of this methodology invariably comes as a big surprise, because Sprague-Grundy theory really applies only to disjoint impartial games in which the players are fighting over the last move, while Dots-and-Boxes players are actually trying to outscore each other by completing more boxes. And since completing a box gives that player an additional move, Dots-and-Boxes also fails to be "disjoint".

Berlekamp first presented this Dots-and-Boxes theorem to a symposium at the University of Calgary in the late 1960s. An improved exposition of this theorem and some of its extensions appeared in Chapter 16 of Winning Ways. Yet more results, with over 100 problems and examples, appear in the self-contained book The Game of Dots and Boxes Both books are published by A K Peters Ltd.

	Home / Research Interests / Game Theory / Dots-and-Boxes
Home Publications Research Interests Algorithms Applied Analysis Games Dots-and-Boxes Konane Amazons Mathematical Go Four Games for Gardner Complexity Computer Architecture Encoders Finance Business Information Theory Philanthropy Thesis Students Awards Board Memberships K-12 Outreach Education / Employment Biographies Contact Information and Site Credits Site Map	Dots-and-Boxes Dots-and-Boxes is a popular children's game, which Berlekamp has played and studied since he learned it in the first grade in 1946. This game is remarkable in that it 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. The figure depicts a typical application of the classical nim-like Sprague-Grundy theory to this game. The success of this methodology invariably comes as a big surprise, because Sprague-Grundy theory really applies only to disjoint impartial games in which the players are fighting over the last move, while Dots-and-Boxes players are actually trying to outscore each other by completing more boxes. And since completing a box gives that player an additional move, Dots-and-Boxes also fails to be "disjoint". Berlekamp first presented this Dots-and-Boxes theorem to a symposium at the University of Calgary in the late 1960s. An improved exposition of this theorem and some of its extensions appeared in Chapter 16 of Winning Ways. Yet more results, with over 100 problems and examples, appear in the self-contained book The Game of Dots and Boxes Both books are published by A K Peters Ltd.