Dots and Boxes

KBK 1 October 2002

Over the last year or two, a number of Tcl'ers have become interested in the game of Dots and Boxes - a pencil-and-paper strategy game that's simple enough for a six-year-old to learn and deep enough to challenge an adult. No doubt, one catalyst was the appearance of Elwyn Berlekamp's book, The Dots and Boxes Game: sophisticated child's play [1 ], and the review of the book that appeared in Ian Stewart's column in the January, 2001 issue of Scientific American. [284:1, pp. 102-103]

Jonathan Cook got the ball rolling with his 'dotsgame' Tclet. It was written as a framework for a programming contest, so allowed contestants to have various robot players, and allowed human-human, robot-robot, and human-robot play. It's still available at http://www.cs.nmsu.edu/~jcook/dotsgame.tar.gz .

The sample robot player that Jonathan developed was extremely weak, but Donal Fellows got interested in improving it, and brought out a much stronger robot: http://www.man.ac.uk/~zzcgudf/tcl/bitsandpieces/thinker

Kevin Kenny saw this robot as a challenge, and worked with Donal to come up with even stronger players.

Working independently, Allen Flick introduced another Dots and Boxes game, now located at: http://phaseit.net/claird/comp.lang.tcl/games/eDots.zip His game allows multiple human players, but appears to have no robot player.

Kevin Kenny has recently (October, 2002) decided to integrate the best available features into a single program, and wrap it up into a Starkit at https://www.tcl-lang.org/starkits/dots.kit . This program supports a two-player game, with either player being a human or robot. The robot player supports six levels of play, from a player that plays completely at random to one that can beat most beginners. Intriguingly, in robot-robot play, each level consistently trounces the one below it.

There are at least three additional levels possible, judging by the performance of human players, and adding them would be a "Small Matter of Programming." (Kevin would like to try this sometime, since he finds the strongest current level of play to be no challenge to beat.)

Kevin mostly did the Dots and Boxes Starkit to learn about Starkit packaging. His assessment: "It's pretty cool, having a strategy game, complete with GUI, computer player, and help system -- all in a 64K byte download!" (KBK - As an afterthought, I added a bunch of "eye candy" to the GUI in version 1.1, which nearly trebled the download size, but makes it a lot prettier on the screen. Still pretty cool.)

For more information on Dots and Boxes, there are a lot of pointers at [3 ]. In particular, David Wilson's site [2 ] is worth a visit.

01oct02 jcw - Kevin's starkit is now on the Starkit Distrbution Archive [4 ].


I am told that Dots and Boxes is known as Pigs and Sties in the North of England, and as Käsekästchen (Cheese Boxes) in Germany.