Minesweeper Identical Boards Problem, Part III
In part I of this article it was uncovered that Minesweeper is passing at most 65536 inputs to srand. This number does not imply that the total possible number of Minesweeper boards are limited to 65536. The player can keep on generating new boards for a session. A player can even generate more than 65536 distinct boards in one session. However, the generated boards will be identical to ones generated by another player with the same srand input. Actually, this statement is not strictly true. Later we will examine some ways to generate non-identical boards with identical srand inputs.
The number 65536 is reasonably large. Few people can expect to play all the possible distinct Minesweeper sessions. In fact on average a person will need to start Minesweeper 764646 times in order to play the 65536 distinct sessions. This is a consequence of randomness in the input to srand. If a player has played 65535 out of the 65536 distinct sessions then on the next try she is unlikely to play the one remaining session. Most likely she will come up with a session she has played before. If the player could pick the input to srand then she can be done in exactly 65536 tries.
If a player wanted to play all the different sessions for the three standard Minesweeper modes (beginner/intermediate/expert) she will need to play 2.3 million boards (3 times 764646.) This means that after about 2.3 million Minesweeper sessions, all possible initializations for all modes of Minesweeper get played. This number looks large but is fairly small in proportion to all the Minesweeper sessions being played all over the world. Most likely more than this many sessions get played in a single day.
An interesting prediction can be made that it will be very hard to improve Minesweeper records significantly. The best Minesweeper records stand around 40 seconds for the expert mode. Computer players can finish the game in under 10 seconds but humans are a lot slower as they have to move the mouse. Improved mouse handling might shave an additional 3-4 seconds off the records, but things are not going to get better than that. To improve the records significantly players need to come upon boards that are easy to win.
Theoretically it is possible to have an expert board which opens with a single click. The probability of coming upon such a board is fairly low. Although it can be reasonably expected to come upon a board which opens with a couple of clicks. Unfortunately, we know that no such boards are amongst the boards people are playing routinely. If there were any such boards, Minesweeper records would have reflected that.
To significantly improve Minesweeper records, players need to examine Minesweeper boards which have not been played by anyone yet. There are gazillions of such boards but Windows Minesweeper provides no access to them. Is there a way to access them?
One way to expand potential Minesweeper boards is to keep on generating new boards in the same session. The problem is people don't play a single Minesweeper game. Many people play long sessions and unless someone generates thousands of boards they are unlikely to come upon anything new. Therefore, this approach can only be effective if the player leaves Minesweeper running all the time.
Fortunately there is another trick to get Minesweeper to generate different boards. The boards generated are identical only if the player sticks to their initial board setting. If in one session they change the board setting and in the other session (with same srand input) the player generates a different layout board and then restores the initial setting they are likely to get different boards.
To understand why this is so we need to examine the Minesweeper board generation algorithm. The algorithm is fairly straightforward and it works as follows:
- create an empty board with no mines
- pick a random row of the board
- pick a random column of the board
- At the junction of the row and column place a mine if a mine is not already there
- repeat the process until the correct number of mines are on the board
For a particular initialization of srand, a particular sequence of numbers is generated. The location of mines in the generated board depends on where in the sequence the board starts consuming numbers. A board that is generated after consuming 220 random number will be different from one that is generated after consuming 240 random numbers. Generating expert boards repeatedly might generate the first board after consuming 0 random numbers, the second after 220, the third after 456, etc. However, if we generate a beginner board first it might consume 22 random numbers. Now the first expert board will start after 22 random numbers have been used. Consequently it and any future expert board generated will be different.
I used the WinDbg program to initialize the srand function with input 0 and produced the following two expert level boards. Board in figure 1. was the first Minesweeper board generated after starting Minesweeper in expert mode. Board in figure 2. was the first expert board generated by starting Minesweeper in beginner mode and then switching to expert mode. If you pay attention you will notice that the two boards are very much identical with many of the mines on the same square on both boards. This is due to the boards using many identical numbers in their generation.
Figure 1. Board generated using 0 for srand initialization.
Figure 2. Same input for srand but a beginner board is generated first.
Shuffling board settings can extend the number of boards produced by Minesweeper in proportion to the number of mines on the board. For expert boards this implies that somewhere close to 99 times as many boards can be produced as before. Unfortunately, as the figures above show, the boards generated are not altogether different.
Another approach for improving Minesweeper board generation would be to disassemble Minesweeper using a disassembler, improve the code that feeds srand and reassemble the code. This process is not as complicated as it sounds and has been accomplished for the Windows Calculator program.
Ultimately, all of the above outlined workarounds are inconsequential. They are not likely to have any real impact as very few people are knowledgeable and motivated enough to employ them. The most promising approach will be to pester Microsoft for an improved version of Minesweeper which addresses all the shortcomings mentioned in this article.
by Usman Latif [Oct 24, 2003]