Minesweeper AI – Postmortem

Standard

Well the testing day for our Minesweeper AIs came and went, and my AI pretty much performed as expected.

Results:

While I lacked the time to make AI compete with the class’s top contenders, its solid win rate of 60-70% on small games and its occasional triumph of medium sized games allowed it to pass class specifications.

Last Minute Optimizations:

I made two last minute optimizations, one that really sped up AI thinking time on larger boards, and one that bumped my win rate a bit.

If you remember from my planning post, I had two phases in which I scan the grid for revealed cells for mine counts, and attempt to use surrounding data in order to mark mines and reveal cells that are guaranteed to be safe. Originally, I just looped through each cell ever update. As you can imagine, this would start to take quite a while on larger boards. The optimization was to have a different lists to loop for for both steps. On start up, this list of cells consists of the whole grid, but if a cell has already been used for data, is empty, or contains mine, we prune it from the list. This really helped increase the speed of the algorithm on medium and large boards.

The second optimization was pretty straightforward. As I mentioned before, if there are no safe cells found after the algorithm runs, my AI just picks a random cell. The change I made was when I pick a random cell, instead of just using the whole grid, it forms  a list of what random cells are safe to pick. In short I only pick cells that haven’t been picked yet (to save time) and cells that are definitely not mines.

In an Ideal World

I feel like the main thing my algorithm was missing was some sort of pattern recognition or “tank” solving algorithm, as I mentioned in my last post. Having a second, more intensive algorithm to fall back on would’ve really helped my AI in harder difficulties. I detailed the tank algorithm I would’ve used in my last post.

Conclusion:

I wish I could’ve put some more love and care into it, but at the end of the day I’m pretty satisfied with what my AI was able to do. I’m looking forward to the next assignment – Gin and Rummy.

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