Somewhat OT... Computer playing Minesweeper

[Paul Rubin]

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.