Implementing a Minesweeper Bot

A few weeks ago I wrote a minesweeper bot. It was a great exercise and the complexity of the algorithm was not unlike the Project Euler problems that I solve. For those that are interested, I am posting a video demonstration, as well as the implementation details at the bottom of this post.  I had two main motivations for coding this bot:

  • To learn about JNA
  • To create a computer program that can play minesweeper better than myself

JNA is a java API that is useful for interacting with the Windows OS. I used it to gain information about the minesweeper board. I wanted to learn it so I can write more automated programs that can interact natively with applications on my computer.

This isn't the first time that I've devised a program that can play a game better than myself, but it's the first single player game that I've solved. I've also done work with Nim, Farkle, and BlackJack.  I find it fascinating that a computer program can be more intelligent than the programmer that created it. While that is not entirely true in this case, I did create a computer that was better than myself at a specific task. In my mind, that is still pretty impressive.

Video



Implementation

I programmed the entire bot in java.  I broke it up into 2 main components: parsing the board and creating the intelligence.

Parsing the Board

Parsing the windows 7 game was probably the biggest challenge of this project.  They implemented a fairly advanced lighting system, so cells in the top left corner are brighter than cells in the bottom right corner.  This made it challenging to classify cells based on value and without an accurate reading of the game board, it's impossible to run intelligence.  I used one external library to help with this step - JNA (Java Native Access).  JNA is a java API that allows you to interact natively with the windows operating system, it allowed me to find windows on the screen, determine their dimensions, and manipulate them with java code.

Programming the Intelligence

Writing the AI was the most fun component of this project, as it required a fairly complex backtracking algorithm.
I implemented my AI in steps, adding more and more complexity in each step.

Step 1: Direct Deduction

This step required finding cells within the game that can be picked or flagged using direct deduction.
This is how a beginning minesweeper player would probably play.  This implementation alone yields fairly good results.  
After 1000 trials on each level, this AI earned 824 wins on Beginner, 536 wins on Intermediate, and 24 wins 
on Advanced.  Not bad for a prototype.


Step 2: Multi-Cell Evaluation

The major limitation of the first technique is that it is not able to detect patterns among combinations of 2 or more cells when using deduction.  It fails to find a large portion of cells that can be picked or flagged based on the information given.  The algorithm to solve this is an "optimistic backtracking algorithm".  The basic idea of the algorithm is as follows:


Using this technique, it is possible to find multiple solutions.  To determine which cells are safe to click and which cells are not, I take the intersection of all the possible solutions.  So if cell (5,5) contained a bomb in every solution that this algorithm found, I know that I need to flag that cell.  The java Set interface and the retainAll method proved to be invaluable in this step, providing me an easy and elegant way to merge all the possible solutions.  This AI was much better than the simple deductive AI from Step 1.  From 1000 trials on each difficulty level, this AI earned 939 wins on Beginner, 836 wins on Intermediate, and 326 on Advanced.

Step 3: End-Game Evaluation

This is the most computationally expensive step in the AI, and it only gets invoked when it's absolutely necessary and when the search space is small enough.  It has an advantage over the previous 2 techniques because it takes into account the number of remaining bombs, which can often mean the difference between a Win and a Loss in end game situations.  This algorithm basically distributes the bombs among all possible empty cells and checks for contradictions.  The search space is huge for this technique and is not very useful unless the board is mostly solved.  The actual search space is a combinatorics problem, and the total number of possible configurations is $\binom{unknown \: cells}{remaining \: bombs}$.

Step 4: Adding a Probabilistic Component

In certain situations, it is not possible to directly deduce which cells are safe and which cells are not.  In these situations, I use the same method as in Step 2, but instead of finding the intersection of all solutions, I search for the cell that appears in the most solutions.  This guarantees that I am picking the safest possible cell.  Note that while I pick the safest cell, it's not necessarily the optimal choice as other more risky cells might yield more useful information.  This AI performed the best out of all AI's that I've tested so far.  Out of 1000 trials on each difficulty level, it earned 950 wins on Beginner, 848 on intermediate, and 379 on Advanced.

Conclusion

 My final AI uses pieces from every step.  The first step is the least expensive computationally but also the worst performing, and my AI uses that until it can't anymore.  At that point it transitions to the next one and so forth.  With all the pieces combined into one AI, I believe that it would be pretty difficult to optimize it further.

Note that my simulations are not done with the windows minesweeper software but instead with a custom designed game state.  I assume that bombs are uniformly distributed after the first pick - which may or may not be true in the actual version.  I wrote my own GameState to give me a nice test bed for my AI without worrying about interacting with the windows 7 version.  It also allowed me to run simulations 10x as fast.

The code for this project is available on GitHub, along with a bunch of other AI related projects I've done.  If you try to run it on your own computer, there are a few things you should keep in mind:
  • Make sure you have java 8 installed
  • Make sure you are running Windows 7
  • Make sure the minesweeper style is set to green cells, not blue
  • Let the minesweeper board take up at least half of the screen
  • Make sure Minesweeper is open when you run it, or edit the PROGRAM_PATH variable in the Windows7GameState class to point to the executable



Comments

Post a Comment

Popular posts from this blog

Multi-Core Programming with Java

Efficiently Remove Duplicate Rows from a 2D Numpy Array

Beat the Streak: Day Three