This being a mathematics blog, I’m sure a lot of readers out like to play Minesweeper. I’ve just obtained a personal best today (94 seconds on expert level) which, as Minesweeper buffs know, is nowhere close to world-class levels, but which made me happy anyway, as I’d never broken into the double digits before today!
It seems to me that world-class competitors must know some tricks with the mouse which I’ve never bothered to master, particularly because my laptop doesn’t have a mouse but rather a touchpad. This being the case, I keep my right index finger on the touchpad to guide the cursor, and the left index finger to click. I always left-click: that is, in my style of play, I [practically] never flag squares for bombs; I click only on non-bomb squares. For it’s well-known, or at least it should be, that the program doesn’t care if you identify where the bombs are — you get full credit for only identifying all the numbered squares.
To play in this style well, one needs to be fluent in a number of tactical tricks, which I don’t have good names for, but which in my personal argot I call things like “1-2-1″, “1-2-2-1″, “rule of three”, to name just a few. But that’s not what I set out to discuss, really. What I’d really like to hear from good players is: what opening strategies do you use?
The personal best I just set came after deciding on a new opening strategy. What I had been doing is clicking along border squares. Under that strategy, one could of course just keep clicking until one opens up an area, but often I would add to that the observation that if one clicked on a 1, thus leading to, e.g.,
x 1 x (–> border row)
x x x
then one could then click on the non-border square just adjacent to the 1, with only a 1 in 5 chance of setting off a bomb. If one then hits another 1:
x 1 x
x 1 x
x x x
then one can immediately open up the line of squares on the third rank, leading to a configuration such as
x 1 x
x 1 x
1 1 1
or better. This is often a cheap and quick way of opening up squares or otherwise getting a tactical toehold.
The new strategy I began using today is not to click along the border, but to click along the ranks or files adjacent to the border. Under this strategy, if one lands on a 1, leading to
x x x (–> border row)
x 1 x
x x x
then one can click on the border square adjacent to the 1, with only a 1 in 8 chance of setting off a bomb. If one does not set off a bomb, that square has to be a 1:
x 1 x
x 1 x
x x x
and then one can proceed as before. So I’ve just lowered my odds of hitting a bomb, plus a very small fractional gain in processing time that comes with the certain knowledge that it’s a 1 if not a bomb. So far the strategy has paid off well!
I’d like to hear other people’s opening strategies, and also I’d like to know some statistics. For example, considered over the space of expert-level games, what is the probability of getting a 1, a 2, and so on? Does anyone know? (It seems this would be very difficult computing analytically — one is probably better off using a Monte Carlo simulation. But I don’t have the wherewithal to set that kind of thing up.)
22 comments
Comments feed for this article
March 6, 2009 at 10:13 am
Vishal Lama
Having never played Minesweeper before – an embarrassing admission, I acknowledge – but encouraged by your post, I decided to test my skills in this game, following which after numerous attempts (don’t ask how many) I too obtained an awesome personal best: 78 seconds [Edit: 54 seconds!] at Beginner’s level! This was achieved without even using your much-touted ‘opening strategy’. I am now convinced that I am the future world-champion in this game!
Jokes apart, the one among many interesting aspects of this game, to me, is its connection with the ‘P=NP?’ problem. A little bit of googling revealed that Richard Kaye’s original paper, titled Minesweeper is NP-complete, published in The Mathematical Intelligencer, establishes exactly what the title reveals. I think I am going to spend some time reading the article.
March 7, 2009 at 2:01 pm
Todd Trimble
Yes, to some extent the NP aspects justify all my time spent playing Minesweeper: perhaps by playing enough, I’ll find a way to solve P = NP!
Mathematicians ought to love this game. There are many tiny lemmas that one has to have mastered as automatic subroutines in order to play quickly. Here’s one that comes up very often: if you have
0 0 0
1 2 1
x x x
then you can immediately clear the middle x (it’s not a bomb); the other two x’s must be bombs. This has evident corollaries: this situation is “isomorphic” to, for example,
1 b 1
2 3 2
x x x
where ‘b’ denotes ‘bomb’. This is the 1-2-1 lemma I referred to earlier.
The 1-2-2-1 lemma is where one has
0 0 0 0
1 2 2 1
x x x x
where this time one can deduce that the middle two x’s must be bombs, and you can clear the x’s on the ends. This again has immediate corollaries, e.g., it is isomorphic to, for example,
1 b b 1
2 4 4 2
x x x x
I’ll give two more. Very often, after opening a large area, one has a row of 1’s, so that one may have for example
0 0 0 0 0 0 0
1 1 1 1 1 1 1
1 x x x x x x
x
and the observation here is that the third x in the row in front of the 1’s cannot be a bomb [if it were, then neither of the x's before it could be a bomb, and this leads to a contradiction], so one can clear it, leading to e.g.
0 0 0 0 0 0 0
1 1 1 1 1 1 1
1 x x 2 x x x
x
and then by the same reasoning, one can clear the third x to the right of the 2 (or whatever was just cleared), because it can’t be a bomb either. So, one just counts by threes and clears those squares. This is what I call the ‘rule of 3′. This rule applies particularly often to the third rank or file away from an edge.
Last one: if one sees
0 0 0
1 1 1
x 1 x
x x x
one can automatically clear the three x’s ahead of the 1, leading to, e.g.,
0 0 0
1 1 1
x 1 x
1 1 1
because none of those x’s can be a bomb (proof left to reader). An easy corollary is that if one sees, e.g.,
0 0 0
b 2 1
x 2 x
x x x
then again one can immediately clear the row of x’s.
These are just a few of many tricks that one can discover. My repertoire of such lemmas is large enough now that I just about never feel the need to flag squares for bombs, because I know how to play around them, and it’s now largely unconscious — my fingers automatically know what to do.
March 7, 2009 at 11:00 pm
Henry Wilton
After playing Minesweeper for long enough, I often end up wishing that it were different. Specifically, I wish it encoded the “isomorphisms” Todd described above explicitly, as follows: if you mark a bomb (shurely a mine, not a bomb?), then the interface should subtract one from each neighbouring numbered square. If this brought some squares down to 0 then it should click on them automatically. I daresay this game wouldn’t be very entertaining, but the realization that a huge proportion of playing Minesweeper consists of performing these mind-numbing subtractions rather spoiled my fun.
For what it’s worth, my opening strategy is usually to click near a wall. If I get a 1, then I click near that, and hope for another 1, which gives the following pattern:
x 1 x 1 x
x x x x x
In this case, you can clear all but the middle two squares. Which is nice. It seems obviously worse than Todd’s second strategy, though.
While we’re on the subject of games that mathematicians should like, for me the winner’s got to be cryptic crosswords (I’m talking about the genuinely cryptic sort here, not American ones). Solving a cryptic clue is, for me, the activity most similar to proving a theorem.
March 7, 2009 at 11:43 pm
Vishal Lama
Henry,
When you mentioned “non-American” cryptic crosswords, did you mean something of this sort?
March 8, 2009 at 1:16 am
Todd Trimble
I love all crosswords: British, American, what have you. I also like constructing them myself.
Did you know that one of the methods used to select cryptologists (in the code-breaking sense) for Bletchley Park during World War II was via timed cryptic puzzles? I was once sent one of those puzzles by a Brit I know: the allotted time was 12 minutes. [It wasn't particularly well constructed in my opinion, but perhaps that's sour grapes on my part, since I wasn't very close to 12 minutes in my solution time.]
March 8, 2009 at 2:33 am
Vishal Lama
Todd,
Here’s one for you: Initially, this man was not quite even, but later he turned thin-and-fit and sounded almost like a “ball”! (4, 7)
March 8, 2009 at 3:45 am
Todd Trimble
Oh you devil. “Todd Trimble”. Ha ha ha!
March 8, 2009 at 4:34 am
Vishal Lama
Ha ha ha! What took you so long?!
March 8, 2009 at 2:18 pm
Henry Wilton
Indeed, several cryptic clues feature in Robert Harris’ Enigma, for exactly that reason. (I’d recommend that book to any crossword-doing mathematician who hankers after a thriller whose hero he can identify with!)
My impression (and I’m no expert) is that styles have changed quite a lot since then, so I’m not surprised that the one you did didn’t seem “particularly well constructed”.
Actually, it may have been unfair of me to label cryptic crosswords “non-American”, as I’ve heard a rumour that the New Yorker sometimes carries one. But I’ve never managed to locate it.
March 8, 2009 at 4:46 pm
Todd Trimble
I’d heard of that book, Henry, and now I think I’ll check it out.
Part of my difficulty with that 1942 cryptic could be attributed to being on the other side of the pond for one thing, but I think you’re absolutely right about big changes in style over the decades. This is also visible in American crosswords: I’m working through a large collection of puzzles from the Eugene Maleska era of the New York Times, which are markedly different in feel from those of the present Will Shortz era. IMO there has been a general improvement in the art of crossword puzzle construction.
Yes, The New Yorker carries a cryptic crossword from time to time. The Nation also has one in each edition (but I don’t think it’s all that hot) — at least it did when I was a regular subscriber.
March 11, 2009 at 7:13 pm
Scott Carnahan
I used to play minesweeper without flagging, but I have found that with a multibutton mouse, it is somewhat more efficient to use the “clear the neighborhood” functionality, either simultaneously clicking both left and right buttons (in Windows – you can often hold one button down and click the other), or clicking the middle button (in Unix).
March 11, 2009 at 7:35 pm
Todd Trimble
You’re right, Scott, and such tricks are seemingly mandatory for one to have a prayer of getting times of, say, under a minute. The mouses (mice?) I have in my house are crap, though, and I’ve not developed the chops in using that functionality efficiently. That would be next on my minesweeper agenda; I doubt there’s much left for me to learn on the intellectual level.
March 18, 2009 at 4:03 pm
Kea
Ah, brings back memories. Many years ago, I used to get insanely good scores when I played minesweeper instead of working in my hated job as a -yuk yuk yuk- quant.
March 20, 2009 at 1:11 am
notedscholar
Interesting post! When I play Mind Sweeper (not often), I typically mimic a well-known investing strategy called “technical analysis.” It doesn’t seem to work that well. I think I’ll try your more rigorous approach!
(Then again, I play so rarely that it’s unlikely I’ll ever be able to improve)
NS
March 29, 2009 at 1:08 am
RaiulBaztepo
Hello!
Very Interesting post! Thank you for such interesting resource!
PS: Sorry for my bad english, I’v just started to learn this language
See you!
Your, Raiul Baztepo
April 1, 2009 at 6:10 am
Martin
Hi!
And let me ask the other readers: Do you all try to win as many games as possible?
Interesting! Your target seems to be to lose as few games as possible.
I took “the” other approach: I try to optimize my personal best, and so my approach for the start is a “boring”, but more successful one for this goal: I click a number of times until I feel I have a good starting position, for example until many squares open up with one click. (Surely this leads to losing many games.) Please let me know if this is morally inferior to your approach
April 1, 2009 at 7:07 am
Todd Trimble
Martin: I often wonder about this very point. Putting morals aside for the moment, one defense might be that it’s hard knowing at the very beginning of a game if the overall configuration one is dealt is really a good one, even if the first substantial opening may seem really good. So my approach is in a sense to maximize my chances of finding out.
But putting morals back in: you’re right, I’m not in it just for the time. (I mean, if that were the case, then there would be no point in continuing a game once I go over my personal best!) I do always try to complete the game, even if it means I sometimes have to think hard in some situations and rack up the seconds — it gives me pleasure to figure them out. And I studiously avoid looking at the clock.
April 25, 2009 at 8:46 pm
Gil Kalai
Congratulations. 94 looks amazing to me. There is a paper on the mathematics of minesweeper game:
ELCHANAN MOSSEL (2002). The Minesweeper Game: Percolation and Complexity. Combinatorics, Probability and Computing, 11 , pp 487-499
April 26, 2009 at 2:34 pm
Todd Trimble
Thanks, Gil. I think the world record is something like 37 seconds (!), so 94 seconds would have to be considered a modest achievement, but perhaps pretty good after all considering I don’t take advantage of the functionality pointed out by Scott. [AFAIK it's still better than J.K. Rowling's best
]
I looked at the paper by Mossel, which seems amusing and clever although I don’t know anything about percolation theory. Here is a link for anyone who’d like to take a look. I think anyone who’s played Minesweeper can quickly understand at least the statements of the theorems (and somewhat less quickly if they haven’t!).
April 26, 2009 at 6:09 pm
Vishal Lama
Aww, c’mon Todd, you can never beat that world record! You should give up playing minesweeper!
April 26, 2009 at 7:12 pm
Todd Trimble
Yes, you’re absolutely right.
How’s your chess game these days?!
April 26, 2009 at 7:21 pm
Vishal Lama
Oh, you hurt me!
