CS50AI - Minesweeper AI

Check out the code for this project here

Building a Minesweeper AI

Minesweeper is a fun game which I have probably wasted many hours in the school library playing. It is a great game to try and solve computationally as it is possible to find the locations of all the mines with surity using reasoning.

For this project I build an "AI" (really just an algorithm) to play minesweeper. I made this project for Harvard's CS50’s Introduction to Artificial Intelligence with Python. This was a good introduction to the knowledge representation of data and how programs can be used to draw new conclusions from this knowledge.

credit

The Architecture of the program

To get a computer to understand the rules of minesweeper i.e. understand that a number 2 means that there are 2 mines in the adjacent squares. To get a computer to understand this we have to translate the board into a formal Knowledge Base.

To do this we use set theory. Each time that we uncover a safe cell the algorithm we have an add_knowledge function which generates a Sentence object that consists of two parts:

• The Cells: A set of all hidden cells surrounding the clicked cell.

• The Count: The number of mines that are in that specific set.

What this means is that if we click a cell and see a 1 and it is adjacent two three hidden cells (A, B, and C), the program represents this as: {A, B, C} = 1.

How the code works

When we have a knowledge list full of these sentences. The program then uses rules to generate information it can then act on. These rules are the following:

• The All-Safe Rule: If the count is 0 this means that every cell in the set is guaranteed to be safe. This means {A, B, C} = 0 and in this case the program loops flags A, B, and C as safe.

• The All-Mine Rule: If the number of cells in the set is exactly equal to the count this tells us that every cell must be a mine. This means {A, B} = 2 and in this case program flags both A and B as mines.

• The Subset Rule: Here I use Python's built-in .issubset() method to compare the sentences. If we know that {A, B, C} = 2 and also know that {A, B} = 1 we can deduce the difference. If we subtract the smaller set from the larger set we gain a brand new sentence: {C} = 1. This sentence tells us that C is definitely a mine.

I then combine this all with a while loop where we recursively check if any of the new data we get unlocks more moves we can make until it finds all and then we make a move via the make_safe_move function.

What's Next?

This algorithm is almost perfect but there a few edge cases where it does not work and we have to make a 50/50 decision. Here is how we could change it to solve these cases:

• Probability: At the moment when we cannot predict a perfectly safe move we just use a make_random_movefunction to make a random move. Instead of doing this we could find a probability of a mine being in each cell using the knowledge sets that we have. This way we could make a better than random move and we would be less likely to lose.

• Global mine count: Currently the program only considers the local number of cells. However, one thing we could do is look at the global number of mines and look at the number of mines we flag to see how many mines are left. This could help us if we have one of these edge cases in the end game.

This was a fun way to learn how to implement the knowledge representation of data and also hopefully to make the hours I spent on minesweeper in the school library worth it.