Somewhat OT... Computer playing Minesweeper

[Matteo Dell'Amico]

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