How to solve "Minesweeper" (and make it better)

Minesweeper is a simple game with simple rules, however some of its configurations create interesting difficulties. In this article, we will create a Minesweeper solver with increasing complexity, and reflect on how the dynamics of the game changes with a gradual increase in the level of help. In the end, we will develop a new version of the game with much more interesting gameplay.

Local reasoning: zero adjacent mines

In the original game , one automatic mechanism is used: when a player opens a cell, next to which there are no mines, the game engine opens all neighboring cells. This does not threaten the game, so you can safely let the computer do it, and the situation itself is immediately clear to the player and does not interfere with the gameplay.

This reasoning is completely local: only one cell information is taken into account to decide on the next action.

It is difficult to come up with a situation in which the game would become worse without this automatic help. Try to play such a game to get an idea of ​​how it goes without automatically opening the cells [in the original article, all examples are interactive]:

Local considerations based on the environment

It will be easy for a new player to understand that if the number of neighboring mines, that is, the number shown in the cell, is equal to the number of undiscovered neighboring cells, then all these cells must be mines, so you need to put flags on them. Similarly, when the number of neighboring mines is equal to the number of neighboring flags, then the remaining undiscovered neighboring cells must be empty.

In these rules, one cell is taken into account, as well as the state of neighboring cells (open / checked).

Manually implementing these rules can be fun. If you add a timer, the player begins to learn how to apply them quickly and accurately. This turns the Minesweeper into a reaction game . What happens if we automate these rules?


Such automation has an interesting side effect - checking the box can have fatal consequences instantly.

Otherwise, we may experience situations that can be divided into three categories:

1. Games fully resolved by applying automatic rules
2. Complicated situations requiring more cells for reasoning
3. States of the game in which there is no logical way forward - the player can only choose by chance, possibly taking into account the probabilities.

Situation 1 seems beautiful, but not particularly interesting if it arises too often. Would such games be better without an automatic solution? Maybe not; such games are very simple even when solved manually, and the player is not particularly interested in playing games in which there are no difficulties. Although, of course, there is always difficulty in the reaction game: you need to act as quickly as possible.

Situation 2 seems very attractive to me. We focus more on solving logical conditions, spending less time on precise aiming and pressing the right buttons. This makes Minesweeper more like an active puzzle .

Situation 3 completely destroys all the fun. However, I heard that some people like to play games with randomness .

Is it possible to get rid of situation 3?

Complete Solution: Global Reasoning

For the algorithmic detection of all the logical conditions necessary for the state of the game, we need to perform an exhaustive search for all the states of the game. Minesweeper is proven to be an NP-complete task . Below is a small, but interesting and illustrative example of the state of the game, having only one logical solution, but to find it you must take into account the state of the game as a whole:


Is it possible to search the entire space of game states? How many variations of s state exist ?

Given:

w = field width

h = field height

k = number of mines

n = w · h

Then the number of possible states s is

$$

For the standard levels "Beginner", "Amateur" and "Professional" this gives us:

$$

$$

$$

We understand that a naive approach is completely inappropriate here. Let's see how a naive algorithm might look and find out if it can be optimized into something that works.

Naive algorithm

The task of the algorithm is to find all the logical conditions necessary for the given state of the field. It would be difficult to implement this by carefully considering the solutions; the computer does a much better job of quickly performing a bunch of stupid actions.

What can we do “stupid”: generate all possible permutations of mine positions for all remaining mines. If such a permutation corresponds to all open numbers, then it will be the correct solution to the game. Then we study all possible permutations, find all possible solutions, but still do not know which one is correct.

If in all possible solutions there is something in common, either among open cells, or among cells marked as mines, then we understand that this common should be part of the right decision for the current field. And in fact: it is impossible to create the right solution that does not have such matching elements, otherwise we would have discovered them.

Thus, we can find all the logical conditions necessary for the current state of the field.

Cells with and without restrictions

The above algorithm has an obvious problem: the number of states that it needs to investigate. But not all cells are the same. Unopened cells next to a number are obviously limited to that number. We will call these cells limited. The remaining cells we will call unlimited.

If we implement the above algorithm, but we will only search in the space of states of restricted cells, and we will go back as soon as we break the restriction, then in many games we can solve all the logical conditions in a reasonable amount of time:


In the case of unlimited cells, we can’t find out where the mines are located, and logically we immediately know about it. This means that you can exclude them from the calculation and consider only the location of mines near open numbers.

However, we know that a certain number of mines can enter many unlimited cells; if there are 6 min and 4 restricted cells, then in limited cells there can be a maximum of 4 mines, that is, at least 2 minutes must be in unlimited cells. By a similar logic, we can sometimes determine that all unlimited cells must be empty or all contain mines.

In the case shown below, we know the positions of all mines, so the AI ​​should be able to understand that the remaining cells are not occupied:


In the following case, we do not know the positions of all mines, but we can understand that the remaining mine must be placed in one of the two cells in the upper left. This means that the cell remaining in the lower right corner is free:

Random version

If we automatically run the global solver, we will get a randomly optimized version of Minesweeper:


You can divide the games in this version into three categories:

1. Games in which the player makes arbitrary choices and wins.
2. Games in which the player makes arbitrary choices and loses.
3. Games in which AI requires a lot of time, and the player can actually use reasoning.

Obviously, this is a game of chance. What is the appeal of such games? In terms of logic, the game shown above is similar to this:


But which random game is better? It seems that the meaning of other games with randomness lies in the existence of a complex relationship between the player’s actions and winning / losing. To draw the lottery numbers, complex machines are used that are not particularly in a hurry in choosing a number and make a whole show out of showing this number.

Perhaps a large field, which is decided automatically, is a pretty good game
with randomness, given the fact that the player observes the gradual opening of all cells.

Can we come up with a different type of game?

Deterministic Version

Now we have an AI capable of determining all logical steps from a given game state. Sometimes he will not be able to find logical steps. In such situations, the player has to guess and he can lose if he is not lucky.

What if we add another rule? When the game has no logical way forward, we can ask for help. If the AI ​​agrees that the player cannot do anything, then he comes to his aid. Otherwise, the player loses immediately. This may be interesting. What kind of help can this be? Perhaps you need to open one cell, regardless of the presence of mines in it:


Thus, we completely got rid of situations in which one could lose by chance.

However, there is one exception: there is still the possibility of degenerate situations in which the global solver cannot complete the calculations in a reasonable amount of time. Unfortunately, this is the inevitable result that the Minesweeper task is NP-complete.

How does the “Ask for Help” button affect the gameplay? It leads the game to focus more on logic; This is the most "puzzling" version of "Minesweeper". Someone might think that the game will become easier, but in fact it is becoming more complicated. Now there are no excuses for the player’s mistakes, and the button will punish him if he missed something. Without a button, it is easy to conclude that you have exhausted all the logical possibilities and the only option for the development of events is to try to guess randomly. But due to the existence of the button, the player must be right in this assessment.

Finally

By implementing the full Solver “Minesweeper” solver, we were able to create a variation of the game, free from its curse: now it is impossible to lose due to the fact that you have to choose by chance when you have almost decided the whole field. This version differs from the original game only in those moments when you need to guess randomly, so I can assume that it is much more fun than the original game.

In addition, we developed a version of the game that automatically solves simple local rules. Whether to use such help is up to you. It shifts the focus of the game from mechanical clicking to a more puzzling gameplay. In this case, it is not necessary to use the improvement of the gameplay, which is provided by the button “Ask for help”.