Somewhat OT... Computer playing Minesweeper
Tue Jul 13 23:22:16 CEST 2004
Heiko Wundram <heikowu at ceosg.de> writes:
> 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...
Determining whether a given minefield is solvable is in general
NP-hard. So, there are only better and worse approximations. I found
a Windows minesweeper solver written in Turbo Pascal a while back and
its solution rate at the expert setting was maybe 1/3. I don't remember
trying it on the beginner setting.
More information about the Python-list