Minesweeper (computer game) - AbsoluteAstronomy.com

Minesweeper is a single-player video game. The object of the game is to clear an abstract minefield

Land mine

A land mine is usually a weight-triggered explosive device which is intended to damage a target—either human or inanimate—by means of a blast and/or fragment impact....

without detonating a mine. The game has been written for many system platforms in use today.

Minesweeper cannot always be solved with 100% certainty, and may require the occasional use of probability to flag the square most likely to have a mine.
In other words, one must sometimes guess to solve a minesweeper puzzle.

Overview

The player is initially presented with a grid of undistinguished squares. Some randomly selected squares, unknown to the player, are designated to contain mines. Typically, the size of the grid and the number of mines are set in advance by the user, either by entering the numbers or selecting from defined skill levels depending on the implementation.

The game is played by revealing squares of the grid, typically by clicking them with a mouse. If a square containing a mine is revealed, the player loses the game. Otherwise, a digit is revealed in the square, indicating the number of adjacent squares (typically, out of the possible eight) that contain mines. In typical implementations, if this number is zero then the square appears blank, and the surrounding squares are automatically also revealed. By using logic, the player can in many instances use this information to deduce that certain other squares are mine-free, in which case they may be safely revealed, or mine-filled, in which they can be marked as such (which, in typical implementations, is effected by right-clicking the square and indicated by a flag graphic).

In some implementations, a question mark may be placed in an unrevealed square. This has no meaning in the rules of the game, but can serve as an aid to logical deduction. Another convenience feature present in some implementations is an interface to quickly clear around a revealed square once the correct number of mines have been flagged around it. The game is won when all mine-free squares are revealed, meaning that all mines have been located.

Some implementations of Minesweeper will set up the board by never placing a mine on the first square revealed, or by arranging the board so that the solution does not require guessing. Minesweeper for versions of Windows through Vista protected the first square revealed

Minesweeper (Windows)

Windows Minesweeper is a variant of the computer game Minesweeper, created by Curt Johnson, originally for OS/2, and ported to Microsoft Windows by Robert Donner, both Microsoft employees at the time...

. Minesweeper with Windows 7 also protects the first square unless the user chooses to replay a specific board.

Minesweeper can be modeled as algebra of binary variables with some exception that it does not possess a unique solution all the time. At such cases, the player has to guess for the location of a mine. See below for an example of a case that the player has to guess. See board puzzles with algebra of binary variables

Board puzzles with algebra of binary variables

Board puzzles with algebra of binary variables ask players to locate the hidden objects based on a set of clue cells and their neighbors marked as variables . A variable with value of 1 corresponds to a cell with an object...

for reducing the minesweeper locally into algebra of binary variables.

History

Minesweeper has its origins in the earliest mainframe games of the 1960s and 1970s. The earliest ancestor of Minesweeper was Jerimac Ratliff's Cube. The basic gameplay style became a popular segment of the puzzle game genre during the 1980s, with such titles as Mined-Out (Quicksilva

Quicksilva

Quicksilva was a British games software publisher active during the early 1980s.Amongst the company's successes were Jeff Minter's Gridrunner and Bugaboo , a title licenced from Spanish software house Indescomp S.A....

, 1983), Yomp (Virgin Interactive

Virgin Interactive

Virgin Interactive was a British video game publisher. It was formed as Virgin Games Ltd. in 1981. The company became much larger after purchasing the budget label, Mastertronic in 1987. It was part of the Virgin Group...

, 1983), and Cube. Cube was succeeded by Relentless Logic (or RLogic for short), by Conway, Hong, and Smith, available for MS-DOS as early as 1985; the player took the role of a private in the United States Marine Corps

United States Marine Corps

The United States Marine Corps is a branch of the United States Armed Forces responsible for providing power projection from the sea, using the mobility of the United States Navy to deliver combined-arms task forces rapidly. It is one of seven uniformed services of the United States...

, delivering an important message to the U.S. Command Center. RLogic had greater similarity to Minesweeper than to Cube in concept, but a number of differences exist:

In RLogic, the player must navigate through the minefield, from the top left right angled corner to the bottom right right angled corner (the 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.

The gameplay mechanics of Minesweeper are included in a variety of other software titles, including:

The mini-game Vinesweeper implemented into the MMORPG
MMORPG
Massively multiplayer online role-playing game is a genre of role-playing video games in which a very large number of players interact with one another within a virtual game world....

RuneScape
RuneScape
RuneScape is a fantasy massively multiplayer online role-playing game released in January 2001 by Andrew and Paul Gower, and developed and published by Jagex Games Studio. It is a graphical browser game implemented on the client-side in Java, and incorporates 3D rendering...

; in this iteration (written by Jagex
Jagex
Jagex Games Studio, based in Cambridge, is the UK’s largest independent developer and publisher of online games. Jagex is best known for RuneScape, the world's largest free-to-play MMORPG....

developer Danny J), the Minesweeper gameplay is given a large multiplayer aspect and the "game board" adopts a continually resetting timer. This allows for a never-ending game of Minesweeper where the skill is awarded assessed in points rather than "game completion".
The PC game Mole Control (developed by Remode); in this game, the minesweeper mechanic is integrated into a puzzle adventure game based in a village called Molar Creek, which has been overrun with exploding moles. You play the local inventor's assistant, who is tasked with clearing the village of exploding moles, and you can also take part in the Molar Creek Annual Mole Control competition in a Time Attack Mode.

Distribution and variants

Versions of Minesweeper are frequently bundled with operating system

Operating system

An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...

s and GUI

Gui

Gui or guee is a generic term to refer to grilled dishes in Korean cuisine. These most commonly have meat or fish as their primary ingredient, but may in some cases also comprise grilled vegetables or other vegetarian ingredients. The term derives from the verb, "gupda" in Korean, which literally...

s, including Minesweeper

Minesweeper (Windows)

in Windows, KMines

KMines

KMines is a minesweeper game for KDE, originally created in 1996 by Nicolas Hadacek under the GPL. It is part of the Kdegames package.KMines has three default sizes, "easy" , "normal" , and "expert" , as well as custom levels. The custom levels can have dimensions from 5×5 to 50×50...

in KDE

KDE

KDE is an international free software community producing an integrated set of cross-platform applications designed to run on Linux, FreeBSD, Microsoft Windows, Solaris and Mac OS X systems...

(Unix

Unix

Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...

-like OSes), Gnomine

Gnomine

Gnomines is a minesweeper game for GNOME is licensed under the GPL as part of GNOME Games. The game was written in C by Pista and it was later improved by face artwork made by tigert...

in GNOME

GNOME

GNOME is a desktop environment and graphical user interface that runs on top of a computer operating system. It is composed entirely of free and open source software...

and MineHunt in Palm OS

Palm OS

Palm OS is a mobile operating system initially developed by Palm, Inc., for personal digital assistants in 1996. Palm OS is designed for ease of use with a touchscreen-based graphical user interface. It is provided with a suite of basic applications for personal information management...

. Apart from the bundled versions, a huge number of clones of all shapes and sizes can be found on the Internet.

Variants of the basic game generally have differently shaped mine fields in two and three dimensions, or various two-dimensional 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 others.

A minigame in FIFA 11
FIFA 11
FIFA 11 is the 18th title in Electronic Arts' FIFA series of football video games. Developed by EA Canada, it was published by Electronic Arts worldwide under the EA Sports label...

is a variation of Minesweeper.

The Voltorb Flip game in the non-Japanese releases of Pokemon HeartGold and SoulSilver
Pokémon HeartGold and SoulSilver
are enhanced remakes of the 1999 video games Pokémon Gold and Silver. The games are part of the Pokémon series of role-playing video games, and were developed by Game Freak and published by Nintendo for the Nintendo DS...

is a variation of Minesweeper and Picross. This game was designed by veterans to recreate World War II, and was used as stress relief for them. This game has also been considered controversial to natives of China.

Another derivative of Minesweeper is Tentaizu (puzzle)

Tentaizu (puzzle)

Tentaizu is a logic and algebra puzzle. It falls in the category of board puzzles with algebra of binary variables. The hidden objects in this game are stars. The player solves the puzzle by locating a number of stars on a board with adjacent cells...

with unique solution all the time.

The game is called "Prato Fiorito" (flowery lawn) in the italian versions of Windows, in response to requests to have a game not based on deadly anti-personnel mines.

Patterns and solving

There are many patterns of numbered squares that may arise during a game that can be recognized as 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. There are a few broad methods for solving problems in minesweeper games without guessing.

Single-square analysis

Example case 2

EWLINE

a and b must be mines; the only squares that can provide those demanded by the 3 are a and b.

Example case 1

EWLINE

a and b are safe to open, as the 3 is satisfied by adjacent mines.

There are two special cases that are of extra interest when solving a board that can be solved using analysis of only one square and its surrounding squares:

If the number of unrevealed (blank or flagged) squares adjacent to a numbered square is equal to the number on that square, all these unrevealed squares must be mines.
For any numbered square, if the number of flagged mines located adjacent to that square is equal to the number of the square, all other squares adjacent to that numbered square must be 'safe' (e.g. If you know the square to the right of a 1 is a mine, then you can deduce that all the other squares next to that 1 do not contain mines.)

Multiple square analysis

To solve more complex puzzles, one needs to consider more than one square at a time. Some strategies that involve considering more than one number at a time:

If you have two adjacent numbers, the difference between those numbers is equal to the difference in the number of mines for the 3 squares adjacent to each that are not adjacent to the other number. For example: if these numbers differ by 3, all of the adjacent squares to the higher number not shared by the other are mines, and all the opposite ones are safe.
In a similar method, sometimes it can be known that there are a certain number of mines in a certain number of squares (without necessarily knowing which are the mines and which are safe) and you can often utilise this information to find out information about other squares.

One method that is commonly used by minesweeper AI

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

s is to consider the board as a constraint satisfaction problem

Constraint satisfaction problem

Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...

.

The variables/unknowns are the unopened squares, and the constraints are the adjacent squares that are opened. The algorithm consists of trying every combination of mines that satisfies all the numbers in the adjacent squares, and making a conclusion from there. For large puzzles, this is a time-consuming process for a computer, but expert minesweepers might be able to quickly see which squares need this procedure, and where one might expect it to succeed. The two rules above are such special cases.

Example

EWLINE

Example:
A corner square and the 3 adjacent squares have been opened, and the numbers given revealed. The letters here are unopened squares and they are the variables.

Blindly trying every combination gives the 4 valid configurations (out of 2⁵), namely

and

, where 1 represents a mine.

The only common number in all these configurations is that the variable e is never a mine. The conclusion is that in all possible valid configurations, e is safe, and one can safely open that square. Analogously, if a square is marked as mine in every valid combination, then the square must be a mine.

One can also think of this as a system of equations, where the variables must be in {0,1}.
In the above example, the constraints gives that a+b=1, c+d=1 and a+b+c+d+e=2. The third equation can be reduced to 1+1+e=2 and hence the square e must be safe. This strategy is more similar to the human approach, but is harder to implement as a computer program.

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.

In some versions of the game the number of mines on the field is known. Near the end when almost all the tiles are lifted, knowing the number of mines remaining can give some insight to otherwise unresolvable patterns.

Elements of guesswork

In most implementations of Minesweeper, it is possible for a grid to be generated which cannot be solved without an element of guessing. For instance, in the following situation:

Example

EWLINE

The player must guess whether

is the mine.

The constraint satisfaction problem above might help slightly to estimate the likelihood that a square is a mine; list all the valid combinations and count how many times each square is occupied by a mine. If the density of mines is known (or estimated during the game), the player can pick the square that is least likely to contain a mine.

Another apparent instance of required guessing is when an unrevealed square is completely surrounded either by mines, or by (more commonly) a combination of mines and the perimeter of the game window. In this case, since no numbers touch the unrevealed square, a player has no information about the likelihood of the unrevealed square being a mine. However, there is still a good strategy when facing this situation that will allow the player to avoid simple guessing: simply play the rest of the game and ignore this square. When the number of unrevealed, unflagged spaces left equals the number of mines left unmarked, then all remaining spaces are mines. Some versions may automatically flag these spaces once all other squares in the game window have been unrevealed by the player, or reveal them once all flags have been placed.

Computational complexity

In 2000, Richard Kaye published a proof that it is NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

to determine whether a position in a Minesweeper game is consistent with some placement of mines.

Measuring board difficulty

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

Method

The 3BV of a board is the total count of:

openings of the board, i.e. regions of orthogonally or diagonally contiguous squares having no neighbouring mines, together with the immediately surrounding numbered squares
numbered squares that are not part of any openings.

For example, in the illustrated example, there is one opening (shown by white borders) and there are seven further numbered squares (green dots), giving a 3BV rating of 8. Equivalently, it is the minimum number of clicks required in typical implementations to reveal all of the mine-free squares.

3BV/s

3BV/s stands for 3BV per second.

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.

Criticism

In 2001, the Italian "International Campaign to Ban Winmine" voiced strong concern over the game, contending that it is an "offense against the victims of the mines" and those who risk their lives to clear them. They created their own "Winflower" game, and lobbied Microsoft to use it in place of Minesweeper in Windows 98

Windows 98

Windows 98 is a graphical operating system by Microsoft. It is the second major release in the Windows 9x line of operating systems. It was released to manufacturing on 15 May 1998 and to retail on 25 June 1998. Windows 98 is the successor to Windows 95. Like its predecessor, it is a hybrid...

. As a reaction to this criticism, the version of Minesweeper included in Windows Vista and Windows 7 offers a mode in which the mines are replaced with flowers.

External links

Constraint Processing Techniques for Minesweeper
Ian Stewart on Minesweeper - Article by a lecturer in pure mathematics.
Ivanche Minesweeper - Scalable type of minesweeper

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.

Overview

History

Distribution and variants

Patterns and solving

Single-square analysis

Multiple square analysis

Final analysis

Elements of guesswork

Computational complexity

Measuring board difficulty

Method

3BV/s

Criticism

See also

External links