Minesweeper AI – Postmortem

So, my AI ended up performing decently, but not great.

Since last time

At the time of my last minesweeper post, I was trying to fix the brute force algorithm. However, as I was testing some modifications, I decided to see how often each portion of my AI was being called. As I might have stated before, the three components of my AI implementation were:

  1. “Basic strat” – flagging cells that were guaranteed to be mines (when the number of hidden cells adjacent to a revealed cell are equal to the revealed cell’s mine number) and then revealing cells based off of the flags that were guaranteed to not be mines
  2. Weighted pick – get all hidden cells bordering revealed cells and calculate the local probability of it being a mine, then reveal the cell with the lowest weight
  3. Brute force algorithm – go through all possible mine configurations for the hidden cells bordering revealed cells and choose the cell that appears in the least configurations

As I was observing how many times each component was being called, something seemed to be off – the the basic strategy was not being called a lot of the time and was failing when it was called. It ended up being a simple bug that was causing the basic strat to fail very often. After fixing that, my win percentage became a lot better. Now, I could consistently win around 90% games of each board size with the class (easy) parameters. When testing with the actual minesweeper settings, however, I was winning around 15/30, 7/30, and 1/30 games (S, M, L) with the actual minesweeper parameters.

So, now that the basic strat was fixed, I spent the rest of my time trying to fix the brute force algorithm and testing different combinations of brute force and weighted picking. In the end, it seemed like the brute force algorithm didn’t make too much of a difference.

Analysis

Anyway, here’s some stats on how well the AI performed. Most of the time I was testing 30 games of each difficulty. Here’s some stats for one of the 30/30/30 test sessions using the class parameters, and one of the test sessions using the minesweeper parameters.

So, I did quite well with the class parameters, and not-so-great with the minesweeper parameters. However, I did improve the win percentage quite a lot since my last post, but that was probably mostly due to fixing the bug with the basic strat.

Thus, my AI does better when there is a lower mines-to-cells ratio, and struggles once the mine start to take up a larger percentage of the board, as they did in the minesweeper parameters. This would in theory be the place where the brute force algorithm would pick up the slack, but unfortunately, that didn’t work out as well as I planned. However, my basic strat worked quite well and did win a lot of (easy) games, and a few difficult ones.

What went wrong

In terms of bringing my AI to the next level (going beyond the basic strat), I had mixed results. I do indeed believe that I made a brute force algorithm that was able to generate several possible mine configurations. However, it was very inefficient in that it did so in a random manner, placing mines at random (if possible) until a configuration was generated. Also, I was unable to get the actual maximum number of possible combinations, because I think you might need the number of mines remaining to do so (and this might be impossible in situations where configurations of different numbers of mines satisfy the conditions). I might be wrong about that. Anyway, I wrote the first pass on this brute force algorithm when I was quite tired, so there were some bugs that I fixed in the following days. But, I must’ve done something wrong, because ultimately, the algorithm did not strengthen my win percentage that much (sometimes not at all). I retraced my logic and went through the various functions I wrote (for the algorithm) a few times, but it definitely would’ve benefited from more rigorous testing and picking apart.

You would expect the brute force algorithm to be able to shine brightest in situations where there are lots of mines, because this typically means lots of data and fewer possible safe cells. However, like I said, the brute force algorithm did not improve my win percentage, and so was not very successful.

What went right

Although I had a few slip-ups getting the basic strat implemented, ultimately I got it working quite well – to the level that it would be expected to at least, it’s a very common strategy. But, that was sort of the base-line for this project. I felt like the List class I made did indeed help me and made my code a tad cleaner, so that was nice as well. And even though my brute force algorithm failed, I thought that it was a good exercise to try and sort out the logic for such an algorithm, even if my implementation was very inefficient.

If I had more time?

Time was one the primary constraint for this project (we had roughly 1.5 weeks to work on it). If I had more time to work on it, I definitely would write a proper brute force algorithm, or at the very least, I would test my current one much more extensively to see where its flaws are. Going along with that, I would try to improve the efficiency of the brute force algorithm. Aside from that, I would potentially add some logic for situations where it gets close enough to the endgame where you can use your knowledge of how many mines remain to choose the correct mine configuration.

Overall, it was pretty fun to work on this project. I like the idea of making an AI to play a game. Before this, I’d only done it a handful of times. One time I had made a simple flashpunk game, and I made it play itself in order to figure out if the memory used by the game was too much (it was, needed to recycle sprites more). Last semester, I made kind of a makeshift AI for my Production II game so I could test our game without needing 4 controllers (it sorta worked but had several bugs, so it didn’t make it into the final build). Ultimately, I liked working on this Minesweeper AI but I can’t wait to dive into our next project: making an AI to play Gin Rummy.

-“David Hartman”

 

Advertisements

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