Somewhat OT... Computer playing Minesweeper

[Heiko Wundram]

Am Dienstag, 13. Juli 2004 23:22 schrieb Paul Rubin:
> Determining whether a given minefield is solvable is in general
> NP-hard.

Right, I know that.

That's why I'm running a Monte-Carlo simulation on the whole thing, using a 
general algorithm for solving a given mine-field, and testing for "many" 
distinct fields. But, the thing is: KMines tells me that on simple setting 
the solvability rate is somewhat near 80% for 200 runs, while my algorithm 
gives a solvability rate of 55-65% for 200 runs.

And I don't really see where the difference might come from, as IMHO the best 
possible algorithm discovers fields which are zero probability for a mine, 
flags fields which are one probability for a mine, and only if this fails, 
tries to discover a field which has the lowest probability of all remaining 
fields for having a mine.

I've not looked at the solution algorithm which KMines uses (yuck, C++ ;)), 
but I'm really somewhat astounded where this difference (15-25%) comes 
from...

Maybe I'm just a lousy Minesweeper player, and couldn't think of a better 
algorithm to solve a field, but at least what the program does is what I do 
when I try to solve a field... ;) And that's why I asked, if somebody knows 
of a better general algorithm to solve a given field.

btw: KMines tells me that for expert setting (30x16, with 99 mines) the 
solvability rate is 42%, but as a human player I get somewhere around 3-4%... 
That was my initial incentive to try to write the algorithm for myself, as I 
couldn't believe the 42% that it spit out... But, okay, as I said, I'm a 
lousy player, and maybe my program is too. ;)

Heiko.