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
- its a mine
- its a safe square
- 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.
Solution 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} \square& X & M \\ M & M & M \end{matrix}$, where $\square$ 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\%$.
Solution 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.
Solution 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.
Solution 4:
To answer your question, I made a simulation (with $2000$ expert games) with the IA : http://mrgris.com/projects/minesweepr/ who use several strategies to complete a game.
The result, if you have a perfect play, is $1$ game on $4$ will be a WIN and your average total accumulated risk will be $50\%$. Also, to give you an idea, $1$ game on $50$ will not required any guess.
Good game.
Solution 5:
I consider myself an expert player. I have analyzed ambiguous final board positions many times, and while a depressing number of them have terrible odds (50/50 or worse), there are some in which one or two of the covered squares have very good odds (in excess of 90% chance of no mine). Clearly, clicking these squares first is optimal (despite the claim that a "riskier" square might yield more info). Lucky for us, the Windows 7 version of Minesweeper keeps track of your win statistics. Assuming that I only fail winnable games a small percentage of the time (maybe 2-3%), you can consider my long-run win percentage as an estimate of the winnability of Expert minesweeper. My long-run win percentage hovers around 32%, or slightly less than a third of all games. I would be surprised if the true percentage were higher than 35%. Although my current record is only based on 190 games, I have played many many times this number on multiple computers since Windows 3, when I first encountered the game (yes, that is more than 2 decades of Minesweeper).
Although one of the posters claims to only get 20% on expert using a program, I would infer that the algorithm used is inferior and fails to employ sufficient logic to deduce safe squares under certain complex conditions. I have encountered board states in which a chain or cycle of dozens of squares must be considered together to discover that there is only 1 logically consistent solution. These tend to be fairly rare, but solving these correctly is essential to determining the true winnability rate.
If we exclude games which end in ambiguity and there are less than, say, 5 bombs left, then I'd say the winnability rate goes up significantly...to maybe 2/3 or so. I would really prefer the game if it could detect ambiguity and either give you a free guess every time, or simply give you a fixed number of bad guesses each game (the Windows 8 version has a mode which does this). With, say, 4 free guesses, I would say that well more than 99% of the games would be winnable.
To that end, another interesting question is: How many free guesses would be required for 100% of the games to be winnable?