Demine Help
Introduction
Demine is a nice helper while trying to solve Microsoft ™ Minesweeper.
Minesweeper (as suggested by its the name) is the game where the user has to guess where bombs are knowing only how much bombs there are around some positions.
The following image shows a typical situation where a single mistake (i.e. pressing the tile corresponding to the bomb with a red background at the right-bottom corner) led the user to a total
disaster:
Had she used Demine things could have gone very differently:
So if in trouble consider using Demine.
Demine looks very similar to Minesweeper:
The number on the left is the number of bombs to discover, while the number on the right is the elapsed seconds number as with Minesweeper. The difference
is that such number are painted in green and that the seconds counter ticks every 2 seconds. The central symbol highlights user preference 'cause Minesweeper comes in many different flavors at
least this is the situation here in Italy. Then there are the game board and some menus.
How to use Demine
As said Demine has been created as a help to solve Minesweeper. The typical situation in which Demine proves helpful is the following: the user runs minesweeper and starts playing with it until she cannot make more guesses. She then runs Demine, let the program take a snapshot of the game board and then let it think about the situation to produce suggestions. Usually one or more suggestions are produced and the user can see them as a set of blinking tiles on the game board; suggestions come in two flavors:
a suggestion to click a position on the game board (i.e. the position is safe)
a suggestion to place a flag on the game board (i.e. there is a bomb at the position)
The program can issues the mouse clicks for You (You can even decide the speed at which each click follows the other) or You can force it to only show suggestions without directly interacting with the game board. Obtaining only suggestions is useful to try to understand why such decisions are taken i.e. to try to understand more deeply the game and to improve Your own strategy to successfully solve it. In other words think about Demine as a personal trainer that can help You exploring the entire Minesweeper board safely i.e. without causing explosions.
However things aren't as good as it seems 'cause chance can sometimes play an important role in some board configurations (this is also true at the very beginning when there aren't discovered tiles and so the only option is a guess.) i.e. there are configurations for which even Demine cannot guess bombs' position but can only tell You about the probability for a position to hide a bomb. This happens 'cause multiple 'admissible' configurations are possible i.e. bombs can be placed in many (at least two) different modes without violating the game's rules.
When this happens Demine doesn't blink suggestions (as there aren't safe moves) but it draws a probability on each 'contour' tile. Contour tiles are covered positions that have some discovered tiles as neighbors i.e. are the tiles You concentrate on while playing the game. The probability is calculated as the ratio between the number of admissible configurations and the number of times the tile has been a bomb in such admissible configurations. The following images shows how probabilities are drawn on board (using two different 'draw as' bitmaps):
the numbers are percentages i.e. 27 stands for a probability of 27% to hide a bomb while the position(s) with the lowest percentage to be bombs are highlighted in yellow (11% here); 0 stands for 0% i.e. it's safe to click such a position while a red uppercase 'B' stands for 100% i.e. place a flag here. A blue uppercase 'W' can be drawn on some tiles but only if the configuration is wrong i.e. only if it has been manipulated by hand or it's the consequence of misplaced flag(s) (W stands for wrong).
Usually probabilities are shown only when no safe guesses can be made, but they are however always drawn on a specific form accessible with the menu item 'View Probabilities'. When Demine cannot make safe moves lets You decide what to do next; it's upon to You to decide which tile to click as next; You can do it by double-clicking a tile on Demine board or a tile of the 'Probability Form' and the corresponding tile on the game board will be clicked: this is useful 'cause for example we can directly double-click the tile with the yellow 11 instead of trying to find it on the game board. Be careful however that such double-clicks will be always reflected on the game board, no matter if You forced the program to not generate automatic clicks. Also remember that even the tile with the lowest probability can hide a bomb !
Now Demine let You know if contour tiles have the lower probability or if a random click on a non-contour still covered tile has less probability of hitting a bomb, in the former case probabilities are drawn on contour tiles as explained above, while in the latter case the probabilities of contour tiles are drawn in red meaning 'it's better to click elsewhere'. The following image shows this new feature (Thank to TPReal for the suggestion). Also moving the mouse on the board after a solve phase shows the probability of being a bomb associated with contour tiles and all the other still covered tiles.
Note that all the probabilities for contour tiles are drawn in red because the probability of still covered non-contour tiles is better (it ranges from 16% to 24% because isles use from 7 to 9 bombs leaving from 4 to 6 bombs for the 25 non contour covered tiles).
Let's now take a look at how all the above can be accomplished with Demine by examining the program's menus.
Tools Menu
The most important part of the program is the Tools menu:
Capture analyzes the game board and try to parse it. It can handle successfully a good variety of slightly different games as four Italian variations
plus an English/American version of Win XP that has apparently the same tile's bitmaps as the Italian version for Win NT. The main differences between variations are in tile's bitmaps as demonstrated by the following image (if Your version of the game is different I would like to see it):
also there is a Black&White version for all them. The user is responsible to run her preferred version of minesweeper as the program handles the game only if minesweeper is already running. The program can detect automatically games if their name is one of the following:
'Campo minato'
'Prato fiorito'
'Minesweeper'
'Buscaminas' [Spanish] is now a recognized name, too (New).
'Saper' [Polish] is now a recognized name, too (New).
If in Your main language the game is named differently You can try to add its name to the file <Demine exe name>.gam (placed where the exe is) (and I
would like to know it too).
This file can contain a game's name on each line as a space-separated pair WinClassName WinName (Usually they are the same, but who knows); also remember to use " if one or both
names contains spaces as in "Campo minato" "Campo minato"). Provided the bitmaps is one of the above the game should now be recognized too. For example:
"Campo minato" "Campo minato"
Minesweeper Minesweeper
can add the program the capability to recognize two game's names (remember however that the above names are already handled automagically).
If the capturing phase is successful (as it should be) the program builds an internal representation of the game board and can reproduce it using the user preferred bitmaps.
An important point while capturing is that minesweeper board and bombs' numbers MUST not be covered by other windows or the capturing could fail, also the game board MUST be completely visible on screen. Demine try to automate this check by setting Minesweeper as the foreground window and minimizing 'Windows Task manager' so to avoid possible overlapping before capturing; it also make sure that the entire game board is visible on screen but should it fail it's upon to You to make sure that nothing covers the game board before trying to capture it.
As an additional help You can add the Win class name and win name of the programs Demine must minimize before trying to capture to the file <Demine exe name>.top (placed where the exe is) as a pair exactly as with the .gam file above. This is useful for 'stays on top' applications that if not minimized should cover the game board. Task manager is already taken care of automatically (or it should), but as an example the corresponding line in the .top file could be:
#32770 "Task Manager Windows"
While capturing a Log Window with an active timer pops up and depending on whether 'autoclose log' option is checked or not You could be required to press the OK button when finished. Usually the 'Autoclose Log' option should be checked so You don't have to press the OK button to close the window, but uncheck it if something goes wrong as the log shown by the window is the place to look to try to understand what failed.
When the capturing has been performed it's possible to require the program to analyze the board and produce suggestions or at least probabilities with one of the available Solve sub-menu items. By pressing CTRL+Space a capture phase followed by a Solve phase are issued.
When the Solve phase is finished it's possible to look at probabilities with the View Probabilities menu.
The Capture clipboard menu can parse a bitmap of the full game window or of the game board alone; this is useful for example to record a particular configuration even if we don't have Demine at hand: it's sufficient to take a snapshot of the game and Demine will parse it.
The Solve menu has some sub-items as shown by the following image:
Depending on the configuration currently at hand some of them (namely the obvious and contradiction ones) can be disabled 'cause the corresponding techniques aren't able to produce suggestions for the current configuration. These techniques are detailed in the 'Techniques.html' file.
Solve original uses a brute-force exhaustive (i.e. try all possibilities) technique; it's named original 'cause this technique was available in the program from the very beginning.
Solve obvious is a different method to solve a configuration; it's faster but is less powerful than standard (original) or new solve; also standard and new solve can protect itself from wrong configurations, while obvious solve cannot. If however the current configuration is surely correct then this fast method is the way to go.
Solve by contradiction is just another fast method to solve a configuration; it has exactly the same pros and cons as the Obvious one. It is an implementation of a technique developed for an AI project at the University of British Columbia Okanagan (here is the exact link); I found such technique while surfing the net and liked it so I decided to adopt it and ported it to Demine.
Solve new uses a brute-force exhaustive (i.e. try all possibilities) technique but different from the original one; it's named new 'cause this technique has been developed after the original technique.
Now returning to the Tools menu, the View isles option let You see how the program breaks down the problem in little pieces to solve it as in the following image (each isle is a sequence of tiles painted with a different color):
The View Good Configurations menu item let You explore directly the admissible configurations for each isle (Yes the program can remember every good configuration it finds for every isle !). The following image shows You an example. The window is composed by 3 panels, the upper panel, the left panel and the right panel. The upper panel contains a combo on the left that let You choose an isle, then there is an edit by which is possible to select a good config index and an edit that shows some information about the isle as the isle index, the good config number, the min and max number of bombs of the good configurations (yes the two numbers can differ, for example the configuration in the image can be satisfied by 2 bombs placed as the flowers show, or by a single bomb placed in the central tile) and the number of 'contour' tiles (i.e. the tiles You can still click to discover or to put a flag). The right panel shows a copy of the main-board. Contour tiles are the bomb tiles (flowers in the image) plus the covered tiles drawn in yellow; the good configuration placed a bomb where shown and leaved empty the yellow tiles.
The red cross in the image above marks a good configuration rejected by the final phase algorithm; i.e. a configuration that is admissible for the isle, but that must be discarded to avoid using too much bombs ! So it's clear that in the image above there is only one missing bomb and the good configuration with 2 bombs must be discarded. The isle's description underlines this fact when it says that the good configurations use from a min of 1 bombs to a max of 2 bombs, while the accepted configurations i.e. the real ones use only 1 bomb. The left panel contains a treeview that shows the isles and some good configurations indexes to let You reach in a fast way a good configuration. It's also possible to type directly in the apposite edit a configuration index You want to inspect. This menu item can appear disabled if the program doesn't remember good configurations i.e. if the corresponding option isn't checked.
The Create configuration menu opens a new form that let You select good configurations for the isles to create a starting configuration for DemineExercizer as shown by the following image.
A simple click on any isle's tile allows You to select a good configuration for the isle and when all the wanted good configurations have been chosen, a right click with the mouse activates a popup menu that accept the configuration and let save it to a file. If there are more bombs they are placed randomly in the still covered not-contour tiles. This possibility is useful if the user recognizes an interesting combination of bombs in some isles; she can then select the interesting good configuration from the isle good configurations and so force it as a configuration for DemineExercizer to be able to study it; had she continued to solve the game she could have discovered that the real configuration of the game was different so loosing the possibility to study the interesting configuration.
Last but not the least Redraw board can be used for example to remove blinking suggestions from the board.
Options Menu
The Options menu let You customize some program's behaviours:
The Draw as option lets You choose which bitmaps to use to draw the game board so for example it's possible to have a
color representation of Black & White game board.
The available bitmaps are 8: 4 B&W and 4 colored.
The Prefer option lets You choose which game to prefer just in case some different games are at the same time on the screen:
here in Italy we had 'Campo minato' but now it seems to have been replaced by 'Prato fiorito', a 'more politically correct' version of the game where bombs have been replaced by flowers, also You can prefer the English/American version minesweeper. Note however that Demine will not run these games for You as preference come to action only when more different versions of the game are active on the screen.
Each possible choice is highlighted with a symbol that in Demine replaces the faces of minesweeper (from left to right 'Campo minato', 'Minesweeper', 'Prato fiorito' and 'DemineExercizer'):
DemineExercizer is a custom version of Minesweeper that allows configurations to be created 'by hand' and bombs to be seen. It has been created to exercise Demine i.e. to play some configurations again and again: it's especially useful to debug Demine or to study the improvements added on the same configuration (an impossible thing with a .min file or a board bitmap).
The Really do clicks option lets decide if the program suggestions are automagically turned into clicks on the game board or if they should remain suggestions (useful to study a configuration without modifying it).
The Play speed option decides the speed at which clicks on the game board are issued (if allowed). This menu item can be disabled if the program is not allowed to produce clicks.
The Opacity option uses W2K e XP alpha blending capability to draw Demine board in transparent mode.
The Autoclose Log option decides whether You want or not to take a look at the log produced by the Capture and Solve phases on the specific window.
The Keep good configurations option tell the program to remember (if checked) all good configurations it produces for every isle. You can leave it unchecked if You don't want to take a look at good configurations and You'll spare memory (sometimes a lot of memory). Remember however that if this option is unchecked You'll never open the 'View Good Configurations' window as the associated menu item in the tool menu will always be disabled.
The Direct capturing option decides which algorithm to use while capturing the game configuration. One algorithm copies the relevant parts (tiles and digits) of the game board into internal images before parsing them while the 'direct capturing' variant accesses directly the pixels on the original game board. This option should be leaved checked as both algorithms can correctly parse the game configuration. The 'copy capturing' algorithm has been particularly useful in the development of the methods to parse a game board 'cause copying tiles and digits into internal images makes it very easy to spot immediately if wrong parts of the board or of the digits are considered.
The Full evaluator option decides if during the solve phase an attempt should be done considering all possible configurations (the smart solver, used by default, can avoid to explore some configurations while still ensuring that all admissible configurations are considered). This option can be leaved unchecked as it's mostly an option useful while debugging to verify that the smarter solver MUST consider as many admissible configurations as the dumber one). Also warning as with this option enabled it can take a while (lot more) for isles with a rich contour set to be solved.
The Use new tech option if selected forces the use of the new exhaustive solve technique instead of the original one during the CTRL + space capture & solve cycle.
File Menu
The File menu let's You save and load game configurations and Exit the program (are You sure to really quit the program ?).
Load can handle .min files (configuration files), a bitmap of the board or a bitmap of the entire game's windows. Now it's also possible to drag&drop a .min file to the program to load it.
Save can produce a bitmap of the board, or a .min file; .min files are a custom way of saving a configuration. The following is a sample file:
Demineur_G1@nn1Luc1@n1(2003)
Width= 9
Height= 9
Bombs= 8
..1=Q====
..1F=====
..11=====
...1=3===
...1===3=
...1==1==
.111=====
.1F======
.1=======
Edit Menu
The Edit menu has the following items:
The Bmp to clipboard menu allows the bitmap of the board to be copied to the clipboard.
The Copy menu puts the current configuration on the clipboard as a string whose content is exactly the same as the content stored in files to save the configuration.
The Paste menu allows a configuration on the clipboard to replace the current one on the board; this menu is disabled if there isn't a valid configuration on the clipboard.
Help Menu
There is only one sub-menu, namely About that's obvious.
Conclusion
Well that's all, I just suggest You to remember the CTRL+Space shortcut to do a capture + solve phase in sequence and to use Obvious & Contradiction solve (continue until they cannot be applied any more) if the board to solve is correct and has not been manipulated: they will save a good amount of time in some occasions.
Development info
The program has been developed on Windows XP with Service Pack 2 using C++ builder 5 Pro with service pack 1 and then ported to C++ Builder 2006 Pro with service pack 1.
The program uses boost from www.boost.org version 1.33.1.
Boost version 1.33.1 (the last currently available) has been used replacing the file boost\config\compiler\borland.hpp with the corresponding file from the project bcbboost from SourceForge.
Demine is a freeware/donationware and has been tested on Windows 2K & XP.
Enjoy it.
Gianni Luciani.
Bug-fixes to the Aug 3 2006 version
Improvements
Improvements to the Sep 18 2006 version
Acknowledgements
Many thanks to TPReal for the bugs finding, the ideas and the suggestions.
P.S. Suggestions, different game bitmaps (both to be parsed and draw as bitmaps), different game names, ideas, bugs and so on are welcome.