Article written by Sean Barrett
, in 1999
contents :
A nasty Minesweeper position
Minesweeper : logic or probability
?
An endgame tactic
Local probabilities
Resolving local probabilities conflicts
Counting arrangements
Counting unencountered mines
A final solution
Playing the game
A
nasty Minesweeper position
In this position, I know about a bunch of mines on all
the remaining fronts, but I can't quite determine where
they are. There are a few mines that might be in one of
two positions (red or blue), a cluster of mines that might
be in one of two arrangements (green), and a more complex
situation in the top left which I haven't marked explicitly,
involving the 
and the 
.
Minesweeper
: logic or probability ?
Minesweeper can be played two ways: as a game of logic
or as a game of probability.
Technically, probability subsumes logic. If you can logically
prove a mine must be in a location, its probability must
be 100%; if you can prove one cannot be, its probability
must be 0%. So probability is all you need, in some sense.
Nonetheless, you use logical deduction to detect those 100%
situations; sometimes, especially at easier difficulty levels,
that's all you need to complete a Minesweeper game; no appeal
to probabilities is necessary.
But there are definitely situations where all the logic
in the world won't save you. The 'T' situation which appears
in the bottom center of the game board above is a simple
example of this - slightly complicated by the extra nearby
mines. (The simplest scenario replaces the 
with a
and the with a 
, so that it is symmetric.)
There is no way of getting any further information about
the likely location of the one mine that remains in these
two spaces. It's a 50-50 chance - a toss of a coin. When
you find something like this, you're probably better off
taking a guess right away, rather than saving it for later
- so if you guess wrong, you won't have wasted a lot of
extra time solving the rest of the board. (I'm a completist,
so I save it for last, and don't blame myself for guessing
wrong. And, mind you, it's a bad game design that puts
the win or loss of the game on the toss of a coin.)
An
endgame tactic
One very easy endgame tactic you can use is counting the
number of remaining mines. Suppose I had resolved everything
but the bottom right section of the board. Here are the
only two configurations of mines that match the data:
Valid configurations of mines in the bottom right corner
If you reach this position and the counter says there are
only two mines left, you're done; it must be position B.
If the counter says there are three left, it's not necessarily
position A, though. It could be position B with the remaining
mine in one of the lower-right 3x3 cluster of squares.
In fact, the odds are in favor of it being B.
Local
Probabilities
If you only examine the probabilities "locally",
you can see that each of the squares in the marked mutually
exclusive groups have a 50-50 chance of being a mine. By
locally, I mean that if you have a next to two unknown
squares, each has a 50% chance of being a mine.
The bottom center situation is exactly like this: each
of squares adjacent to the unknown pair has exactly one
mine unaccounted for, so each adjacent piece of data suggests
a 50% chance. The very top left is similar:
With absolute certainty, each purple oval covers exactly
1 mine; so there are 7 mines remaining
The bottom right situation is somewhat like this as well;
each of the numbers on the "front" has one mine
unaccounted for and two squares where it might be.
If a square had one unaccounted-for mine next to it, but
three unexplored squares, each square would have a probability
of 33%; four unexplored squares would give each a 25% chance
of having a mine. If it had two unaccounted-for mines and
three unexplored squares, each would have a probability
of 66%.
Here's the "local probability" situation for
the full board:
As you can see, several squares in the top left area have
more than one probability; the unexplored square adjacent
to the & and the one adjacent to the and
the . (The one by the and the still has 66% due
to both, so there's no apparent incompatibility.)
Resolving
local probability conflicts
You should be wondering at this point what it means to
have conflicting local probabilities. One intuition is that
the bigger probability should win. For example, the square
between the and the must really be 66%. That would mean
the leftmost square that's assigned a 50% is actually only
33%, though. Or you might think you combine the priorities
somehow; perhaps the chance should be 5/6, or the average.
But none of these are really correct. The data the probabilities
are derived from aren't independent of one another, so no
direct mathematics on the probabilities is valid. The reason
a local guess of 50% is correct in the bottom center is
because it really is independent of anything else. If you
randomly constructed boards which matched all the data collected
so far, exactly half of them would have the mine in each
of the two possible locations. (Probabilty sometimes confuses
people, who have trouble knowing what rules of probability
apply in what situation. This approach is essentially a
guaranteed valid way, because it underlies the definition
of probability as predictive statistics: measure across
all possible arrangements that might have led to the current
situation, assuming each was equally probable.)
Thus, the correct measurement for the top left situation
involves looking through all possible arrangements of mines
that meet the currently collected data, and measuring which
percentage of them has a mine in the correct position.
This would be rather time consuming if we did it directly.
Fortunately, there are better methods.
Counting
arrangements
The abstract way of computing probabilities is to run
through all possible arrangements of mines, discard the
ones that don't match the data we've collected, and count
up the statistics for each possible location.
A more practical approach is to only consider the ones
that wouldn't get discarded at all. To do that, you have
to apply logic and generate all of the possible situations
that could match the current data. I already showed the
two scenarios for the bottom right; here are the possibilities
for the top left:
Valid configurations of mines in the top left corner
(As before, the double-height oval indicates that a mine
could be in either position with equal probability. I might
have listed each of these two cases separately, so there'd
be 10 arrangements, but it won't turn out to be useful.
As to the organization: the two rows (numbered '1' and '2')
are distinguished by the position of the mine in the fourth
row. The three columns are characterized by the position
of the mines in the second row.)
Now, you might be tempted to simply say "aha, there
are five cases, so we can count up the number of cases for
each possible mine location". For example, the mine
in the fourth row (by the lower-left ) is to the left
in the two cases in row 1, and to the right in the three
cases in row 2. So you could attempt to argue that it has
a 60% chance of being to the right, adjacent to the .
(This is a position that has conflicting local probabilities
of 50% and 66%.)
However, this misses an important subtlety--the number
of mines in different in some of the cases; there are
6 mines in A1, 4 mines in B2, and 5 in the other cases.
Counting
unencountered mines
Let's return to the simpler bottom right scenario to explore
this subtlety in detail.
Valid configurations of mines in the
bottom right corner
Suppose that I've completed all of the rest of the board,
and I know there are exactly three mines remaining.
One temptation might be to assume that configuration A,
with exactly three mines, is more likely. This is incorrect.
Another temptation would be to consider how many total
mines there were, and how many board squares, and to say
"what are the odds that the bottom 3x3 region would
be empty". This is incorrect. The exact reason why
this is incorrect is complex to explain, and could perhaps
be likened to the Let's-Make-a-Deal "paradox".
Suffice it to say, however, that the actual odds for this
situation are independent of the total number of mines and
the total board size.
The real answer is this: how many possible arrangements
of three mines are there that fit the knowledge I have of
the board? The picture shows two: configuration A and configuration
B. But B only has two mines. The third mine could be in
any of the bottom 3-by-3 region of squares for which I haven't
collected any data. There are thus nine variant B configurations;
I just haven't gone to the effort of drawing them out.
Thus, there are ten possible arrangements. Each of these
ten arrangements is equally likely to occur. (As mentioned
before, this is the crucial notion to understanding probability.
The odds of the computer having generated any of these cases
the first place was small, but it was equally small, because
the computer [as far as we know] was giving every arrangement
an equal chance. You are equally likely to toss ten heads
in a row as you are to throw the pattern two heads, one
tails, one heads, three tails, one heads, one tails, one
heads. You're more likely to throw a total of five heads
and five tails than ten heads, but not any particular pattern
of heads and tails. In Minesweeper, we're concerned with
arrangements of mines, which are like patterns of coin tosses.)
Since each of the ten arrangements (nine for B, one for
A) is equally likely to occur, configuration B is 90% likely
in this particular scenario!
If there were four mines left at this point, then configuration
A would have nine variants. Configuration B would have one
variant for each arrangement of two mines in the bottom
left corner; this is C(9,2), which is 9!/((9-2)! * 2!),
or 9*8/2, which is 36. In this case, configuration B is
only 75% likely.
With five mines, configuration A has 36 variants, and configuration
B has 9*8*7/6 = 84 variants; so the odds for B are just
over 66%.
With six mines, B is about 60% likely. With seven mines,
B is only 50% likely. With eight mines, B is lesslikely
than A; at this point, there are so many extra mines to
go into the remaining locations that there are fewer configurations.
Consider the worst case, where there are 11 mines remaining.
(This is extremely unlikely to occur, but if it did occur,
these probabilities would apply.) With configuration B,
all the unencountered square must have a mine; with configuration
A, all but one does--and thus there are 9 variants for
A, and only one for B.
A
final solution
In the actual board under discussion, there are 9 mines
remaining. One of those goes to the bottom center, which
has a totally independent choice that we can ignore. Therefore,
we consider the full board except for that case; there are
only eight mines unaccounted for. (I'll continue to explicitly
count the oval in the top left since it's in the picture
for the top left, just to be unambiguous.)
Any combination of a top-left configuration and a bottom-right
configuration could occur, except one of them (A1 + A) which
would require nine mines. Therefore, we have to enumerate
each of these possible configurations, and count up the
remaining mines and the unencountered squares.
Actually, the number of unencountered squares is independent:
there are nine in the bottom right and three in the top
left, so there are 12 total.
Top-left |
|
Number of mines |
Mines left |
Unencountered variants |
A1 |
B |
8 |
0 |
1 |
B1 |
A |
8 |
0 |
1 |
B1 |
B |
7 |
1 |
12 |
A2 |
A |
8 |
0 |
1 |
A2 |
B |
7 |
1 |
12 |
B2 |
A |
7 |
1 |
12 |
B2 |
B |
6 |
2 |
66 |
C2 |
A |
8 |
0 |
1 |
C2 |
B |
7 |
1 |
12 |
Thus, there are a total of 118 possible combinations.
From this you can count the number of combinations for
each of the top left and bottom right configurations independently
:
Configuration |
Variants |
Percentage |
A1 |
1 |
1 |
B1 |
13 |
11 |
A2 |
13 |
11 |
B2 |
78 |
66 |
C2 |
13 |
11 |
A |
15 |
13 |
B |
103 |
87 |
Next, I went through each square on the board and computed
its probability, by adding up the number of variants in
which it appeared, dividing by 118. (Actually, by just
adding the percentages above.) Also, on average each unencountered
square had a mine in 15 of the 118 variants (after all,
the odds that at least one unencountered square has a
mine is very high). [This can be computed by multiplying
the number of mines left by the unencountered variants,
which tells you the average number of mines on unencountered
squares.]
(Note that this doesn't show all of the information available.
For example, we know that the probability of the the two
dark green '87' squares are linked - if one is true, the
other must be. Similarly, the three pale blue '13's that
are mines for configuration A are also linked. The remaining
pale blue '13's are not linked--rather, if any one were
to be a mine, the odds of any of the remaining ones being
mines decreases.)
Playing
the game
Odds are you're not going to want to sit down and work
out all that math when you're playing a minesweeper game.
Neither did I.
I did enumerate the possible configurations in the top-left
and bottom-right. I noticed that one configuration (B2-B)
used one fewer mines than all the others. I applied the
"fewer mines means more unencountered variants"
rule of thumb (which applies roughly until the number of
unencountered-squares is less than double the number of
unaccounted-for mines), which means that configurations
that use fewer mines are much more likely.
Since there were a lot of configurations in the top-left,
determining the odds for any one square is somewhat complicated.
Therefore, I just figured that configuration B in the
bottom-right was a lot more likely, and guessed one of
the appropriate squares. (I hoped that this would allow
me to complete the bottom-right, and then armed with more
knowledge about the number of mines remaining I could
complete the top left, and I'd only be left with the center
bottom coin toss. Of course, ideally I'd pick a square
that will maximize the likelihood I'd get useful information,
but any of these guesses would have allowed me "entry"
into the bottom right corner for further data collection.)
The odds favored configuration B, so I picked a square
that had a mine for configuration A.
Eight times out of nine, I would have been right.
Sean
Barrett
