Solving Minesweeper: Pt 1

Background for anyone reading this fresh:

Artificial Opponents is effectively Advanced Game AI, where we don’t create actual AI, we just create an algorithm that solves whatever problem we’re looking at, but never actually learns from its experiences.

The class has three games that we’re to create optimal solving algorithms for, the first being minesweeper. This blog post is to try and detail my thoughts going into the project, and how I aim to solve it.

The human brain is a powerful thing, able to perform a lot of quick calculations without our conscious knowing. It’s how professional players in esports are capable of pulling off split second moves and strategies before they themselves can fully comprehend what they’ve done.

Using that idea – that human brains subconsciously attempt to make the best decisions, especially after multiple attempts of trial and error where we develop a problem solving algorithm of our own, which can also be called ‘using your gut’ – as a basis for my algorithms, I first looked at myself, having played a fair bit of minesweeper – in particular, how exactly I solve minesweeper – and what particular moves I take to undergo that process successfully.

Also of note, at times there are situations of random chance, but before the time comes where you have to randomly click on a square to reveal it, you can narrow it down as far as possible without tripping a mine through a series of calculations.

The standard rotation of moves that can be made until real calculations need to be done I have determined to be as of follows:

  1. Click a square to begin, center or corner, author’s pick (I have chosen the upper left corner of (0, 0) for now, but it may more optimal to choose a center square).
  2. Add any revealed cells to a revealed cells list (for optimization, scanning just that you can see will be far quicker in the long run than scanning cells you have no information of).
  3. Add any cells that are obviously mines to the flag list. Ex. The cell you are currently viewing is marked as 1, and of the 8 surrounding cells, 7 are revealed. The 8th must be the mine, and can safely be flagged.
  4. Using the flag list, reveal all squares that are 100% assuredly not mines, adding those revealed cells to the revealed cell list.
  5. Return to step 2 and loop this process until there are no more guaranteed moves.

Typically the size of the map has some impact on the success of that loop alone. The smaller a map, the less conflict there will be, and you could use this process to determine with 100% accuracy the solution. As the size of the map increases at a rate that is not parallel to the increase in mine count (higher difficulties have a higher ratio of bombs to area), this loop will eventually hang, and you must begin calculations to determine what squares are safe.

Allow me to show you an example:

MinesweeperSit1-1

 

In the above example, we’re looking at the red squares in particular, and what we can determine from them, despite no obvious answers.

So let’s take a moment and get some answers. The 2 square within the red guarantees that we have 2 bombs within the orange area, each square having a 33% chance of having a bomb. So of the left two most squares, there is a 100% chance of being a bomb, as one of those squares must contain a bomb.

In this particular case, we don’t care which one it is, all we need to know is that the 1 square within the red knows that 1 bomb exists within the 3 squares below it, and because we know that a bomb must exist within the 2 right most squares (of the blue square and using orange’s left 2 squares), blue must be a safe square.

And voila:

MinesweeperSit1-2

In this case, that was but a small example, but ideally with proper calculations and the above 100% deterministic loop, much more can be solved than just the 100% loop alone.

Last thing to cover, there is absolutely the potential of running into a situation where you have to guess. In those situations, you can guess randomly, or guess intelligently, using much of the same logic as just demonstrated. Narrowing down the % odds of a square being safe will increase the rate to which you can be successful.

More to come, hopefully I can manage it to work.

Advertisements

One thought on “Solving Minesweeper: Pt 1

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s