Somewhat OT... Computer playing Minesweeper

Discussion in 'Python' started by Heiko Wundram, Jul 13, 2004.

  1. 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.
     
    Heiko Wundram, Jul 13, 2004
    #1
    1. Advertising

  2. Heiko Wundram

    Paul Rubin Guest

    Heiko Wundram <> 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.
     
    Paul Rubin, Jul 13, 2004
    #2
    1. Advertising

  3. 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.
     
    Heiko Wundram, Jul 13, 2004
    #3
  4. Heiko Wundram

    Paul Rubin Guest

    Heiko Wundram <> 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.
     
    Paul Rubin, Jul 13, 2004
    #4
  5. 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
     
    Scott David Daniels, Jul 15, 2004
    #5
  6. 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?"


    Hmm... I thought about this today, and I came up with an improvement: out of
    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.
     
    Heiko Wundram, Jul 15, 2004
    #6
  7. Heiko Wundram

    John Doe Guest

    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.
     
    John Doe, Jul 15, 2004
    #7
  8. 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.
     
    Heiko Wundram, Jul 15, 2004
    #8
    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:
    970
    KeiverH
    May 7, 2005
  2. Terry Reedy
    Replies:
    2
    Views:
    461
    Heiko Wundram
    Jul 14, 2004
  3. Heiko Wundram
    Replies:
    2
    Views:
    456
    Heiko Wundram
    Jul 14, 2004
  4. Heiko Wundram
    Replies:
    1
    Views:
    426
    Matteo Dell'Amico
    Jul 23, 2004
  5. Jay
    Replies:
    15
    Views:
    1,733
    Emile van Sebille
    Jul 2, 2010
Loading...

Share This Page