Hi list!

I've written a little program which plays Minesweeper, using quite a simple

algorithm, which I've written in Python (pseudocode):

total_fields = 0

for field in <all possible consistent fields>:

total_fields += 1

for pos in <all positions>:

if pos is marked:

hist[pos] += 1

for pos in hist:

hist[pos] /= float(total_fields)

Now, the only non-trivial algorithm in this program is compute all possible

consistent fields, which does not compute all fields that are consistent, but

only computes those fields which have mines next to already discovered

numbers, to speed things up, and all positions which do not lie to a

discovered field get the standard probability minesleft/fieldsleft, which

should be the same as looping over all possible combinations (if I'm not

mistaken).

What the computer then does is evaluate the histogram: If a position has

probability zero of having a mine: discover it, if it has possibility one:

mark it, and only if there are no positions which have possibility zero or

one: discover a random field from the list of fields which have the lowest

probability of having a mine.

This is done iteratively until no empty fields are left, or a discovery blows

up.

I've let this little program run to check the average number of "solvable"

games on an 8x8 field, with 10 mines (this is the easy setting of any

Minesweeper clone), and I get a number in the range 55-65%.

Now, if I let KMines get the solvability rate for a field of this size, it

spits out a number of 80%...

So, I guess, either my algorithm is wrong (or suboptimal), or KMines algorithm

for solving a field is wrong (taking information into account which it may

not).

If anybody here knows more about game-theory than I do, I'd be happy if he/she

could enlighten me...

For anybody willing to try the program, you can download it here:

http://www.heim-d.de/~heikowu/PyMines.py
In case you don't have psyco installed, comment out all lines which concern

psyco. And be prepared that the runtime is somewhat slow, because the

algorithm used to find the consistent fields is recursive.

Thanks for any help!

Heiko.