# Odds of winning at minesweeper with perfect play

How would someone go about doing this? Assume that the first "click" will never be a bomb, and that the number of mines and the area are both known. Rather hoping there is a clever way to do this, but I will not be so surprised if there isn't.

EDIT: I would assume (though without any real proof) that a program could be written that could solve minesweeper in linear time (as the board gets bigger linearly, if the mines/area ratio stays the same).

It would seem to me that in general no more than 9 blocks need to be considered (the high end of what i've see playing minesweeper at expert) to determine if

1. its a mine
2. its a safe square
3. the odds that its a mine

That would support my earlier assertion.

EDIT 2: This would also seem to contradict the fact that minesweeper is NP complete, and with probably not so much work one (maybe even I, but probably not) could write an algorithm that can play a perfect game of minesweeper that would have a linearly increasing runtime which would contradict (summery of) the paper here. So I guess this raises the next question which is: where is the flaw in my logic?

EDIT 3: I really am more interesting in the odds than in the algorithm to solve minesweeper. And it would be helpful to me if someone could explain why the number of checks/tests/calculations one has to do does not rise linearly with respect to area.

-
This might be of use to you. I've not read it personally. web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm – Austin Mohr Jun 1 '11 at 3:13
Its very interesting, but since I want to know a simpler piece of information (what are the odds, not what algorithm will get me those odds) is it possible? – soandos Jun 1 '11 at 3:20
@saondos: I have deleted my answer. I apologize for the oversimplification. – JavaMan Jun 1 '11 at 3:27
@DJC not a problem, every piece of input is appreciated. – soandos Jun 1 '11 at 3:32
I can't see why picking the square least likely to contain a mine should be the best play. It might be that some other square is more dangerous but (if you survive) more likely to give information allowing you to proceed without guesswork. – Chris Eagle Jun 1 '11 at 9:05

I am a very good minesweeper player, and I can say that perfect play can get you to win in $99\%$ of the easy ($8\times 8$ with $10$mines) or intermediate ($16 \times 16$ with $40$ mines) levels. In the expert level ($16 \times 30$ with $99$ mines) it becomes harder to win without making any guesses.

About first click not being a mine, this is obvious, since the mine positions should be generated after your first click, and I think this is the case in the known minesweeper games.

Although, perfect play is not enough, if the distribution of mines is completely random. For instance, I encountered many times the following configuration in a corner of the board $\begin{matrix} O& X & M \\ M & M & M \end{matrix}$, where $0$ is free square, $M$ is a marked mine, and $X$ is an unknown mine. Imagine this configuration in the upper left corner of the table, and the counter says that there is only $1$ mine left. You would have to guess and have only $50\%$ chances of winning, since there is no clue as to where the mine is.

About implementing an algorithm of solving minesweeper games with perfect play, there are some things you should consider, since some of the mines are not always obvious to find. I have in mind a few steps when I solve minesweeper games:

• first mark the obvious mines;

• open the safe squares;

• look for some patterns learned before (e.g. $1-2-1$ or $1-2-2-1$);

If at one point, none of these steps can be applied, you can only guess the next step. Considering probabilities, is not very conclusive, since the values would be relatively close to $50\%$.

-
 So how many of those configurations can there be, and what are the odds of getting out of them is the question – soandos Jun 1 '11 at 9:13 I played a few games today, and in the expert level, it's almost inevitable not to reach these situations, and in most cases its a mine out of two squares, i.e you have to guess with probability $1/2$ what is the mine. These configurations can appear in numerous ways, and you can't devise an algorithm for guessing. That is exactly what I said in the answer: if the distribution of the mines is arbitrary, no perfect play is sure to win. – Beni Bogosel Jun 1 '11 at 9:20 Thanks the kind of thing i was looking for. – soandos Jun 1 '11 at 9:24 Its always the beginning and the corners that get you. If your first click is near at least one mine every strategy is going to have to start guessing, which destroys any hope of a perfect play strategy. Now if you were interested in speed instead of accuracy... – Joshua Shane Liberman Jun 1 '11 at 12:49 @Joshua perfect play can mean making guesses. Thats the point of the question. What are the odds that you will win (not 1, as some guessing may be required)? – soandos Jun 1 '11 at 19:12

You need to consider more than the 8 surrounding blocks sometimes. As an exercise in computer AI, we were asked to implement a minesweeper agent.

On the boundary between solved and unsolved squares, one might need to consider every possible combination of solved/unsolved. Consider following example:

The boundary consists of 15 squares. Thus, there are $2^{15}$ possible ways to distribute mines here. However, the numbers on the known squares adjacent to the boundary will impose severe conditions, so maybe only 10 of these are compatible with the numbers. If square x is a mine in only 1 of these 10 cases, we should guess that it is safe, if the given mine density is greater than one in 10. Or, even better, square x is never a mine in any of the possible cases, and we have a safe bet. However, there are certainly examples where you actually NEED to do this kind of computations, (considering the boundary of the solved squares) to do this kind of things, and this is exactly what one does to show that minesweeper is NP-complete.

Example: Consider the series #1#1#1# of squares, where # is unknown. Every other unknown must be a mine, so the probability that the first and last unknown square is not independent. The first one is a mine iff the last one is a mine. From here, you can construct problems that emulates 3-SAT or similar.

-
 That would seem to simplify the problem, not make it harder... Btw, the nine I was talking about are on the boundry, it would make zero sense to consider a 3x3 square. – soandos Jun 1 '11 at 6:32

I would leave this as a comment, but I don't have the reputation. This is my take, which is a bit different, but not so much, from the other posters.

Part of the problem is that simply picking the square with the lowest probability of a mine being present isn't always perfect play. After each click, you typically have new information about the position of the mines, which helps the algorithm. A square with a low chance of a mine but also a low chance of providing new information might not be as good a choice as a slightly riskier square which nets a large amount of information. The algorithm you design has to also factor in the expected value of that information (which in turn depends on the information potential in the new state as well as how risky it is), and somehow compare the options based on both the information content and the riskiness. There isn't, as far as I can see, an easy way to do this.

One way to get around this, for a particular board size, is to create a table of all the possible positions and do some preprocessing on that. In practice, this only saves you time if you want to play A LOT of games, and even then the memory requirements are probably impossible even for a relatively small board.

-
I am not looking for the best possible algorithm. I just want to know the odds of winning perfect play. Not how to win with the least total computation and the fanciest heuristics. It think it got sidetracked – soandos Jun 1 '11 at 6:42
I don't see any reason why that should be significantly easier to compute than an actual algorithm. It seems to me that the problems arising when attempting to create an algorithm should also arise in any attempt to compute the odds of winning with perfect play in some form. I'd be happy to be proven wrong, though. – TheBlaarg Jun 1 '11 at 7:11
Because the only thing that matters is how many unsolvable (need guessing) configurations are there with n mines in m space and what are the odds of solving them. – soandos Jun 1 '11 at 7:14
I don't see why there should be a simple connection between the odds of solving a particular configuration and the odds of a particular square being a mine. How can I compute the odds of a particular configuration of mines being solvable given only the odds of each square being a mine? This may be exactly what you are asking. In any case, it seems to me a very difficult problem for all but the smallest cases. – TheBlaarg Jun 1 '11 at 8:18
It is not clear to me that one can not calculate the odds of winning with perfect play unless one also has an algorithm for perfect play. If an area of mathematics has a well developed theory then, in that area, an algorithm-free calculation of odds might be possible. To the best of my knowledge minesweeper does not have such a theory. – Jay Jul 15 '11 at 16:32
show 1 more comment

Considering an Expert board is randomly generated and your only "help" in winning is that the first click you are guaranteed not to lose (since the board is set only after your first click), there is no set odds of winning. I just played an Expert game that came down to 4 separate 50/50 guesses, giving me a 6.25% chance of winning after playing 8 minutes of "perfect strategy." I managed to get 1 right and failed on the next guess. Minesweeper does help keep your logical reasoning skills up for a while, but Expert games almost always come down to multiple, unavoidable coin flips.

-
Right, but if you could count the average number of such coin flips, you'd have the odds of winning. – Nate Eldredge Jul 16 '11 at 13:49