Bayes’ Theorem and Minesweeper

I suppose I must have learned about Bayes' Theorem at sixth form. In those days, maths was Pure and Applied, so I could - and did - largely avoid statistics until midway through my PhD I was roundly mocked by my future boss for not knowing what 'significant' meant. I quickly put that right.

However, I know I knew about Bayes' Theorem because of something a good friend told me while we were supposed to be working on our seditious sixth-form magazine: "If you had to pick someone to play Minesweeper for your life, it'd be Colin." I think he meant it as a criticism (his record times were far below mine, and he won many more games than I did; however, my win percentage dwarfed his.) My secret? Maths.

Thinking about it, that's not much of a secret.

When you start a game of Minesweeper on the basic level (my friend's favourite, of course), you have to find ten mines spread across a field of 81 squares. Even my pal could work out that that gave you about a one-in-eight chance of hitting a mine. But then, something you might not know: Minesweeper never gives you a mine on the first go, which is awfully nice of it.

Why you should click in the corner

Clicking in the corner is, I reckon, the best way to start. First up: you have about a 67% chance of hitting a clear square, which normally gives you plenty to work with. Your chance of getting a useless 1 is about 30%.

Clicking in the middle will leave you with a clear square about 33% of the time, and give you a useless 1 about 41% of the time. The fewer neighbours you have, the more likely you are to get a good start.

Bayes' Theorem

Bayes' Theorem - one of the few bits of progress to come out of the 18th century between Newton and Babbage - is pretty reasonable: if you want to find the probability of something when you have extra information, the updated ('conditional') probability is the probability of both things happening divided by the probability of your information.

For instance, if you want to know the probability of rolling at least a 10 on two dice, given that you've already rolled a 6, you'd work out the probability of rolling either (6,4), (6,5), or (6,6) - the only three ways of rolling at least 10 when the first die is a 6. That would be three rolls out of 36 possible pairs, making one in twelve on the top. The probability of rolling a six - the condition - goes on the bottom; that's one in six. So, you do a twelfth divided by a sixth, which is a half. In case you've given up on fractions like a fool:

$$\frac{1}{12} \div \frac{1}{6} = \frac{1}{12} \times \frac{6}{1} = \frac{6}{12} = \frac{1}{2}$$

(Really, read up on fractions. They'll make your life so much easier.)

Bayes' Theorem and Minesweeper

For example, imagine you have failed to take this advice and clicked somewhere in the middle of the screen to get a 1 - then you've compounded your error and clicked next to it to get a 2. What were you thinking? OK, well, let's figure out what you need to do next.

Minesweeper: what were you thinking?!

Minesweeper: what were you thinking?!

What you've now done is split the world up into four distinct types of cell: you've got three cells (marked A) next to the 1 but not next to the 2; three other cells (marked B) next to the 2 but not next to the 1; and four cells (marked C) next to both of them. Oh, and you have 69 other cells that aren't next to either.

You've also got two possible scenarios: either there's a mine in zone A and two in zone B, (leaving 7 elsewhere) or there's a mine in zone C and one in zone B (leaving 8 elsewhere).

Look, here's a table showing the probability of hitting a mine if you pick a random cell in a given zone in each situation:

Cell type ABB BC
Zone A $\frac{1}{3}$ $0$
Zone B $\frac{2}{3}$ $\frac{1}{3}$
Zone C $0$ $\frac{1}{4}$
other $\frac{7}{69}$ $\frac{8}{69}$

One thing jumps out: you definitely don't want to click in zone B. You have at least a one in three chance of dying if you do; zone A is definitely a better proposition than zone B in either case. However, the other choices aren't as clear-cut: clicking elsewhere is about 10% in either case, and zones A and C are both fairly low probabilities - depending on how likely the two situations are, either of them might be a better bet than clicking randomly elsewhere.

Why, hello Reverend, nice to see you!

What we have here are conditional probabilities: the 1/3 next to the A is $P($ A1 is a mine $|$ setup is ABB $)$, for instance. You can write that as $P(A1 | ABB) = \frac{P(A1 \cap ABB)}{P(ABB)}$, and rearrange it (and the same thing for its friend) to get:

$$P(ABB) \cdot P(A1 | ABB) = P(A1 \cap ABB)$$
$$P(BC) \cdot P(A1 | BC) = P(A1 \cap BC)$$

Since ABB and BC are mutually exclusive (they can't both happen) and exhaustive (nothing else can happen), $P(A)$ is just $P(A1 \cap ABB) + P(A1 \cap BC)$ - which is a the average of the two probabilities, weighted by the probability of each situation.

Which is the problem, of course: we don't know how likely either situation is! Yet, at least.

Luckily, Impala the Koala is brilliant at combinatorics and can work this out without Bayes' Theorem. What's that you say, li'l buddy? ABB is a $\frac{3}{7}$ shot and BC is $\frac{4}{7}$? Thanks, that's really helpful - have some eucalyptus!

That means we can work out the probability of dying if we click in any of the zones:

$$P(A) = \frac{3}{7} \cdot \frac{1}{3} + \frac{4}{7} \cdot 0 = \frac{1}{7} \simeq 0.143$$
$$P(B) = \frac{3}{7} \cdot \frac{2}{3} + \frac{4}{7} \cdot \frac{1}{3} = \frac{10}{21} \simeq 0.476$$
$$P(C) = \frac{3}{7} \cdot 0 + \frac{4}{7} \cdot \frac{1}{4} = \frac{1}{7} \simeq 0.143$$
$$P(other) = \frac{3}{7} \cdot \frac{7}{69} + \frac{4}{7} \cdot \frac{8}{69} = \frac{53}{483} \simeq 0.110$$

This supports the idea that B is a really bad move (you're almost 50-50 to die); A and C are just as likely as each other to contain a mine, but clicking elsewhere is slightly more likely to leave you alive.

(Final aside: no, those probabilities don't add up to 1. They're not mutually exclusive - there are definitely mines in both B and other, so there's no reason they should add up to 1.)

* Edited 2015-03-13 to fix a counting error (thanks to Stefan Kremer for spotting it!) and a LaTeX error.

Colin

Colin is a Weymouth maths tutor, author of several Maths For Dummies books and A-level maths guides. He started Flying Colours Maths in 2008. He lives with an espresso pot and nothing to prove.

Share

4 comments on “Bayes’ Theorem and Minesweeper

  • Joe sweetsox

    Any hints on how impala the koala found p(abb), p(bc)?

    • Colin

      He’s declining to say! (Or in other words, he whispered the answer to me four years ago and I’ve absolutely no recollection of the detailed working he showed me at the time). I would imagine he worked out the probability of the remaining 69 squares having either seven or eight mines in them, but I’m afraid I don’t know the details offhand. I’ll have a think and see if I can reproduce his work!

      • J

        For P(ABB) and P(BC) count the number of patterns, I get 9 configurations for ABB and 12 for BC, so P(ABB) occurs 9 out of 21 configurations.. and P(BC) occurs 12 out of 21…maybe?

        • Colin

          That seems plausible!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Sign up for the Sum Comfort newsletter and get a free e-book of mathematical quotations.

No spam ever, obviously.

Where do you teach?

I teach in my home in Abbotsbury Road, Weymouth.

It's a 15-minute walk from Weymouth station, and it's on bus routes 3, 8 and X53. On-road parking is available nearby.

On twitter