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 '5' and the '6'.

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 '2' with a '1' and the '5' with a '3', 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.)

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:

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

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 '1' 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:

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 '2' & '6' and the one adjacent to the '3' and the '5'. (The one by the '5' and the '6' still has 66% due to both, so there's no apparent incompatibility.)

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 6 and the 2 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.

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:

(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 '1') 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 '6'. (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.

Let's return to the simpler bottom right scenario to explore this subtlety in detail.

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

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 *less*likely 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.

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

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.

[ HOME ] [ ]