Minesweeper AI Code Report

My approach to the AI ended up not being very different from what I had planned in my last post.

I ended up making a single class to contain all of the tiles marked as either safe or as a mine. That same class has all of the functions that do checking on tiles as well. It’s called SpikerSweeper.

SpikerSweeper contains two int vectors, each containing a list of mines, either the known safe locations, or known mine locations.

Mines and safes get added to those vectors from my two major algorithms methods: detectMines() and detectSafes().

My mine detection works approximately like:

for every square with value N:
if it has exactly N adjacent-unopened squares:
add each of those squares as mines.

Safe detection is similar:

for every square with value N:
if it has exactly N adjacent-mine squares:
add each of those squares as safes.

The major article I used when developing my strategy for playing the game, that I then put into code for the AI, was a post on Bai Li‘s programming/math/tech blog, located here.

The major feature I didn’t have time to implement that I was hoping to, was Bai Li’s tank algorithm, which would have helped to solve the larger boards with much more consistency. As it is now, the program has a pretty high win rate on the beginner boards, but struggles with higher difficulties.

If anyone is interested in taking a look at the code, in it’s final form, check out my github.

Minesweeper AI Planning Stage

My approach to this project is going to be to try and solve it similarly to how a person would, with some changes to better utilize the computer’s ability to do large amounts of data processing very quickly.

A quick, off-the top, very rough idea of what this could look like would be:

  • A “controller” class that holds general data and drives the rest
    • Creates and holds references to the other classes
    • Stores some of the data needed by all other pieces
      • The board state in whatever format I decide to use
      • A list of tiles know to have mines, basically the flag system
  • A 3×3 “chunk” class that will hold the nine tiles needed for the quick-and-dirty algorithm
    • Holds the data for the chunk
    • Runs the quick square check to determine if there are any very-easily locatable mines
    • Returns the location of one if it finds it
  • An NxM chunk class that should solve most areas the 3×3 class can’t easily resolve
    • This separation means that the more time-intensive algorithm is only used as needed
    • This class will check every possible square and see if there is a possibility for it to contain a mine
      • Depending on how large NxM is, this could take a VERY long time, so it’s imperative that the controller class does a bit of legwork and sanity-checks areas and cuts them into more manageable pieces
    • The class then returns every square that it didn’t mark
      • In other words, squares that cannot contain a mine

The singularly most useful resource in forming both my ideas for this project, and for having really good starts (especially as I’ve never played minesweeper before) was a post on Bai Li‘s programming/math/tech blog, located here.

Next week, I’ll have my code up and (at least somewhat) implemented. Until then, you can take a look at what I’ve got so far on my github.