Minesweeper Code Report

Writing the program went about as I expected. Most of what I did followed what I said in the planning post. The biggest changes were that the steps weren’t completely separated, and the guessing function doesn’t actually take a random guess of spaces with equal probabilities. These were changed for simplicity, and the ideas behind the original steps were kept. The steps still follow the original process of only doing the processing when they are needed, but the actual processes are very similar, so it makes sense to do some of them together. The guesses still guess the bottom right first, but always the last mine with the lowest probability in the event of a tie.

The AI uses a singleton class to keep track of the processing and functions. The code interface is through static class functions, which initialize an instance if one is not yet created, and call all of the necessary functions to return a choice. When a reset event is received, a flag is set in the class to reinitialize data with the new board, including checking if the dimensions have changed. This occurs the next time a move is requested.

The first thing the AI does when a new move is requested is check the board for mines. The way it determines mines is by checking if a revealed number is next to the same number of covered spaces as its number. If so, each of those spaces has its mine probability set to 1 in an array holding the probabilities of each space. If mines aren’t found, it moves on to the next space. It goes through and checks each space this way until it gets to the end of the board.

After finding all of the guaranteed mines, the program then looks for guaranteed safe spaces. It does the same process again, but with the added information of the known mines. If a space has the same number of adjacent mines as its number, each other space is known to be safe, and they are added to a list of safe guesses. Otherwise, the ratio of mines to unknown spaces is added as a probability to the probability table, but only if the new probability is higher than the old one.

If the last step found any safe spaces, they are chosen by each new space request until the list is finished. Otherwise, a guess is the next step. All spaces without a probability assigned to them by the last step are given a probability of the number of mines not yet found divided by the number of unknown spaces left on the board. The next move is to look for the lowest probability of a mine in the list. A tie is broken by checking the zero probability, which is the chance of a space being a zero. This chance is determined by the highest probability of a mine within range. This helps by giving the guess a better chance of opening up more space on the board and giving the next move more information to use. This was a late addition to hopefully increase success rates without complicating the code too much. If spaces share the same lowest probability and zero probability, the one farthest to the bottom right is picked.

After a guess, the AI uses the new information to hopefully find more mines and free spaces, and guesses more when it needs to. This gives the program a good success rate on easy, a decent chance at medium, and I still haven’t seen it beat hard. To be fair, I don’t think I’ve ever beaten hard minesweeper either. Hard is hard.

One additional optimization I thought of to make the AI more successful is something to help find free spaces and mines. It would group up areas that are next to a number as having that number of mines in that area to try to think of them as a group. It would help to find mines with certain patterns, like when a 1 and a 2 are next to each other along an edge. In this situation, the only space next to the 2 that isn’t next to the 1 must be a mine, because that is the only place a second mine could go. Instead of simply looking for that specific pattern, I figured it would be more effective and smarter to try to find things like that with the group process. I haven’t really figured out how to write it, and I’m almost out of time, so I probably won’t end up doing it. It would probably increase the success rate on the harder levels by a lot, because every mine and free space found decreases the number of guesses required, and it would find a lot of mines and free spaces.

Update:

I implemented a replacement step with a similar purpose to the last optimization I wrote of. It checks the surrounding revealed spaces and processes the spaces that are adjacent to one space separately, using the information from both spaces. It increased the success rate significantly, giving it the ability to actually complete the hard difficulty at a good rate. It does slow the program down a bit, but it only runs this bit of code when it would make a guess, and it is skipped whenever possible.

This additional process catches the example pattern scenario I described earlier, and any similar patterns. It finds safe spaces and mines, greatly reducing the number of guesses required to solve a level. I had a little trouble where after finding a mine, it would then make incorrect decisions if it continued the process, so I just stopped looking after finding a mine. It still works fine, because every new bit of information helps, and it then goes back to the other step which is much faster. It might even work better this way. The process also finds more free spaces than mines, and usually doesn’t even find any mines.

I tested the program with 100 boards of each size, using the standard minesweeper dimensions and mine counts. It beat the easy board 88 times, the medium board 70 times, and the hard board 20 times. This is a massive improvement from before the change, although I never ran a big test before.

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