Dots-and-Boxes Analysis Programs

The analysis program is now complete. This is the current released version dated April 30, 2002. Send your e-mail address to dwilson@cae.wisc.edu to be notified of any new releases that fix bugs.

The analysis package has two programs: analyze, which does the analysis, and play, which displays summaries of the analysis results. The analyzeL and playL programs also do loony move analysis, placing a v suffix on a score if player A must make the next loony move or a ^ suffix if player B must. The version with loony move analysis can't handle scores greater than 31 in absolute value. The normal version can handle scores up to 127 in absolute value. If you use the loony move analysis program on a problem where the number of boxes (plus the absolute value of any last move penalty) exceeds 31, you should check the results by also running the analysis using the normal version.

The input to the analysis program is a text file describing the problem. For example, for the 3x5 Swedish game this file is:

0
+-+-+-+-+-+
|         |
+ + + + + +
|         |
+ + + + + +
|         |
+-+-+-+-+-+

The number on the first line is either 0 or a negative number giving a penalty to be applied to the player who makes the last move. This is useful if you are analyzing part of a game and it is known that whoever moves first into the other part of the game suffers a loss of that many squares. I have analyzed problem 11.16 with penalties of increasing magnitude.

The first line may have two more additional numbers: the number of megabytes of RAM your computer has and the number of gigabytes of free disk space available. Default values are 16 and 1. You should use the values for your own PC.

The three numbers may be followed by an A or B indicating which player is on the move. This may be needed if there has already been a loony move in the game. Also, boxes already captured should be filled in with A's and B's.

The file should have a .txt extention. I called this file swed.txt. 3x3.txt, 3x5.txt and iceland.txt are other examples of input files. (3x5.txt has values for RAM and free disk space; make sure they're appropriate before using it.) Both programs start out asking for the name of the problem, which is the name of the text file omitting the .txt extention.

The disk space needed to store a complete analysis is slightly larger than 2n bytes where n is the number of lines not yet filled in. A chain counts as a single open line. This is reduced for symmetric positions and positions where the corners are empty. 220 bytes is a megabyte, 230 bytes is a gigabyte. The analysis files are stored in a directory named for the problem. If the complete analysis won't fit, the analyze program stores the analysis for as many initial moves as will fit. The play program does an in-memory analysis once this opening book is exhausted to cover the rest of the moves.

On my machine, swed.txt and 3x3.txt were analyzed in less than a minute. iceland.txt took half an hour. 3x5.txt took three days. (The program is written so it can start where it left off after it is aborted or after a reboot. Thus, the three days can be scattered over nights and weekends.) Each additional open line doubles the time, RAM and disk space required by the problem.

This program cannot analyze the 5x5 game. However, the 5x5 game has been analyzed by William Fraser using his own program.

Once that analysis is done, you use the play program to display the result. For example, for the Swedish game:

   a  b  c  d  e  f  g  h  i  j  k

a  +-----+-----+-----+-----+-----+
   |                             |
b  |    -1    -1    -1    -1     |
   |                             |
c  + -1  +  3  +  1  +  3  + -1  +
   |                             |
d  |     5     5     5     5     |
   |                             |
e  + -1  +  3  +  1  +  3  + -1  +
   |                             |
f  |    -1    -1    -1    -1     |
   |                             |
g  +-----+-----+-----+-----+-----+

Enter move for player A (two letters); .=stop; <=back; !=reset: be

   a  b  c  d  e  f  g  h  i  j  k

a  +-----+-----+-----+-----+-----+
   |           |                 |
b  |     5     |     1     1     |
   |           |                 |
c  +  5  +  5  +  1  +  5  +  1  +
   |                             |
d  |     5     5     5     5     |
   |                             |
e  +  1  +  5  +  1  +  5  +  3  +
   |                             |
f  |     1     5    -1     3     |
   |                             |
g  +-----+-----+-----+-----+-----+

Enter move for player B (two letters); .=stop; <=back; !=reset: fg

   a  b  c  d  e  f  g  h  i  j  k

a  +-----+-----+-----+-----+-----+
   |           |                 |
b  |    -7     |    -1    -5     |
   |           |                 |
c  + -7  + -7  + -1  + -7  + -5  +
   |                             |
d  |    -3    -3    -3    -3     |
   |                             |
e  + -5  + -7  + -1  + -7  + -7  +
   |                 |           |
f  |    -5    -1     |    -7     |
   |                 |           |
g  +-----+-----+-----+-----+-----+

Enter move for player A (two letters); .=stop; <=back; !=reset: .
Done.

The numbers are the resulting score with best play if the player on the move selects the corresponding line. Positive numbers are wins for the first player to move (player A); negative numbers are wins for the second player to move (player B). Thus, with best play the first player wins by 5. The above investigated the analysis for one of the worst plays for the first player. To win, the second player must make exactly the right move. To keep loses to a minimum, the first player must then immediately give away a square.

The analysis of the Icelandic game took about half an hour on my PC. I couldn't run in on the Sun because it needed 230 bytes (1 gigabyte) free disk space and I didn't have that much room in my Sun account. The initial screen from the play program is:

   a  b  c  d  e  f  g  h  i  j  k

a  + -3  + -3  + -3  + -3  + -5  +
   |
b  |    -3    -5    -3    -3    -5
   |
c  + -5  + -3  + -3  + -3  + -3  +
   |
d  |    -5    -3    -1    -3    -3
   |
e  + -5  + -5  + -5  + -5  + -3  +
   |
f  |    -5    -3    -1    -3    -5
   |
g  +-----+-----+-----+-----+-----+

Thus, the result with best play is a win for the second player by 1 square.

For an overview of how the analysis works, see Dots-and-Boxes Analysis Methodology.

Instructions for Unix

Create a directory called: boxes using mkdir boxes in your Unix command window. Save copies of the following files into that directory:

To save a copy of a file, first display the file by clicking on its link and then use "Save As..." on the File menu in your browser. Change to the boxes directory using cd boxes in your Unix command window. Then enter the command: make This creates the analyze, analyzeL, play and playL programs as well as the zero byte all file, which you don't need to keep. Next create the input file using vi or some other file editor. (Or you can copy the input files linked earlier.) Then, enter the command: analyze or analyzeL When that's done, enter the command play or playL depending on which analysis program you ran.

Instructions for PCs

Create a folder named Boxes on whichever disc has the most free space. Save copies of the following programs into that folder:

To save a copy of a program, right click on its link and select "Save Link As...". Open the Boxes folder. Next create the input file using: Start -> Programs -> Accessories -> NotePad (Or you can copy the input files linked earlier.) Then, double click on: analyze or analyzeL When that's done, double click on play or playL depending on which analysis program you ran.

PHP Programs for the Web

Plays using an already complete analysis. Includes loony move flags. This is mostly a translation of playL from C to PHP.

<- Parent Directory

David Wilson / dwilson@cae.wisc.edu