Somewhat OT... Computer playing Minesweeper

[Heiko Wundram]

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.