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.

Return to school

By Ed Yakovich [Public domain], via Wikimedia Commons

I haven't posted in a while as I haven't been working on anything that can be considered project-driven or really worthy of a post. In the late summer, I was signed up for three additional Coursera courses: Computer Networks, Startup Engineering, and Discrete Optimization. I didn't post on any of them because I wasn't able to finish them. I was interrupted for a very good reason. This fall, I'm jumping back into the academic life. I had a decent time working as a mechanical engineer in industry but never felt satisfied with my level of knowledge. I would spend a lot of free time researching some advanced topics that interested me and now I am ready to start devoting myself to that purpose full time. It is very exciting.

Earlier this month, I moved to Philadelphia to start working at the Scalable Autonomous Systems lab under Dr. Ani Hsieh. I'll be taking over a project that was started by two students over the summer. They have been developing a new generation of the SAS lab's ground robots to be used as a platform for future research. The primary motivation for the new robots is to utilize the multi-core processors recently available on ODroid single-board computers for processing data from RGB-D sensors. I spent most of my time during the first week trying to digest their design documentation and code as I'll need to understand all of the work that they have done in order to continue development.

By Conspiritech (Own work) [Public domain], via Wikimedia Commons

In reality, a lot has been done already, there was a functioning (moving) robot when I walked in the door on the first day. However, as with all projects of this nature, there are plenty of places where improvements can be made. Concessions are often made on the road to functionality and it is important to identify which ones are worth shoring up. I spent a majority of last week rewriting the Arduino code to eliminate the use of floating point data types, implement interrupt-driven encoder reads, eliminate redundant variables, and generally streamline things as much as my naive C-coding skills will accommodate.


Tomorrow I start my first class as a Mechanical Engineering PhD student at Drexel University. I'll be studying Advanced Dynamics and Applied Engineering Analytical Methods. Advanced Dynamics kind of looks like it will cover the same topics that I was drawn to last year when I was playing around with writing an inverted pendulum simulator in GNU Octave. The Analytical Methods course will hopefully be relevant to the work that I do in the future. I don't often like application-driven classes as they tend to skimp out on the theory but this one seems worth while. Overall, I am excited to get started, we'll see how energetic I am next month.