Minesweeper AI Planning Post

My plan for a minesweeper AI is to use a simple system with three steps I came up with to work through the level using guarantees and probabilities. The steps I have planned are checking for mines, checking for safe spots, and then if no guaranteed safe spots are found, picking the space determined to have the lowest probability of a mine. Each step’s exact implementations can be improved as necessary to increase efficiency.

The first step will use some method of determining where mines definitely are. The first implementation of this method will be just simply finding numbers on the board that have exactly as many adjacent covered spaces as their number, indicating that each adjacent covered space is a mine. This information will be useful for the next step, as well as guaranteeing that this space will never be clicked. Future solutions could look for patterns or other methods if this does not prove to be adequate.

The second step will find numbers that are adjacent to as many guaranteed mines as their number, indicating that every additional adjacent space is safe. If any safe spaces are found, they will be clicked on first. This step seems much more straightforward, and might not really have any optimizations.

The final step is to pick a space that has a low chance to be a mine, used only if no guaranteed safe spaces can be found. The current planned method is to give each space a percentage chance of being a mine, based on the status of the numbers adjacent to it. As an example, a space with an adjacent 7 with no known spaces around it would be given a 7/8 chance of being a mine. If one of the eight spaces around the 7 is known to be a mine, the probability for the first space would be 6/7. As of right now, the highest probability found for a space would be used, and all others would be ignored. Any spaces with no numbers around would be given a probability of the number of  mines over the number of spaces left on the board, not counting already determined mines. The lowest probability space will be clicked, and a tie will result in a random choice between the tied spaces. This step could potentially be improved later if deemed necessary.

The program will start out by picking a random space out of the second half of the board. This will give an equivalent distribution of possible first picks, while avoiding the top left, which has a slightly higher chance of having mines and stopping a chain of 0s. After this, the program will run the first step. If any mines are found, the second step will be run until all safe spaces are found and opened. After those spaces are opened, the first program will loop back to the first step and proceed the same way. If no mines are found by the first step, or no safe spaces by the second step, the program will go to the final step. After opening a space, the program will go back to the first step, and proceed as expected.

While this program will likely not be perfect, it should perform far better than random choices even in its simplest form. The steps themselves can be improved and optimized if decided to be necessary by testing if the program is too inconsistent or slow. I don’t know how consistent or fast it will be, because it is entirely made of unproven ideas from my own head. Hopefully it works out alright.

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