Minesweeper AI Plan

Being tasked with creating an AI to solve minesweeper puzzles and never having played more than a handful of minesweeper games, I took to the internet to figure out how to play the game most successfully. The first site I found was: http://www.minesweeper.info/wiki/Strategy, a guide to how humans should approach the game. The useful information from this page is the “First Click” section, this shows the success rate for various different starts.

After a bit more searching I found this page: http://luckytoilet.wordpress.com/2012/12/23/2125/, which is the most comprehensive post on writing a minesweeper solver I’ve found. Here three phases of solving are outlined, straightforward, tank, and endgame.

Straightforward compares the number N of a square, number of flags F around the square, and the number of unopened U squares. If N = F + U, then all the unopened neighbors need to be flagged. If N = F, then all the unopened neighbors can be opened. The Straightforward phase also can use the information of two neighboring squares to make a choice.

If neither of these options are available, the tank solver comes in to brute force our way to intelligence. The tank solver enumerates all possible mine positions and looks for the consistencies across all possibilities. For example, if across all possibilities there is only one position for a mine, then we can flag that square, same for any tiles that are clear in all possibilities.

At this point if the tank solver failed, guessing is just about as best as we can do. The endgame phase uses probability and some tricks to make the best guesses it can with the given information when few squares are left unopened/unflagged. The probability is deduced from enumeration, one trick is using the mine counter when we have more possible positions than mines left.

I think this pretty much summates how I’d like to approach the solving algorithm, I still need to figure out how my enumeration logic will work, but I think that’s a minor risk. By far the best part of this approach is that it needs no scaling from me, no matter the size of the board, the approach is the same.

As for the classes I plan on using with this algorithm, I think I’ll wrap most everything into a “solver” class. The 3×3 data describing a square and its neighbors will be either a class or a struct, and might contain space for probabilities, but I can’t say for sure. Based on the algorithm I’ve described I’m fairly certain that I could get away without classes for this solution, but I think a solver class will make my code much more tidy when dealing will the transactions my .dll will need to handle.

 

Advertisements

2 thoughts on “Minesweeper AI Plan

  1. Hey. I’m the author of the minesweeper AI post that you linked to. Recently I’ve seen a lot of blog posts linking to my article, all trying to create a minesweeper AI. I’m curious — is this for a school project? What course is it?

    Liked by 1 person

    1. I gotta thank you a ton, your post is the best on the subject I’ve found. The posts are for a project that’s part of a class at champlain college titled: artificial opponents. Our professor made a c++ minesweeper game that takes a dll for handling a player/ai input.

      Like

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