Somewhat OT... Computer playing Minesweeper
Heiko Wundram
heikowu at ceosg.de
Tue Jul 13 23:41:49 CEST 2004
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.
More information about the Python-list
mailing list