Using Bayes' Theorem to Track Probability Distribution of Minesweeper Grid (Part 1)

Señor Smiley says, "deal with it"

Introduction

Your head a splode

I've decided that it would make a fun project to create a Minesweeper solver. Minesweeper is a classic puzzle game composed of a grid in which a known quantity of mines are randomly distributed. The objective of the game is to identify all of the squares that contain mines. The player may progressively select elements of the grid to reveal. If the element is unoccupied, it will display the number of adjacent mines. If an element is occupied, it will explode and end the game.

The two right-most squares on the
bottom row have a 50% chance
of containing a mine.

For the most part, when solving Minesweeper, deductive logic will do most of the heavy lifting. However, many games of Minesweeper cannot be completed strictly without guessing. Especially on expert level games, there may be situations when the player does not have enough information to conclude that any particular unrevealed element is unoccupied.

I'm interested in creating an algorithm that will track the probability  of containing a mine for each element in the grid. Primarily, I want to explore whether or not I can utilize Bayes' rule to calculate subsequent probability distributions by leveraging the current distribution. More explicitly, if the game is split into a sequence of choices and their resulting game states, I want to find out whether or not I can leverage the probability distribution at state n along with the measurement (the number of mines adjacent to the latest revealed element) in order to calculate the distribution at n+1. I believe that I can do this by framing the question in terms of conditional probability. After a measurement is made, the probability of a particular element containing a mine conditioned on the measurement can be computed using Bayes rule.

Bayes' Rule

This is not necessarily an efficient approach to solving games of Minesweeper. Depending on the mine density, some games can be solved without ever relying on guessing. Therefore, one strategy that would be more efficient than this one would be to apply deductive elimination whenever possible and calculate the probability distribution (as needed) directly from the current game state. My hope is that, if I develop the probabilistic approach correctly, the deductive methods will emerge organically.

Python Tkinter Minesweeper

The solver needs access to a few pieces of information to start: the total number of  mines and the dimensions of the grid. In addition, at every step of the game, it needs the location of the latest revealed element and the measurement at that position.

In order to make this information available, I decided to create my own version of Minesweeper in Python using Tkinter. While I could have borrowed an open-source implementation or written an interface for the Windows version that could interpret the current state of the board visually, I was compelled to write my own version because it seemed relatively fun and straightforward. I chose to use Python because the Tkinter package is available with the default installation and is useful for quick and easy GUI development.

Señor Smiley

There are a few important features to include when creating a Minesweeper game. There must be a grid of buttons, a display indicating the number of flags remaining to be placed, a clock showing elapsed time, and a smiley face. I chose to forgo the clock as I am not particularly interested in the speed of my solver (and if I were interested in speed, I would not include a GUI in the analysis). Functionally, the game needs to respond to the user's selections by revealing the number of adjacent mines or ending the game if the element selected contains a mine. The win condition must also be tested when a square is revealed. This can be evaluated by comparing the number of mines to the number of remaining unknown elements.

Silly win condition

Some common non-essential features are the ability to place flags and question marks in order to track the location of mines. These flags do not have any bearing on the win condition; if they did, Minesweeper could always be solved without risk by placing flags over all possible configurations.




The game must also guarantee that the first user-selected element is not a mine. This can be done by waiting to generate the random mine distribution after the first selection is made, excluding the current selection.

Empty elements reveal
adjacent squares.

Finally, one particularly convenient feature is for the grid to automatically reveal adjacent squares when an empty square is selected and to propagate this behavior over all locally connected empty squares.

Implementation Overview

I encapsulated everything in a single minesweeper class which inherits from the tkinter.Tk class. On initialization, a grid of buttons are created and stored in a list, the solver is initialized, and all of the other GUI features are initialized. When tkinter buttons are initialized, the "command" callback function can be defined as a lambda function with constant arguments indicating the location of the button. 

In that way, a general callback function is defined for all of the grid buttons which will uniquely address their location in the grid. When the user makes the first selection, the game generates a random distribution of mines, always excluding the selected square.

First choice never
results in a mine.

Right-click callback functions are assigned to grid buttons with tkinter's "bind" function. This callback function cycles the text parameter in the referenced button object through a sequence of symbols: an empty string, a flag "F", and a question mark.

Currently, game parameters (width, height, number of mines) are defined as command line arguments when running minesweeper.py. There is no way of modifying these parameters in the game. Additionally a minesweeperSolver is instantiated within the minesweeper class; whether or not it is allowed to make selections in the grid is optional, but the solver is always running in the background. This might cause problems when trying to play a particularly large game manually. The user may also choose to allow the solver to highlight the recommended square in green.

Ideally, for the sake of organization, there would be a container or parent application which would instantiate both minesweeper and the minesweeperSolver. I don't intend to change these organizational things as they aren't really part of my focus.

In later posts, I will describe my process for developing the minesweeperSolver class using Bayes' rule. As of this post, there are still issues with the solver. I'm trying to determine whether or not the problem is with my theoretical approach or in the implementation. Somewhere along my quest for a purely probabilistic solver, I ended up creating a constraint-based algorithm. I am starting to wonder if I would be better off abandoning the current measurement-update model; more on that next time.