Welcome to NRICH.

 
Minesweeper
By Luqman Bajwa on Friday, May 31, 2002 - 10:10 pm:

here is a probability question that has really been anoying me for a while. if we have a minesweeper game with 3x5 squares such that after clicking on two squares the setup is as below (ignore the #'s), wat is the probability that there is a mine in the box marked X?


## ## ##
     
  2  
  X  
  1  
     


i worked out a probability of 19/112, but i am finding it difficult to justify my method, i am having to go on intuition.

any thoughts

luqman

(for those of you who don't know how minesweeper works, the object of the game is to determine where all the mines are without clicking on the actual squares. by clicking on any other square will produce a number telling u how many mines are in the adjacent squares. with that information u can figure out which squares have mines, and which are safe to click on. u should play it it is good fun!)
By Steve Megson on Saturday, June 01, 2002 - 01:38 pm:

The vital question here is how you believe the computer goes about placing the mines in the first place. Does it mine each square independently with some fixed proability? Does it place each of a fixed number of mines on a random empty square? Does it place a random number of mines in this way, and if so what is the distribution of the number of mines?

My preferred method would be to place a fixed number of mines randomly, since this appears to be what most versions of minesweeper do.

In this case it makes sense to condition on whether we believe that the board contains 2 or 3 mines (it certainly contains no more or less).

2 mines
Here we certainly have a mine in a blue or ? square, and a mine in a red square, so the probability of ? being mined is 1/3 (the probability that the blue-or-? mine is on ?).

3 mines
Here we have 2 mines in red squares and one in a white square, so we never have a mine on ?.

So we have

P(? mined) = 1/3 P(2 mines used)

and it just remains to decide the probability of having 2 mines in the board, which again simply depends on how you think the computer produced the board.
By Luqman Bajwa on Saturday, June 01, 2002 - 01:50 pm:

But the big question is how does the computer decide how to place the mines. say we have no information whatsoever about how the computer does this and that before clicking on any squares the chances of there being 14 mines is identical to the chances of there being 1 mine.

Thats essentially what my question has been from the start, what is the probability of there being two mines.

By David Loeffler on Saturday, June 01, 2002 - 02:15 pm:

In standard Windows Minesweeper, isn't there always a fixed known number of mines at the start?

David

By Luqman Bajwa on Saturday, June 01, 2002 - 04:27 pm:

ok lets say we are talking about a game with NxN squares where N is very large, that way any density of mines in any region is possible. what are the chances X=mine then?

luqman

By Steve Megson on Saturday, June 01, 2002 - 04:56 pm:

By reaching this position you know that there are either 2 or 3 mines. Suppose that either case is equally likely before you start the game, so you have P(2 mines) = P(3 mines) = 1/2. You need to compute

P(2 mines | this position occurs)

which by Bayes' Formula is

P(2 mines) P(position | 2 mines)
--------------------------------------------------------------------
P(2 mines) P(position | 2 mines) + P(3 mines) P(position | 3 mines)


P(position | 2 mines):
You can place 2 mines in 15C2 = 105 ways, and of these this position can occur in 5C1 x 3C1 = 15 ways (5 possible red squares and 3 possible blue-or-? squares). This gives
P(position | 2 mines) = 15/105 = 1/7

P(position | 3 mines):
You can place 3 mines in 15C3 = 455 ways, and of these this position can occur in 5C2 x 5C1 = 50 ways (2 from 5 red squares and 1 from 5 white squares). This gives
P(position | 3 mines) = 50/455 = 10/91

So P(2 mines | position) = (1/7) / (1/7 + 10/91) = 13/23
and P(? is mined | position) = 13/69
By Steve Megson on Saturday, June 01, 2002 - 05:27 pm:

Luqman, you may want to consider the following in relation to your logic above of taking the average of 2 bounds. You assert that P(A | B and C) must lie between P(A | B) and P(A | C).

Suppose you have 3 doors, one of which hides a prize. At the outset you have no information about where the prize is. You open the first door, and do not reveal the prize (equivalent to clicking on the 1 square and not finding a bomb). We correctly deduce a probability of 1/2 that the prize lies behind door 2. Now rewind time and open door 3 instead. Again, you find no prize (click on the 2 square and find no bomb) and deduce that the probability of the prize being behind door 2 is 1/2.

Now by your logic we deduce that if we open doors 1 and 3 and find no prize behind either, the probability of the prize being behind door 2 is between 1/2 and 1/2, so must be 1/2. However, it must certainly be 1.

Steve

By Luqman Bajwa on Saturday, June 01, 2002 - 06:47 pm:

thanx steve ur method makes far more sense. i tried to link conditional proabability into this problem myself but i didnt know what events to define and how to look at it. after looking at ur solution i am far more convinved. i can now play minesweeper in peace!

thanx

luqman

By Steve Megson on Saturday, June 01, 2002 - 08:33 pm:

My solution assumes that we know the probabilities of having 2 or 3 mines, and as written assumes that they are equal (I in fact assumed them to be 1/2, but equality is all that is needed), which solves the original problem where this is the whole board (unless we have more information about how the number of mines is chosen). For the case of an NxN board of which this is part, with a known number m of mines in total, the assumption that the probabilities are equal is unsound. For example, if we have a huge board with very few mines, we are more likely to have 2 mines rather than 3. We need to decide how many of the possible arrangements of m mines on an NxN grid have 2 or 3 in our 5x3 region.

We have a total of N2Cm arrangements, and 15C2 x (N2-15)C(m-2) of them have 2 mines (and similarly for 3 mines). From here we can plug in numbers of our choosing and work through to the probability that ? is mined, though the algebra for general N and m would get somewhat ugly.

Take as an example the easy setting of Windows Minesweeper, which has and 8x8 grid with 10 mines. Here we get, well we get a lot of large numbers which I suspect would overflow most calculators, but then we get the probabilities
P(2 mines) = 0.3126
P(3 mines) = 0.2580
so indeed the probabilities are not equal

P(2 mines | position) = (1/7 x 0.3126) / (1/7 x 0.3126 + 10/91 x 0.2580)
= 0.4466 / 0.073
= 0.6117
(Note also that the 0.073 is the total probability of this position occurring on this grid.)

So P(? mined | position) = 0.2039
For comparison, the result of 13/69 obtained before is 0.1884.

As an aside, in light of the probabilities above I should probably be quite impressed that when I opened minesweeper to check the grid size, the top-left corner of the grid gave exactly the position we are considering.

I also have a horrible feeling that this thread may lead to me programming a computer to play minesweeper after my exams. Actually the idea of using that as a screensaver quite appeals.

Steve

By David Loeffler on Sunday, June 02, 2002 - 08:03 am:

As for programming a computer to play minesweeper: there's money in it. It's been shown that to determine whether the game may be safely solved given a particular set of initial conditions is an NP-complete problem.

David

By Steve Megson on Monday, June 03, 2002 - 10:05 pm:

By way of revision-avoidance, I knocked up a program which creates minesweeper boards using my assumptions and counts those that have a mine on ?. The results from this seem to support my calculations. If anyone wants to try it, it's here: http://spinel.chu.cam.ac.uk/misc/mines.php.

Steve

By Elaine Stevens on Tuesday, June 04, 2002 - 06:52 pm:

David,

From experience playing Minesweeper, I know there are many cases when it comes down to a simple 50/50 chance whether a square is a mine, or it's adjacent square. Surely this rules out any possibilities of knowing whether a game can be negotiated safely or not? Therefore, surely a program cannot be written?

Or am I barking up the wrong tree?

By William Astle on Tuesday, June 04, 2002 - 06:57 pm:

It may be possible to write a procedure such that you never get to that situation.

By David Loeffler on Tuesday, June 04, 2002 - 06:57 pm:

The problem is really to determine whether or not a given board, with some of the squares uncovered, can be safely solved, without any dangerous guesswork. This is the problem that has been shown to be NP-complete.

Incidentally: if I can be facetious for a moment, there is a method of doing this very effectively that relies on quantum physics and the "many worlds" theory.
1) Pick a random set of squares that the mines could be on
2) Uncover every other square
3) If your conclusions were wrong, destroy the universe

Then the only universe which does not get destroyed is the one in which you chose the correct set of squares! So you have solved the puzzle in the surviving universe.

David

By Steve Megson on Tuesday, June 04, 2002 - 07:58 pm:

David, pardon me if I don't feel too happy about any algorithm including the instruction "destroy the universe". One small bug and it all gets terribly messy :-).

Steve

By Yatir Halevi on Tuesday, June 04, 2002 - 08:03 pm:

David, I think we had a conversation about this sort of thing before in AskNrich...Something about a machine that will kill you if you don't win this week's lottery...
The universes will split, and in one you will survive and also be rich...

Yatir

By Luqman Bajwa on Tuesday, June 04, 2002 - 10:53 pm:

excuse me if i sound a bit stupid but wat is a NP-complete problem?

By David Loeffler on Wednesday, June 05, 2002 - 10:42 am:

It's one of a large set of difficult combinatorial problems, for which it has been shown that if there exists a computationally efficient algorithm to solve one of them, it will solve all of them (they may be transformed into each other efficiently).

In this context "efficient" means that the running time is bounded by a polynomial in the size of the problem (the board size here for example), rather than scaling exponentially or factorially - there are obvious factorial-time algorithms for a lot of these; you could just test every possible layout of mines on the board, but the number of these grows very, very fast for large boards.

One of the 1000000$ Clay prizes is to either find a polynomial-time algorithm for NP-complete problems, or show that none exists.

David

By Julian Pulman on Thursday, June 06, 2002 - 10:51 am:

Surely your "bad-universe" termination algorithm has the possibility of never ending, David. What if every time the random set of squares is picked to be the same as the last choice? - I know, hardly very random, but is probable.

By David Loeffler on Thursday, June 06, 2002 - 11:13 am:

Not in the "many worlds" interpretation - in this every possible state corresponds to some universe, necessarily including the one where the problem is sorted correctly. In this version, when you open the box containing Schrodinger's cat, the universe splits into two.

David

By Luqman Bajwa on Thursday, June 06, 2002 - 08:47 pm:

what r ppl's best times then for minsweeper on intermediate, mine is 42 secs

By Luqman Bajwa on Thursday, June 06, 2002 - 09:02 pm:

(no pun intended)

By Yatir Halevi on Friday, June 07, 2002 - 01:29 pm:

Mine is 1 sec.
(There is a cheat :-))


Yatir

By David Loeffler on Sunday, June 09, 2002 - 11:15 am:

Really? I heard somewhere that if you type "XYZZYX" it will give you access to one cheat but this one isn't really all that helpful. How does the 1s one help?

David

By Kerwin Hui on Sunday, June 09, 2002 - 01:29 pm:

Hold down both left and right mouse buttons, release and hit Escape. This stops the clock.

Kerwin

By Yatir Halevi on Sunday, June 09, 2002 - 03:16 pm:

Kerwin's cheat is what I use...


Actually you first nead to click the left button, then hold the right and left button and hit escape (without releasing the escape button), Otherwise minesweeper will minimize.


Yatir