Minesweeper AI: Code Report

Approach

Having mostly finished the project, my main focus on it was to make sure it functioned and didn’t freeze up. Ideally this would’ve been the first step but due to time constraints it turned into my main goal. From here it’s just a matter of optimizing the code base to be as quick as possible.

Classes

The only class I worked in was the provided class for making the solving DLL, which handles all the decision-making, flagging, and cell selection in the program. The only major addition to it I added besides the actual algorithm is a light system for flagging all the known mines.

Major Algorithms

As mentioned before, while I’m not sure about the exact name of the algorithm, my code mainly functions using two rules:

– If the number of mines adjacent to a cell is the same as the number of adjacent, unknown cells, flag all of them

– If the number of mines adjacent to a cell is the same as the number of adjacent flags, select all the adjacent non-flagged cells

These two rules do a surprising amount of work and when they fail, we resort to god ol’ random guessing. They typically win smaller boards but don’t work well with larger boards as they are.

Compromises

Due to time constraints, I haven’t been able to implement extra techniques for improving the algorithm for larger boards. As is, it should run relatively well when tested on boards of varying sizes, but there’s not much that can be done at this point to improve it on larger scales without changing the base of the code. Luckily I should be able to speed it up a bit by the time its put to the test.

References

Good blog for the rules, demonstrating them, and optimizations:

https://luckytoilet.wordpress.com/2012/12/23/2125/

Advertisements
Minesweeper AI: Code Report

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