Somewhat OT... Computer playing Minesweeper

[Terry Reedy]

"Heiko Wundram" <heikowu at ceosg.de> wrote in message
news:200407132252.49595.heikowu at ceosg.de...
> 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