The Straight Dope

Go Back   Straight Dope Message Board > Main > General Questions

Reply
 
Thread Tools Display Modes
  #1  
Old 01-24-2005, 10:41 AM
Schnitte Schnitte is offline
Guest
 
Join Date: Feb 2001
Minesweeper - is luck involved or not?

Some days ago, I started playing the classic gimmick Minesweeper included in Windows. After some success on the Beginner and Intermediate levels, I decided to change to the Expert level, where I'm constantly failing. My impression is that there are situations where pure luck is involved, i.e. it's not possible to detect a square I know, for logical reasoning, to be "safe." Of course it's constantly so at the beginning of each game, when you simply click around on the board trying to find clues for continuing; but those situations where you can have good or bad luck because you just don't know for sure how to go on seem to appear on the Expert level even towards the end of the game, unlike in the two easier levels. Is that just my impression based on frustration after losing a dozen games in a row, or does luck actually play a role so much more important on the Expert level?
Reply With Quote
Advertisements  
  #2  
Old 01-24-2005, 10:45 AM
GorillaMan GorillaMan is offline
Guest
 
Join Date: Oct 2003
Yes, luck certainly comes into it. Quite often, you'll end up with two 'cornered' squares, and it's not possible to determine which has a mine.
Reply With Quote
  #3  
Old 01-24-2005, 10:47 AM
Johnny L.A. Johnny L.A. is offline
Charter Member
 
Join Date: Jan 2000
Location: NoWA
Posts: 48,119
Quote:
Originally Posted by Schnitte
Is that just my impression based on frustration after losing a dozen games in a row, or does luck actually play a role so much more important on the Expert level?
In my experience, the end-game is luck. I have never hit a mine on the first square I chose, so I think that the first one is 'free'. The second square is luck, since all you know is that there is a mine (or are mines) adjacent to the square. Depending on your first move and the number it shows, the subsequent choices may not involve luck. However, I usually come to a point where the remaining squares have a 50/50 chance of holding a mine and there is no logical way to determine which are safe. That's what I don't like about Minesweeper. At the end, it comes down to luck.
Reply With Quote
  #4  
Old 01-24-2005, 10:48 AM
BrotherCadfael BrotherCadfael is offline
Guest
 
Join Date: Feb 2003
As your field of possible moves decreases, you eventually get into a position where you can algorithmically determine that there are two possible layouts for the remaining mines. You have no way to determine which is correct, so you pick one at random. 50% of the time you will be right, and play continues.

You then reach a second such situation, and again you choose randomly. 50% of the times that you reach this point (ie: only 25% of all games) you will choose correctly.

If you get a third such random situation, your chance of winning the game is thus only one in eight, if you reach a fourth, then one in sixteen, etc.

So, yeah, luck plays a part.
Reply With Quote
  #5  
Old 01-24-2005, 10:53 AM
InvidiousCourgette InvidiousCourgette is offline
Guest
 
Join Date: May 2004
Luck is more important in the Expert level because there is a higher mine density.

Beginner: 1 mine every 8.1 cells
Intermediate: 1 mine every 6.4 cells
Expert: 1 mine every 4.8 cells

With a higher mine density you are more likely to encounter a situation where logic can't help and you need to rely on luck.
Reply With Quote
  #6  
Old 01-24-2005, 11:11 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
IME, it's very rare for luck to be a significant factor on the intermediate level, let alone the beginner.
Reply With Quote
  #7  
Old 01-24-2005, 11:31 AM
DarrenS DarrenS is offline
Guest
 
Join Date: Mar 2000
Well, the first square you click is always pure luck, but I don't think that's what you were asking.

I was also interested to note that Minesweeper has been proved NP-complete - http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm - does this have any bearing on the question?
Reply With Quote
  #8  
Old 01-24-2005, 11:35 AM
BobLibDem BobLibDem is offline
Guest
 
Join Date: Jul 2003
The expert level usually has a great deal of luck. I have gotten lucky and with the first pick opened up vast tracts of squares and could deduce every mine. It's the first few picks that make a quick loss or a playable game. If the first square is "1", I'll pick an adjoining square for pick 2 since you have a 7/8 chance of being right. If the first pick is "3" or worse, I'll take the second one far away and take an unknown chance. But many times there will be situations where you simply cannot deduce.

I generally get no such situations in intermediate.
Reply With Quote
  #9  
Old 01-24-2005, 11:36 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by DarrenS
Well, the first square you click is always pure luck, but I don't think that's what you were asking.
I've been playing Minesweeper regularly for six years now, and I've never clicked on a mine the first time. I don't think it's possible.

Quote:
I was also interested to note that Minesweeper has been proved NP-complete - http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm - does this have any bearing on the question?
Hmm....All NP-complete problems are decidable, so that may factor in here. However, that would only mean that you can play it so you don't need luck, not that you can't play it so that you don't need luck.
Reply With Quote
  #10  
Old 01-24-2005, 11:46 AM
yabob yabob is offline
Charter Member
 
Join Date: Mar 2000
Posts: 7,215
Mind you, the first time or casual player often doesn't recognize some of the more involved logic - the sort of situation where "there's 4 next to this square, 1 is marked, therefore there are two in the remaining three squares, 2 of which also happen to be next to something with 1 mine. One of those two has to be a mine because of the 2 out of 3, therefore I can eliminate all the other neighbors of the 1 square." That said, yeah, with sufficient mine density, you are likely to come down to a point where no amount of logical inference allows you to click something with certainty.
Reply With Quote
  #11  
Old 01-24-2005, 11:50 AM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Quote:
Originally Posted by ultrafilter
I've been playing Minesweeper regularly for six years now, and I've never clicked on a mine the first time. I don't think it's possible.
Just go to a Custom configuration--I think for an n x n grid, the maximum allowed number of mines is (n-1)^2, but for a 16x16 grid, that's 225 mines. Then click. You'll see that the mine configuration is set after the first click.
Reply With Quote
  #12  
Old 01-24-2005, 11:54 AM
yabob yabob is offline
Charter Member
 
Join Date: Mar 2000
Posts: 7,215
Excuse me, I meant to say "3 MINES next to this square", not 4. I was picturing a case where there were 4 squares next to something with three mines, 1 known mine, and two of those three remaining bordering another square known to have 1. It's easier to SEE these cases than describe them in English.
Reply With Quote
  #13  
Old 01-24-2005, 11:56 AM
Squink Squink is offline
Guest
 
Join Date: Oct 2000
Quote:
Originally Posted by RM Mentock
You'll see that the mine configuration is set after the first click.
That probably varies with the particular implementation of the game.
Reply With Quote
  #14  
Old 01-24-2005, 11:59 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by DarrenS
I was also interested to note that Minesweeper has been proved NP-complete - http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm - does this have any bearing on the question?
OK, I checked around. What was actually proven NP-complete is the Minesweeper consistency problem, which takes as input a given set of squares--hidden, clear, or numbered--and decides whether there's a mine configuration that's consistent with that layout. It does not tell you where the mines are, so despite Dr. Kaye's assertions to the contrary, it's not exactly equivalent to playing Minesweeper.
Reply With Quote
  #15  
Old 01-24-2005, 12:05 PM
Flander Flander is offline
Member
 
Join Date: Jul 2003
Location: Jensen Beach, FL
Posts: 2,840
Quote:
Originally Posted by ultrafilter
I've been playing Minesweeper regularly for six years now, and I've never clicked on a mine the first time. I don't think it's possible.
You're kidding right?!?
Reply With Quote
  #16  
Old 01-24-2005, 12:05 PM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Quote:
Originally Posted by Squink
That probably varies with the particular implementation of the game.
O sure, I was talking about the Minesweeper that came with my Windows. The one on my linux machine changes the configuration after every click to make sure that you always end up with a non-determinable situation. And then it always makes you lose. Frustrating.
Reply With Quote
  #17  
Old 01-24-2005, 12:07 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by Flander
You're kidding right?!?
No.
Reply With Quote
  #18  
Old 01-24-2005, 12:11 PM
Flander Flander is offline
Member
 
Join Date: Jul 2003
Location: Jensen Beach, FL
Posts: 2,840
HHmmm....after experimenting, it seems you're correct, although I could have sworn I remembered clicking a mine on the first time. Oh well. I guess that makes sense. I mean, would you want to play a game that declares you the loser on your first move?
Reply With Quote
  #19  
Old 01-24-2005, 12:16 PM
CandidGamera CandidGamera is offline
Guest
 
Join Date: Feb 2004
In my extensive Minesweeper experience, the only time I've seen a first-click mine is the time I tried out the 'Minesweeper Cheat Code' - the code basically toggles a single pixel's color when your cursor is over a mine, so the game has to generate the layout before you click for the first time.
__________________
-Official Doper Brat #007- When life gives you harlequins, make a harlequinade.
I am the very model of the modern kaiju Gamera / I've a shell that's indestructible and endless turtle stamina. / I defend the little kids/ and I level downtown Tokyo/ in a giant free-for-all mega-kaiju rodeo.
Reply With Quote
  #20  
Old 01-24-2005, 12:58 PM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 53,977
Quote:
HHmmm....after experimenting, it seems you're correct, although I could have sworn I remembered clicking a mine on the first time. Oh well. I guess that makes sense. I mean, would you want to play a game that declares you the loser on your first move?
In the card game "Cruel", also distributed with some Windows versions (though not nearly as ubitquitous as Minesweeper), it's possible for the initial deal to be completely unplayable. As in, you'll hit "New Game", and it'll immediately tell you "Game over, 48 cards remaining".

A couple of examples, by the way, for a pure-luck situation:

First of all, in a corner:
Code:
??1
??2
12F
(? is an undetermined square, the numbers mean the same thing as in the game, and the F is a flagged mine)
Assuming that I have two mines left to be found, they could be the upper-left and the lower-right, or the upper-right and the lower-left of the question marks. However, if I have only one mine unaccounted for, or three (and this is the only unknown part of the board), then this is solvable: If there's only one mine left, then the lower-right one is the mine, and if there's three left, then the lower-right one is safe. Of course, this can happen in any corner.

Another common one is on an edge:
Code:


                    FFF
                    3?3
                    1?1
Here, I have no way of knowing, regardless of how many mines are left.

And occasionally, you'll even get a more complicated one, like so:
Code:


                    FFF
                    3?3
                    1?1
                    1 1
                    1?1
                    1?1
                    1 1
                    1?1
                    1?1
Here, I know that one of each pair of question marks is a mine, but I don't know if it's the three top ones or the three bottom ones. Once I make my guess, though, I'll be able to get all of them (or, of course, I'll die).
Reply With Quote
  #21  
Old 01-24-2005, 03:56 PM
Apos Apos is offline
Guest
 
Join Date: May 2002
A related question here is whether and when the mine placement is fully determined. I think it is definately true that the mine placement is NOT determined until AFTER you click the first space. However, I'm not entirely convinced that it's then fully determined at that point either. I could swear, but the program seems to punish uninformed guesses at a more than random rate, even when the patterns don't seem to _mandate_ that there must be a mine at a cetain location.
Reply With Quote
  #22  
Old 01-24-2005, 04:08 PM
chaoticbear chaoticbear is offline
Guest
 
Join Date: Jun 2003
Do you guys start in corners or in the middle? I always start in the corner because I feel like there's a greater chance of getting many squares to go away, and it's easier when I see a 1 diagonal from a block to say "Hey, that's a mine!" Is there any mathematical proof that either is better?
Reply With Quote
  #23  
Old 01-24-2005, 04:19 PM
CurtC CurtC is offline
Guest
 
Join Date: Dec 1999
I saw once on the SDMB that a couple of posters had beaten the expert level in under 100 seconds! I thought that I was quite the expert player, with my best at 139 seconds. I can't imagine getting it down to less than 100.
Reply With Quote
  #24  
Old 01-24-2005, 05:07 PM
BlackNGold BlackNGold is offline
Guest
 
Join Date: Aug 2003
Quote:
Originally Posted by chaoticdonkey
Do you guys start in corners or in the middle?
I always start in the corner. Not because I get a better "clear", but because the corners can be such a biznatch sometimes. I figure three corners are better than four.
Reply With Quote
  #25  
Old 01-24-2005, 06:02 PM
Ephemera Ephemera is offline
Guest
 
Join Date: Dec 2002
I always clear out the four corners as my first four moves and work from there.
Reply With Quote
  #26  
Old 01-25-2005, 04:19 AM
Popup Popup is offline
Guest
 
Join Date: Jan 2001
Quote:
Originally Posted by CurtC
I saw once on the SDMB that a couple of posters had beaten the expert level in under 100 seconds! I thought that I was quite the expert player, with my best at 139 seconds. I can't imagine getting it down to less than 100.
Back in my university days I used to spend an inordinate time in front of a win3.1 machine running minesweeper. After a lot of practice I managed indeed to do it in under 100 seconds. (I believe that my record was 96 seconds.) It involved clicking all four corners and somewhere in the middle within the first couple of seconds. Which of course often led to a very early explosion, but once in a while it opened up quite a lot of the playing field.
Then it's all pattern matching and luck.
Reply With Quote
  #27  
Old 01-25-2005, 05:16 AM
Paladud Paladud is offline
Guest
 
Join Date: Dec 2003
If you aren't concerned with losing, corners are a good bet.

For the smallest possibility of losing initially (and my logic may well be faulty) it is better to start toward the center.First off, if you get a 1, it's 1 mine out of eight squares, rather than out of three (corner) or five (side).

Second, it's best to make the next guess in a diagonally adjacent square. It is actually irrelevant on the first pick, but if the square reveals 2 or greater, then you know that your next pick is less likely to be a shared mine

For example with

?3?
?1?
???

you would logically rule out the four squares that are adjacent to the 1 and the 3 for the next pick, since there's a good chance that the 1 and 3 'share' a mine. This narrows your choices down to the three at the bottom (of which you can 'safely' pick both bottom corners or just the bottom center), and makes you that much more likely to have to pick another square at random elsewhere on the board.


Whereas with

??3
?1?
???

you can pick the other three corners as necessary.

Once a chunk of the board is revealed, it's playable. Otherwise, I go diagonally from the 1s, avoiding squares that are also adjacent to revealed 2s or higher (since Expert has a 1/4.84848... chance of a mine in any given square, it is better to guess at random elsewhere rather than click an uncertain square adjacent to a 2).

Beyond that.. I usually lose. Yes, the random factor bites at times. The way I figure, though, it's more fun to survive farther into the game
Reply With Quote
  #28  
Old 01-25-2005, 03:09 PM
Chronos Chronos is offline
Charter Member
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 53,977
If you happen to get a 1 in the middle, that's better than a 1 in the corner, but the flip side to that is that you're much less likely to get a 1 in the middle. And a 0 is very helpful no matter where it is, and that's significantly more likely in a corner. I always start in one corner and work from there, and my best time for Expert is 80-something (though I'd probably have to get a new mouse before I could replicate that). If I get a 0 on my first move, I'll clear some area, and probably be able to make an actual deduction on my next move. If I get a 1, then any of the three adjacent spots has a 2/3 chance of safety, slightly better than a random spot on the board, so I go in one of them (typically also on the edge). If it's a 2 or 3, then I skip over one, and pick the next one on the edge, so I have some shared squares and therefore at least some information about the arrangement.
Reply With Quote
  #29  
Old 01-25-2005, 04:48 PM
borschevsky borschevsky is offline
Guest
 
Join Date: Sep 2001
My best expert time is 81 seconds, and if I'm trying for a record time I'll start by randomly clicking until I've opened up one or two good-sized blank areas. This causes lots of quick losses but allows for fast games when it works.

And as Chronos mentioned, having a good mouse and being able to click quickly makes a difference. There are lots of patterns that you can recognize faster than you can click.
Reply With Quote
  #30  
Old 01-26-2005, 12:50 AM
GilaB GilaB is offline
Charter Member
 
Join Date: Mar 2001
Location: New York, New York!
Posts: 2,456
For us computer-ignorant types, what is NP-complete?

Apos, I don't think it punishes random guessing. I don't think it's an advanced enough program, for one thing; you just remember the bad outcomes more than the good ones.

FWIW, just to brag, my best time on the expert is 78 seconds, which I've managed to repeatedly replicate but haven't broken since I set it 3-4 years ago. It's a question of a good mouse, knowledge of the patterns involved, and years and years of time wastage.
Reply With Quote
  #31  
Old 01-26-2005, 05:27 AM
Schnitte Schnitte is offline
Guest
 
Join Date: Feb 2001
Thanks to all of you, guys. Yesterday I managed my fisrt expert game in the astonishing time of 719 seconds.
Think I have to practice a bit
Reply With Quote
  #32  
Old 01-26-2005, 06:17 AM
scotandrsn scotandrsn is offline
Guest
 
Join Date: Mar 2000
I never even continue a game unless I can open a blank field of sqaures in the first few clicks.

Oh, and the fast times probably come from the feature where, once you have placed the indicated number of flags around a numbered cell, you click both mouse buttons simultaneously on the number, and the remaining cells all open up (even the ones containig the mines you erroneously thought were in another square. I had been playing for a shamefully long time before someone pointed it out to me, but it's right there in the Strategies and Tips in the Help file.

Reply With Quote
  #33  
Old 01-26-2005, 10:40 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by GilaB
For us computer-ignorant types, what is NP-complete?
Basically, the set of NP-complete problems are the hardest problems to solve out of the set of problems that allow quick verification of an answer.
Reply With Quote
  #34  
Old 01-26-2005, 12:00 PM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Quote:
Originally Posted by scotandrsn
(even the ones containig the mines you erroneously thought were in another square.
which of course ends the game, if that happens

If you overassign--set two flags next to a one, and double-click, for instance--nothing will happen, even if there are adjacent nonflagged squares.
Quote:
Originally Posted by ultrafilter
Basically, the set of NP-complete problems are the hardest problems to solve out of the set of problems that allow quick verification of an answer.
Depends upon what you mean by "hard"

An NP complete problem may be easy to solve--straightforward, even--but what is hard is finding a way to do it quickly.
Reply With Quote
  #35  
Old 01-26-2005, 12:07 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Quote:
Originally Posted by RM Mentock
Depends upon what you mean by "hard"
In this case, problem A is harder than problem B iff there exists a polynomial-time reduction from an instance of B to an instance of A. That's what I mean by "hard" here.
Reply With Quote
  #36  
Old 01-27-2005, 01:29 PM
Dead Cat Dead Cat is offline
Guest
 
Join Date: Feb 2005
Quote:
Originally Posted by Schnitte
Thanks to all of you, guys. Yesterday I managed my fisrt expert game in the astonishing time of 719 seconds.
Think I have to practice a bit
The World Record for Expert Minesweeper currently stands at an astonishing 41 seconds (according to this site: http://metanoodle.com/minesweeper/ ).

All I can say is: unbelievable!

Not the 41 seconds, the amount of time and effort you'd have to invest to approach this mark. For those who want to, this site offers tips: http://www.frankwester.net/winmine.html
Reply With Quote
  #37  
Old 01-27-2005, 08:40 PM
GilaB GilaB is offline
Charter Member
 
Join Date: Mar 2001
Location: New York, New York!
Posts: 2,456
The guy with a 41-second best time on the expert also has a best time of 1 second on the beginner level, as do a bunch of other ranked people. That has to be luck, as you don't have time for more than a couple of clicks in a second.
Reply With Quote
  #38  
Old 01-30-2005, 05:53 AM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
BTW, Minesweeper (and P vs NP) featured prominently in the plot of the second episode of Numb3rs. I don't think it's going to save it though.
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump


All times are GMT -5. The time now is 05:41 AM.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2014, vBulletin Solutions, Inc.

Send questions for Cecil Adams to: cecil@chicagoreader.com

Send comments about this website to: webmaster@straightdope.com

Terms of Use / Privacy Policy

Advertise on the Straight Dope!
(Your direct line to thousands of the smartest, hippest people on the planet, plus a few total dipsticks.)

Publishers - interested in subscribing to the Straight Dope?
Write to: sdsubscriptions@chicagoreader.com.

Copyright 2013 Sun-Times Media, LLC.