←back to thread

Minesweeper thermodynamics

(oscarcunningham.com)
206 points robinhouston | 2 comments | | HN request time: 0.432s | source
1. GistNoesis ◴[] No.45124602[source]
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.

replies(1): >>45128048 #
2. gus_massa ◴[] No.45128048[source]
Most of the times Minesweeper is deterministic, and you can just think and get an empty spot. From time to time, you are unlucky and has to guess.

A few years ago, I modified the version of minesweeper in the "Games" collection of Racket to get more mines per board and get more hard cases. (I added the trick to autoopen the squares that have enough flags around, so it solved all the easy cases and it was more fun. I never upstreamed the changes...)

I like Dragonsweeper (discussed in a sibling comment) because it has a more clear probability and information tradeoff.