The name......
I retired from the University of Wisconsin, known to my fellow workers as "P Robert".  It is a bit of an 'in' joke but the fact was that there were three people in the same room named 'Paul' and it was getting confusing.  At any rate, the 'PRs' in the program's name stands for "P Robert's";  ie: P Robert's Boxes.

The idea.....
I wrote a program very long ago for MSDOS running on a 386.  It tried to play Dots and Boxes.  It did a bit of Nim-String analysis, as I recall.  It also attempted to reduce the number of positions examined by forming a 'canonical' representation of each position.  It worked.  I do not remember how well.  It was quite an accomplishment in my mind as it even had a GUI.  Recently I discovered 'Dabble' by J. P.Grossman.  It appeared to be a very clean and clever program for playing the game.  And it certainly plays well.

I thought I might do better.  There were several things I thought would help.

1) A nimstring analysis.  The nimstring value can generally be computed more quickly than a brute force alpha/beta search for a winning strategy.

2) A canonical representation for each position.  Other programs take advantage of mirror images, rotations, corner equivalences, etc.  I wanted to remove **ALL** equivalent positions.  The computation needed to find the canonical representation is a big price to pay but I thought it would make the exponential search **MUCH** smaller.  And the memory required to maintain a cache of values might be small enough to maintain on modern computers.  Only by writing the program and trying it would I be able to know for sure.

3) The nimstring value of a position is a good indication of its dots-and-boxes value.  Therefore, the brute force search might be more efficient if I could use nimstring values to choose better moves to try first.

4) Early in the game, before any analysis whatsoever is possible, I would attempt to make the position more amenable to nimstring analysis and more likely to have the same outcome as the nimstring game.  I would attempt to divide the board so that the nimstring value of the parts can be computed separately.  I would also attempt to remove short loops from the game since they tend to require large sacrifices in order to maintain the nim-value at zero.

5) During the (approximately) one to three moves where I could know the nimstring value but not the dots-and-boxes value, I would attempt to make moves that would help me .  If I could not make the nimstring value zero then I would attempt to make a move that would require my opponent to sacrifice to keep the value at zero.  Failing that, I would try to make a move that would leave my opponent a maximum number of moves that would not reduce the value to zero (the 'enough rope' principle).  If I could reduce the value to zero myself then I would try to select moves that did not require a sacrifice on my part, which broke up the possibility of short loops, or which extended the longest 'long chain'.

6) Don't enforce precision.  The cache of position values may very well have undetected crashes, such that two very different positions might appear to be the same position.  But it should be rare enough not to affect play very often.  I do not know how much of this actually happens but it cannot be too terrible.  Getting the cache to fit reasonably in memory was important to me.  You should not bet too much on the results of this program being correct. 

The result is PRsBoxes.exe.  Here is what I wrote to David Wilson after finishing the program:

I think I have run out of ideas to improve my program that plays Dots-and-Boxes.  I quit.

It is exceedingly ugly.  I wrote the entire thing from scratch three times.  Nevertheless, it needs a fourth rewrite.  I am too tired to do it. Special cases everywhere.  Global variables that contain God-knows-what.  Etc.

It should play a perfect 5x5 game in 5 seconds on a relatively fast computer (Thanks to your analysis program).  I have a 1GHz P3 and it lost one game out of thirty to Dabble when the time limit expired.

I played a 60-game tournament on a 6x6 board with Dabble using the default 5-second turn limit. PRsBoxes won 44 to 16.  It seems to have about a turn-and-a-half advantage and that is insufficient to recover from all bad positions because in such cases I have to rely on  my opponent to make a mistake.  Moreover, a nimval analysis is a bit weak on a 6x6 board. I think it would be better on a large board  where there is more likely to be at least one very long chain.

At any rate, you are welcome to try it.

It is sorta big (one-quarter megabyte) due to the opening book for the 5x5 board.  I have tried to limit memory usage to about the same as Dabble's.

Paul R. Stevens
Madison, Wisconsin
email address