Minesweeper: The Trouble with Random Boards
Randomization is critical to ensuring replayability in Minesweeper. However, the obvious way of generating random boards effectively results in the generation of an uninteresting board. A typical Minesweeper board generated using the standard algorithm has mines distributed evenly throughout the board. This evenness eliminates most interesting patterns.
The expert level board in Windows Minesweeper has 16 rows and 30 columns. There are 480 squares on an expert board and 99 of them are mines. Let an odd board be an expert level Minesweeper board where all the odd rows have mines and the even rows don't have any mines. Of course, an odd board can occur randomly, but it is safe to say that no one has ever randomly generated such a board.
There are Binomial[480,99] expert level Minesweeper configurations possible. Of these Binomial[240,99] configurations are odd boards. Therefore, the probability that any given randomly generated expert board is odd is given by:
Binomial[480,99] / Binomial[240,99] = 2.29 * 10^69 / 5.6 * 10^104 = 4.01 * 10^-34
The probability computed above is effectively zero. Even considering all the Minesweeper boards that will ever be played there is simply no hope for anyone ever randomly coming up with an odd board. The problem is not caused by a shortage of odd boards. There are 2.28 * 10^69 odd boards, an immensely large number. The problem is a consequence of the number of possible non-odd boards, which is even larger and therefore such boards appear more frequently.
Randomly generated odd boards are not very interesting, but more interesting Minesweeper boards must be possible. Dr. Richard Kaye in his well-known paper proves that the Minesweeper consistency problem is NP-complete. The Minesweeper consistency problem is equivalent to determining which squares of the Minesweeper board are mines or non-mines. NP-complete problems are very hard to solve, and as a solution to Minesweeper consistency problem is needed to determine if a Minesweeper configuration can be solved without guessing, solving Minesweeper has to be a very tough problem.
Unfortunately, most randomly generated Minesweeper boards are fairly easy to solve and many people after playing for a while believe they have mastered Minesweeper. Dr. Kaye's paper proves that this simply is not the case. Minesweeper is a vastly complex game, the seemingly shallow nature of the game is a consequence of 'biased' board generation. The random algorithm typically used is biased towards simpler Minesweeper boards.
Any fix for this problem must preserve the random nature of Minesweeper boards. The fix would involve defining a subset of Minesweeper boards, such as odd boards, etc. and randomly picking a board from the subset. In the case of odd boards the solution is trivial and is left as an exercise.
One method of generating more complicated Minesweeper boards is to translate a random propositional calculus (boolean logic) formula to a Minesweeper board. The article "Minesweeper is NP-Complete" provides an algorithm for this conversion. The algorithm works by translating the logic formula into a circuit diagram with logic gates. Minesweeper patterns can be used to emulate (see previous link for details) circuit components, such as gates, wires, cross-overs, splitters, terminates, turns, etc., allowing the circuit diagram to be translated into a Minesweeper configuration. For keeping board sizes manageable it is essential to keep the randomly generated logic formula fairly simple.
Generating boards this way probably won't lead to very interesting games either. Some portion of the board will need to be uncovered so that the player can notice the structure of the underlying circuit. Uncovering too much of the board will convert the game into a logic puzzle, and uncovering too little will make the player guess too much.
Perhaps a Minesweeper 'maze' consisting solely of wires might lead to interesting play. Such a maze will have to be connected, so that a cascade anywhere allows the full board to be explored. Generating such a board might be possible with classic maze generation algorithms.
Minesweeper always had a mathematical tilt to it. Minesweeper boards satisfying specific properties extend the mathematical flavor of Minesweeper and are a fascinating new direction for Minesweeper gameplay.
by Usman Latif [Dec 18, 2003]
Thanks to Dr. Richard Kaye for corrections.