Minesweeper (game)

Minesweeper is a single-player computer game. The object of the game is to clear a minefield, without exposing a mine. The game has been ported to many computer platforms.

Table of contents 1 Rules 2 Computer implementations 3 Best times 4 Elements of analysis of the game 4.1 Not solvable without guessing 4.2 NP-completeness 4.3 Mine probabilities are not enough 5 External links

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. If a number appears, it means that that number of adjacent (including diagonally-adjacent) squares contain mines. If 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.

Most implementations of minesweeper "cheat" in favour of the player by never allowing the first square clicked to be a mine.

Computer implementations

On 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 (at least Windows 2000) feature a 9 x 9 Beginner field instead of a 8 x 8, with the same number of mines.

There is an easter egg 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 easter egg only works in Microsoft Windows 3.1, and Microsoft Windows for Workgroups 3.11. It was removed in Windows 98 but reappeared in Windows 2000. xyzzy was a magic word in Colossal Cave Adventure.

Best times

On the Windows version, the unofficial record for Expert is 44 seconds. A time under 100 seconds is considered to be very good. The unofficial record for Intermediate is 10 seconds. Many people publish screenshots or video recording 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.)

Elements of analysis of the game

Not solvable without guessing

Minesweeper is not always solvable without guessing. For instance, in the following situation:

 .....
 NXXXN
 N3?3N
 N1?1N
 _____

(X represents a mine, . represents an unimportant square, _ represents the edge of the board, N represents a known non-mine square (either a known number or an empty square), and the numbers are the standard Minesweeper numbers)

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.

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 chosing squares with lowest mines probabilities. Let's examine the following situation:

 XXXXXX
 XXaX7X
 X7bdeX
 XXcX7X
 XXXXXX

(As above X represents a mine, and the numbers are the standard Minesweeper numbers; a b c d 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.

External links

• Minesweeper is NP-complete! (http://www.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm)