Odds of winning at minesweeper with perfect play

Question

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.

Answer 1

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\%$.

Answer 2

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.

Answer 3

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.

Answer 4

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.