			       MINESOLV

If you've played minehunt much, you probably can quickly get to the
point where either you've solved a game, or there are no 100% safe
moves.  Then, based on your intuition about which squares are more
likely to contain mines, you make a guess that is as safe as possible.
I was interested in how good my intuition is, so I wrote a little
program that calculates exactly how safe each square is.  It does this
by rapidly enumerating all possible games which match the incomplete
information that has been obtained in a game, keeping track of how
many times each particular square is a mine.

The accompanying source file, minesolv.c, should be fairly easy to
port to any system with an ANSI C compiler.  Just issue a command
like:

  cc -O -o minesolv minesolv.c

The program's usage message is below.  

  usage: minesolv [-g] [-m mines] [MxN]
         where M is the number of squares in the x-direction
         and N is the number of squares in the y-direction
         -g toggles the existence of a goal square
         -m specifies the number of mines

The default settings are:
  there is a goal square
  there are 20 mines
  the game board is 16x8

The command line options allow this program to be used to analyze the
Windows version of minehunt, although it is a bit unwieldy to input
the game information for a large game board.  Also, I have not tested
the performance of the algorithm for large boards.

With its default settings, the program takes 8 lines of input, one for
each row of the game board.  Each character represents one column of
the game board, and is either a number between '0' and '8' inclusive
or is the letter 'x'.  The numbers represent how many mines neighbor
this square, while the letter 'x' represents a square you haven't been
to.  If fewer than 16 characters are input in a line, it is assumed
that all remaining characters are 'x's.

Here's a sample input:

1111x2
1x1112
1110012xx2
000001xxx1
000112x3213
0001x23xx1
00012x4
00001

1.6 seconds later (on a 100MHz 486) the output of the program looks like:

....M.gOOOOOOOOO
.M....gbeeeOOOOO
.......bd.dOOOOO
......gjc.hiOOOO
......g....iOOOO
....M..Ma.fiOOOO
.....g.MdddOOOOO
.....gggOOOOOOOG

Safety factors:
a:  96.85
b:  96.06
c:  95.28
d:  80.00
e:  66.67
f:  63.15
g:  50.00
h:  44.72
i:  30.71
j:   7.87
O:  88.56

The game board map has '.' for squares you've visited, 'M' for proven
mines, 'O' for squares you can't get to, and 'G' for the goal square.
The lower case letters represent squares with varying degrees of
safety, which are printed below the map as percentages.  Note that the
information provided is completely accurate: if it is possible to prove
that a particular square is a mine, the program will prove it and tag
it with the 'M' character.

Another discussion item which shows that I've spent entirely too much
time thinking about this game: just because a square is safest does
not mean that it is the "best" move.  For example, there might be a
situation where you have two squares, one of which is a mine, and no
further play can make this any better than a 50% guess.  There also
might be a 90% safe square which will become either 100% or 0% depending
on the outcome of the 50% guess.  Obviously, you're better off taking
the guess that you can't avoid, first.  So what you really need is a
program which finds not the safest square, but the one which maximizes
your chance of winning the game.  This problem is quite a bit harder
than the one that I solved.
--
Scott Hemphill	hemphill@alumni.caltech.edu
