Minesweeper Advanced Play
Almost every computer user has played Minesweeper and there are some very good tactics pages about Minesweeper. The surprising thing I noticed is that almost all of them are incomplete. Most focus only on the deductive aspects of Minesweeper.
Every experienced Minesweeper player knows situations where no deductive solution exists and the player is required to take a chance. I did find analysis of some such situations on the web but I didn't find any good analysis of the most important scenario of all, the beginning of the game.
Most players start a Minesweeper session by clicking randomly on the board and hoping that a cascade (lots of squares opening up due to one move) occurs. Often a cascade allows some portion of the board to be solved using only deductive reasoning. Actually, this part of Minesweeper can be automated and there exist programs that do just that (see link for smrtmine).
The above behavior of Minesweeper players can be attributed to the traditional metric used for evaluating Minesweeper performance. The traditional metric records only the best time taken to finish a board. Not finishing a board is not considered important, and does not entail a penalty. The game becomes much more challenging if a different metric is used. The new metric I propose is the number of games won divided by the number of games played.
When using the new metric, the initial clicks become important. Obviously it is unreasonable to expect winning the game by random clicking. A cascade must occur and then the user can solve some portion of the board deductively. If the cascade does not occur quickly, chances are the player will step on a mine and lose the game. Therefore, the goal of the initial clicks should be to maximize the probability of a cascade.
A cascade occurs when all the adjacent squares around the square that is being clicked are empty of mines. The cascade uncovers all the adjacent squares and continues if the newly uncovered squares themselves satisfy the above criteria.
To maximize the chance of a cascade the player should be looking to minimize the chance of adjacent squares turning up a mine. Let us assume we are playing the Windows Minesweeper at the expert level, on a new board with 99 mines, and 381 non-mines. Let's say we click somewhere near the center of the board. The windows version of Minesweeper never uncovers a mine on the first click, so the square being clicked is a freebie. After our click the uncovered square is surrounded by eight more squares, for a cascade to occur they have to be non-mines. We have 380 non-mines and of those we want to choose 8 non-mines and no mines. This can be done in binomial[380,8] ways (binomial means binomial coefficients). All the ways we can select those 8 squares is binomial[479,8]. Dividing the first number by the second gives us 0.1545 as the cascade probability.
It should be obvious that the probability of cascade depends critically on the number of adjacent squares. If we can reduce the number of adjacent squares we can reduce the probability of one of the adjacent squares containing a mine and hence increase the probability of a cascade. The obvious way to reduce the number of adjacent squares is to go to the corners. At the corners there are only 3 adjacent squares. Consequently, the probability of a cascade is:
binomial[380,3] / binomial[479,3] = 0.4984
This number is a huge improvement over clicking in the center. The following table summarizes some of the results:
First Click Non-mines needed Probability ======================================================== corners 3 0.4984 sides 5 0.3125 center 8 0.1545
What happens if the first click does not start a cascade? Now there are 380 non-mine squares and 99 mines. A click on one of the remaining uncovered corners will start a cascade if the corner square and the adjacent squares are non-mine. We need 4 non-mine squares and no mines. The cascade probability can now be computed using the expression:
binomial[380,4] / binomial[479,4] = 0.3848
(Note: This analysis is slightly incorrect, as it ignores some information)
The case for clicking in the middle yields a cascade probability of 0.1220. The difference between the two numbers is still very large.
Combining the numbers from the earlier analysis we see that after two clicks, the probability of a cascade not having occurred in the corner case is:
(1 - 0.4984) * (1 - 0.3948) = 0.3036
while for the middle case the probability of the same event is:
(1 - 0.1545) * (1 - 0.1220) = 0.7423
The analysis gets more complicated for the third click as the game could have finished on the second click, but the pattern should be clear. A cascade is much more likely at the corners than in the center.
The only problem with the above analysis is that the cascade at the corner doesn't have the same room to expand as a cascade in the center so it is likely to be smaller. Does that matter?
I have no clue as to the relation between the expected size of the initial cascade and the probability of finishing the game. On intuitive grounds I do expect a bigger cascade to yield better results if it occurs. Unfortunately, more often than not looking for a bigger cascade will lead to stepping on a mine and loss of the game. Consequently clicking in the middle is a poor strategy.
Analysis of the above kind can be carried out in the middle of the game as well, and in very many different situations. Combined with techniques described in other Minesweeper tactics pages, a good Minesweeper player should be able to raise his/her percentage of wins considerably.
Minesweeper has quite a number of subtleties which nobody has yet explored. There is certainly need for better tactics in cases where the player has to take a chance. Some people consider having to take chances in Minesweeper a design flaw, but it really adds a whole new dimension to Minesweeper gameplay.
by Usman Latif [Sep 28, 2003]
Thanks to Chris Charokopos for corrections.