[Tutor] Dots-And-Boxes

[Danny Yoo]

Hi everyone,

[Warning; somewhat long message.  Sorry!]


For fun, I picked up Elwyn Berlekamp's "The Dots and Boxes Game", which is
a book about a deceptively simple game.  Here's Berlekamp's paragraph
describing the game:


"""Dots-and-Boxes is a familiar paper an pencil game for two players; it
has other names in various parts of the world.  Two players start from a
rectangular array of dots and take turns to join two horizonally or
vertically adjacent dots.  If a player completes the fourth side of a
square (box) he initials that box and must then draw another line.  When
all the boxes have een completed the game ends and whoever has initialed
more boxes is declared the winner.

A player who can complete a box is not obligated to do so if he has
something else he prefers to do."""



To make the game clearer, I'll run through a sample game.  Let's say that
two players, A and B, are playing Dots-And-Boxes on a 3x3 board:


 +  +  +

 +  +  +

 +  +  +



Here's one run through the game:


 +--+  +

 +  +  +

 +  +  +


Player A chooses to join the first two dots.




 +--+  +
    |
 +  +  +

 +  +  +

Player B chooses to join the mid-top and middle.  The game can proceed
like this:




 +--+  +
    |
 +  +  +        A moves a bit more down.
    |
 +  +  +



 +--+  +
    |
 +  +  +        B makes it snake around a bit.
    |
 +  +--+


 +--+  +
    |
 +  +  +        A connects the lower left and mid left points.
 |  |
 +  +--+



 +--+  +
    |
 +  +  +        A connects the lower left and mid left points.
 |  |
 +  +--+


 +--+  +
    |
 +  +  +        B forgets that the game is not Hangman.
 |  |
 +--+--+


 +--+  +
    |
 +--+  +        A completes a square.  Because of this, it's A's turn
 | A|           again.
 +--+--+



 +--+  +
 | A|
 +--+  +        A completes the upper left square.  Another free turn.
 | A|
 +--+--+


 +--+--+
 | A|
 +--+  +        A plays the upper right square, finally giving a turn
 | A|           to B.  But it's too late.
 +--+--+


 +--+--+
 | A|
 +--+  +        B places a futile line.
 | A|  |
 +--+--+


 +--+--+
 | A|
 +--+--+        And A promptly trounces.
 | A| A|
 +--+--+


 +--+--+
 | A| A|
 +--+--+        A dominates the game.
 | A| A|
 +--+--+


So it's sorta like Tic-Tac-Toe, but a little more interesting.  Yahoo
Games actually has this as one of their Java applets, I think... but
wouldn't it be fun to write a Python program to play this game?  *grin*

(We could even hold a Tutor Dots-And-Boxes competition, where our program
battle each other!  Hmmm!)



Fantasies aside, I'm written some toy code and thought perhaps someone
here might be interested too.  My code for the game is here:

    http://hkn.eecs.berkeley.edu/~dyoo/python/dots-and-boxes/board.py

I need to start working on the GUI for it since entering coordinates can
be a bit non-user-friendly; I'll start on this tomorrow.