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

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

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.

Answer 5

Many years ago as a programming exercise I wrote a Minesweeper emulation/solving program in Business Basic and I am currently doing the same thing in Java. My current version wins approximately 40% of games on runs of 1000 games at expert level (16x30 with 99 mines and guaranteed clearance on the first click). When it comes down to having to guess, I'm just doing it randomly, I expect I can boost the percentage when I figure out how to make smarter guesses. Unfortunately, though, my algorithm is decidedly NOT linear. Basically, I have an array of objects that I call "facts". For example, if I click a cell on the board and don't hit a mine, I create a fact containing the number of minimum and maximum number of mines adjacent to that cell and the numbers of the cells adjacent to that cell. AS you mark or clear a cell you adjust the counts in the facts containing that cell. You can make a lot of progress just by looping through the facts looking for obvious marks or clears. When you can't find more marks/clears that way, compare each fact to the other facts and look for interactions. For example if "Fact 1" says that 1 of cells 1 and 2 is a mine, and "fact 2" says 1 of cells 1, 2, and 3 is a mine, you can deduce that cell 3 can be safely cleared. Once you've tested every possible combination of 2 facts (which is the non-linear part) then you have to resort to guessing. And of course even if comparing 2 facts does not give you a definitive mark or clear, you can sometimes create a new fact that will be useful in future comparisons. For example, if "Fact 1" says there are 2 mines in cells 1,2,3,4 and "fact 2" says there are 2 mines in cells 1,2, and 5, you can safely create a new "fact 3" that says there is a minimum of 1 and maximum of 2 mines in cells 1 and 2.

Playing manually I get about 31% wins at expert, I'd do better but for occasional mis-clicks :)

Answer 6

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?

Answer 7

Having played Minesweeper on and off since Win 95 was young, I'm convinced that the game is cheating nowadays. Before Win Vista you could occasionally (perhaps once in 20 attempts) get a very promising start just by clicking around three or four times before starting to solve the board in earnest, thereby clearing very large areas almost instantly. But nowadays the mines are rather evenly spread out over the whole board. I have observed three changes that affect play nowadays:

1 You will never encounter an easy board. 2 However, you will rarely encounter a really impossible board, either. 3 You can no longer hope to clear the board anywhere as quickly as you could before Vista. (My best true score (i.e. without peeking/restarting) under Win 7 is 172 s, my best score under Win XP was 84 s. And no, I have no proof to back up that claim. My cat "extinguished" that computer for good.)

Yes, there will (almost) always be at least one or two 50/50 guesses, typically when you have one or more sets of two mines in a 2x2 Square. But you will rarely find more than half a dozen such situations at a time. I really thought this was always so, but after playing about 2500 boards, I encountered one that didn't require any guesswork at all. Of course, I have very likely missed several others before that, by triggering a mine by mistake. After all, I am always going for speed-play.

Anyway, results aside, what I want to propose is that the logic behind setup of the mines, since Win Vista is no longer random. Also, it may be deliberately biased to create those situations that cannot be solved without guessing. You can probably figure out how and if this affects your discussions.

Answer 8

So I tried writing a program to play against minesweeper. I made a minesweeper game with the usual 9x9 with 10mines or 16x16 with 40 or 30x16 at 99mines and the rule that you can never lose on the first move (the mine is moved randomly if it should be hit on first move.)

My play algorithm tries the following on each move, using the first success: 1. find easy no-mine spots (known mines=mine readouts) 2. Find spot pairs with 50% chance of a mines, make two copies of the screen, and set each copy (A or B) with the mine at one of the two location alternatives. The choice then forces other spots to be mines or not. Find all the other spots that are determined by the 50/50 selection. Branch on the three possibilities: a) position A or B cause there to be too many mines somewhere, meaning that one of the positions is impossible and the other is correct; or b) Both seem possible. On b) compare the two case results and look for spots that are open in both cases and return these as the play. This picks up things like 111 running in from an edge where the third 1 in cannot be a mine. 3. If b) occurs but there are no common open spots, search for the next 50%/50% pair and repeat 2. 4. If all 50%/50% spots fail to give a move, guess, selecting amongst the covered spots, initially requiring the chosen spots to be fully surrounded so the risk is mines/total spots in the sequence: a) corners b) edges c)rest of spots. If there are no fully surrounded spots: d) choose least likely to be a mine.

Using this algorithm I get 89.9% wins for the beginner game and 69.0% for the intermediate game. All of the losses happen on guesses. For the expert game I only win 17.9% of games.

The distribution of guesses (after the first move) for the intermediate game is in 1000 games is 0=283,1=313,2=191,3=97,4=45,5=31,6=31,7=12,8=4,>8=10 . The distribution of guesses for lost games is 0=0,1=135,2=72,3=39,4=27,5=19,6=6,7=8,8=1,>8=3. The intermediate win rate 69% is less than (90% of) what you would expect for the number of guesses= (216/256)^1.618=76.0% This may be due to ambiguous 50%/505 cases in the endgame.

For the expert game the distribution of guesses at T 3.59 guesses/game is 0=19,1=236,2=206,3=151,4=124,5=73,6=41,7=50,8=34,>8=66

It would be interesting to count how many of the losses involve guesses at 50%/50% spots - the indeterminate spot patterns. I'll work on it.

Answer 9

The only way to achieve your goal is to list all combinations of mines on the board -then consider the fact that a user can start by clicking any one of 99 squares, then consider the fact that even though the board opens a series of squares upon the first click, a user may have to make one or several guesses in mid-play, then you would have to list all such guesses in mid-play, then, with perfect play a user ends up with either a clear board or one to several guesses with a probability of 1% to 50%. I am sure such tasks is possible, but it sure would be daunting.

Instead, I wish to add to this board from a practical user perspective, having played thousands of expert level games and having seldom made mistakes of logic during play. Empirically speaking, I would assign the following probabilities: 1 of 10 games - can be solved with perfect play without any guessing 4 of 10 games - can be solved with a guess whose chance of success is 50% 3 of 10 games - can be solved with a guess whose chance of success is 25% 1 of 14 games - can be solved with a guess whose chance of success is 12.5% 1 of 14 games - can be solved with a guess whose chance of success is 6.25% 1 of 16 games - can be solved with a guess whose chance of success is 3.125%

I'm no math wiz, so, I'll leave the probability calculation to you. I find that my own winning percentage tends to hover around 36%.

Answer 10

I think a starting point is the survival for a random pick where there is no information about the spot. This is to first order the number of unmined squares over the number of squares. So for beginner at 10 mines on a $9x9=81$, a survival of a random pick is $0.87$. At Expert $99$ mines in $16x30$, the survival rate is $0.79$. Assuming perfect play, meaning all determinable mines are identified, the winning rate is the survival rate raised to the power of the number of guesses required. There is a minimum of one guess (the first move) so the upper limit for beginner games is $0.87$ and expert games $0.79$. I find that I run about $75$% success at beginner so there are about $2.06$ guesses per beginner game. This same number of guesses in the expert game gives an odds of winner of no more than $61$%. Interestingly, the best strategy is usually to avoid the points where the mine is one of two spots since there is high risk of losing but to select nearby points where odds are still $0.79$ and use the information from that to decide the ambiguous mines.

I think the case of indeterminable final regions is usually confined to edge squares because there are squares off-board that would otherwise give information. The only case I can think of inside the board would be a $3x3$ square as the core is indeterminate. Perhaps the configuration and likelihood of these indeterminate cases could be estimated. Similarly could the same be done to estimate when a guess is needed in the mid game?

Answer 11

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.