Nu Programs
 • News
 • About
 • Contact

Minesweeper
 • Home
 • About
-- Articles --
 • Randomness
 • Board Cycles
 • Dream Boards
 • TLM Theory
 • First Click
 • 1 Click Bug




On Randomness in Microsoft's Minesweeper
by Tim Kostka


In order to explain how boards in Minesweeper are generated, it is important to know the basics behind randomness in computers.

How does a computer generate random numbers?
A computer is an exact machine. It follows a strict and absolute set of commands and always processes them in the exact same way, so how can a computer be programmed to do something random? What we find, in the case of generating "random" data (such as Minesweeper boards), programmers often use a pseudo-random number generator. This generator will produce the same sequence of numbers every time it is called, but the numbers in the sequence seem random to anyone who doesn't know the pattern behind the numbers. The programmer often seeds the generator with some value so it will start in the middle of a cycle of random numbers. Some use the time of day to do this, or the number of seconds that have elapsed since 1928, or the number of bytes in the files in the C:\Windows\ directory of the users computer, or something of that nature.

An example of a pseudo-random number generator
Say the numbers in a sequence are generated using the rule Xn+1 = (Xn * 5 + 3) % 16. That is, the generator takes the last number, multiplies it by 5 and adds 3, then takes the remainder of that number divided by 16. So starting from a seed number of 0, the next number would be ((0 * 3 + 7) % 16) = (7 % 16) = 7. The next number would be 13, then 1, etc... The series would eventually produce a number it produced, and then there would be no more unique numbers. The series looks like this: {0, 7, 13, 1, 10, 7, 13, 1, ...}. Notice how the sequence {7, 13, 1, 10} is repeated over and over and the number 0 is never reproduced. Minesweeper boards are strikingly similar to this, except the repeated sequence is many thousand instead of 4 as in the example.

How are boards in Minesweeper generated?
Boards in Minesweeper are generated using a pseudo-random number generator. When Minesweeper is opened, a random number is seeded into the generator and the board is calculated from this number. I'll call this the board number. This is all before the user taps a block, so the timer hasn't started yet. The program already has an idea of what the grid will look like before the first block is tapped. When the user taps a block, if that block should be a mine, the program moves that mine from the tapped block to the top-left corner of the board. If the top-left corner was tapped, or there's already a mine there, then it moves the mine to the next open spot to the right on the board. This accounts for boards that have exactly one mine out of place, but are otherwise identical.
After the player loses, wins, or hits F2, a new board is calculated using the number immediately following the previous board number. Even if the board was modified due to the player's first click, the board number remains the same, and so all the boards following a certain board will be calculated from the same board number. And so, just as a 1 always followed 13 in the example, the same board always follows a different board. Eventually, just as in the example, the boards will enter into a cycle.

 
This page and all its contents are © 2002 by Tim Kostka. All programs here are distributed with this freeware license. If you have any other questions, please feel free to contact me directly.

Last updated: