You know how sometimes you start a game of Minesweeper and immediately get stuck?
Like maybe there are some cells that you know are mines, but there aren’t any places that are safe to click.
In this example there are five different ways you could fill in the mines in the neighbouring cells. Note that there’s no cell which is safe in every possibility, so there’s nowhere we can safely click to get more information.
So in order to plan our next click, it would be good to know how likely it is that each cell is safe. You might think that each of the five possibilities is equally likely, in which case the probability that a cell is safe would be the proportion of them in which it isn’t a mine:
But it’s important to notice that the five possible arrangements have different numbers of mines. One has $5$ mines, three have $6$ and the last has $7$ (in addition to the $5$ mines we already found).
Let’s say for example that we’re playing the ‘expert’ version of Minesweeper: a $30\times 16$ board with $99$ mines. That means that outside the solved region there are $444$ remaining cells and $94$ remaining mines. So for each possibility the total number of ways to arrange the mines in the rest of the board is one of the following.$$\binom{444}{94-5}=1.930\times 10^{95}$$ $$\binom{444}{94-6}=0.483\times 10^{95}$$ $$\binom{444}{94-7}=0.119\times 10^{95}$$
Different versions of Minesweeper randomise the mines slightly differently, but after your first click it’s a good approximation that every possibility is equally likely. So the possibility with only $5$ mines is about $16.2$ times as likely as the possibility with $7$ mines!
This means we should calculate how safe each cell is by finding the proportion of the possibilities in which it’s safe, but weighted by the above numbers. That gives us the following probabilities:
Previously we thought that the six best cells each had a $40\%$ chance of safety. Now we see that some of them have a $69.0\%$ chance of safety, and some of them only have $17.2\%$!
In statistical mechanics, the Boltzmann distribution is a law that tells you how likely a physical system is to be in a particular state. It works in the context that your system is in equilibrium with a larger environment that acts as a ‘heat bath’, holding it at a particular temperature $T$. Each of the states of your system has some amount of energy $E$, and Boltzmann’s formula says that the probability to find it in a given state is proportional to$$\exp\left(-\frac{E}{kT}\right)$$where $k$ is Boltzmann’s constant.
Ising Model (from Wikipedia)
A typical application might be something like a grid of atoms that can each be in either an excited or unexcited state. The Boltzmann distribution lets us calculate how many atoms are excited. But I want to apply it to Minesweeper.
The idea is that our little corner of the Minesweeper grid is like a physical system within a larger environment; a ‘mine bath’. The probability of the corner being in each possible state is determined by the number of mines, which we want to treat like the energy.
Above we saw that the probability of a possibility with $m$ mines is proportional to$$\binom{C}{M-m}$$where there are $C$ cells and $M$ mines remaining. In order to make our analogy precise, we would have to express this in a form matching Boltzmann’s law,$$\binom{C}{M-m}\propto\exp\left(-\frac{m}{T}\right)$$where $T$ is some sort of ‘mine temperature’ defined in terms of $C$ and $M$.
When we rewrite the binomial coefficient in terms of factorials, we get$$\frac{C!}{(M-m)!(C-M+m)!}.$$If we increase $m$ by $1$ then the $(M-m)!$ term will decrease by a factor of $M-m$ while the $(C-M+m)!$ term increases by a factor of $C-M+m+1$. So the overall probability will change by a factor of $(M-m)/(C-M+m+1)$.
At the start of the game the number of remaining mines is large compared to the number of mines that we’re worrying about at the boundary of the solved region. So $m$ is small compared to $M$ and $C$. So we can use the approximation $(M-m)/(C-M+m+1) \approx M/(C-M)$. This suggests that for small $m$ the probability of a possibility with $m$ mines is proportional to$$\left(\frac{M}{C-M}\right)^m.$$
This can then be rewritten in the form$$\exp\left(\frac{m}{1/\log\left(\frac{M}{C-M}\right)}\right).$$ So we can indeed pretend that Boltzmann’s law applies to this situation, with a ‘mine temperature’ of $1/\log\left(\frac{M}{C-M}\right)$.
How good is this approximation? Well in our case $M/(C-M) = 94/(444-94) = 0.269\dots$. So the possibility with $5$ mines would be $1/(0.269\dots)^2 = 13.86\dots$ times as likely as the possibility with $7$ mines. But we saw above that this ratio was actually about $16.2$. So it has the right order of magnitude, but it’s not a very accurate estimate.
Statistical physics is often applied to macroscopic physical systems, where the number of particles is in the region of Avogadro’s number. If Minesweeper’s expert mode had $6\times 10^{23}$ mines then our approximation would be much better!
Addendum: This post was discussed on Hacker News, Reddit, Mastodon and Lemmy.
