Velocity Reviews > Somewhat OT... Computer playing Minesweeper

# Somewhat OT... Computer playing Minesweeper

Heiko Wundram
Guest
Posts: n/a

 07-13-2004
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.

Paul Rubin
Guest
Posts: n/a

 07-13-2004
Heiko Wundram <(E-Mail Removed)> 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.

Heiko Wundram
Guest
Posts: n/a

 07-13-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.

Paul Rubin
Guest
Posts: n/a

 07-13-2004
Heiko Wundram <(E-Mail Removed)> writes:
> 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.

I don't know how either your program or KMines works, but with the
Windows program I used to use, you had to clear a few squares by hand
before the algorithm could infer anything. Sometimes you blew
yourself up while clearing those first few squares. There's not
enough information to avoid that. I don't know if KMines counts those
explosions against it's algorithm's success rate.

Scott David Daniels
Guest
Posts: n/a

 07-14-2004
Heiko Wundram wrote:

> 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:

So far so good.

> discover a random field from the list of fields which have the lowest
> probability of having a mine.

Here improvement is possible. You want the move that has the greatest
expected useful information (where "Boom" is very un-useful information).
Your algorithm may be taking a number low-risk gambles with low payoff.
One measure of payoff might be "how many squares are revealed?"

You also don't track "how many undiscovered mines are out there" -- that
might provide answers to collapse consistent states.

--
-Scott David Daniels
http://www.velocityreviews.com/forums/(E-Mail Removed)

Heiko Wundram
Guest
Posts: n/a

 07-15-2004
Am Donnerstag, 15. Juli 2004 01:54 schrieb Scott David Daniels:
> Here improvement is possible. You want the move that has the greatest
> expected useful information (where "Boom" is very un-useful information).
> Your algorithm may be taking a number low-risk gambles with low payoff.
> One measure of payoff might be "how many squares are revealed?"

the squares which have the least probability of having a mine, select one
which is closest to a discovered field (so that in the common case you have
some kind of interaction between an existing square and a square which was
just discovered). This didn't improve runtime as far as I can tell...

> You also don't track "how many undiscovered mines are out there" -- that
> might provide answers to collapse consistent states.

I do track that. And consistent means not only that the discovered fields fit,
but also that there are no more mines selected than are available on the
field... So the number of states I track is certainly not more than there are
squares available...

Heiko.

John Doe
Guest
Posts: n/a

 07-15-2004
I expect you'd get much better performance by randomly selecting the
first get() in solve(). As it is, for the first get, you iterate over
every possible combination of fields of the apropriate size, only to
learn that they are all equally likely, since you have no information.

As for your percentage accuracy, I think another poster had a point,
in that while your first random get is capable of causing a Boom, in
most implementations of Minesweeper, it cannot. You are throwing in
an extra 15% failure rate, right there on your 16x16 with 40 mines.

Heiko Wundram
Guest
Posts: n/a

 07-15-2004
Am Donnerstag, 15. Juli 2004 04:34 schrieb John Doe:
> I expect you'd get much better performance by randomly selecting the
> first get() in solve(). As it is, for the first get, you iterate over
> every possible combination of fields of the apropriate size, only to
> learn that they are all equally likely, since you have no information.

As I said before, the program does not iterate over all possible states, but
only over those states that can be created by placing mines surrounding
already discovered fields. In the case you mention, there is only one
possible state, and that is returned by __iterConsistentStates(), as there
are no discovered fields. The time it takes to calculate this state is
negligible, concerning the whole runtime.

I've already thought about what you said, but I kept it as is, as IMHO it's
much cleaner to just have a loop which always does the same thing, and not
special-case the first time round.

> As for your percentage accuracy, I think another poster had a point,
> in that while your first random get is capable of causing a Boom, in
> most implementations of Minesweeper, it cannot. You are throwing in
> an extra 15% failure rate, right there on your 16x16 with 40 mines.

Okay, I already replied to that poster, that I didn't think that other
Minesweepers were always giving you a free first shot. But, at least for
Windows Minesweeper, I checked, and yes, it gives you that first free shot,
always. I'll try and incorporate that... Maybe the numbers will get closer
then, but still: 1/0.85*65% <> 80%...

Heiko.