An Artificial Intelligence Approach to Minesweeper


1. Introduction

Minesweeper is a puzzle video game that is introduced with Microsoft Windows at 1989. In this game, environment is represented as a grid of squares. The grid has a limited number of total mines, and each of the squares may or may not contain a mine. The game proceeds by arbitrary choices of the player agent. If the player clicks on a square which is a mine, player looses the game. However if the square is not a mine, then a number is appeared on the square, which indicates how many mines exist in adjacent squares of the clicked square. This hint helps player to click squares more clever instead of random choices. The game is successfully completed whenever the user reveals all the squares that are not mines.

2. Objective

The main objective of this article is to describe an artificial intelligence agent that plays the game in a rational way, with considering performance and computational complexity.

NP-completeness of the Minesweeper consistency problem was proved by Richard Kaye by demonstrating algorithmic equivalence of Minesweeper consistency and SAT problems. Therefore under assumption of \(P \neq NP\), we can conclude that the best solution to this problem is exponential. However, we can expect to improve the algorithm enough to solve all reasonably difficult games of a typical implementation of Minesweeper.

3. Problem Domain

3.1 Minesweeper Consistency Problem

Kaye's study has a fundamental importance for understanding the general Minesweeper problem domain. Kaye defines a decision-problem called MINESWEEPER CONSISTENCY or CONSISTENCY for short, such that "Given a rectangular grid partially marked with numbers and/or mines, some squares being blank, determine if there is some pattern of mines in the blank squares that give rise to the numbers seen". Kaye constructed a polynomial-time Turing reduction from SAT to CONSISTENCY.

Theorem 1. A decision problem \(Z\) is NP-complete if and only if \(\exists X \in\) NP-complete, \(Z \in NP\), and \(X \leq_T^p Z\).

Proof. The proof was given by Brassard & Bratley.

K. Pedersen has demonstrated that \(SAT \leq_T^p CONSISTENCY\) and \(CONSISTENCY \in NP\). NP-completeness of the SAT problem was proved in early 1970's by Steven Cook as well. Therefore it is demonstrated that CONSISTENCY problem is NP-complete.

3.2 Minesweeper Inference Problem

It is important to notice that NP-completeness of CONSISTENCY problem does not imply that Minesweeper itself is NP-complete. Allan Scott defines a separate decision problem called MINESWEEPER INFERENCE or INFERENCE for short such that, "Does there exist at least one covered square whose contents can be safely inferred given a consistent configuration?". According to D. Bacerra, INFERENCE problem is integral to Minesweeper itself.

Despite not being NP-complete, general Minesweeper problem is still computationally difficult to solve. This conclusion comes through proof of co-NP-completeness of INFERENCE problem. In a similar fashion to Kaye's proof, Allen proves co-NP-completeness of INFERENCE problem by first showing INFERENCE is in co-NP, and then constructing a polynomial Turing reduction with Boolean circuits.

Under the assumption of \(P \neq \textit{co-NP}\), we can conclude that general Minesweeper problem is not solvable in polynomial-time. Hence our artificial intelligence agent have to run an exponential-time algorithm.

4. The Solution

4.1 First Move Considerations

The first click of the Minesweeper has a special importance. In initial configuration, knowledge-base is empty and player is forced to make a guess. There are typically two types of implementation approach in terms of first move. Some of the implementations of the game guarantee that the first move is always safe whereas in some implementations player has the probability of clicking a mine.

For a \(M \times N\) rectangular grid with \(B\) number of total bombs that uniformly distributed to grid, a non-constrained cell \(x\) is unsafe (i.e contains a mine) in probability of: \[ P(x = mine)= \frac{B}{M.N} \tag{1} \]

In a similar manner, for a safe cell \(x\) whose adjacent are non-constrained and undiscovered, label of x is zero in probability of:

\[ P(label(x) = 0) \approx (1-\frac{B}{M.N})^{k + 1}, \tag{2} \]

where k is total number of neighbors of \(x\). As it is seen from the equation, best choice would be selecting the cell which has minimum number of neighbor cells.

Heuristic 1. In case of absolute zero knowledge and no constraints, agent should click the square with minimum number of total adjacent.

4.2 Constraint Satisfaction

As demonstrated before, a Minesweeper configuration can be modeled as a Constraint Satisfaction Problem. Each revealed square specifies a constraint, and each unrevealed square becomes a variable with two possible domain values such as safe or not safe. Also total number of remaining bombs indicates a constraint as well. Each and every unrevealed square is under some constraint in this manner.

Minesweeper is not a deterministic winnable game by its nature. At some point current constraints and knowledge-base may not be sufficient to make a new inference or find out the value of a new variable. In this case our agent would appeal to make a guess using probability calculation of being safe by enumerating all possible layout configurations.

Let \(E(V, A)\) be the set of all possible valid layout configurations of bombs under current constraints of the all variables \(\forall v \in V\), according to all assignments \(\forall a \in A\). For a square \(x\);

\[ P(x = safe) = \frac{|E(V - \{x\}, A \cup \{x := safe\})|}{|E(V, A)|} \tag{3} \]

This approach necessitates our agent to enumerate all possible configurations. While each unrevealed square is a variable, there are \(2^n\) possibilities for \(n\) number of unrevealed square. Thus our inference algorithm would be \(\Omega(2^n)\). This kind of brute force approach is not feasible in practice, even for a typical game layout with \(50 \times 50\) grid. Therefore our agent must behave more clever without any trade off.

4.2.1 Quick Action Strategy

Because of the Minesweeper's nature, every new information of our knowledge-base is likely to make our agent to have more 'valuable' inferences. In this way, some new information may cause our agent to use more efficient methodologies for inference, as we will discuss later.

Heuristic 2. If our agent finds out using any inference mechanism that a square is safe, it should immediately click that square, and terminate current enumeration or search operation if any.

4.2.2 Single Square Strategy

Normally constraint satisfaction systems are solved with respect to all constraints, variables and domain values. Fortunately, for Minesweeper problem, in many cases we can make inferences by only considering one constraint, because usually there exists some constraint that has only one influential variable.

Heuristic 3. For each move, agent should first investigate and solve individually solvable constraints until no more individually solvable constraints are left.

This is an intuitive and very powerful heuristic whose time complexity is linear. The agent might even complete the game using this heuristic in easy levels of Minesweeper, also it is likely to make significant progress in hard levels in linear time.

4.2.3 Constraint Partition

Let \(Q\) be the set of all unrevealed squares, and each of them is a variable. Each square is constrained by the 'total number of remaining bombs' parameter, and some squares are constrained by the 'label' of other revealed squares.

Definition 1: A square is \(directly\)-\(constrained\) iff any of its adjacent squares is a constraining cell (i.e a revealed cell which has a label on it). An unrevealed square is either directly or indirectly constrained.

\[ Q = \{\;x\;|\;x\;is\;unrevealed\;\} \] \[ D = \{\;x\;|\;x\;is\;directly\,constrained\;\} \] \[ I = \{\;x\;|\;x\;is\;indirectly\,constrained\;\} \] \[ D \; \cup \; I = Q \; and \; D \; \cap \; I = \varnothing \]

It is redundant to make exponential enumeration (or backtracking) for indirectly constrained cells. Mine probability of an indirectly constrained square only depends on two variables, and it is equal to \(\frac{b_I}{|I|}\) where \(b_I\) is the total number of remaining bombs on indirectly constrained cells. Although the game only gives us the value of \(b\), which is total number of remaining bombs on overall grid, we can find \(b_I\) as \(b - b_D\) where \(b_D\) is the total number of remaining bombs on directly constrained squares.

The value of \(b_D\) is not deterministic but probabilistic. For some layout configurations value of \(b_D\) may be different from some other configurations. Those values can be calculated by enumeration. However by the assumption of the bombs are uniformly distributed to grid, we can approve that mine probability of an indirectly constrained square is

\[ P(x = unsafe \; | \; x \in I) = \frac{B}{M.N} \]

With constraint partition method, number of variables that are considered for enumeration is reduced significantly.

Heuristic 4. It is sufficient to investigate only directly constrained squares by backtracking, and after calculating mine probabilities of the directly constrained squares, the agent should click the cell with lowest probability of being unsafe with considering indirectly constrained cells also.

4.2.4 Independent Variables

Intuitively, values of the some directly-constrained variables may have no effect to some other directly-constrained variables. For such cases, we can separate directly-constrained squares into disjoint sets, and enumerate these sets individually.

Definition 2. Two directly-constrained squares \((x,y)\) are considered dependent iff both \(x\), and \(y\) are constrained by the same label, or there exists some directly-constrained square \(z\) such that both \((x,z)\) and \((y,z)\) are dependent pairs. Any pair of directly-constrained squares are either dependent or independent by definition.

Heuristic 5. Directly constrained squares should be split into disjoint sets according to variable dependency, and each set should be considered separately for enumeration.

4.3 Enumeration by Backtracking

Since the INFERENCE problem is co-NP-complete as stated before, enumeration is the inevitable solution method after some point. Until now, we have investigated several ways to reduce the total number of variables that will be enumerated in one time. Henceforth we need to model our CSP as a linear equation system, and enumerate all valid configurations using backtracking in order to calculate equation (3).

Each constraining square \(x\) (i.e revealed square which has a label on it) indicates a constraint, and that constraint can be expressed as an equation \(e\) such that,

\[ v_1 + v_2 + \cdots + v_n = C \]

where \(C\) is the label of \(x\), and \(v_1, v_2, \cdots, v_n\) are the possible values of the adjacent unrevealed squares of \(x\), with domain values \(0\) means the square is safe, and \(1\) means the square is not safe (i.e contains a mine).

For \(k\) number of constraining cells, we have an equation system \(E\) that consists of \(e_1, e_2, ... , e_k\).

\[ \left\{ \begin{array}{ccc ccc c @{\extracolsep{ 2.5pt}}c@{\extracolsep{ 2.5pt}}c} v_{1,1} & + & v_{1,2} & + & \cdots & + & v_{1,n_1} & = & C_{1} \\ v_{2,1} & + & v_{2,2} & + & \cdots & + & v_{2,n_2} & = & C_{2} \\ \vdots & & \vdots & & \ddots & & \vdots & & \vdots \\ v_{k,1} & + & v_{k,2} & + & \cdots & + & v_{k,n_k} & = & C_{k} \\ \end{array} \right. \]

The backtracking algorithm will be empowered by forward checking and constraint propagation. After each new assignment, current status of the assignments will be checked by our constraint equations, and available domain values of the all variables will be tracked as well. In this way, the algorithm will be able to detect some of the inevitable failures early. Also our agent will use some other heuristics in order to improve performance.

Heuristic 6. If there exists some constraint equation with \(n\) variables and right-hand-side value of \(C=0\), then all of its variables are equal to \(0\). Also if \(C=n\), then all of its variables are equal to \(1\). Enumeration is not required for these variables for such cases.

Heuristic 7. While forward checking, equations should be sorted in descending order with respect to total number of variables in that equation, and while selecting new unassigned variables to assign to, variables should be chosen according to the order in which they are seen in the sorted equation system.

5. Conclusion

In this article, we described an artificial intelligence agent to solve Minesweeper problem in reasonable performance, by modeling the problem as a CSP, generating linear equation systems, and enumerating by special kind of backtracking algorithm with support of some heuristics.

Although this algorithm has polynomial space and exponential time complexity, we have achieved to improve the algorithm enough to solve all reasonable instances of a typical Minesweeper game.

6. Sample Implementation

An example implementation that was originally created for a school assignment can be found at: https://github.com/align-els/MinesweeperAI