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 [L1 ], 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.cs.man.ac.uk/~fellowsd/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 http://mini.net/sdarchive/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 download that's less than 64KB, with a strategy game, complete with GUI, computer player, and help system!"
For more information on Dots and Boxes, there are a lot of pointers at [L2 ]. In particular, David Wilson's site [L3 ] is worth a visit.
I am told that Dots and Boxes is known as Pigs and Sties in the North of England, and as Cheese Boxes in Germany.