Minesweeper Item

Aug 16 06:25 UTC 2000

This item is about the ubiquitous minesweeper game, the best program
Microsoft ever wrote.  Perhaps some explanation is required.

A few weeks ago I was playing "Gnome Mines" (the Linux clone of
minesweeper) late into the night before going to bed.  Once in bed, I
found myself thinking obsessively about minesweeper instead of sleeping.
Eventually I figured out that I was running a fever and this was just
the usual augmentation of my normal obsessiveness that fevers usually
cause.  Still, some of my conclusions are mildly interesting.

First, I don't like the minesweeper is normally scored.  The scorefile
keeps track of the 10 fastest times for solving the game.  Obviously
this encourages playing very fast, taking as little time to think as
possible.  I'd like a version where you can alternately select to keep
score by the percentage of your last 100 games which were successfully
completed.  This would encourage a much more thoughtful approach to the
game.

When playing for speed, I typically start with a buckshot approach -
click very fast at random at a bunch of points all over the screen. 
Usually I get blown up, and hit the new game button and try again.  When
I do survive the buckshot, I get a starting position with a fair amount
of "free" information, enabling me to play a faster game.  If you were
patient, you could probably get very high scores this way - do lots of
buckshotting, getting blown up in screen after screen, until you finally
have one with lots of data on it, which can be solved quickly.

The point is, playing for speed doesn't necessarily require a lot of
intelligence.  It's not really that interesting.

Playing for survival, winning as many games as possible is much more
interesting.  Concocting optimal strategies is challenging.

Let's suppose we have a partially solved board.  It is possible to
compute for every square on the map what the probability is that that
particular square is a mine.  Does anyone know an efficient algorithm
for doing thing?  I think it would be interesting to implement someday.

One note:  Every click on any square on the map whose probability was
not zero or one changes the probability of every other square that was
not already zero or one.  This is because the a priori probability
changes.

You might think that if you had such an algorithm, then you could simply
play by always clicking on the square with the lowest probability of
being a mine.  In fact, may not be an optimal strategy.

Here's an example.  Let's assume we have solved the entire board except
for five squares A,B,C,D,E at the bottom edge of the board.  It looks
like this (stars are mines, numbers are squares we have explored,
letters are unknown, lines are edges of the board):

   | 2 3 2 1 1 2 2
   | * * * 2 2 * *
   | A * B C D E *     two bombs left
   +---------------

Now, there are three possible arrangement of the bombs:
     A   . C . .    case 1
     A   . . D .    case 2
     .   B . . E    case 3
Thus the probabilities of a bomb are 2/3 for square A, and 1/3 for the
other four squares.  But squares B,C,D,E are not really equally good
choices.  Suppose we choose C.  One third of the time we get blown up.
Two thirds of the time it comes out to be a 2.  We then have to guess
which of the remaining two patterns is correct, a 50/50 chance.  So our
total chance of winning is only 2/3.  However if we guess B, then we
still have a 1/3 chance of being blown up (case 3), but if we don't get
blown up, then we either get a value of 4 (case 1) or 3 (case 2). 
Either way, we have figured out where all the other bombs are, and we
are done.  So the best choices here are B or E, which give a 67% chance
of winning, as opposed to A,C or D which all give a 33% chance of
winning.

The point is that guesses have to be made based not only on the
immediate risk of being blown up, but also on the value of the new
information we recieve if we are not blown up.  In the example above,
some moves with equal probabilities turned out to be better than others.
Are there cases where a move with worse immediate odds of blowing up
actually gives better odds of winning the game?  I wasn't able to come
up with any during my fever dreams.

response 2 of 29:

Aug 16 11:33 UTC 2000

The Palm Pilot version places the mines before the first click, so you can
get blown up on your first try.  The Windows version actually waits until
after the first click... neat, huh?

You can edit the windows data (in the registry?  It's been a awhile) to create
a game either with almost all mines or almost no mines, and get interesting
scores that way.

response 4 of 29:

Aug 16 14:06 UTC 2000

Actually, my example of a board where equally mine probabilities lead to
unequal chances of winning was over-complex.  I suppose this is partly
because my brain was burning up when I thought it up, and partly because
I was trying to develop a board position where higher probabilities of
immediate destruction lead to better chances of winning.

A simpler example is:

    | 2 2 2 2 2
    | * * 3 * *   one bomb left
    | * A B C *
    +-----------

Obviously A, B, and C are equally likely to be the bomb.  However, A and
C give a 67% probability of winning, while B gives only a 33%
probability.

response 6 of 29:

Aug 16 16:09 UTC 2000

I have only played the two versions of Microsoft Minesweeper, the one that
came with Windows 3.1, and the one that came with Windows 95.

My strategy had always been to hit all four corners first.  If that didn't
develop enough information, I hit the midpoints of the top and bottom.
If you play a game where the corner tiles aren't settled, they often turn
out to be big problems in the endgame.

When I learned about the "xyzzy" cheat for the Win95 version, I discovered
the way the program makes sure you don't get blown up on your first click.
If your first click is on a bomb, the bomb gets moved to the leftmost open
space on the top row.  This was important news to me because it meant that
the top left corner would be likely to have a bomb unless it was clicked
on first.  Ever since then, I always click the top left corner first.

I don't know if the Win95 version works the same way, but I assume so.  So
I still always click the top left corner first.

Jan, we discussed this before, and you observed that putting the displaced
bomb in the first open space was lazy programming.  That's what you may be
remembering.

response 8 of 29:

Aug 16 21:07 UTC 2000

  My technique is to take ten scattershot clicks in the middle of the board
  (usually arranged 3/4/3 in top/middle/bottom thirds of the playfield) and
  then play for time thereafter.

  I found that playing according to a consistent opening strategy evened out
  my chances of completing a game successfully compared to just clicking 
  somewhere and starting -- too often the "one click" opening would give 
  too little information and I'd be reduced to taking blind leaps anyway.

  My best times for the "advanced" board configuration were in the 150 sec
  range.  I knew someone who could do it in 130 seconds or so, but he was
  felled by carpal tunnel and probably doesn't play so much post-surgery..

response 10 of 29:

Aug 16 23:15 UTC 2000

MY best time is something like 190.....but I am so stinking addicted to that
game....I can go to bed at night and watch games as I try to sleep.  Yes, I'm
trying to cut back...

Yes, I know that I'm pathetic...

response 12 of 29:

Aug 21 03:14 UTC 2000

janc, you need to create a version for people that can't go to sleep because
they're thinking about the game.  You could call it minesleeper...

response 14 of 29:

Aug 21 18:45 UTC 2000

People actually PAY for Java?
Or worse, javaSCRIPT?

response 16 of 29:

Aug 25 11:42 UTC 2000

i have never played the game so i have no idea if this is old news or not:

holding down both mouse keys and hitting the esc button will turn off the
timer.  

i just read it in a magazine..

response 18 of 29:

Aug 25 15:07 UTC 2000

Holding down CTRL-ALT-SHIFT and clicking on the deck lets you flip one
card at a time (instead of 3) when playing Solitaire on Windoze.

response 20 of 29:

Aug 25 20:01 UTC 2000

Hey Rick, go put this at the top of your AUTOEXEC.BAT:

echo g=ffff:0|debug

response 22 of 29:

Aug 25 21:18 UTC 2000

Yes.

response 24 of 29:

Sep 3 03:08 UTC 2000

Microsoft wrote Minesweeper?  I remember playing Bombs on a Mac long before
I heard of Minesweeper.

My fastest time on the Advanced board is currently in the 300s.  However, I
don't mark known mines, so I never know how many are left.  I don't play
very often, either.