Writing a Simple Minesweeper-Engine in Python
Originally published on LinkedIn on August 2, 2020
Coming across this project from the Harvard CS50 course made me want to take up the task of writing a solver for Minesweeper. The task combines four intriguing aspects:
Understanding a game of whose strategy requires the application of logic and probabilistic estimates;
Nostalgia (this was, perhaps, the first game I came across on Windows machines as a kid!);
Riding the wave of AI (which, in this case, merely means encoding the steps behind solving the game into an algorithm);
Lastly, it is simple enough to fit a weekend, especially using Python (in contrast to the much more daunting task of writing a C++ Chess engine..)
The implementation is crude in some respects and there are much better solvers around. However, the methods both sufficiently different from my previous article on Chess as well as interesting enough to warrant their own analysis.
This article with start with a brief overview of how to code the game from scratch and a description of the step by step process to code the solver – broken up into some immediate deterministic steps to deduce which cells must be mines (this is the task of the aforementioned CS50 course), and a brief outlook onto the (computationally much harder) probabilistic part. The code is available on github.
The Game
The game is played on a width by height grid containing initially uncovered cells, under each of which there may or may not be one of m mines. Upon uncovering a cell, the game is over in case a mine is hit (the first uncovered cell is guaranteed not to be a mine); Otherwise, the cell will reveal the number of neighboring cells that are mines. The game is won if all cells that are not mines are uncovered. The player also has the option to flag cells that she knows to be mines (or suspects to be).
To encode the game, each cell can be represented as a class, with the default initialization values; The grid is then simply a 2D array of cells and the user interface is implemented using the pygame module.
For each click-event of a cell, the game checks if it is the very first click. If it is, then the mines are randomly distributed across the grid.
If it is not the first click, then:
It is next checked if the cell contains a mine; If not – and the cell hasn’t been clicked already – the neighboring mines are counted (let’s denote that count nb) and displayed on the now uncovered cell. A feature of the original Minesweeper version is that, if nb=0, all other neighboring (nb=0)-cells are revealed. This speeds up the way the game is played out and can be seen in the animation at the beginning (the large whitespaces are instantly visible from one frame to the next).
If, instead, the clicked cell is a mine, the game is over; mines are highlighted in red. The game keeps track of the cells that were already uncovered, and if uncovered cells = width * height – mines, then the game is won by the player.
About 200-300 lines of Python code is all there is to the basic game, which someone more proficient could certainly optimize and further shrink down!
Introduction to Coding a Solver: Representing Knowledge
On a very high level, the suggested solution works along the lines of saving sets of “knowledge” upon each uncovered cell, and performing set-theoretic operations upon them to deduce which cells must be safe to click and, conversely, which must contain a mine.
I followed exactly that approach, with the minor deviation that initially decided not to have the AI “shadow” the game as it is played and add knowledge as each cell is clicked. Instead, the AI analyzed the entire board from scratch each time it is requested to make a move. The obvious disadvantage is that this approach is much slower, which becomes a problem if one wants to simulate many games as a means of estimating play strength. Hence, I discarded this first iteration, and created one with “memory” as suggested - i.e. a persistent set of knowledge that is added on and deduced from each time a move is made. (N.B.: Games are solved five times faster using this persistent knowledge-approach versus my naïve first implementation!)
Now, a set of knowledge can be represented by associating a set of cells with a number. For example, from the below picture, we could infer that:
{A,B,C} -> 2
{A,C,D,E} -> 1
{D,E,F,G} -> 1
In general terms: If cell (x,y) is newly revealed, then we save the number underneath it along with the adjacent cells which must contain exactly that amount of mines (sidenote, if we want to be highly formal and mathematical: This is a mapping from a restriction of the power set of all cells to the natural numbers).
In the python script, a set of knowledge is saved as a list of cell coordinates and an associated integer.
Making Single-Cell Observations
In implementing the above section, we have to update each piece of knowledge as relevant. For example, in the below picture, assume that cell A has been clicked last and is hence known to be safe. Thus, it can be removed from all lists it was contained in: Rather than {A,B}->1 from the upper right corner C, we will now have {B}->1 and hence we know that B must be a mine.
Once we know that B is a mine, we can make a further reduction:
{E,B} -> 2 now becomes {E,B}\{B} = {E} -> 2 – 1 = 1, i.e. we both remove B from the list and reduce the minecount by one. We then know that E must be a mine, and hence {…} -> 4 from cell F can be updated to {…} -> 3.
Implementing the general principle is part of the updateKnowledge() method within the AI-class, which is called each time a move is executed by the game.
Deductions from Subsets
If we have two sets of knowledge K and L, and the cells K.cells of K are contained in those of L (L.cells), then we can infer that the mine count the complement L.cells\K.cells must be the difference in mine counts, i.e. L.cells-K.cells. An example is attached below, where the top right number degenerates from 2 to 1 due to the known mine underneath and the adjacent cells take the role of L.cells. The top middle cell takes the role of K, and then we can immediately deduce that the two yellow cells must be safe.
The algorithm implements this by adding a new knowledge-item for each intersection.
In my initial approach, these subset-checks were performed for all knowledge-pairs, each time a new move is made. Under the revised “persistent” approach, this check only needs to be done for pairs of knowledge with one item restricted to updated/new knowledge, improving performance.
Estimating Probabilities
There are board configurations and move sequences where the player will be forced to make a guess. The CS50 suggested solution involves selecting a random move if the above deduction steps yield no known safe cell (of course, this random selection should exclude known mines).
Sticking to this approach, the solver has a win rate of 67.7% after 10.000 games on Advanced (16x16 board, 40 mines).
We can do better by considering the probabilities yielded from the constraints imposed by the numbers under safe cells. We start by looking at the remaining uncovered cells, f, and the remaining mines that must be present, m. The initial probability estimate for each remaining field will hence be m/f Now, this number is a bad lower bound for the probability of a mine being present and does not tell us much since it is constant across cells. If we now consider each piece of knowledge, we might improve these estimates: For example, given {A,B,C}->1 we can estimate p(A)=p(B)=p(C)=33.3%. Iterating through all sets of knowledge and updating the cell probabilities as needed, we can obtain a naïve set of lower bounds, and select the cell with the lowest estimate.
This simple approach already improves the win rate to about 75% (tested over 10.000 games).
A more sophisticated approach would consider the actual configuration space of the remaining uncovered cells, accounting for all constraints imposed by the bordering numbers simultaneously. The precise probability of a cell X being a mine would then be:
# all possible distributions of mines on the grid where X is a mine / # all possible distributions of mines.
This would be extremely computationally intensive. At the beginning stages of the game, where the number of configurations will be close to (#cells)! / (#mines)! * (#cells - #mines)!, and hence for all practical purposes infinite, such an approach makes no sense. It could, however, be done at the endgame with only a few remaining cells left; Or it could be done earlier than that, where the distribution of mines is only sampled (instead of fully computed). However, the implementation of such an algorithm will be left for another day.