Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is just a question I thought of while playing minesweeper. I think that finding the solution might be kind of fun, so I'm sharing it with you guys. If you have no concept of what minesweeper is, this question might be kind of tough. Also, if you have no concept of what minesweeper is go play it. It's fun.

It's an expert board. That means you have a grid of 16 by 30, for a total of 480 squares. A random 99 of these squares have a mine hidden under them.

When you click a square, three things can happen. You can click a mine, resulting in an instant loss. You can click on a square next (diagonal included) to at least one mine, resulting in a number being shown under the square. Or you can click on a square that isn't a mine and isn't next. When this is done, all 8 surrounding squares are revealed. If any of those squares are also not next to any mines, all of the surrounding squares that are not yet revealed become revealed.

That should make sense if you've played minesweeper before.

You're playing expert mode. The mines are spread randomly. What is the average number of squares revealed by your first click?

I would count clicking a mine as 0 squares revealed.

Have fun!

share|improve this question
4  
(+1) This seems like it is essentially a percolation-model problem. –  cardinal Sep 7 '11 at 1:01
1  
This is probably easier to solve on an infinite board where the probability of any given cell being a mine is $99/480$ independently. In which case you have $99/480 * 0 + 381/480 * (1 - (381/480)^8) * 1 + (381/480)^9 * x$, where x is the average number of cells revealed given that the first cell is not adjacent to a mine. $x>9$, but figuring out the exact value will be tricky. –  Craig Sep 7 '11 at 3:15
1  
@Craig, that is essentially getting close to how the problem would be formulated in the percolation-theory framework. The problem of interest there essentially becomes whether there is positive probability $\theta$ of an infinite number of cells being revealed, especially when we generalize further to the case where the probability of any given cell being a mine is parametrized by $p \in (0,1)$, so that $\theta(p)$ is now a function. Here is a good starting point. –  cardinal Sep 7 '11 at 11:28
1  
Yes, I'm aware. And since this is a 2-d problem, and p < 1/2, the probability $\theta$ is essentially zero, and the probability that n cells are revealed falls off exponentially as a function of n. But I don't know how to calculate the exponential fall-off rate, and I don't know how to correct that for fall-off for small n. –  Craig Sep 7 '11 at 12:21
1  
After 25 tries using the corner square, the mean number of squares uncovered was about 16 and the standard deviation was 10. After 15 tries with one of the 4 middle squares, the mean was 45 and the standard deviation was 13. More squarea are uncovered at the centre because each square has 8 meighbours and the adjacent squares, and squares adjacent to the adjacent squares.. are also more likely to have 8 neighbours rather than 7 or 6. –  Angela Richardson Sep 7 '11 at 18:25

1 Answer 1

This is not a complete answer, but is too long for a comment (or perhaps even an answer!).

An analytical solution for the finite grid seems difficult. In such situations, either simulation and/or asymptotics can be helpful. Here I briefly sketch a little bit of both.

Monte Carlo Simulation

One way to get an estimate of the average number of revealed cells is to simulate a large number of games and look at what happens. Sometimes some simple analytical tricks can help along the way.

Below is an example heatmap showing the estimated average number of cells revealed at each position in the expert minesweeper board. Below that, I describe some details on how it was generated.

The cells are colored in a gradient from lowest (red) to highest (white) average number of cells revealed. This image was generated from averaging over 10 million random game instances. (Click on the image to see a larger version. For a version without the superimposed averages, click here.)

Heatmap of Expert Minesweeper from 10,000,000 simulated plays

If you were to pick a cell randomly to play first, then the average number of cells revealed would be approximately 7.955. From this, it is clear that playing along the second band is quite suboptimal and on average you open up the board by two more cells by starting on the top or bottom row in the center.

Some details on the simulation

Note that if we are going to generate a random instances of the game, we might as well track how many cells on average are revealed at each position on the $16 \times 30$ grid. A simple, but slightly naive approach, is to generate random instances and keep track of the running total of cells that would be revealed by clicking on each of the starting positions.

However, we can immediately improve on this by recognizing a couple of key facts. First, we can use symmetry to reduce the variance. There are four different symmetry reflections of the board that must yield exactly the same averages. These are: (i) the original board, (ii) flipped along the vertical axis, (iii) flipped along the horizontal axis, and (iv) rotated 180 degrees. So, we can take our naive Monte Carlo and average over the four orientations to get an estimate that respects the symmetry and has lower variance.

Second, note that the individual cells partition nicely into equivalence classes. Cells that have mines or that are adjacent to mines form two separate classes. All other cells are clustered such that there is a closed border surrounding them formed by a combination of "mine" cells, "adjacent" cells and/or the board border. Each cell in a particular cluster will reveal the entire cluster when clicked and so each such cell reveals the same number of cells. This can be used to speed up the computation considerably.

Lest the behavior in the corners seems unintuitive, consider what happens when clicking on cell (1,1) versus (2,2). There is probability $p = 99/480$ in each case of the game immediately ending. Let $q = 1 - p$. Then, the probability of one cell being exposed is roughly $q-q^4$ in the first case and $q - q^9$ in the second. On the other hand, the probability of at least four cells being exposed is about $q^4$ for the (1,1) cell, whereas for the (2,2) cell, more than one cell being revealed occurs only with probability about $q^9$.

Asymptotics

As alluded to in the comments, this problem is closely related to the study of site percolation. In that context, we would consider the lattice $\mathbb{Z}^2$ with independent probability $p$ of each point of the lattice having a mine. We consider starting play by always uncovering the cell at the origin. We can ask the question of what the expected number of cells revealed will be, but we have to be careful since there may be positive probability of an infinite number of cells being revealed.

In site percolation models, it becomes more interesting to study the quantity $\theta(p)$, the probability that an infinite number of cells will be revealed. These problems are surprisingly challenging and rich mathematically. The book G. Grimmett (1999), Percolation, Springer, 2nd edition is a nice place to start.

In our case, it seems clear that an infinite cluster will contain the origin if and only if there does not exist any closed path surrounding the origin formed by $3 \times 3$ tiles that are adjacent (or touch at any corner) to one another, with a mine located at the center of each tile.

However, calculating that probability does not seem trivial, even using some standard percolation machinery.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.