Solving Minesweeper

Minesweeper is a simple game with simple rules, yet some configurations yield interesting challenges. In this article, we will develop a Minesweeper solver of increasing refinement, and discuss how the game dynamics develop as we employ the increasingly advanced help. In the end, we will develop a new variant of the game which has more interesting gameplay.

Local reasoning: Zero adjacent mines

The original game employs one automatic mechanism: When you reveal a square that has zero adjacent mines, all the adjacent squares are revealed by the game engine. This trivially has no risk, so it is safe to let the computer do it, and it is trivially obvious to the player that this is the case, so it should not ruin any fun to do it.

This reasoning is entirely local: information from only one square is used to determine which action to take next.

It is hard to make the case that the game would be better without this automatic help. Try the following game to get a feel for how it acts when there is no automatic reveal:

Local with surroundings

It shouldn't take long for a new player to realize that when the number of adjacent mines—that is, the number shown on the square—is the same as the number of adjacent unrevealed squares, all of those squares must be mines, so they can be marked as such. Similarly, when the number of adjacent mines equals the number of adjacent flags, the remaining adjacent unrevealed squares must be safe.

These rules take into account one square and whether or not adjacent squares are revealed or flagged.

Performing these rules manually can be entertaining. Combined with a timer, you train to be able to execute these rules quickly and accurately. This makes Minesweeper a twitch game. So what happens if we automate these rules?

One interesting side effect of making this automatic is that placing a flag in the wrong place can now be an immediately fatal mistake.

For the rest of the game, we are left with situations that fall into three categories:

1. Games that are completely resolved by the automatic rules
2. Elaborate situations that require reasoning involving more squares
3. Game states that have no logical way forward—the player is left with no recourse other than to guess at random, maybe weighted by probability

While situation 1 above is kind of neat, it is hardly satisfying to play many such games. Would those games have been better without the automatic resolution? Maybe not; such games are very straightforward even when you solve them manually, and it is not very satisfying to win at games where you have not felt challenged. Of course, for a twitch game there is always some challenge in acting more quickly.

I find situation 2 very satisfying. We get to focus more on resolving logical requirements and less on accurately aiming and clicking the correct buttons. This makes Minesweeper more of a puzzle game.

Situation 3, however, completely ruins the fun. Although I have heard about people that like to play games of chance.

Can we eliminate situation 3?

Complete solution: Global reasoning

To algorithmically discover all logical necessities from the game state, we have to resort to exhaustive search of all game states. Minesweeper is actually proven to be NP-complete. The following is a small, but interesting and illustrative example of a game state that has only one logical solution, but you need to take into account the entire game state to find it:

Is it feasible to search the entire game state space? How many possible states, s, are there?

Given

Then the number of possible states, s, is

For the standard beginner, intermediate and expert configurations, this works out to:

That's a solid "no", the naive approach is out the window. Let's examine what the naive algorithm would have been and see if we can optimize it into something workable.

The naive algorithm

The goal for the algorithm is to find all logical necessities from a given board state. It is tricky to reason about this in a smart way; the computer is better at doing lots of stupid things quickly.

What we can do stupidly, is to generate all possible permutations of mine positions for all the remaining mines. If such a permutation fits with all the revealed numbers it could be the correct solution for the game. When we explore all the possible permutations, we find all possible solutions, but we still do not know which is the correct one.

If there is something in common, either open squares or squares marked as mines, between all the possible solutions, we know that this must be a part of the correct solution for the current board. It is indeed impossible to create a sound solution that does not have this in common, or else we would have discovered it.

This way, we can find all the logical necessities from the current board state.

Constrained and unconstrained squares

The immediate problem with the above algorithm is the number of states it has to explore, as calculated above. But not all squares are the same. The unrevealed squares that are adjacent to a number are obviously constrained by this number. We will call these squares the constrained squares. We will call the remaining squares the unconstrained squares.

If we implement the above algorithm but only search the state space of the constrained squares, and we make sure to backtrack as soon as we violate a constraint, we can resolve all logical requirements in a reasonable amount of time for many games:

For the unconstrained squares we have no way of knowing where the mines go, and we know this logically up front. This means we can remove them from the calculation and only consider the placement of mines adjacent to revealed numbers.

However, we do know that some amount of mines can go into the set of unconstrained squares; if there are 6 mines and 4 constrained squares, at most 4 mines go in the constrained squares, hence at least 2 mines go in the unconstrained squares. By similar logic we can sometimes determine that all the unconstrained squares must be empty or that all of them have mines.

For the following case, we know the position of all the mines, so the AI should be able to realize that the remaining squares are unoccupied:

For the next case, we don't know the position of all the mines, but we can tell that we need to place the remaining mine in one of the two upper left squares. This means that the remaining square in the lower right corner is free:

The chance version

If we automatically execute the global solver, we get the chance optimized version of Minesweeper:

We can kind of divide the games in this version into three categories:

1. Games where you make some arbitrary choices, and you win
2. Games where you make some arbitrary choices, and you lose
3. Games where the AI takes a long time to execute, and you can actually do some reasoning

This is clearly a game of chance. What is the allure of such games? In a logical sense, the above game is similar to the following one:

But which is the better chance game? It seems that other games of chance make a point of having an elaborate connection between your actions and whether or not you win. Drawings of lottery numbers use complicated machines that deliberately take time to select a number and make a show of which number is chosen.

Maybe the large board that is automatically resolved is a somewhat good chance game, given the show of watching all the squares be revealed.

Can we make another type of game?

The deterministic version

We now have an AI that can determine what all the logical steps from a given game state is. Sometimes it will find no logical steps. These are the situations where the player has to guess and may lose the game because of bad luck.

What if we add a new rule? When the game has no logical way forward, you can ask for help. If the AI agrees that there is nothing you can do, you get help. Otherwise, you immediately lose the game. This could be interesting. What should the help be? Maybe that you get to reveal one square regardless of whether or not it holds a mine:

At this point, we have truly gotten rid of the game forcing you into situations where you can lose by chance.

There is only one exception to this, namely that it is still possible to get into degenerate situations for which the global solver will not finish evaluating in a reasonable amount of time. This is unfortunately an unescapable result of the problem being NP-complete, as noted above.

How does the "Request help" button affect the gameplay? It makes for a logically focused game; this is the ultimate puzzle game variant of Minesweeper. One might think that the game would become easier, but instead it gets harder. You no longer have any excuse to make mistakes, and the button is sure to call you out on anything you might have missed. Without the button it is easy to come to the conclusion that you have exhausted all logical possibilities and the only course of action is to guess randomly. With the button, you have to be correct in this assessment.

Concluding remarks

By implementing a full solver for Minesweeper, we were able to develop a variant of the game that gets rid of the bane of Minesweeper; when you risk losing the game randomly after you have invested time and thought into solving almost all of the board. This version is different from the original only in the situations that would require random guessing, so I would suggest that this version is strictly more fun than the original game.

We also developed a variant that will automatically resolve the simple local rules. Whether or not you employ this help is more a matter of taste. It shifts the focus of the game to be less mechanical and more puzzle focused, and is not necessary for getting the improved gameplay that the "Request help" button gives.