Re: Somewhat OT... Computer playing Minesweeper

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

  1. Terry Reedy

    Terry Reedy Guest

    "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
    #1
    1. Advertising

  2. Terry Reedy

    Jeff Shannon Guest

    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
    #2
    1. Advertising

  3. 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
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. KeiverH

    Minesweeper |BuscaMinas|

    KeiverH, May 7, 2005, in forum: C++
    Replies:
    0
    Views:
    957
    KeiverH
    May 7, 2005
  2. Heiko Wundram
    Replies:
    7
    Views:
    1,194
    Heiko Wundram
    Jul 15, 2004
  3. Heiko Wundram
    Replies:
    2
    Views:
    454
    Heiko Wundram
    Jul 14, 2004
  4. Heiko Wundram
    Replies:
    1
    Views:
    424
    Matteo Dell'Amico
    Jul 23, 2004
  5. Jay
    Replies:
    15
    Views:
    1,714
    Emile van Sebille
    Jul 2, 2010
Loading...

Share This Page