Somewhat OT... Computer playing Minesweeper

[John Hazen]

* Heiko Wundram <heikowu at ceosg.de> [2004-07-13 19:08]:
> Am Mittwoch, 14. Juli 2004 04:02 schrieb Heiko Wundram:
> > Anyway, as I said, I don't know if __iterConsistentFields() does what it
> > should, that's basically why I asked... And I don't know whether this
> > approach is the best approach to solving a minefield...
> 
> PS-ing myself: I can't see a better (in terms of finding the solution) 
> approach, but of course this algorithm lacks speed, as the amount of 
> consistent states can become quite large for a single field which has very 
> much scattered information, like:
> 
> . . . . . . . . . x . x x . x . . . . . . . . . . . . x . .
> . . . . . . . . . x x . . . . . . x . x . . x . x . . . x .
> . . x x . . x . . x . . . . . . x . . . . x . . . . . . 2 .
> . . . . . . . . x . . x . . . . x . . . . . . . x . . . . x
> . . . . . . . . x . . . . . . . . . . . x x . . . . . . . .
> . x . . x x x x . . . . . . . x . . . . x . . . . . x x . .
> x 2 . x x . . . . . . . . . . 2 . . . . . . x . . . . x . .
> . 2 1 3 . . x . . x x . x . . x . . . . x x . . . . . x . .
> x 2 . . x . x . . x . . . . . x x . . . . . x . . x . . . .
> . . x . . . . . . x . . . x x . . x x . . . . . . 2 . . . .
> . . . . . . . . . . . x . x . x . x . x x . . . . . x . . .
> . x x . . . . . . . . x . . x . . . x . . . . . . . . x . x
> . . . . x . . . . . . x . . . x . . . . . x x . . . . . . .
> . x . . x . . . . . . . . . . x x . . . . . . . . . . . . .
> x . . . x . . . x x x . . x . . x x . . . . x . x . . . . .
> . . . . . . . . x x . . . . . . x . . . . . . . . . . x . .
> 
> With the numbers being the only fields which were discovered so far. The 
> number of states which are possible only taking this information into account 
> already goes into the millions.

Actually, if my calculations are correct, it's 2^32, which is about 4.3
Billion.  (There are 32 undiscovered squares about which you have some
information.)

You mentioned partioning the squares that you want information about
into non-contiguous sets.  If you do this, the number of combinations
goes down (in this example) dramatically:  2^16 + 2^8 + 2^8 = 66048.

This should get you a large performance improvement.

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.)

For the larger region, things are more complex.  I'm going to re-draw
your example with each square in the large region labeled by a letter.
(To not lose information, I'll use a capital letter if there is actually
a mine there, and lowercase if not.)

> . . . . . . . . . x . x x . x . . . . . . . . . . . . x . .
> . . . . . . . . . x x . . . . . . x . x . . x . x . . . x .
> . . x x . . x . . x . . . . . . x . . . . x . . . . . . 2 .
> . . . . . . . . x . . x . . . . x . . . . . . . x . . . . x
> . . . . . . . . x . . . . . . . . . . . x x . . . . . . . .
> c D e . x x x x . . . . . . . x . . . . x . . . . . x x . .
> B 2 f G H . . . . . . . . . . 2 . . . . . . x . . . . x . .
> a 2 1 3 i . x . . x x . x . . x . . . . x x . . . . . x . .
> P 2 l k J . x . . x . . . . . x x . . . . . x . . x . . . .
> o n M . . . . . . x . . . x x . . x x . . . . . . 2 . . . .
> . . . . . . . . . . . x . x . x . x . x x . . . . . x . . .
> . x x . . . . . . . . x . . x . . . x . . . . . . . . x . x
> . . . . x . . . . . . x . . . x . . . . . x x . . . . . . .
> . x . . x . . . . . . . . . . x x . . . . . . . . . . . . .
> x . . . x . . . x x x . . x . . x x . . . . x . x . . . . .
> . . . . . . . . x x . . . . . . x . . . . . . . . . . x . .


Each discovered number shows (by definition) the number of mines in the
surrounding 8 squares.  So, we can assign a fractional mine count for
the unknown surrounding squares by (the number of mines - the marked
mines) / the number of unknown squares.

So, for example, the upper "2" assigns a,b,c,d,e,f all fractional-mines
of 2/6 = 0.3333.  And, the "1" in the middle assigns f,g,k,l all 1/4 =
0.25.

If we take the minimum of the fractional number assigned to each square
by all the surrounding exposed (numbered) squares, and sum that minimum
up for all the squares in the region, we should have a lower bound of the
number of mines in the region.  Likewise for the maximum.

So, for all the unknown squares, we find the min and max values:

        min      max
a:     0.33      0.40  (min from upper 2, max from middle 2)
b:     0.33      0.40  (min from upper 2, max from middle 2)
c:     0.33      0.33  (only upper 2)
d:     0.33      0.33  (only upper 2)
e:     0.33      0.33  (only upper 2)
f:     0.25      0.43  (min from 1, max from 3)
g:     0.25      0.43  (min from 1, max from 3)
h:     0.43      0.43  (3 only)
i:     0.43      0.43  (3 only)
j:     0.43      0.43  (3 only)
k:     0.25      0.43  (min from 1, max from 3)
l:     0.25      0.43  (min from 1, max from 3)
m:     0.33      0.33  (only lower 2)
n:     0.33      0.33  (only lower 2)
o:     0.33      0.33  (only lower 2)
p:     0.33      0.40  (min from lower 2, max from middle 2)

Total: 5.29      6.20

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.

So, using number-of-mines information, in this scenario, compared to
using just the region splitting, reduces the 66048 combinations to 8064.
6 orders of magnitude isn't bad!

I'm not sure whether the extra computations taken to reduce the solution
space are worth it, but I suspect they are.  Maybe I'll try writing my
own version, and time it (with some error-checking to see if my logic
about minima and maxima is correct).

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

-John