Some days ago, I started playing the classic gimmick Minesweeper included in Windows. After some success on the Beginner and Intermediate levels, I decided to change to the Expert level, where I’m constantly failing. My impression is that there are situations where pure luck is involved, i.e. it’s not possible to detect a square I know, for logical reasoning, to be “safe.” Of course it’s constantly so at the beginning of each game, when you simply click around on the board trying to find clues for continuing; but those situations where you can have good or bad luck because you just don’t know for sure how to go on seem to appear on the Expert level even towards the end of the game, unlike in the two easier levels. Is that just my impression based on frustration after losing a dozen games in a row, or does luck actually play a role so much more important on the Expert level?
Yes, luck certainly comes into it. Quite often, you’ll end up with two ‘cornered’ squares, and it’s not possible to determine which has a mine.
In my experience, the end-game is luck. I have never hit a mine on the first square I chose, so I think that the first one is ‘free’. The second square is luck, since all you know is that there is a mine (or are mines) adjacent to the square. Depending on your first move and the number it shows, the subsequent choices may not involve luck. However, I usually come to a point where the remaining squares have a 50/50 chance of holding a mine and there is no logical way to determine which are safe. That’s what I don’t like about Minesweeper. At the end, it comes down to luck.
As your field of possible moves decreases, you eventually get into a position where you can algorithmically determine that there are two possible layouts for the remaining mines. You have no way to determine which is correct, so you pick one at random. 50% of the time you will be right, and play continues.
You then reach a second such situation, and again you choose randomly. 50% of the times that you reach this point (ie: only 25% of all games) you will choose correctly.
If you get a third such random situation, your chance of winning the game is thus only one in eight, if you reach a fourth, then one in sixteen, etc.
So, yeah, luck plays a part.
Luck is more important in the Expert level because there is a higher mine density.
Beginner: 1 mine every 8.1 cells
Intermediate: 1 mine every 6.4 cells
Expert: 1 mine every 4.8 cells
With a higher mine density you are more likely to encounter a situation where logic can’t help and you need to rely on luck.
IME, it’s very rare for luck to be a significant factor on the intermediate level, let alone the beginner.
Well, the first square you click is always pure luck, but I don’t think that’s what you were asking.
I was also interested to note that Minesweeper has been proved NP-complete - http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm - does this have any bearing on the question?
The expert level usually has a great deal of luck. I have gotten lucky and with the first pick opened up vast tracts of squares and could deduce every mine. It’s the first few picks that make a quick loss or a playable game. If the first square is “1”, I’ll pick an adjoining square for pick 2 since you have a 7/8 chance of being right. If the first pick is “3” or worse, I’ll take the second one far away and take an unknown chance. But many times there will be situations where you simply cannot deduce.
I generally get no such situations in intermediate.
I’ve been playing Minesweeper regularly for six years now, and I’ve never clicked on a mine the first time. I don’t think it’s possible.
Hmm…All NP-complete problems are decidable, so that may factor in here. However, that would only mean that you can play it so you don’t need luck, not that you can’t play it so that you don’t need luck.
Mind you, the first time or casual player often doesn’t recognize some of the more involved logic - the sort of situation where “there’s 4 next to this square, 1 is marked, therefore there are two in the remaining three squares, 2 of which also happen to be next to something with 1 mine. One of those two has to be a mine because of the 2 out of 3, therefore I can eliminate all the other neighbors of the 1 square.” That said, yeah, with sufficient mine density, you are likely to come down to a point where no amount of logical inference allows you to click something with certainty.
Just go to a Custom configuration–I think for an n x n grid, the maximum allowed number of mines is (n-1)^2, but for a 16x16 grid, that’s 225 mines. Then click. You’ll see that the mine configuration is set after the first click.
Excuse me, I meant to say “3 MINES next to this square”, not 4. I was picturing a case where there were 4 squares next to something with three mines, 1 known mine, and two of those three remaining bordering another square known to have 1. It’s easier to SEE these cases than describe them in English.
That probably varies with the particular implementation of the game.
OK, I checked around. What was actually proven NP-complete is the Minesweeper consistency problem, which takes as input a given set of squares–hidden, clear, or numbered–and decides whether there’s a mine configuration that’s consistent with that layout. It does not tell you where the mines are, so despite Dr. Kaye’s assertions to the contrary, it’s not exactly equivalent to playing Minesweeper.
You’re kidding right?!?
O sure, I was talking about the Minesweeper that came with my Windows. The one on my linux machine changes the configuration after every click to make sure that you always end up with a non-determinable situation. And then it always makes you lose. Frustrating.
No.
HHmmm…after experimenting, it seems you’re correct, although I could have sworn I remembered clicking a mine on the first time. Oh well. I guess that makes sense. I mean, would you want to play a game that declares you the loser on your first move?
In my extensive Minesweeper experience, the only time I’ve seen a first-click mine is the time I tried out the ‘Minesweeper Cheat Code’ - the code basically toggles a single pixel’s color when your cursor is over a mine, so the game has to generate the layout before you click for the first time.
In the card game “Cruel”, also distributed with some Windows versions (though not nearly as ubitquitous as Minesweeper), it’s possible for the initial deal to be completely unplayable. As in, you’ll hit “New Game”, and it’ll immediately tell you “Game over, 48 cards remaining”.
A couple of examples, by the way, for a pure-luck situation:
First of all, in a corner:
??1
??2
12F
(? is an undetermined square, the numbers mean the same thing as in the game, and the F is a flagged mine)
Assuming that I have two mines left to be found, they could be the upper-left and the lower-right, or the upper-right and the lower-left of the question marks. However, if I have only one mine unaccounted for, or three (and this is the only unknown part of the board), then this is solvable: If there’s only one mine left, then the lower-right one is the mine, and if there’s three left, then the lower-right one is safe. Of course, this can happen in any corner.
Another common one is on an edge:
FFF
3?3
1?1
Here, I have no way of knowing, regardless of how many mines are left.
And occasionally, you’ll even get a more complicated one, like so:
FFF
3?3
1?1
1 1
1?1
1?1
1 1
1?1
1?1
Here, I know that one of each pair of question marks is a mine, but I don’t know if it’s the three top ones or the three bottom ones. Once I make my guess, though, I’ll be able to get all of them (or, of course, I’ll die).