PRsBoxes
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