Minesweeper AI – Code Report

Standard

Just a bit of a warning, my other capstone project hit me pretty hard this week, so I didn’t get to do all that I really wanted to for my minesweeper AI – but here goes.

The Approach

The approach I ended up implementing was pretty much exactly what I detailed in my previous blog post.

My implementation consisted of one new class, Mr Robato. Mr Robato’s main purpose is to run an update loop at every PICK_CELL event and returns an index for the game to reaveal. This update loop goes through three main steps at the moment.

  1. Pick a random cell. Gotta start the game somehow.
  2. Go through the grid, find a revealed cell with mines nearby. See if we can 100% mark off a mine using this info.
  3. Go through the grid and find a revealed cell with mines nearby (again). At this point, we used the info we gained in step 2 to see if we can ensure that other cells around our chosen cell are safe for sure. If they are, stick them in the clickQueue.

Mr. Robato’s update loop structure starts by checking if the “toClick” queue is empty. If it’s not, then we pop the queue and return the index to be revealed (thanks step 3!) If it is empty however, we go through the steps listed above.

The Flaw

What really hurts with development is when you know there’s something wrong but you simply don’t have the time to fix it (at least right now). The main flaw is that if we finish step 3 and the board conditions simply do not let us populate our toClick queue, then we just revert to step 1 – which is go random (I’m sorry).

If I had more time to work on this, I would’ve really liked to implement something along the lines of the “tank” algorithm mentioned in this blog post: https://luckytoilet.wordpress.com/2012/12/23/2125/

The general gist is that it’d be a backup plan that isolated a part of the gameboard – the smaller the better. From here, it would generate every possible configuration for mine places. Then it would cross reference the configurations to either isolate a safe zone or choose a cell with the least chance of having a mine.

It’s not all Doom and Gloom

While my AI may not be perfect right now it does in fact have the capability to win minesweeper. To be honest, the win rate isn’t very high for large and medium game boards, but for the small ones I’d say it’s pretty respectable:

mineOutput

Here’s the console output for 10 games

Out of this batch, my AI won 7 out of 10 games on the small game board. Overall, throughout all my testing the win rate has been about 50/50.

Another thing to mention is that while it does struggle to win the higher difficulties – it definitely makes progress with them, and in some cases comes pretty close to winning. From what I can see, implementing that final step I mentioned is probably the last push the AI needs to start competing in higher difficulties and beyond.

Besides that, there are some minor optimizations I can make before the class competition on Friday that will hopefully improve my AI’s speed. Overall I think it’ll be passable – I’ll post an update with my AI’s performance and any last minute modifications I made at a later date.

 

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