|
Minesweeper is a single-player computer game, invented by Robert Donner in 1989. The object of the game is to clear a minefield, without exposing a mine. The game has been rewritten for many computer platforms.
Rules
The game screen consists of a rectangular field of squares. Each square can be cleared, or uncovered, by clicking on it. If a square that contained a mine is clicked upon, the game is over. If the square did not contain a mine, one of two things can happen. A number could appear indicating the amount of adjacent (including diagonally-adjacent) squares containing mines. Or no number appears, then the game automatically clears those squares adjacent to the empty square (since they could not contain mines). The game is won when all squares that do not contain a mine are cleared. The player can optionally mark any square believed to contain a mine with a flag, by right-clicking. In some implementations, middle clicking on a number having as many adjacent flags as the value of the number reveals all the unmarked squares neighboring the number; the game ends on such an action if one of the flags had been incorrectly marked.
Most implementations of minesweeper "cheat" in favour of the player by never allowing the first square clicked to be a mine.
History
A lesser known game known as Relentless Logic (or RLogic for short) by Conway, Hong, and Smith, was available for MS-DOS as early as 1985. In RLogic, the player is a United States Marine Corps marine private, delivering an important message to the U.S. Command Center. RLogic and minesweeper are similar in concept, but a number of differences exist:
- In RLogic, the player must navigate through the minefield, from the top left corner to the bottom right corner (Command Center).
- It is not necessary to find all of the mines. Consequently, there is no mechanism for marking mines or counting the number of mines found.
- The number of steps taken is counted. Although no high score functionality is included, players could attempt to beat their personal best score for a given number of mines.
- Unlike Minesweeper, the size of the minefield is fixed. However, the player may still specify the number of mines.
Because the player must navigate through the minefield, it is sometimes impossible to win — namely, when the mines block all possible paths.
The connection between RLogic and Donner's Minesweeper is unclear. RLogic is undeniably the earlier game, but due to the simplicity of the concept, the similarities are quite possibly a coincidence. Relentless Logic has become virtually unknown whereas Minesweeper has remained popular.
Computer implementations
In the popular Microsoft Windows version, there are three sizes:
- Beginner: 8 x 8 field with 10 mines
- Intermediate: 16 x 16 field with 40 mines
- Expert 16 x 30 field with 99 mines.
Newer versions of Windows (from Windows 2000 onwards) feature a 9 x 9 Beginner field instead of a 8 x 8, with the same number of mines. This was apparently because with the previous dimensions, the chances of clicking on a mine were the same for Intermediate and Beginner:
8x8=64, 10/64
16x16=256, 40/256 = 10/64
3D versions of the game are also available; one is called MineSweeper3D. Some versions of minesweeper also feature different 2D layouts. For example, X11-based XBomb adds triangular and hexagonal grids, and Professional Minesweeper for Windows includes these and many others.
A version of the game was also available for the Game Boy portable console.
In 2003, Microsoft added a variation of the original Minesweeper, called Minesweeper Flags in MSN Messenger (from version 6 onwards). This game is played against an opponent, and the objective of this game is to find the mines by actually clicking on the squares where they're located, not by clicking the surrounding squares. The person who has uncovered the most mines when the game is over, which happens when all mines are uncovered or the game is quit for any reason, has won.
Elements of analysis of the game
Patterns
Naturally, there are many patterns that may arise during a game that can be recognized for their one possible solution. In the interest of finishing quickly, it is often easiest to process the patterns that are certain first, and continue on with the uncertain parts later. For an example, the number 1 placed against a corner of a rectangular group of blocks indicates that the single square is a mine.
This is by far the easiest pattern to recognize, though all are easy to deduce with time. The number 3 placed against a flat "wall" (often surrounded by 2s) indicates three mines in a row, with the center being at the number three.
If by some chance in the advanced levels you should find the number 8, you will quickly discover that it is wholly surrounded by mines.
There are several other patterns; find them!
Not always solvable without guessing
Minesweeper is not always solvable without guessing. For instance, in the following situation:
( represents a mine, and the numbers are the standard Minesweeper numbers. The position is at the bottom of the board.)
The player must guess which of the two squares marked with a ? is a mine.
NP-completeness
The following is an interesting problem: given a board position with the numbers, is it valid? In other words, is there some way that the mines could be arranged in the hidden squares that would be consistent with those numbers? This problem is known to be NP-complete. That means it is easy to check that a particular arrangement of mines corresponds to the given numbers, but it is probably hard to find such an arrangement, in some cases. This might mean that it's sometimes hard to play Minesweeper perfectly.
Because of Minesweeper's relation to mathematics here, it is mentioned in the Clay Mathematics Institute's unofficial description of one of the Millenium Problems, namely P=NP?.
Mine probabilities are not enough
If "playing Minesweeper perfectly" means finding a strategy that ensures the best probability of solving a random board, then there is more to playing perfectly than just choosing squares with lowest mines probabilities. Let's examine the following situation:
(As above represents a mine, and the numbers are the standard Minesweeper numbers; a, b, c, d and e are the unknown positions.)
There is 2/3 probability of mine on a, b or c and 1/2 probability of mine on d, e; you can see that by computing the 6 possibilities of mine placement on a+b+c+d+e. But playing d or e will bring you no useful information: if you don't step on a mine, you'll see a 6 appear under e, or a 5 appear under d. Overall playing d or e will let you solve the area in only 1 of the 6 possible cases. If you play a (or b or c) and you don't die, you'll immediately know whether there is a mine on d or not; overall you'll solve the area in 2 of the 6 possible cases. So the moves a b c with the highest immediate danger turn out to be the best in the long run.
Best times
On the Windows version, for Expert, a time under 85 seconds in Windows 2000 (and under 80 seconds in Windows 3.1) is considered to be very good. The official record for Intermediate is 11 seconds and 1 second for the 8X8 Beginner board. The official record for Expert is 39 seconds. (Note that the timer instantly goes to 1 on the first click, rather than after a second.) Many people publish screenshots or video recordings of their best performances.
The record for Beginner (9x9 board) is 0 seconds. Out of 127800681 games played in a row, by clicking in the corner, and seeing if all the squares get uncovered at once, 1519 won on the first click. This gives an approximately 0.00119% ± 0.00003% chance of winning instantly, by clicking in the corner. In 6713134 games, clicking in the middle, 39 won on first click, giving only an approximately 0.00058% ± 0.00009% chance of winning instantly, by clicking in the middle. In 10839687 games, clicking in the middle of an edge, 103 won on first click, giving an approximately 0.00095% ± 0.00009% chance of winning instantly, by clicking in the middle of an edge. (Current computers are not capable of computing an exact chance of winning on the first click.)
There is a cheat code in Minesweeper for Windows, which allows you to cheat: Start Minesweeper normally. When it has loaded, type "xyzzy <ENTER> <SHIFT-ENTER>". The upper left hand pixel on your screen will light up whenever your mouse is over a safe square. This code works in Microsoft Windows 3.1, Windows for Workgroups 3.11, Windows 2000 and Windows XP, but not in Windows 98.
In some versions of Windows, the following cheat code also exists: When both the left and right mouse buttons are pressed to depress nine squares, <ESC> may be pressed to start or stop the timer.
This is what a normal Minesweeper game with difficulty beginner (9*9 grid) looks like.
the same game, completed, looks like this.
External links
- Minesweeper (http://www.planet-minesweeper.com/) - All what you need to know about Minesweeper: tips, records, videos, forum...
- MineSweeper Java Applet (http://www.reed.edu/~mcphailb/applets/jmine2/) - Play MineSweeper online.
- MineSweeper3D (http://www.software3d.com/Mines3D/) - A 3D version of the game.
- Crazy Minesweeper (http://www.astatix.com/crazyminesweeper.php) - Interesting minesweeper with mines of different power and other useful features.
- Minesweeper Active Ranking Page (http://www.active-ranking.de.vu/) - Biweekly Score Submission and Ranking
- The Authoritative Minesweeper (http://metanoodle.com/minesweeper/) - Unofficial Home for the Minesweeper Community
- Professional Minesweeper (http://granzeau.com/~gonzo/profmine/) - Minesweeper with a great variety of grids.
- XBomb (http://www.gedanken.demon.co.uk/xbomb/) - Minesweeper for X11 with hexagonal and triangular grids.
- Richard Kaye's Minesweeper Pages (http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm) - Proof of NP-completeness.
- Ruckus Buck's Dangerous Mines (http://www.dangerousmines.com) - Minesweeper game with 3 game modes, one that is played in rounds against the clock. Windows and MacOS X
- LuckySweeper (http://www.jsingler.de/java-applets/luckysweeper/index.php) - LuckySweeper. You are "automatically" lucky in case you have to guess.
- Minesweeper (http://www.numberonefree.com) - #1Free Minesweeper is Freeware Minesweeper game thats a looks a lot better than the one that came with windows.
- Ian Stewart on Minesweeper (http://www.claymath.org/Popular_Lectures/Minesweeper/) - Article by a lecturer in pure mathematics.
| 
