Minesweeper AI – Implementation

In my previous post I discussed my plan on how I was going to create my Minesweeper AI implementation. Now that I’m mostly finished, I will now discuss how my implementation turned out.

General Approach

Overall, my approach was pretty simple:

  1. use the basic “guaranteed” Minesweeper novice strategy (looking for revealed cells that are touching a number of hidden cells equal to their mine number) until it cannot be used anymore
  2. brute force through all the possible combinations of mines on the border cells to get the best probability of where the next mine is

Originally I thought about looking for patterns, like the 1-2-1 and 1-2-2-1 pattern, but overall, this is where I had to compromise a bit, as my the original way I set up my logic wasn’t really conducive to pattern matching.

Classes Used

List – this was a simple extension of the std::vector class that I made in order to make my code cleaner and more readable. Has various functions such as add(), remove(), getIndex(), contains(), etc., like you would find in the C# List class.

CellChecker – this is where I put all of my logic for choosing the next cell to reveal. I probably could’ve split this class up a bit more. It is separated into functions for the basic strategy and the brute force strategy, with copious helper functions to facilitate both.

  • basic strategy
    • buildRevealedOpenList()
    • buildFlaggedList()
    • chooseCellsToReveal()
  • brute force
    • bruteForceLogic()
    • checkIf2DVectorContainsVector() – checks to see if a board combination has been tried before
    • adjNumsZeroed() – checks to see if the current possible combination (that is being tested) has placed all the mines it needs to
    • getIfCanPlaceInvisibleFlag() – checks to see if a flag can be placed at a certain cell in the current possible combination (that is being tested)
  • various helper functions

Algorithms?

The basic strategy was just based on the psuedocode I had created in the previous post, with some tweaking to get it “working.”

As for the brute force strategy, I based the idea of it on this post, as well as a few other resources (linked below in the references section) but I had no idea on how to create the actual algorithm for generating possible combinations. So, I came up with a really inefficient method that literally picks random border cells until it comes up with new combinations, and keeps doing that until it has a decent number of possible configurations. Very inefficient, possibly broken, likely flawed, but hey, that’s what I have right now.

Compromises

The brute force idea was much more difficult than I expected to implement. I think part of the problem was that I set up my initial logic for the AI more to suit the basic strategy, rather than anything more complicated than that. Had I set up a more sophisticated system of looking at possible configurations and patterns and such, I think I would be in a much better position now. As it stands, I’m just going to try and refine the brute force strategy and hope it combines well with the basic strategy to form something halfway decent.

Assessment

I don’t have very high hopes for my AI (in its current state). Here’s how it currently stands: on 3 board sizes (Large, Medium, Small) with much easier mine counts than in regular Minesweeper, it will win about 30% Large, 40% Medium, and 60% Small with just the basic strategy supplmented with random picking. However, these mine counts are not even close to what is used in an actual Minesweeper game. When I set the board sizes and mine counts to the classic Minesweeper standards (Large: 16×30 with 99 mines, Medium: 16×16 with 40 mines, Small: 9×9 with 10 mines), my AI won around 0% Large, 0% Medium, and 5% Small. I even played around with the mine counts and it was only when I got within a close range to the original easier constraints, that I was able to repeat my original moderately successful results. Of course, this is where the brute force part of the AI will be useful: situations where the basic strategy just isn’t enough. Unfortunately, as of right now, my brute force supplement is still a bit buggy, so I’m hoping that once I fix it (before this Friday), then it will provide the added competency needed in order to improve my AI’s win rate.

minesweeper-copy

And that is how things stand at this moment, as far as my implementation goes. Next steps: fix brute force algorithm, make both the basic strategy and brute force logic more cohesive, and get a decent win rate by Friday.

– David Hartman

References

http://www.minesweeper.info/wiki/Strategy

http://www.nothings.org/games/minesweeper/

https://luckytoilet.wordpress.com/2012/12/23/2125/

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s