Back in 2012 I’ve made a Windows Minesweeper AI that can play Windows 7 Minesweeper using backtracking, combinatorics and windows input API but I never “released” it. There are many cool project examples. Indeed, building an AI to beat perhaps one of the first frustrating computer games you have played is a very rewarding project.
Recently, I decided to revisit that project and really kicked it up a notch – at least in the algorithmic department. I threw some diehard techniques in there, and the result is a hilariously cutting edge Minesweeper AI that I believe evaluates the largest grids ever quickly and correctly. Here is a real-time clip of it in action, playing on a grid 9 times larger than expert:
The AI can do even larger grids than that (see the demo at the end of the series).
In this series I will lay out every detail of this Minesweeper AI in its full magnificent glory.
Part 1: The Foundations of a Minesweeper AI
Bai Li’s Luck Toilet blog covers the workings of a backtracking algorithm really well and is also a great read so feel free to read that too
How to play minesweeper:
You start with a grid of hidden tiles, some with mines. This is the minefield. The objective is to clear all the safe tiles, thus locating all the mines. Stepping on a tile clears it and either reveals:
1. Mine. You lose. Avoid doing that if you can.
2. Number. These are your only clues you have to navigate the minefield. The number represents how many mines are surrounding this tile.
3. A clear tile. This means there are no mines surrounding it, and the game automatically cascades on these.
If you are certain of a mine’s location, you can also flag it, preventing you from accidentally clicking it in the future, and to help you in future calculations.
A simple solver:
A simple way to play minesweeper as you start learning, is to look at forcing moves. There are two cases:
1. A number has the same number of hidden tiles around it. In that case, you can confidently flag all surrounding tiles as mines.
2. A number has the same number of flags around it. In that case, you can safely clear the remaining tiles around it (assuming all your flags were actually mines, otherwise you lose :P)
By repeatedly resolving tiles using these two techniques, you can get quite far, but it’s far from perfect. It will work for a majority of beginner games, some lucky intermediate games but very few expert games. Here’s an example of a situation that requires a bit more of a global look:
After examining all possible valid configurations of mines, we could see that some squares are actually safe to clear and progress the game for us. Some on the other hand are certainly mines, while others have middling chances. That’s something we couldn’t have deduced using the simple method alone.
It turns out that solving arbitrary minesweeper situations like the ones above is an NP-complete problem. This means that we can’t solve every case in better than exponential time, so we should avoid wasting our time in pursuit of such an algorithm. However it doesn’t stop us from solving reasonable cases in a reasonable amount of time. A well thought out backtracking method can do that for most expert games.
This was what the “Tank AI” mentioned in the Lucky Toilet blog does, and also what CodeBullet did. (Also what I did in 2012). A backtracking algorithm would enumerate all possible mine configurations on the perimeter of the visible minefield. Looking at all the valid configurations as a whole, we then have two possibilities for each tile:
1. If we have a tile that is clear in all configurations, then we have deduced that it must be safe, and we can clear it, giving us more information and progress in the game.
2. If no tile is certainly clear, then for each tile we at least have the probability that it is a mine. The probability is just #arrangements it has a mine vs #arrangements it is clear. For this article, we focus on how to calculate these probabilities accurately and quickly. Picking the lowest probability tile to hit is guaranteed to progress the game, with the lowest risk of dying. However it’s not always the best tile to hit, as another higher-risk tile may reveal more information and might be expected to progress the game further. This is another dimension to the game that I might explore in a different article.
Making the probabilities actually correct:
There is something that’s left out in Lucky Toilet’s blog: not all configurations have the same likelihood. In minesweeper we know the total number of mines in the game. The number of mines in a configuration affects its likelihood, because the different number of remaining mines will distribute among the remaining tiles a different number of ways.
For example, a 5-mine configuration in the example above on an intermediate 16×16 40 mine game leaves 35 mines in the rest of the field and would be ~5.4 TIMES AS LIKELY than any given 6-mine configuration which leaves only 34 extra mines. So that last configuration in the diagram is actually more likely than the other four combined.
This can be taken into account by adding weight to each arrangement according to the number of mines it uses, after calculating the required combinatorics.
Speed improvement with grouping:
We can speed up our exponential backtracking by splitting the boundary into multiple independent parts, and backtrack on those smaller groups separately, improving our runtime exponentially. In the Lucky Toilet blog, they are called “segments”.
…Except that if we also want correct probability calculations using mine counts, then those parts are not entirely independent. The likelihood distribution of #mines in one group will affect the likelihood of any configurations in all other groups with different #mines.
To solve this, we can look at each group individually. First, as a precomputation, tally #combinations for every #mines in every group. Then, consider each group in turn. Look at all other groups except the current one. It is possible to calculate the number of combinations to arrange N mines among those other groups and other blank tiles using dynamic programming. So do that for every N, to get the correct combination counts for any N number of mines. Using these counts we can generate correct weights for all arrangements in the current group given its #mines.
But don’t go anywhere folks, we are far from done.
The current method plays the majority of 30×16(99) expert games well. Still it often hiccups when faced with a large continuous perimeter that don’t group, and occasionally it stalls exponentially when eventually faced with especially large ones. On truly massive grids, it explodes exponentially all the time. This is unsurprising, but also unacceptable.
So, some truly crazy things follow in part 2 to make this algorithm slice through those situations