Minehunt: a Strategy


In the discussion along the development of the sample game we found four ways of progressing:


  1. Random click because of total ambiguity (we used this only once, at the very start).
  2. Flagging bombs and uncovering cells with certainty by simple accounting of the surroundings of a single cell.
  3. Deducing where bombs or safe cells are by considering all possible bomb configurations.
  4. Discarding configurations that do not respect the total number of bombs.

An algorithm could then be:

  1. If the situation is ambiguous, pick a covered cell at random and click on it.
  2. Examine the accounts of each uncovered cell:  if its surroundings correspond exactly to its bombcount, then they can be flagged or uncovered.
  3. Consider all configurations of the not yet determined bombs, overlay these to find cells that either have a bomb in each configuration or that have no bomb in any configuration.  Flag/uncover if there are such cells and in that case repeat step 2.  If there are no such cells, then the situation is ambiguous:  go to step 1.

Obviously we stop if we step on a bomb, so we will not explicitly mention this case again.

A mathematically much cleaner algorithm is:

  1. Repeat until nothing changes:
    1. Consider all configurations of not yet determined bombs.
    2. Overlay these to find cells that have a bomb in each configuration and those that have no bomb in any configuration.
    3. If such cells exist, flag/uncover them.
      If there are no such cells, then the situation is ambiguous, click a randomly chosen covered cell.

While this is certainly correct, it is rather impossible to implement:  the first step forces us to compare all configurations of bombs at a time when we know nothing at all.  Even for a very small grid of 5x5 and only 5 bombs, the number of possible configurations is (25x24x23x22x21)/(5x4x3x2x1) or 53'130.  We need to keep these to overlay them, and yet we know that we will find an ambiguous situation.  For more realistic gridsizes, the computing time is simply unrealistic.

Even when we start out by a random click, we will not get there in a reasonable time:  in many cases a random click uncovers only a single cell; uncovering a sea is a stroke of luck.  You usually have to click more than once at random before you can start any reasoned deductions.  I observed that it is common to discover a sea if I start from a cell that has a 1 as bombcount and work out from there along a diagonal.  I stop as soon as I have a sea.

But even having uncovered a large sea, we can still not use the clean mathematical algorithm:  there simply is too much covered land left.  I therefore concentrate the search for combinations on the shoreline.  This means I do not take into account the total number of bombs as long as there is still a lot to uncover.

When I see that only a few bombs are left to identify, but there is still a lot to uncover, I see if these bombs have to be close to the shore or not.  If the bombcounts in the shoreline cells are such that all the undetermined bombs must be there, and yet there is a lot of land behind the shore, then obviously most of it is safe to step on.  At this stage it may be possible to determine an entire area of land that cannot contain bombs and can be clicked on.  This then usually uncovers a sea, but at the very least gives some extra info.

Even if there is no completely safe area this knowledge can be useful.  Suppose there are still seven bombs to be placed, five of which must be within a confined area near the shore, the uncovered area is still 23 cells big and I am in an ambiguous situation.  It is then obvious that it is much less risky to click away from the shore than to pick a cell in the confined area where I know there is a concentration of bombs.  So the choice of covered cell to click in an ambiguous situation is not obvious and step 3 of the mathematical algorithm should be refined by computing a probability for each cell to contain a bomb and choosing the least probable one.

Valid XHTML 1.0 StrictValid CSS

next planned revision: 2005-06-01