Somewhat OT... Computer playing Minesweeper

[Heiko Wundram]

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.