39
$\begingroup$

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.

  • 1
    This might be of use to you. I've not read it personally. http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm2011-06-01
  • 0
    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?2011-06-01
  • 0
    @saondos: I have deleted my answer. I apologize for the oversimplification.2011-06-01
  • 1
    @DJC not a problem, every piece of input is appreciated.2011-06-01
  • 0
    Knowing a non 0/1 probability of a mine being present doesn't help you to solve minesweeper. That's why it's not linearly solvable.2011-06-01
  • 0
    1. It does (calculate this for all available squares. If none are zero, then guessing is a must anyway, and this way the program can pick the lowest) , and two, I just want to know the odds of it being beaten with perfect play.2011-06-01
  • 0
    And as a not so significant aside, people can do this pretty quickly with simple logic for a decently large sized board (expert) without making mistakes, so I am not sure what the author of the paper was talking about when he said all solvers are slow...2011-06-01
  • 2
    @soandos: Go to the link that Austin Mohr provided for you, and *read it*. The Minesweeper Decision Problem is NP-complete. The assumption in your first edit is simply wrong.2011-06-01
  • 0
    My question is why though. (I do know what NP means, but it would seem to me (not that means a lot) that since one only has to consider a relatively constant number of blocks to advance, then as the grid gets bigger, this process has to be done more times. But not some power more, just linearly more)2011-06-01
  • 1
    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.2011-06-01
  • 0
    @Chris Eagle Agreed, I guess I was hasty. So the conclusion is that its basically impossible to figure out?2011-06-01
  • 0
    @soandos: *sigh* No -- the conclusion is that it is *NP-complete* to figure out.2011-06-03
  • 0
    @soandos: Your assumption that it is enough to look around a constant number of squares is incorrect. Look at this pdf: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf.2011-07-15
  • 0
    @Aryabhata, Thank you. I realize this is stupid, but it "seems" that given a number of mines, and the area, it should be possible to determine the odds of winning with perfect play. To actually do the perfect play is not the way to go about it, but in the aggregate, I was hoping for some clever way.2011-07-17
  • 0
    I have a minesweeper solver that is quite fast and it uses Matrix mathematics to solve the deterministic part of minesweeper. You can find my post here: http://robertmassaioli.wordpress.com/2013/01/12/solving-minesweeper-with-matricies/ I am going to start working on the probabilities and statistics involved in the game soon. I'll write more information on that blog if I work anything more out. And, as @soandos mentions, minesweeper solvers are fast, my solver can play 100000 expert games in less than a minute and a half on my computer.2013-01-16
  • 0
    @RobertMassaioli thanks, and would appreciate any updates2013-01-16
  • 0
    Intermediate level gives a higher expectation of winning the game. In some games there are required guesses. I have played $754$ games and won $618$ of them or $82.2\%$. My longest winning streak is $14$ games and longest losing streak is $3$ games, (played $17$ won $14 = 82.4\%$). I recognize the basic patterns ($1,2,1; 1,2,2,1;$ etc) but may miss larger patterns. I play carefully and lose by making the wrong guess rather than a blunder. Does this mean anything more than I have reached my own expectation of winning?2013-02-22
  • 0
    I have written a quick program to play minesweeper. It doesn't play perfectly (there are still a couple of tricks I haven't taught it yet), and it doesn't make guesses. Currently, it can win about 70% of easy games (8x8, 10 bombs), about 60% of medium games(16x16, 40 bombs), and 8% of hard games (16x30, 99 bombs). Let me know if you want more information.2016-04-27

11 Answers 11

13

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

  • 0
    So how many of those configurations can there be, and what are the odds of getting out of them is the question2011-06-01
  • 0
    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.2011-06-01
  • 0
    Thanks the kind of thing i was looking for.2011-06-01
  • 0
    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...2011-06-01
  • 0
    @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)?2011-06-01
  • 0
    Is it true that the mines are placed only *after* the first move? That raises the question: What is the eoptimal first move ... ?2013-02-22
  • 0
    @HagenvonEitzen: I do not know exactly, but it never happened to me that the first click was on a bomb. This suggests that the mines are generated after the first click. Find more infos on the net: http://www.squidoo.com/minesweeper2013-02-23
  • 0
    If a guess has to be made, computing the probability of a mine using belief propagation greatly improves your odds of success. The odds are definitely not 50%, an educated guess can be made many times. No one knows the optimal algorithm to maximize the chances of success in minewsweeper http://www.minesweeper.info/articles/GraphicalModelsMinesweeperProject.pdf2013-08-12
  • 0
    My understanding is that in most Minesweeper programs, the mines are preset at the start of play, but if you click on a mine on the first move, the program swaps that mine with an empty square at or near a corner so that the game can continue. Knowing the exact details might help in later corner situations where one has to guess. As an aside: my first move is not on an edge, but is adjacent to a square on the edge; if my move reveals a '1', then I immediately click on that edge square, and if *that's* a '1', I can immediately unlock three more squares.2013-10-13
  • 0
    Not only is the first click always safe, it is also always a zero.2015-08-24
  • 0
    Where does that 99% claim come from? Experimental data rather (like in the paper referenced by Gowtham) shows success rates of 85% for 16x16 fields with 10 mines.2016-12-07
  • 0
    16x16 fields with 10 mines? That must be a joke. 10 mines are on a 8x8 field and on a 16x16 field there are usually 40 mines. Anyway, if you do not arrive at a place where you need to guess you win easily...2016-12-11
  • 0
    Not a joke, a typo. I meant 16x16 with 40 mines or 8x8 with 10.2017-02-12
  • 0
    1−2−1 & 1−2−2−1, have a more basic paattern: 1−2. Really 1−2−? OR ?−2−1 ( Where the "?" can be anything ). At least one bomb is always above the ?. This can be generalized to situation where you are looking at one number and listing all the possible mine locations. So for a 2 up against a wall it is: The above square mine possibilities are: M−M−?, M−?−M, or ?−M−M. If 2 is right next to a one on a wall, that immediately rules out the option where both mines are next to the one. Of the remaining possibilities you'll notice that one tile always has a mine, you flag it safely.2017-12-20
5

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.

  • 0
    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.2011-06-01
4

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.

  • 0
    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 sidetracked2011-06-01
  • 1
    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.2011-06-01
  • 0
    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.2011-06-01
  • 0
    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.2011-06-01
  • 0
    If there is a square that cannot be solved, there it becomes and odds thing. If it can be solved and its just a matter of runtime i dont care about it. Reminds me a bit of the game of life.2011-06-01
  • 2
    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.2011-07-15
2

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?

2

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 :)

1

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.

  • 1
    How does a cat extinguish a computer?2013-08-29
  • 0
    By hosing it down.2013-08-29
1

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.

  • 0
    I've fixed some errors and bugs. When guesses are required I find that the corners are the best start, then the edges - with the requirement that the guess be fully surrounded by blocks, if not possible, to have the lowest probably of being a mine, finally the 50%/50% locations.2013-09-19
  • 0
    For the expert game, I up to 20% wins. In the expert games there are 50%/50% guess situations in about 10% of the games adding a 5% loss rate. The losses overall are all from guesses, 3.58 guesses per game.2013-09-19
  • 0
    This is nice to know :)2014-04-14
0

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

0

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?

  • 0
    In minesweeper you can't lose on the first click2016-04-27
0

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.

-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.

  • 4
    Right, but if you could count the average number of such coin flips, you'd have the odds of winning.2011-07-16