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

This post is part of a series, please see the first post for more background.

A successful attempt by the solver

Developing the Solver

When a game of minesweeper is begun, two pieces of information are known: the number of elements in the grid and the number of mines. From this information, the probability of containing a mine for each element in the grid is

This seems intuitive, but it is actually a special case of a more general form.

The probability of a random event can be expressed as the number of outcomes for which the event occurs divided by the total number of possible outcomes. In the case of minesweeper, the probability of a  particular square containing a mine can be found by dividing the number of configurations of mines that include the square by the number of possible configurations.

The example below illustrates the probability of a mine occupying the square in the top left corner.

Three favorable configurations

---------------------------------------

Six possible configurations

The number of possible configurations of mines has a special name and notation. The expression in parentheses below is pronounced "n choose k". It is equal to the number of distinct k-sized subsets that can be selected from a set of n elements.

Binomial Coefficient

Consider the animations above. The number of favorable configurations at the top would be calculated as "three choose one". Meanwhile, on the bottom, the number of possible configurations is equal to "four choose two". For the purpose of calculating the initial probabilities at the start of the game, they should be equal across the board. For each element, dividing the number of favorable configurations by the total number of configurations  reduces to the intuitive ratio that we started with.

This seems like a lot of unnecessary thought went in to calculating something as intuitive as the initial distribution. However, as the grid becomes populated with measurements, we will have to augment our approach to calculate the new distributions.

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.