Re: Somewhat OT... Computer playing Minesweeper

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

  1. Am Freitag, 23. Juli 2004 05:13 schrieb John Hazen:
    > [snip]


    You're making wrong assumptions about my algorithm for computing all
    consistent fields... Just to demonstrate what the algorithm actually does,
    I'll limit to exposing the steps the algorithm takes to find the number of
    consistent fields around a 2, just the thing you mention below. If the
    description seems somewhat weird, blame my english, and have a look at the
    source code. ;)

    > If you want a larger improvement than this, you can limit your possible
    > fields generator by how many mines you expect in the set you're
    > currently calculating. For example, in your 2 small regions of 8
    > squares surrounding an exposed "2", the brute-force method generates 2^8
    > combinations (256). But you *know* that there are only 2 mines in those
    > 8 squares, so the actual number of combinations is "8 choose 2", or 28.
    > (Conveniently, in this situation, these are also the complete set of
    > consistent fields for these regions.)


    First of all, let's write some pseudocode for the algorithm.

    def yieldFields(self):
    for pos in (0,0) to (width,height):
    if field at pos is not a number:
    # means unset, marked mine or free
    continue
    unsetfields = calculate unset fields around pos
    mines = calculate number of mines around pos
    if mines > number at pos:
    # We got ourselves into a dead end, don't yield any fields.
    raise StopIteration
    elif mines == number at pos:
    if we have unsetfields:
    # There are unset fields around pos, mark them free, and
    # continue to calculate rest of the field.
    mark all unsetfields as free
    yield all fields which are calculated by self.yieldFields()
    unmark all unsetfields
    raise StopIteration
    else:
    # All fields have been marked, continue with current
    # loop. This field is okay so far.
    else:
    # (mines < number at pos)
    # Mark a certain field as containing a mine, and call ourself,
    # so that the rest of the fields is checked accordingly.
    for unsetfield in unsetfields:
    mark field unsetfield as mine
    yield all fields which are calculated by self.yieldFields()
    # Mark the set field as free, so that the search space
    # is halved.
    mark field unsetfield as free
    unmark all unsetfields
    raise StopIteration
    # We got here, this means that all fields have been filled
    # properly. Now do a sanity check.
    if mines remaining on field > fields remaining on field:
    raise StopIteration
    yield self

    Now, for an actual run, we have the field:

    * * *
    * 2 *
    * * *

    The coordinates of the field are labeled from (0,0) at the upper left.

    1. first field which the algorithm finds that is a number is (1,1).
    2. unsetfields = [(0,0), (0,1), (0,2), (1,2), ...]
    3. mines = 0
    4. go into third branch: mark (0,0) as containing a mine, call same function
    again.
    4.1. first field which the algorithm finds that is a number is (1,1).
    4.2. unsetfields = [(0,1), (0,2), (1,2), ...]
    4.3. mines = 1
    4.4. go into third branch: mark (0,1) as containing a mine, call same function
    again.
    4.4.1. first field which the algorithm finds that is a number is (1,1).
    4.4.2. unsetfields = [(0,2), (1,2), ...]
    4.4.3. mines = 2
    4.4.4. go into second branch: mark all unset fields as free, call same
    function again.
    4.4.4.1. first field which the algorithm finds that is a number is (1,1).
    4.4.4.2. unsetfields = []
    4.4.4.3. mines = 2
    4.4.4.4. go into second branch: no unsetfields, just continue.
    4.4.4.5. no more numbers found, this field is done.
    4.4.4.6. remaining mines = 0, fields remaining = 0, so state is okay.
    4.4.4.7. yield this field. <--- return all the way to caller
    4.4.5. raise StopIteration
    4.5. still in third branch: mark (0,1) as free
    4.6. mark (0,2) as containing a mine, call same function again.
    4.6.1. first field which the algorithm finds that is a number is (1,1).
    4.6.2. unsetfields = [(1,2), ...]
    4.6.3. mines = 2
    4.6.4. go into second branch: mark all unset fields as free, call same
    function again.
    4.6.4.1. first field which the algorithm finds that is a number is (1,1).
    4.6.4.2. unsetfields = []
    4.6.4.3. mines = 2
    4.6.4.4. go into second branch: no unsetfields, just continue.
    4.6.4.5. no more numbers found, this field is done.
    4.6.4.6. remaining mines = 0, fields remaining = 0, so state is okay.
    4.6.4.7. yield this field. <--- return all the way to caller
    4.6.5. raise StopIteration

    etc.

    Just on a sidenote, I use field above for both the whole, and also for a
    square of the whole (I just noticed that), but which of the two is meant
    should be clear from the context.

    The number of fields that will be spit out is exactly 28, the number of states
    possible for this little field (8 over 2). The histogram of positions can now
    be calculated, just looking at each square each of the returned fields. If a
    square is discovered or marked free, add zero, if a square is marked mine,
    add one, if a square is unmarked, add mines remaining divided by fields
    remaining or zero in case fields remaining is zero.

    If we have a look at the second more complicated area, where the actual
    problem with this algorithm lies is the fact that it doesn't just yield the
    fields that come out of analyzing this little area (that would be fast), but
    crossproducts those states with the states that are possible for both of the
    twos on the field. Now, the number of states that must be calculated is
    28*28*20000 (there are around 20000 possible states for the more complicated
    region, as there can either be six or seven mines around it), which is around
    fifteen million. And even though I own a fast computer, yielding all those
    fields takes time... ;)

    > [snip complicated explanation...]
    > So, since the minimum possible number of mines is 5.29, and the max is
    > 6.2, 5 or 7 won't work. So, the number of combinations we have to
    > generate for consistency testing is "16 choose 6", which is 8008.


    Well, I had two thorough looks at what you're doing, but I can't seem to find
    an error (well, I'm no expert in probability theory). I can easily construct
    a consistent field which has six mines surrounding the numbers, the actual
    field has seven mines surrounding it, and I can also construct other fields
    with seven mines.

    Field with six mines:

    x x *
    * 2 * * x
    * 2 1 3 *
    x 2 x * x
    * * *

    Field with seven mines:

    x * *
    x 2 * x x
    * 2 1 3 x
    x 2 * * *
    x * *

    Less than six or more than seven doesn't seem to be possible, though, at least
    for my preliminary look... I'd have to see what my little algorithm tells
    me. ;)

    > Thanks for posing the question! I'm enjoying thinking about it.


    Anyway, I'll start thinking about what you're doing too, and maybe I'll find
    an answer why calculating the number of mines as you did doesn't work (I
    rechecked your calculations, and they were okay...)...

    Thanks for replying anyway! And hope the above info cleared up what I'm
    doing... It's nothing brute-forcish, as I don't calculate all possible
    states, and then check each, but the algorithm will only yield consistent
    states (and all of them).

    Heiko.
     
    Heiko Wundram, Jul 23, 2004
    #1
    1. Advertising

  2. Heiko Wundram wrote:

    [...]

    > Well, I had two thorough looks at what you're doing, but I can't seem to find
    > an error (well, I'm no expert in probability theory). I can easily construct
    > a consistent field which has six mines surrounding the numbers, the actual
    > field has seven mines surrounding it, and I can also construct other fields
    > with seven mines.


    I think this example clearly demonstrates the error:

    1 1 1
    1 . 1
    1 1 1

    This creates an estimate of eight for the unknown point, which is
    obviously wrong. The error lies in the fact that the point is a neighbor
    of eight other points, and their "estimates" gets added.

    Besides, I found your algorithm pretty good, but I think there are three
    possible ways of making your algorithm better:

    (1) Better efficience
    (2) Better estimate of the probability of founding a mine
    (3) Better choice for the square you're going to test

    (1) should be accomplished quite simply by separating the calculations
    for non-contiguous subfields. Of course, when some subfield gives a
    probability of 0 to some adjacent square, short-circuit the algorithm
    and immediatly discover it.

    (2) could be done putting into account the undiscovered squares that are
    non-adjacent to a number. Now you don't take it into account. Let's take
    the case where there are 10 such squares, and one mine left: there are
    10 consistent possibilities in this case, whereas, when there are two
    mines left, the consistent possibilities are 10*9=90.
    The general formula for n squares and x mines is n!/(x! * (n-x)!).

    I'm almost sure I'm so contorted that you're not following me, so let's
    do an example ('.'s are undiscovered squares):

    1 . .
    .. . .
    1 . .

    Suppose in this case we have 2 bombs in all the field.

    Your algorithm (if I understood it correctly) would ignore the three
    rightmost squares, and find these three consistent states ('x' is a
    bomb, '-' is a free square and '?' is a place where you don't know):

    1 x ?
    - - ?
    1 x ?

    1 - ?
    - x ?
    1 - ?

    1 - ?
    x - ?
    1 - ?

    You'd label all the three cases as equiprobable, so each square has
    1/3rd of probability of having a mine.
    This is not true, since - counting the whole field - there are 7
    distinct possibilities: the one in the topmost state, with no bombs
    where there are the questionmarks, and three for each one of the other
    two, with a bomb in the place of one of the questionmarks.
    So, (0,1) and (2, 1) have a probability of 1/7, while (1, 0) and (1, 1)
    have a probability of 3/7.
    By the way, you can infer the probability for '?' subtracting from the
    total number of mines the probabilities that you calculate and dividing
    evenly the outcome; in this case, (2 - 2 * 1/7 - 2 * 3/7) / 3 = 2/7.

    This kind of improved accounting could be accomplished by giving a
    weight to each consistent solution which is equal to s! / (m! * (s-m)!),
    where s is the number of squares that I'd mark with a '?', and 'm' is
    the number of remaining mines.

    This kind of solution leaves you with some headaches if you want to
    combine it with the optimization proposed in point (1). This is left as
    an exercise to the reader. :)

    While (2) was a bit complicated, (3) looks to me as a nightmare ;-) :
    the value you're really interested for each square is not the
    probability of finding a mine when discovering it, but the probability
    of finishing successfully the game if you "click" it. Exploring all
    possible game outcomes looks pretty unfeasible, so you need an
    heuristics for this. The probability of going "boom" in the next step is
    of course a good idea :), but you can consider, as someone else
    suggested, taking into account also the closeness of a subfield for
    which you have some information. Another idea could be the number of
    mines you could immediately identify, or squares that you could
    immediately reveal, after discovering that square.

    By the way, something that could be revealed by experimentation: which
    is the best square to click as a first move? We can simulate many games
    starting by clicking some different squares, and see the percentages of
    success starting from all different parts. :)

    I hope I have been clear (I'm not a native English speaker, so please
    forgive me if not)... this problem is quite interesting, and we *have*
    to beat KMines. :)

    --
    Ciao,
    Matteo
     
    Matteo Dell'Amico, Jul 23, 2004
    #2
    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:
    951
    KeiverH
    May 7, 2005
  2. Heiko Wundram
    Replies:
    7
    Views:
    1,176
    Heiko Wundram
    Jul 15, 2004
  3. Terry Reedy
    Replies:
    2
    Views:
    447
    Heiko Wundram
    Jul 14, 2004
  4. Heiko Wundram
    Replies:
    2
    Views:
    448
    Heiko Wundram
    Jul 14, 2004
  5. Jay
    Replies:
    15
    Views:
    1,687
    Emile van Sebille
    Jul 2, 2010
Loading...

Share This Page