janc
|
|
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.
|
janc
|
|
response 3 of 29:
|
Aug 16 14:02 UTC 2000 |
Here's a disconnected minesweeper puzzle, for those of you more into
psychology than mathematics.
During my recent rounds of minesweeper playing, I was thinking about the
differences between Gnome Mines, Microsoft Minesweeper, and the version
I once wrote. The version I once wrote always started you in the upper
left hand corner and only allowed you to click on squares adjacent to
ones you had previously visited. The corner was never a mine, of
course. Like both of these versions, I used images for the numbers in
the squares, but I didn't need an "8" because that can't happen if you
only move adaject.
I also remember thinking that in my version I had solved the first click
problem not by generating the board after the first click, but by
swapping any mine found on the first click away to a random location.
However, this is inconsistant with my memory of always starting the game
in the corner.
What's really inconsistant, however, is that to the best of my
knowledge, I've never implemented a Minesweeper game, or any other
mouse-based game. So why is my head full of all sorts of little details
about how my version worked? Did I actually write one once and
completely forget about it? Did I write some very similar program or
modify a public source version? Or did I just think about writing my
own version enough that I generated various false memories of actually
doing so?
Personally, I think it's the first sign of senility. Oh well. Reagan
seemed happy enough during his presidential years.
|
janc
|
|
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.
|
polygon
|
|
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.
|
