Planning Minesweeps

The first assignment for my senior level programming class, Artificial Opponents, is to solve mine sweeper as quickly and accurately as possible. To determine how I should code my solver, I first did research on optimal solutions to Minesweeper. My searches quickly led to the discovery that Minesweeper as a mathematical or computational problem is NP-Complete, which makes an optimal solution quite complex.

NP-Complete is a term which means the problem is NP-Complex and also NP-Hard. NP stands for Non-deterministic Polynomial-time. Polynomial-time is a reference to the number of operations needed to complete and algorithm given the size of the problem. If it is non-deterministic, that means it can’t be exactly quantified because even given the same problem, the algorithm may behave differently each time. In other words, there is no one best solution. NP-Hard means it is part of the hardest set of NP problems. NP-Complete refers to the hardest set of NP problems because it is the combination of the above.

What this all means for coding a solver for Minesweeper is that there is no single simple solution. There are many steps to solving the game, there are many methods to reach the same end goals, and the outcomes are not assured to be the same each game played. So, the best one can hope for with a minesweeper solver is to get as much speed as possible with as few lost games as possible, but it is at least uncertain if it is possible to win every time and most likely impossible to get the fastest solution every game. Therefore the focus of my code will be on losing as infrequently as possible and making the code as efficient as it can be.

All that said, while I have researched various techniques to solve, I may attempt to solve it myself before using one of the commonly known solving methods. There are for example articles from Harvard and a blog called Lucky’s Notes which describe various techniques to win the game often and quickly. Before finding these articles though, I had thought of my own idea on how to solve the problem and I will describe it below.

Essentially, the simplest rule in Minesweeper is knowing that if you reveal a square, and the number of open areas around the square is equal to the number of adjacent mines revealed, every open square is a mine. After that, if a square has a number of known mines around it equal to the number of mines around the square, any other open squares are not mines. Given those two rules, a lot can be accomplished in a single game. However for more complex problems, there needs to be more deductive reasoning.

My thoughts on how to solve more unknown squares is essentially to assign them probability. If a square has a given number, such as 1, and there are 2 open squares around it, then give each of the two open squares a single probability mark. If another square near one of those squares has a number as well, that square will receive a second probability mark. After all the uncertain squares in an area are given probability marks, the solver will choose the square with the least marks, assuming it is not a mine.

I plan to use this technique and see if it is effective. If it is, I will try to improve and refine it. If not, I may switch to a more well known technique as described in one of the blog posts. This AI should scale with the larger games because the simple rules still apply, and I will limit the probability checking to given areas based on the number of already revealed squares. The area will most likely be limited to all currently open squares adjacent to revealed squares. Hopefully this will make solving quick and accurate.

For major classes in the actual code structure, there will be a structure to hold information on sets of squares. These sets will be already picked squares, squares know to hold mines, and a list of current squares marked for probability and what that probability is. The functions of this class will filter through these lists after picking which action to take next based on the success of the previous action. This includes picking the first square, marking any known mines, marking probability, and then making the next guess. Ideally this will be a fairly lightweight solution that can also be quick and accurate.

Sources:
http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
https://en.wikipedia.org/wiki/NP-completeness
https://en.wikipedia.org/wiki/NP-hardness
https://en.wikipedia.org/wiki/NP_(complexity)
https://dash.harvard.edu/bitstream/handle/1/14398552/BECERRA-SENIORTHESIS-2015.pdf
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 )

Connecting to %s