Expert Minesweeper Probability Question

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

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.