# Re: Somewhat OT... Computer playing Minesweeper

Discussion in 'Python' started by Terry Reedy, Jul 14, 2004.

1. ### Terry ReedyGuest

"Heiko Wundram" <> wrote in message
news:...
> 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%...

I have no idea what KMines is. I do know that it is easy to undercompute
which unexplored positions are knownable as to their true status and which
therefore can be safely marked or opened. The consequence is gambling when
there is no need to and possibly loosing when there is no need to.

In particular, there are multiposition patterns which are only
deterministic when considered together. For instance, consider the
patterns

ooo oooo
121 1221
??? ????

where o is an unmined position (actual number not relevant). Then ??? and
???? must be xox (x=mined) and oxxo respectively and one can safely open or
mark those three or four positions. There are other patterns I know of
and, I sure, others I do not.

Terry J. Reedy

Terry Reedy, Jul 14, 2004

2. ### Jeff ShannonGuest

Terry Reedy wrote:

>In particular, there are multiposition patterns which are only
>deterministic when considered together. For instance, consider the
>patterns
>
>ooo oooo
>121 1221
>??? ????
>
>where o is an unmined position (actual number not relevant). Then ??? and
>???? must be xox (x=mined) and oxxo respectively and one can safely open or
>mark those three or four positions.
>

With this in mind, I can envision an algorithm which, after exhausting
all of the "obvious" mined and clear positions (as described by the
initial algorithm), then proceeds to scan subsets of the grid for
recognized patterns. This pattern matching could become very complex --
at a minimum, it would need to look at subgrids of varying sizes (3x3,
3x4 at minimum) being matched against four rotational-variations of each
pattern. If it finds a pattern, it can mark/discover the appropriate
positions and then revert to the initial algorithm to check for newly
"obvious" decisions. You will have a hard time coming up with an
exhaustive list of possible patterns, but even a fairly modest list
should greatly improve your solvability percentage.

Jeff Shannon
Technician/Programmer
Credit International

Jeff Shannon, Jul 14, 2004

3. ### Heiko WundramGuest

Am Mittwoch, 14. Juli 2004 03:27 schrieb Jeff Shannon:
> You will have a hard time coming up with an
> exhaustive list of possible patterns, but even a fairly modest list
> should greatly improve your solvability percentage.

As I said in the reply to Terry Reed, there is no need to actually do pattern
matching in case you simply exhaust all possible states which are consistent
in the sense that they match the information which is available. You then
just have to create a histogram which for each field gives a percentage of a
mine being there, and then make a decision.

This algorithm will match _any_ pattern that might turn up.

Heiko.

Heiko Wundram, Jul 14, 2004