MineSweeperProb: The MineSweeper AI.

1. Minesweeper Basics (if you don't know it)

A rectangle board consists of n-by-m blocks. t mines are hidden behind the blocks, at most one mine per block. The player clicks on a block to open it. If that block contains a mine, game over; otherwise, the plays knows the total number of mines in the opened block's immediate neighbor. If there are zero mines around, the system will uncover all immediate neighbors automatically. The player can take advantage of these information and open more and more blocks, until they win the game when all non-mine blocks have been opened.

First click is guaranteed not to hit a mine. Furthermore, if playing under the SNR rule, the first block has zero mines around.

Right click a block to flag the block as "mine". However, it won't change the game play, only helping you memorize the location of mines.

2. Competitive Minesweeper

Human players compete on how fast one completes a game, ignoring failures; AI players compete on how much games they can complete, minimizing failures.

Thus, human players can, and actually should, take risks by randomly clicking some blocks when they can't decide which is the optimal next move; but AI players must minimize such risk.

3. Why Minesweeper AI is hard

Theoretical studies have found that, the problem of determining whether a block has a mine is NP-Complete.

However, in practice, a reasonable Minesweeper game can be solved instantly for consistency. Thanks to modern computer software and hardware, one can instantly know which block(s) is(are) safe to open in a game.

Nevertheless, a fully-fledged Minesweeper AI needs to tackle not only which block is safe, but also make the correct choices when all mines are not safe to open. Indeed, being able to make a smart choice under pressure (i.e. no safety guarantee) is what makes an AI outstanding, not just functioning.

4. Glossary

SFAR (Safe First Action Rule): The system ensures that a player's first click will not hit a mine.

SNR (Safe Neighborhood Rule): The system ensures that neither a player's first click nor its immediate neighbor will contain a mine. In another word, the first click will definitely uncover a block of degree 0.

Degree (of a block): The number of mines in the block's immediate neighbor blocks.

Safe block: A block can be proven not to contain a mine.

Lethal block: A block can be proven to contain a mine.

Trivial situation: There is at least one safe block on the whole board.

Non-trivial situation: There is no safe block on the whole board.

5. The First Move

Although the first click is guaranteed not to hit a mine, due to the lack of degree information at the beginning of the game, the first move deserves special consideration.

Our independent research have found the best move for some common board sizes: (counting starts at 1)

6. Discovery of Safe and Lethal Blocks

MineSweeperProb employs a 3-tier frame to find safe and lethal blocks. If it can find a safe block using a simpler method, it will not invoke a more complex method to save time.

1. Reduce: If an open block's degree equals to known lethal blocks, all surrounding unknowns are safe. Similarly, if an open block's degree minus known lethals equals to unknown blocks, all such unknowns are lethal.
2. Overlap: If two open blocks' neighbors share some blocks, these blocks are subject to multiple constraints and might be safe or lethal.
3. Probability: For all open blocks that have undecided neighbors, list equations using degree info and solve them.

The last one Probability sounds very complex and slow, but in reality there could be many ways to simplify:

• If a number of blocks are topologically indistinguishable (i.e. are neighbor of the same sets of open blocks,) they can be treated as a whole large piece by counting how many mines are among them.
• Instead of recompute, dynamically split and merge such block sets as the game goes.
• Use Gauss elimination to greatly reduce the dimension of search space.

7. Dealing with Non-Trivial Situation

P: In the not-so-rare situation that no safe blocks can be found, the most straightforward strategy is to choose a block with minimal probability of containing a mine. This strategy is called P, and our code computing such probability is found here.

S: When multiple blocks share the same minimal probability of mine, some AIs just give up and randomly choose. However, it is crucial in Minesweeper gameplay to make a best-effort move even under such adversity. Here we have S strategy: choose a block that, upon clicked, possesses the highest chance to lead to a successful discovery of a safe block.

E: When there are still multiple choices, we (strategy E) maximize the mathematical expectation of the number of safe blocks.

Q: Finally, we reach a situation that safe blocks might be infeasible or too risky to achieve. In this situation, Q strategy comes to rescue by maximizing the information entropy received from the discrete distribution of degree info on the block.

In summary, we apply P, and then S, then E and Q. We call this combined strategy PSEQ for short.

Note: This is not a complete list of possible strategies. Please refer to the research paper for more information.

8. Optional: Exhaustive Search for Optimal Solution

Although PSEQ strategy is helpful for many non-trivial situations, it becomes less effective as you approach to the end of the game, where there are so few blocks left open that one can easily exhaustively predict what will happen if you click some blocks.

When configured to enable this Exhaustive Search functionality (PSEQ-D256), near the end of the game (usually when fewer than 256 possible solutions left) it will attempt to enumerate all possible block click sequences and their interactions with all the possible solutions in order to find the absolutely optimal block to click.

This function comes with some cost - the one-off computation might take several minutes to finish. Please be patient and not to refresh the page.