FvdP HOME > Main index > MineSweeper

MineSweeper

Game analysis

How to compute probabilities

Sean Barrett shows how to compute mine probabilities. Besides being a nice introduction to probability reasoning, this provides by far the most advanced MineSweeper tactics I've ever read on the web.

MSW is not trivial: a counter-example

Somebody conjectured that in any given position, at least one optimal move would have minimal mine probability. Here is a counter-example:

		`a`	`b`	`c`	`d`
	`+`	`-`	`-`	`-`	`-`	`+`
`1`	`\|`	`*`	`.`	`*`	`2`	`\|`
`2`	`\|`	`4`	`.`	`.`	`.`	`\|`	(3 more mines to find)
`3`	`\|`	`*`	`.`	`*`	`2`	`\|`
	`+`	`-`	`-`	`-`	`-`	`+`

where "*" represents a known mine and "." a still-covered cell. By computing all 6 (= 3*2) possible solutions, you realize that probability of mine is 2/3 on cells b1, b2, b3 and only 1/2 on cells c2 and d2. However, by playing any of the "2/3" cells you can win 2 out of 6 times; by playing any of the "1/2" cells, you'll win only 1 out of 6 times.

Shortly speaking, c2 and d2 are bad moves because they can bring you no useful information: you know beforehand which result they will yield if they do not kill you (d2 yields 3, c2 yields 5). On the other hand, playing any of the "2/3" moves will tell you (if you survive !) where's the mine in c2 or d2.

MSW is not trivial: NP-completeness

Determining whether a given MineSweeper board is possible is an NP-complete problem (as insight, note that this problem is an instance of integer linear programming.)

For a proof of this look at Richard Kaye's Minesweeper page.

The proof goes by (polynomially) encoding boolean circuits as Minesweeper positions. Since boolean circuit satisfiability is NP-complete, NP-completeness of the Minesweeper board problem follows.

Automatic players or solvers

Source code

More or less by decreasing order of strength:

Truffle-Swine Keeper: this is almost the most advanced solver I've met on the web and it comes with source code ! It computes exact mine probabilities, and last but not least, comes with a graphical user interface on both Windows and Linux ! It does not perform any strategic exploration of the game, though. Written in C++.
The Oz Minesweeper, by Raphael Collet: another solver, written in OZ/Mozart. This one use constraint propagation to determine safe place and sure mines with 100% accuracy, but does not determine mine probabilities. (I have not tried it, but I suppose it works...)
XBomb by Matthew Merzbacher for Unix/X comes with interesting solvers (in C). Get a TAR archive of the sources (180 K). There exists other programs with the same name on the Web... be sure you download the right one !
Dave Rusin (see above) wrote a Minesweeper game & solver program for MS-DOS, in Pascal (bundled with the exe if you want to test it).
I also found a program written in Python.

Windows binaries

Most automatic players will play with the program that ships with Windows. The bad side of this, is that they require Windows 3.1, 95 or 98 in order to work (Windows NT, Windows 2000: no avail !); you must also have the proper original Minesweeper version (which may not be the one that shipped with your version of the O.S. !) They may (or may not) win high scores in your name.

Smrtmine.exe a.k.a. MineBuster: "smrt" for smart, it deserves the name: that's the smarter solver I've met on the web. In last resort, it will enumerate all possible positions in a given part of the game, and if it does not find safe moves, it will move on a cell with low probability of bomb.
Besides that its interface is really well-done.
(Works with all versions of Minesweeper)

One day I will include my own solver in this list. It will compute and display exact mine probabilities, perform exhaustive strategy searching in some situations, etc.

A prototype (?) already exists in Python and computes mine probabilities.

Variants

There is a very interesting continuous variant Dynamine of MineSweeper (for Windows). Here is what the author writes:
It is very different from other minesweeper games because it does not divide the world into neat little boxes and give you exact numbers of neighboring mines. Instead you must carefully watch the shades of gray and stay away from darker regions where mines lurk.