Minesweeper (video game): Difference between revisions

Minesweeper is a single-player computer game. The object of the game is to clear an abstract minefield without detonating a mine. The game has been rewritten for nearly every system platform in use today. The most well-known version comes bundled with later versions of Microsoft Windows. The Windows version credits Robert Donner and Curt Johnson as its creators, but the game's origins can be traced back to a paper-based gambling game in the 1950s, and as a computer game to Cube from 1973.

Game description

File:Minesweeper start generic.png

The game begins when the user clicks on a blank square.

A finished game

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 contains a mine is clicked, the game is over. If the square does not contain a mine, one of two things can happen: (1) A number appears indicating the number of adjacent (including diagonally-adjacent) squares containing mines, or (2) no number appears; in which case the game automatically clears those squares adjacent to the empty square (since they cannot contain mines). Squares so cleared which themselves are empty (do not contain a number of adjacent mines) have their neighbors recursively cleared as well. The game is won when all squares that do not contain a mine are cleared; the score is the time taken to do so.

The player can mark any square believed to contain a mine with a flag, by right-clicking. In some implementations, middle clicking (or clicking both mouse buttons) on a number having as many adjacent flags as the value of the number reveals all the unmarked squares neighboring the number; however, one forfeits the game should the flags be placed in error. This method is a very useful tool when trying to beat a high score. Some of those implementations also allow the player to move the mouse with the right mouse-button held down after marking mines; the player can then left-click on multiple numbered squares while dragging with the right mouse-button, in order to clear large areas in a short time.

Most implementations of minesweeper "cheat" in favor of the player by never placing a mine on the first square clicked; some also change the board so there are no 50-50 guess situations. However, it is argued whether or not this is really cheating, since chance should never become part of a logic-based game.

History

The earliest form of Minesweeper was a gambling game that was briefly popular during the 1950s. The player would buy a punchboard, which was made of paper and cardboard. The top layer was cardboard with a square lattice of holes, each of which corresponded to one of the buttons in the present-day Minesweeper game. The holes were blocked by a layer of paper underneath. The player could choose to punch the paper through any hole, and would then see what was printed on a third layer of cardboard underneath that hole. It revealed color-coded information equivalent to that which Minesweeper reveals from a button-click. If the player succeeded in punching a sufficient number of holes without punching a mined hole, he/she could return the board to the manufacturer for a prize.

These punchboards were sold in restaurants and bars, and probably made the manufacturer an enormous fortune before they became illegal. A familiar sound in a restaurant at that time was the wood-pecker sound of holes being punched at a rapid rate (usually with very little time for thought), which ended suddenly with a loud, vulgar shout.

The earliest known ancestor of Minesweeper as a computer game is Cube, found in the PDP-11 program library catalogue and credited only as "CONVERTED TO RSTS/E BY DAVID AHL, DIGITAL" [2] (referring to David H. Ahl). Cube was played in a 3x3x3 cube with 5 mines, where the player had to find their way from one corner (1,1,1) to the opposite corner (3,3,3). The player entered the co-ordinates of the next square they wished to explore. If the target was more than one square away or there was a mine there, the player lost. No information about the number of surrounding mines was given.

The basic gameplay style become a popular but minor part of the puzzle game genre during the 1980s, with such titles as Mined-Out (Quicksilva, 1983), and Yomp (Virgin Interactive, 1983). Cube was further succeeded by Relentless Logic (or RLogic for short), by Conway, Hong, and Smith, which was available for MS-DOS as early as 1985. In RLogic, the player is a private in the United States Marine Corps, delivering an important message to the U.S. Command Center. RLogic is more similar than Cube to Minesweeper 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 clear all non-mine squares. Also, 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.

One connection between RLogic and Minesweeper appears to be Tom Anderson's mines, written in 1987 for the Sun workstation. [3] Anderson wrote the game after a few minutes watching colleagues play RLogic. Mines added the ability to mark squares as safe or containing a mine by using the other two buttons on the mouse. From there, the final step to today's Minesweeper was to change the objective from navigating the grid to finding all the mines, removing the player from the grid in the process.

Game analysis

Patterns and solving

There are many patterns of numbered squares that may arise during a game that can be recognized for allowing only one possible configuration of mines in their vicinity. In the interest of finishing quickly, it is often easiest to process the known patterns first, and continue on with the uncertain parts later. This is especially important if a guess is required (see below), because if the guess fails, all efforts spent on other parts of the board will be lost.

There are a few broad methods for solving problems in minesweeper games without guessing:

1. Single square analysis

When the number of unopened squares around a numbered square is equal to the number of the square, all the squares adjacent to it must be mines. Conversely, if a square has known adjacent mines equal to its number, any other squares adjacent are not mines and are safe.

Examples of this analysis include:

• In the advanced levels, a user may occasionally find the number eight when revealing a square. In this case, all of the surrounding squares contain mines (though it is not impossible for the beginner level, just much more unlikely).
• The number three placed against a flat "wall" of unrevealed squares indicates three mines in a row, with the center being at the number three.
• Two twos in a row adjacent to a "wall" of unrevealed squares and perpendicular to a border of the minefield guarantee that the adjacent cell on the border, and the next one up the wall, are mines; this is because it is the only possible way for the two on the border to have two adjacent mines. It follows that the next square up must be safe, as if it was not, the higher of the two twos would be a three.

In Programmer's Minesweeper, this is called "single point strategy."

2. Double square analysis:

With two numbers on the minefield, say an x and a y, there exists 3 distinct areas: a) mines near both x and y, b) mines near x only, and c) mines near y only. This method of solving works best for adjacent x and y, but it can be used in many situations. In this example the number of mines in b minus the number of mines in c must be equal to x-y, which can be used to clear squares or find mines in many situations. This covers many types of solving not solvable using single square analysis alone, like wall-1-1, 1-2-1, 1-4 etc.

Examples:

• In a wall (no mines next to the side opposite the wall), where a two is beside a one, there will be a mine by the corner of the two that is away from the one. Many longer patterns can be derived from this one, including some of the following.
• In a wall where a two appears between ones, the center square can be opened to find a number, and the two squares touching the ones will contain the two mines indicated by the two. The reason this makes sense is because if the mine were to be placed over the center square, you could not find any other mines adjacent to the "two" square because then one of the "one" squares would be touching two mines. This may not be true, however, if the numbers adjacent to either of the ones are numbered three or higher; nevertheless, on open walls of cells, the pattern holds.
• Where there is a row of twos by a wall, four twos with ones at the ends means that the mines are beside the two middle twos, and beside the ones adjacent to the twos; five twos in the same setting means that all twos except the two which is in the center are beside mines. These patterns are like extended versions of the patterns where one or two twos appear between ones, and the mines are located by the same principles as with those shorter patterns.
• In a wall of ones where one cell beside the wall has been cleared to reveal a one, the three cells on the far side of the cleared cell are also clear; this is because one of cells adjacent to both the wall and the cleared cell must be a mine, which satisfies the one in the cleared cell.

3. Shared mine analysis

Basic example: The board has a 1. It can be found some other way that two of the squares around that 1 share a mine. That means all the other squares around the 1 except those two are safe and can be cleared.

More advanced examples of that involve a number of flagged mines around that number, having (for example) 2 mines shared by 3 cells being analysed, and "compound shared mine analysis", where you try this analysis, but all you can discover is that another set of squares share one or more mines, and you use that information to find out things about yet more other cells.

Example: When you have a 1 next to a wall and another 1 one square away perpendicular from the wall, all squares that aren't adjacent to the first 1 are safe (this can also be solved with method 2).

4. Final analysis

Used at the end of a game, this can be used to clear a square when all other squares on the board are either safe or can be shown to be mines. Often these final squares are on walls or in corners.

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.

Another apparent instance of required guessing is when an unclicked square is completely surrounded by either (1) mines, or (2) a combination of mines and the perimeter of the game window (the latter being much more common). In this case, since no numbers touch the unclicked square, a player has no information about the likelihood of the unclicked square being a bomb. However, there is still a good strategy when facing this situation that will allow to player to avoid simple guessing: simply play the rest of the game and ignore this square. If the spot is in fact a bomb, it will be automatically flagged when all other squares in the game window have been either clicked or flagged by the player. If the spot is not a bomb, it will not be automatically flagged, and the player will be able to safely click it in the knowledge that it is not a bomb.

A few variants specifically focus on getting this aspect out of the game. At the simplest level, some programs give the solution away any time a guess is needed. Another one furthered the design and demands that the player decides if he or she has to guess or not. The resulting problem is always decidable (within an extended mathematical space). Yet another simply lets any guess the user makes (when they have to) automatically be the correct one.

NP-completeness

Because of Minesweeper's relation to mathematics, it is mentioned in the Clay Mathematics Institute's unofficial description of one of the Millennium Prize Problems, namely that as to whether complexity class P equals that of NP: the P versus NP problem. In 2000, a paper was published detailing the proof that determined whether a position in a Minesweeper game is consistent with some placement of mines is NP-complete [4].

Mine probabilities must be balanced against rewards

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:

File:Minesweeper guess 2 generic.png

( represents a mine, and the numbers are the standard Minesweeper numbers; a, b, c, d and e are the unknown positions. The other spaces/mines on the board are insignificant).

There is ⅔ probability of a mine on a, b, or c and ½ probability of mine on d or e; this can be derived by computing the six possibilities of mine placement on a+b+c+d+e. But playing d or e will give the player no useful information: if the player does not trigger mine, he or she will see a 6 appear under e, or a 5 appear under d. Overall, playing d or e will let the player solve the area in only 1 of the 6 possible cases. If he or she plays a (or b or c) and he or she does not step on a mine, he or she will immediately know whether there is a mine on d or not; overall the player would solve the area in 2 of the 6 possible cases. So the moves a, b, or c, with the highest immediate danger, turn out to be the best in the long run.

Measuring board difficulty

File:Minesweeper 6 3BV generic.png

Beginner board with a 3BV of 6

File:Minesweeper 16 3BV generic.png

Beginner board with a 3BV of 16

File:Minesweeper 59 3BV generic.png

Intermediate board with a 3BV of 59

The difficulty of a given minesweeper board is often measured using the 3BV measure (abbreviated from Bechtel's Board Benchmark Value).

History of 3BV

Stephan Bechtel is supposedly the first person to count the minimum number of left clicks that are needed to solve a Minesweeper board. In June 2002, he wrote about this method in the official "Minesweeper guestbook". Soon thereafter, Benny Benjamin coined the term 3BV to describe this method. During the next two months, Yoni Roll and Benny Benjamin programmed a tool named "Minesweeper Board Reader", which analyzes screenshots of Minesweeper boards and as a result shows the 3BV of that board.

In 2003, Sorin Manea developed a program that records Minesweeper games, and displays the board's 3BV as well as the number of clicks. That was the first program that calculated the 3BV/s (3BV per second speed) of the played game.

In 2004, Rodrigo Silveira Camargo published "Minesweeper Clone" with many 3BV-related features, like playing boards with a prefixed 3BV, ability to select the range of 3BV on the generated board and the main — it saved all the 3BV statistics of finished games in a single file. Due to an easier way to represent the gaming history, the distribution of boards with a certain 3BV (for finished games only) could be analyzed. Also, there were programs which could show 3BV distribution tables for generated boards.

Method

The 3BV of a board names the minimum number of left clicks required to open up all squares without a mine of a Minesweeper field.

• Each opening of a board counts as 1 3BV (white dots on the pictures).
• Each square without a mine but a number which is not a border (white lines) of an opening counts as 1 3BV (green dots on the pictures).

The sum of the 3BV is the 3BV of the whole board.

3BV/s

3BV/s stands for 3BV per second.

• Formula: 3BV/s = 3BV ⁄ (time−1)

Thus, for example, if a Minesweeper board with a 3BV of 16 is finished in 9 seconds, the 3BV/s is 16⁄(9−1) = 2.

Because the time that is needed to finish a Minesweeper board depends highly on the difficulty of the board, it may not be the best way to compare records. 3BV/s on the other hand does consider the difficulty of the Minesweeper board as well as the time needed to finish it. Among the best Minesweeper players, 3BV/s records are not nearly as important as time records, but they give a picture of how fast someone can play with regard to mouse-handling.

If flags are marked, it is possible to require fewer clicks than the 3BV of the respective board. Using only left clicks is called non-flagging (nf) whereas marking mines with right-clicks is called flagging-style.

Implementations

Windows

In the popular Microsoft Windows version, there are three sizes:

Beginner: 8 × 8 or 9 × 9 field with 10 mines

Intermediate: 16 × 16 field with 40 mines

Expert: 30 × 16 field with 99 mines

Custom: Any values from 9 × 9 to 30 × 24 field, with 10 to 667 mines [the maximum number of mines allowed for a field of size A × B is (A − 1) × (B − 1)].

Newer versions of Windows (from Windows 2000 onwards) feature a 9 × 9 Beginner field instead of an 8 × 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:

• 8 × 8 = 64 squares, 10 mines / 64 squares = 15.625% chance of hitting a mine
• 16 × 16 = 256, 40 mines / 256 squares = 15.625% chance of hitting a mine

In fact, when the game allows for the starting square never containing a mine, there was a slightly higher chance of randomly hitting a mine in one move of the Beginner game. The Beginner game is still easier because it has fewer total chances of hitting a mine, and a smaller chance of having a problem that cannot be solved without guessing and the player also is much less likely to make a careless error because the game is shorter.

Alternatively, it could have been changed because controls had been increased in size in later Windows versions, thus allowing nine boxes to fit in a row of width equal to the title and score bars.

Another alternative: The beginner field is now solvable without guessing if a straight row of numbers with an opening on one side and unknown squares on the other side appears.

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 the mines are located, not by clicking the surrounding squares. The person who first uncovers 26 (out of 51) mines wins.

When the business version of Vista is first purchased/installed the games are not enabled. this can be rectified by going to Control Panel -> Programs and Features -> Windows features, there is a check box for "Games", which expands to check boxes for each of the games. The Ultimate and Home Premium versions are fine.

Cheat codes

Some Windows versions of Minesweeper have a cheat mode that uses the top-left pixel of the display to signal the presence or absence of a mine under the cursor. Start Minesweeper normally. When it has loaded, type "xyzzy <SHIFT>+<ENTER> then <ENTER>". After doing this, the top-left pixel of the monitor screen will be white when the mouse pointer is on a square without a mine, and black when the pointer is on a square with a mine. This code works in Microsoft Windows 3.1, Windows for Workgroups 3.11, Windows NT 3.51, Windows 2000 and Windows XP. In Windows 95, Windows 98 and Windows NT 4.0, the pixel is only visible if the standard Explorer desktop is not running. In Windows XP, it is NOT necessary to click at least one square before the pixel accurately reports mine placement.

In earlier Windows versions, the file "winmine.ini" contains the high score table data. Editing this file changes the high score table accordingly, and can be used to falsify "high scores".

In more recent Windows versions of Minesweeper, the high scores list has been moved into the registry (HKEY_CURRENT_USER\Software\Microsoft\winmine). One can forge "high scores" by using a registry editor to access the highscore name and time files and change the data in them.

A cheat code can be used to stop the timer. After the timer has started hold down both the right and left button on the cursor and press escape (ESC). This does not work on Windows XP. (In the Windows 2000 version, pressing the ESC key alone after the game has started will stop the timer.)

The timer may also be stopped by clicking and holding the smiley face at the top of the minefield. Note that in order for this to work without simply causing a new game to start, the player must move the pointer off of the face before releasing the mouse button.

Also, in the windows version, by using the above "xyzzy" and right clicking on all of the mines before ever left clicking allows the player to locate and flag all of the mines without the timer starting. Once the player has flagged all of the mines, he or she simply has to clear the rest of the board by left clicking.

KDE

KMines, in the official release, for KDE. Originally created in 1996 (latest release August 25, 2005 2.1.10) by Nicolas Hadacek under the GPL. See the homepage.

Features

1. Easy, normal, expert and custom levels.
2. Keyboard-only game possible.
3. Configurable colors, mouse buttons and tile size.
4. World-wide highscores.
5. Solver and adviser.
6. "Magic reveal" mode that only let the non trivial cases.
7. Game log: save/load/replay a game.

GNOME

Mines (or gnomine), in the official release, for GNOME under the GPL as part of Gnome Games .The game's "story" is that you have to locate mines floating in an ocean. See the homepage.

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. Getting a time under 60 seconds in expert is very respected by the minesweeper community, naturally called the "minute barrier", or OMB (one minute barrier).

For the beginner level, the record is one second (many players) for the 9x9 and/or 8x8 boards, in cases where one click reveals the entire board. The timer starts at one second, and therefore a time of zero seconds is not possible.

The Minesweeper Community has compiled a best ever list which includes videos of the fastest games ever played. In order to get on that list, records on beginner, intermediate and expert must sum up to no more than 99 (sub 100 seconds). It is officiated by the IMC (International Minesweeper Committee), and the world records listed are all held by Dion Tiu of Australia, with a 38 on expert, a 10 on intermediate (tied by one other person) and a 1 on beginner (tied with many other players).

The odds for winning Beginner (9x9 board) in a single click are as follows. Out of 127,800,681 games played in a row, by clicking in the corner, and seeing if all the squares get uncovered at once, 1,519 won on the first click. This gives an approximately 0.00119% chance of winning instantly, by clicking in the corner. In 6,713,134 games, clicking in the middle, 39 won on first click, giving only an approximately 0.00058% chance of winning instantly. In 10,839,687 games, clicking in the middle of an edge, 103 won on first click, giving an approximately 0.00095% chance of winning instantly. This could be more precisely calculated using combinatorial mathematics rather than statistics - but doing so would probably prove rather tedious.

Examples of the classic game

There are several implementations of the game in its classic form. Here are some examples:

• Minesweeper running in Windows XP
  Minesweeper running in Windows XP
• Minesweeper running in Windows Vista.
  Minesweeper running in Windows Vista.
• 
  Minesweeper clone named KMines for KDE
• 
  Minesweeper in Firefox
• 
  GNOME Mines
• 
  The Ace of Penguins
• 
  XBomb
• xdémineur (Look-alike clone of Microsoft version)
  xdémineur (Look-alike clone of Microsoft version)
• freeware Minesweeper dashboard widget for Mac OS X
  freeware Minesweeper dashboard widget for Mac OS X
• 
  Winemine, Minesweeper game bundeled with wine ,according to the author "I wrote it because it rhymes ;)"[1]

Variants

There are variations of Minesweeper available for download at various places on the Internet. These are generally differently shaped minefields in two and three dimensions, or various 2D layouts (such as triangular or hexagonal grids). For example, X11-based XBomb adds triangular and hexagonal grids, and Professional Minesweeper for Windows includes these and many others.

• There is a game called "Nonosweeper," which applies Minesweeper-style graphics to a nonogram game. It shows a grid with groupings of numbers on the right side and bottom side. These numbers indicate clusters of mines. An example might be 2 1 2 3, denoting that there are clusters of 2, 1, 2, and 3 mines each separated by at least one empty space.

• MineSweeper3D is a 3D version of the classic Minesweeper. The rules are the same, but the game takes place on the surface of a three-dimensional model rather than on a flat grid.

• Hexmines was a variant on a hexagonal grid created by Macintosh developer Ingemar Ragnemalm. Apart from the different board geometry, it is largely identical to the original game.

Examples of variants

• Played on 3D surfaces (shown here on a truncated cuboctahedron) Includes 3, 4 and 5-sided tiles
  Played on 3D surfaces (shown here on a truncated cuboctahedron) Includes 3, 4 and 5-sided tiles
• 3D version
  3D version
• 4D version
  4D version
• 
  A game with hexagonal tiles
• 
  A game with triangular tiles
• 
  An ASCII version (played with the keyboard)
• 
  This program deliberately generates the mine layout in such a way that the player never has to guess.

References

• http://www.gamesetwatch.com/2007/02/column_beyond_tetris_minesweep.php

External links

• Planet Minesweeper
• The Authoritative Minesweeper

Minesweeper in science

• Ian Stewart on Minesweeper - Article by a lecturer in pure mathematics.
• Richard Kaye's Minesweeper Pages - Proof of NP-completeness.