Statistics of Minesweeper (MT to the red courtesy phone) (1 Viewer)

[GregR]

In Minesweeper sometimes you get down to a situation where you cannot completely deduce the location of any mines and have to make an informed guess. So question on whether I'm looking at the informed guess right.

Sometimes the surrounding spots you've revealed allow you to do deduce things like "there is exactly 1 mine somewhere in spots A, B and C" and also "there is exactly 1 mine in spots C, D, E and F".

If you're near the end of a game the number of remaining squares and remaining bombs might allow you to deduce a location, but I hit a situation where I had about 200+ squares and 30 bombs left so that wouldn't help. And I had about 6 sets of information like the above, with multiple cases of a cell being in more than one set I had info about.

In the above scenario, where we get information on C from two different sets of revealed squares, how do you express the odds of there being a mine in square C? In the first bit of info, C has a 33% chance of a bomb and in the second, C has a 25% chance. Am I correct that they should be treated as independent and I should make my eventual random choice as if C has just a 33% chance of a bomb, and not count the lower 25% chance? Or if not, what would be the correct method of combining the odds as I try to figure out the squares I should choose from when I make my eventual guess?

 

[Fennis]

RED COURTESY PHONE?!!!???! HOW DARE YOU!!!

 

[GregR]

RED COURTESY PHONE?!!!???! HOW DARE YOU!!!

Apologies given to Native Americans, Communists, and actors who appeared in Red but not the crappy sequel Red 2.

 

[jon_mx]

They are not independent. Ideally you could get it down to where the only bombs you don't know are the ones you need to guess on, and then you have additional information like whether there are two bombs left or just one bomb. In that way you could either determine spot "C" contains the last bomb if there is only one bomb remaining, or eliminate spot "C" if there are two bombs remaining.

When there are multiple trouble spots it becomes a little more difficult. Say you have two trouble spots. Then you could have anywhere from two through four bombs available. If you have four, the "C" can be eliminated again. If you have three, then it become a coin-flip on which area has two bombs and which area has one. If you gave a specific puzzle, it would be easier to determine the odds and the best strategy.

 

[randall146]

The 90's called. They want their blah blah bla bl. . . . . .

 

[GregR]

They are not independent. Ideally you could get it down to where the only bombs you don't know are the ones you need to guess on, and then you have additional information like whether there are two bombs left or just one bomb. In that way you could either determine spot "C" contains the last bomb if there is only one bomb remaining, or eliminate spot "C" if there are two bombs remaining.

While they aren't truly independent, in the situation I'm giving as an example you cannot narrow it down to the point you're saying where it provides useful information. So the number of possibilities is so great they provide pretty much no useful information about these borders with exposed squares beside them supplying information.

In this example, the most you could get from what you're talking about, would be approximate odds are of clicking on a random square that you otherwise have no information about. But in order to know whether that's the wisest move, I still need to need to know the odds of square C to be able to compare it to that.

 

[CBusAlex]

Well, on first glace, it would appear that there are seven possible mine configurations, only one of which has a mine in space C:

AD

AE

AF

BD

BE

BF

C

On second glace, these configurations may not be equally probable. I think you would need to determine the mine density in the remaining squares and weight them accordingly.

 

[Maurile Tremblay]

In Minesweeper sometimes you get down to a situation where you cannot completely deduce the location of any mines and have to make an informed guess. So question on whether I'm looking at the informed guess right.

Sometimes the surrounding spots you've revealed allow you to do deduce things like "there is exactly 1 mine somewhere in spots A, B and C" and also "there is exactly 1 mine in spots C, D, E and F".

If you're near the end of a game the number of remaining squares and remaining bombs might allow you to deduce a location, but I hit a situation where I had about 200+ squares and 30 bombs left so that wouldn't help. And I had about 6 sets of information like the above, with multiple cases of a cell being in more than one set I had info about.

In the above scenario, where we get information on C from two different sets of revealed squares, how do you express the odds of there being a mine in square C? In the first bit of info, C has a 33% chance of a bomb and in the second, C has a 25% chance. Am I correct that they should be treated as independent and I should make my eventual random choice as if C has just a 33% chance of a bomb, and not count the lower 25% chance? Or if not, what would be the correct method of combining the odds as I try to figure out the squares I should choose from when I make my eventual guess?

It's been a really long time since I've played Minesweeper.

In your scenario, you might start, if possible, by estimating the expected number of mines in group A, B, C, D, E, F. (Based on how many total mines there are left, and how many total covered squares there are left, etc.) You know that the minimum is 1 and the maximum is 2. You also know that if the answer is 1, it's definitely in C. If the answer is 2, then C is definitely clean. If the answer is 1.3 or 1.7 or 1.5, there would be a 70%, 30%, or 50% chance that there's a bomb in C, respectively. (I think.)

 

[jon_mx]

Assuming there are lots of unknown spaces, the best strategy is to randomly pick another square where the density of mines would be lower. If you had to pick a square of those, I would go with D, E, or F.

 

[jon_mx]

Why not get a puzzle down to a situation similar to this and post a screen shot. It might be an interesting excercize. The only cases I remember, is that it comes down to a coin flip between a couple of possible patterns. And they are absolutely not independent. Once you determine one bomb, you have determined the other bomb.

 

[MC Gas Money]

Who plays minesweeper anymore?

 

[GregR]

Wish I'd saved the game at that point, as it was one of the more interesting situations I have come across in a few years of playing it. I've started doing more logic puzzles to try to help keep my cognitive abilities as I age. Minesweeper is an easy once since it's installed everywhere. Solitaire is particularly good too if you use the revert move command to go back and see if you can play a hand out alternate ways to get to an ending.

In any event, a random square might have been the best case. In this particular situation, there was another area with 5 squares and 1 bomb where I made my guess, and chose the bomb of course. But it got me wondering about how 2 sets of information like that would be combined for a square that is in both sets.

I don't remember the exact count of free squares, let alone those I had no information about, but in retrospect it might have been the better play. I think the remaining squares to bombs was probably in the neighborhood of 10 to 1 at the time. After factoring in the squares on the edges I had more info about, a totally random square probably would have been better odds.

 

[Sarnoff]

I thought Minesweeper was NP-Hard, looks like it's been found to be NP-Complete. Back in the 90s it was thought coming up with a minesweeper algorithm could possibly solve "P=NP?" but I guess that's no longer the case.

 

[GregR]

Why not get a puzzle down to a situation similar to this and post a screen shot. It might be an interesting excercize. The only cases I remember, is that it comes down to a coin flip between a couple of possible patterns. And they are absolutely not independent. Once you determine one bomb, you have determined the other bomb.

Right, there are times where you get a block that everything along the border cannot be completely determined. Frequently it's a small block and you can solve the rest and then knowing how many bombs left can help get an answer.

This particular puzzle was interesting in that I basically had the leftmost third of the map that was covered and all the way from top to bottom along where I'd uncovered was a series of these overlapping areas where multiple bomb configurations would work at every spot along the way. Normally you don't get such a large area that you can't break into somewhere.

 

[Sarnoff]

In your situation, the probabilities are definitely related and not independent. Unfortunately coming up with a full mathematical estimation would require working out all possible arrangements of the exact number of bombs left that fit the information available.

Usually, when I played, I click the four corners and about the midpoint of each of the four sides first. That way I'd have at least some information in the endgame, because I don't want to get frustrated with one corner/side left and have to turn the whole game into a 50/50 coin flip.

 

[GregR]

In your situation, the probabilities are definitely related and not independent. Unfortunately coming up with a full mathematical estimation would require working out all possible arrangements of the exact number of bombs left that fit the information available.

Usually, when I played, I click the four corners and about the midpoint of each of the four sides first. That way I'd have at least some information in the endgame, because I don't want to get frustrated with one corner/side left and have to turn the whole game into a 50/50 coin flip.

Right, I'm meaning that the number of possibilities for all the covered squares is too great to work out and there are too many combinations that will work. So it's not providing much more meaningful information beyond average number of bombs per square. Or average number of bombs per square not counting the squares and bombs included in the border zones where you have other information.

I'm thinking I've probably been making the mistake of not choosing a random area in such situations where there is a big area still uncovered. The odds probably favor the random guess over an area I have information. It's a 16x30 board, 480 squares, with 99 mines. So on average you're talking a mine per just under 5 squares. Most of the time you're working a spot you have info on you're talking about knowing there is 1 bomb in a group of 2, 3 or 4 squares, so if you haven't greatly changed the starting ratio by what you've revealed, it probably is the better guess.

I only reveal one square to start, in the middle, and then work it from there so I'm limiting the number of random choices I'm having to do. The day I realized you could double click the numbered square to reveal the squares around it once you had enough flagged, my success rate climbed a lot. I had more failures from miss-clicking than I did from failures of logic.

 

[sn0mm1s]

In your situation, the probabilities are definitely related and not independent. Unfortunately coming up with a full mathematical estimation would require working out all possible arrangements of the exact number of bombs left that fit the information available.

Usually, when I played, I click the four corners and about the midpoint of each of the four sides first. That way I'd have at least some information in the endgame, because I don't want to get frustrated with one corner/side left and have to turn the whole game into a 50/50 coin flip.

Right, I'm meaning that the number of possibilities for all the covered squares is too great to work out and there are too many combinations that will work. So it's not providing much more meaningful information beyond average number of bombs per square. Or average number of bombs per square not counting the squares and bombs included in the border zones where you have other information.

I'm thinking I've probably been making the mistake of not choosing a random area in such situations where there is a big area still uncovered. The odds probably favor the random guess over an area I have information. It's a 16x30 board, 480 squares, with 99 mines. So on average you're talking a mine per just under 5 squares. Most of the time you're working a spot you have info on you're talking about knowing there is 1 bomb in a group of 2, 3 or 4 squares, so if you haven't greatly changed the starting ratio by what you've revealed, it probably is the better guess.

I only reveal one square to start, in the middle, and then work it from there so I'm limiting the number of random choices I'm having to do. The day I realized you could double click the numbered square to reveal the squares around it once you had enough flagged, my success rate climbed a lot. I had more failures from miss-clicking than I did from failures of logic.

If the numbers are anything close to what you suggested, and you really had to guess (which is often not the case), you were better off picking a random square. Assuming you had 6 places where you knew there was a mine. That leaves 24 mines floating around in that ~200 square section of unrevealed area (subtracting the unrevealed area where you know a mine would be).

If those 6 places where you knew a mine resided contained ~20 unrevealed squares your best scenario would be hitting a mine about 1/3 of the time on a guess.

Those 24 other mines floating about in 180 squares mean you hit a mine about one out of every 7-8 times on a guess.

Now, you can help yourself with where you guess. If you have a section like:

?1?

abc

def

ghi

Where 1=a one, ?=any other number, and a letter is an unrevealed square. If you guess e, and e is a 1, then d,f,g,h, and i are all non-mine squares

 

[GregR]

Here's an example I did a screen shot of. Not the game that sparked my post and had more that were still covered, but similar enough to illustrate the situation.

For easier discussion I labeled covered squares that we have info on starting up near the top, A through Z and then A1 and A2. So from what's uncovered you know:

A B contain exactly 1 mine

C D E F contain exactly 1 mine

E F G contain exactly 1 mine

F G H I contain exactly 1 mine

K J contain exactly 1 mine.

A K contain exactly 1 mine

M N contains exactly 1 mine

N O P contains exactly 2 mines

P Q U contains exactly 1 mine

R S T contains exactly 1 mine

U V contains exactly 1 mine

V W A1 contains exactly 2 mines

X Y Z contains exactly 1 mine

A1 A2 contains exactly 1 mine.

Over on bottom right corner, we also know there are 3 squares that contain exactly 2 mines.

The rest though are mostly pretty variable on how many mines they could hold. Examples:

The top area (A through K) could hold 3 mines (B K F or A J F) or it could have 4 mines (combos like B J G E).

MNOP could contain 2 mines (N plus O or P) or it could contain 3 mines (M plus O and P).

While frequently you can clear the whole map without guessing, or perhaps just having to guess one or two final 50/50 calls, it's also not uncommon to get something like this where nothing on the border can be absolutely deduced, so you're going to have to just take a guess somewhere.

 

[GregR]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

 

[chet]

DOOOOD

It's a crappy Windows 97 game. Move on.

 

[sn0mm1s]

Here's an example I did a screen shot of. Not the game that sparked my post and had more that were still covered, but similar enough to illustrate the situation.

For easier discussion I labeled covered squares that we have info on starting up near the top, A through Z and then A1 and A2. So from what's uncovered you know:

A B contain exactly 1 mine

C D E F contain exactly 1 mine

E F G contain exactly 1 mine

F G H I contain exactly 1 mine

K J contain exactly 1 mine.

A K contain exactly 1 mine

M N contains exactly 1 mine

N O P contains exactly 2 mines

P Q U contains exactly 1 mine

R S T contains exactly 1 mine

U V contains exactly 1 mine

V W A1 contains exactly 2 mines

X Y Z contains exactly 1 mine

A1 A2 contains exactly 1 mine.

Over on bottom right corner, we also know there are 3 squares that contain exactly 2 mines.

The rest though are mostly pretty variable on how many mines they could hold. Examples:

The top area (A through K) could hold 3 mines (B K F or A J F) or it could have 4 mines (combos like B J G E).

MNOP could contain 2 mines (N plus O or P) or it could contain 3 mines (M plus O and P).

While frequently you can clear the whole map without guessing, or perhaps just having to guess one or two final 50/50 calls, it's also not uncommon to get something like this where nothing on the border can be absolutely deduced, so you're going to have to just take a guess somewhere.

In this case you are better off guessing outside of your lettered squares. Worst case scenario for you 11 mines of the 18 are required to fill in the lettered squares (and the non-lettered one in the corner). This leaves at worst 7 mines in the 42 unmarked squares.

 

[GregR]

Here's an example I did a screen shot of. Not the game that sparked my post and had more that were still covered, but similar enough to illustrate the situation.

For easier discussion I labeled covered squares that we have info on starting up near the top, A through Z and then A1 and A2. So from what's uncovered you know:

A B contain exactly 1 mine

C D E F contain exactly 1 mine

E F G contain exactly 1 mine

F G H I contain exactly 1 mine

K J contain exactly 1 mine.

A K contain exactly 1 mine

M N contains exactly 1 mine

N O P contains exactly 2 mines

P Q U contains exactly 1 mine

R S T contains exactly 1 mine

U V contains exactly 1 mine

V W A1 contains exactly 2 mines

X Y Z contains exactly 1 mine

A1 A2 contains exactly 1 mine.

Over on bottom right corner, we also know there are 3 squares that contain exactly 2 mines.

The rest though are mostly pretty variable on how many mines they could hold. Examples:

The top area (A through K) could hold 3 mines (B K F or A J F) or it could have 4 mines (combos like B J G E).

MNOP could contain 2 mines (N plus O or P) or it could contain 3 mines (M plus O and P).

While frequently you can clear the whole map without guessing, or perhaps just having to guess one or two final 50/50 calls, it's also not uncommon to get something like this where nothing on the border can be absolutely deduced, so you're going to have to just take a guess somewhere.

In this case you are better off guessing outside of your lettered squares. Worst case scenario for you 11 mines of the 18 are required to fill in the lettered squares (and the non-lettered one in the corner). This leaves at worst 7 mines in the 42 unmarked squares.

Agree, and that's something I hadn't considered enough that the areas without extra information might have the best odds.

Though still, figuring out how to get at the exact odds of F is an interesting intellectual thing.

 

[jon_mx]

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance C is a bomb

20% chance D is a bomb

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick C, D, H, F or I

 

[sn0mm1s]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick H, F or I

This isn't quite right but the gist is there:

In that section we know mines are either at AJ or BK. The possible solutions for the rest in that section are:

F

CG

DG

HE

IE

Now, those aren't equal in likelihood because they require different numbers of mines. Assuming the likelihood of 2 mines vs. 1 mine is 50/50 jon_mx is correct.

If I was playing that game, I would just bit the bullet and see if I guess the correct open square in the corner (why waste the time on something that is a pure guess no matter what). I Would then pick the square to the left of the "S".

 

[jon_mx]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick H, F or I

This isn't quite right but the gist is there:

In that section we know mines are either at AJ or BK. The possible solutions for the rest in that section are:

F

CG

DG

HE

IE

Now, those aren't equal in likelihood because they require different numbers of mines. Assuming the likelihood of 2 mines vs. 1 mine is 50/50 jon_mx is correct.

If I was playing that game, I would just bit the bullet and see if I guess the correct open square in the corner (why waste the time on something that is a pure guess no matter what). I Would then pick the square to the left of the "S".

I was doing it in my head without pen and paper, so a good chance i goofed up a bit.

 

[sn0mm1s]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick H, F or I

This isn't quite right but the gist is there:

In that section we know mines are either at AJ or BK. The possible solutions for the rest in that section are:

F

CG

DG

HE

IE

Now, those aren't equal in likelihood because they require different numbers of mines. Assuming the likelihood of 2 mines vs. 1 mine is 50/50 jon_mx is correct.

If I was playing that game, I would just bit the bullet and see if I guess the correct open square in the corner (why waste the time on something that is a pure guess no matter what). I Would then pick the square to the left of the "S".

I was doing it in my head without pen and paper, so a good chance i goofed up a bit.

Yeah, I did as well. If the odds were 50/50 two vs. one then there is a 50% chance that F is a bomb because it is the only solution if there is only 1 bomb. Regardless, it is much better to choose something outside of the border.

 

[GregR]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick H, F or I

This isn't quite right but the gist is there:

In that section we know mines are either at AJ or BK. The possible solutions for the rest in that section are:

F

CG

DG

HE

IE

Now, those aren't equal in likelihood because they require different numbers of mines. Assuming the likelihood of 2 mines vs. 1 mine is 50/50 jon_mx is correct.

If I was playing that game, I would just bit the bullet and see if I guess the correct open square in the corner (why waste the time on something that is a pure guess no matter what). I Would then pick the square to the left of the "S".

There can also be bombs at B and J which result in bombs at E and G

 

[GregR]

Incidentally, in the actual game I safely guessed one of the squares with no info, cleared the left, then blew up trying to pick the one safe square out of 3 on the far right.

But yeah, what I want to get at is the correct process for finding the odds when a square is a part of multiple scenarios like that. I agree in most cases choosing some other spot is probably going to be best unless you've had an oddly distributed map and have a high density of bombs left.

 

[jon_mx]

And a good example for computing the odds might be F. It is part of 3 different groups that each must contain exactly 1 mine... CDEF, EFG, and FGHI.

Start off by looking at A-k section. There is a 50-50 shot at J and A being bombs or K and B being bombs. You don't want to guess there. There is one bomb between C,D,E and F and one bomb between F, G, H and I.

If J and A are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

If K and B are bombs, the possible patterns are:

I and E

H and E

G and D

G and C

or just F

20% chance H is a bomb

20% chance F is a bomb

20% chance I is a bomb

40% chance E is a bomb

40% chance G is a bomb

So out of those, pick H, F or I

This isn't quite right but the gist is there:

In that section we know mines are either at AJ or BK. The possible solutions for the rest in that section are:

F

CG

DG

HE

IE

Now, those aren't equal in likelihood because they require different numbers of mines. Assuming the likelihood of 2 mines vs. 1 mine is 50/50 jon_mx is correct.

If I was playing that game, I would just bit the bullet and see if I guess the correct open square in the corner (why waste the time on something that is a pure guess no matter what). I Would then pick the square to the left of the "S".

There can also be bombs at B and J which result in bombs at E and G

B and J do not work together. Well, at least not here or for married couples.

ETA....the '1' between A and K will not have an adjacent bomb.

 

[GregR]

Ah, you're right there.

 

[AAABatteries]

Incidentally, in the actual game I safely guessed one of the squares with no info, cleared the left, then blew up trying to pick the one safe square out of 3 on the far right.

You just described why I ####### hate minesweeper and haven't played it in 20 years.

 

[Mister CIA]

When reduced to chance, I just say bleep it and go with what the gut says is lowest risk - I've got a clock to beat.

 

[Politician Spock]

I didn't know it was possible to bump a thread from Old Yeller.

 

[Herb]

So after all this assessment and analysis, you're back to what I figured out twenty years ago when I was addicted to this game:

At some point you have to just guess. There is no way around it. You can stack probabilities and odds and drive yourself nuts, but in

every.

single.

game.

of minesweeper.

ever.

finishing all comes down to a guess.

 

[Gawain]

A has to have a bomb. The 1 on the top edge makes it so.

ETA : LOL, I had scrolled down and missed the top edge.

 

[GregR]

So after all this assessment and analysis, you're back to what I figured out twenty years ago when I was addicted to this game:

At some point you have to just guess. There is no way around it. You can stack probabilities and odds and drive yourself nuts, but in

every.

single.

game.

of minesweeper.

ever.

finishing all comes down to a guess.

Well, the point of the thread was to learn how to combine the different sets of odds in a situation like this. That it was minesweeper was secondary, but made for interesting conversation anyway.

 

[sn0mm1s]

So after all this assessment and analysis, you're back to what I figured out twenty years ago when I was addicted to this game:

At some point you have to just guess. There is no way around it. You can stack probabilities and odds and drive yourself nuts, but in

every.

single.

game.

of minesweeper.

ever.

finishing all comes down to a guess.

I wouldn't say that. There are many games where you don't have to guess - especially if you aren't trying to beat the clock.

 

[Mr. Retukes]

Pardon the interruption...

 

[Ignoramus]

When you nerds figure this one out I have a question about tiddly winks.