Only tangentially related, but Dragonsweeper is an interesting extension of minesweeper where you have hit points and the "mines" have attack values. I got a better appreciation for the mechanics of minesweeper by playing it; it's surprisingly deep. https://danielben.itch.io/dragonsweeper
I hacked up a version of minesweeper that was “forgiving:” if there was no selection that was provably safe, it gave you a safe move. If you picked any square that was not provably a bomb, it would not be a bomb.
Typically, as long as you don’t select a number of bombs equal to the number of squares , your first move is safe. I just extended that for the whole game.
If you select N-1 bombs, you always win on the first move..
The article discusses Boltzmann's formula exp(-E/kT). I was recently looking at the same formula in the context of semiconductors and I realized that Boltzmann's constant k is only needed because temperature uses bad units. If we measured temperature in energy instead of degrees, then Boltzmann's constant drops out. For instance, you could express room temperature as 25 meV (milli electron volts) or 2444 joules/mole and the constant disappears. Likewise, the constant in the ideal gas law disappears if you measure temperature as energy rather than degrees Kelvin. In other words, degrees Kelvin is a made-up unit that should be abandoned. (I'm not sure I believe this, but I don't see a flaw.)
Minesweeper is a probabilistic game, that's why you should use probabilistic tools to solve it.
For example you can use a particle filter to approximate the distribution of mines. Every time you obtain new information you update the filter so that only distributions compatible with constraints remain.
Once you have an approximation to the distribution of mines you can calculate the probability of each spot being a mine. You can also calculate statistical indicator like the Information Gain of each action.
A good strategy is therefore to play low mine probability with highest information gain. But there is a trade-off, when the mine probability is non-zero. So you need to look-ahead.
Fortunately thanks to the mine distribution approximation you can also simulate any actions and their consequences, because you can use your approximation of the distribution to predict which number will be revealed upon a click.
So an even better strategy is to unroll the game tree for the best few candidate moves based on some heuristics, and calculate the cost gain probabilities after a few moves.
Interestingly, the main problem with Minesweeper is that is a game of chance (so the approach discussed in the article is very appropriate).
For a minesweeper variant purely based on logic, I highly recommend the game Tametsi. It has 160 handcrafted levels, and some have very interesting geometrical arrangements. I have logged over 100 hours in this game.
The author’s math considers how mines would be distributed if mines were distributed to the empty squares after reaching that board state.
This is wrong.
This is classic Monty Hall Problem. The author is doing the equivalent of saying “there are two doors left, so the odds are 50 / 50 that the prize is behind either door.
It invalidates all of the numbers after this point.
At first I thought the "equal probability assumption" wasn't too bad an approximation, but it has an average Brier score of 0.217. Much worse than I thought.
13 comments
[ 507 ms ] story [ 3319 ms ] threadFor example you can use a particle filter to approximate the distribution of mines. Every time you obtain new information you update the filter so that only distributions compatible with constraints remain.
Once you have an approximation to the distribution of mines you can calculate the probability of each spot being a mine. You can also calculate statistical indicator like the Information Gain of each action.
A good strategy is therefore to play low mine probability with highest information gain. But there is a trade-off, when the mine probability is non-zero. So you need to look-ahead.
Fortunately thanks to the mine distribution approximation you can also simulate any actions and their consequences, because you can use your approximation of the distribution to predict which number will be revealed upon a click.
So an even better strategy is to unroll the game tree for the best few candidate moves based on some heuristics, and calculate the cost gain probabilities after a few moves.
For a minesweeper variant purely based on logic, I highly recommend the game Tametsi. It has 160 handcrafted levels, and some have very interesting geometrical arrangements. I have logged over 100 hours in this game.
The author’s math considers how mines would be distributed if mines were distributed to the empty squares after reaching that board state.
This is wrong.
This is classic Monty Hall Problem. The author is doing the equivalent of saying “there are two doors left, so the odds are 50 / 50 that the prize is behind either door.
It invalidates all of the numbers after this point.