How to solve Minesweeper. (Hint: you can’t).

Yes, there are cases in Minesweeper where you have to guess. With that, it is impossible to be able to solve Minesweeper 100% of the time using algorithms alone, especially at higher difficulties. Even though we can’t win every game on logic alone, that doesn’t mean an AI agent can take the smartest moves possible to mitigate these situations.

Based on preliminary research, there are two basic fields of Minesweeper AI: linear algebra and pattern matching:

Linear algebra methods include reading in the entire playing field at once, setting up a matrix of the board, with the end column being the number of apparent mines in the row, and then performing a reduce row echelon to solve the matrix and get a list of cells that are mines and a list of cells that aren’t mines. See this page for a great write-up on the details of the implementation. The main problem with this method is that it is computationally expensive: on larger boards it seems to take n^2 time where n is the number of cells. On the other hand, matrices are inherently computer-friendly: they are easy to store and easy to traverse. These two points offset each other enough that neither of them really effect my choice. Here’s a great resource about using matrices and linear algebra as applied to Minesweeper.

Likewise, pattern matching has its pros and cons. It consists of looking at each cell individually, but there are certain times where these patterns can’t correctly assume adjacent mines. There are more advanced patterns that look at surrounding cells, but these need to be checked for symmetrical natures (think the pattern, but rotated, or mirrored). As such, there will be times where it takes longer to find a move. I think pattern matching might be the ‘easier-to-wrap-my-head-around’ approach. Here are a couple of resources on pattern matching and the numerous patterns found in Minesweeper.

After this round of preliminary research, I’m going to first try to implement pattern matching. but if it becomes to spaghetti-like (if X is true, and Y is false, but Z is also true, do A), I think it would make sense to try to implement the linear algebra method, as it would be more concise, even if more complicated in theory. Regardless of which method I end up implementing, there are cases in Minesweeper where you have to guess. There’s no way around it. With our supplied version of Minesweeper, there is no timer, so time in not a factor, and thus our only focus is being as robust and win as often as possible. Therefore, the end-game moves where guessing is necessary are arguably the most important to get right for this assignment. There are ways to improve our odds: Monte Carlo distributions, Bayesian inference, and simple statistics can get us far. Of course, there are a ton of studies and resources on how to best guess in Minesweeper.

I have a game plan of how to complete the agent. Obviously, I need to store a list of flagged mines, as well as cells that have a mine adjacent and aren’t ‘finished.’ Regardless, I have a ton of resources on hand to make the agent as efficient as possible. It seems that the best bots can get a ~40% win rate on the expert difficulty. We’ll see how close mine gets to that. I seriously suggest taking at the numerous links in this post, it’s kind of crazy to think that Minesweeper is at the cutting edge of mathematics.

I know there aren’t any pictures or diagrams here, but there will be plenty for the postmortem describing how I went about ‘solving’ Minesweeper. It’ll be pretty to look at. Hopefully.