Reply
 
Thread Tools Display Modes
  #1  
Old 01-24-2005, 10:41 AM
Schnitte Schnitte is offline
Intermittently active
 
Join Date: Feb 2001
Location: Frankfurt, Germany
Posts: 3,422
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?
Advertisements  
  #2  
Old 01-24-2005, 10:45 AM
GorillaMan GorillaMan is offline
Guest
 
Join Date: Oct 2003
Location: Portman Road
Posts: 17,369
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.
  #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: 57,142
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.
  #4  
Old 01-24-2005, 10:48 AM
BrotherCadfael BrotherCadfael is offline
Guest
 
Join Date: Feb 2003
Location: Vermont
Posts: 9,848
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.
  #5  
Old 01-24-2005, 10:53 AM
InvidiousCourgette InvidiousCourgette is offline
Guest
 
Join Date: May 2004
Posts: 770
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.
  #6  
Old 01-24-2005, 11:11 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
IME, it's very rare for luck to be a significant factor on the intermediate level, let alone the beginner.
  #7  
Old 01-24-2005, 11:31 AM
DarrenS DarrenS is offline
Guest
 
Join Date: Mar 2000
Location: San Francisco, CA
Posts: 2,204
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?
  #8  
Old 01-24-2005, 11:35 AM
BobLibDem BobLibDem is online now
Guest
 
Join Date: Jul 2003
Location: Home 07 NCAA HockeyChamps
Posts: 18,966
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.
  #9  
Old 01-24-2005, 11:36 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
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.
  #10  
Old 01-24-2005, 11:46 AM
yabob yabob is offline
Charter Member
 
Join Date: Mar 2000
Posts: 7,749
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.
  #11  
Old 01-24-2005, 11:50 AM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Location: Durham, NC, USA
Posts: 3,199
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.
  #12  
Old 01-24-2005, 11:54 AM
yabob yabob is offline
Charter Member
 
Join Date: Mar 2000
Posts: 7,749
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.
  #13  
Old 01-24-2005, 11:56 AM
Squink Squink is offline
Guest
 
Join Date: Oct 2000
Location: Yes
Posts: 20,327
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.
  #14  
Old 01-24-2005, 11:59 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
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.
  #15  
Old 01-24-2005, 12:05 PM
Flander Flander is offline
Member
 
Join Date: Jul 2003
Location: Orlando!
Posts: 2,928
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?!?
  #16  
Old 01-24-2005, 12:05 PM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Location: Durham, NC, USA
Posts: 3,199
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.
  #17  
Old 01-24-2005, 12:07 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
Quote:
Originally Posted by Flander
You're kidding right?!?
No.
  #18  
Old 01-24-2005, 12:11 PM
Flander Flander is offline
Member
 
Join Date: Jul 2003
Location: Orlando!
Posts: 2,928
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?
  #19  
Old 01-24-2005, 12:16 PM
CandidGamera CandidGamera is offline
Guest
 
Join Date: Feb 2004
Location: Morgantown, WV
Posts: 10,803
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.
  #20  
Old 01-24-2005, 12:58 PM
Chronos Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 71,597
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).
  #21  
Old 01-24-2005, 03:56 PM
Apos Apos is offline
Guest
 
Join Date: May 2002
Location: Monkey
Posts: 9,652
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.
  #22  
Old 01-24-2005, 04:08 PM
chaoticbear chaoticbear is offline
Guest
 
Join Date: Jun 2003
Posts: 5,724
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?
  #23  
Old 01-24-2005, 04:19 PM
CurtC CurtC is offline
Guest
 
Join Date: Dec 1999
Location: Texas
Posts: 6,253
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.
  #24  
Old 01-24-2005, 05:07 PM
BlackNGold BlackNGold is offline
Guest
 
Join Date: Aug 2003
Location: Pittsburgh, PA
Posts: 225
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.
  #25  
Old 01-24-2005, 06:02 PM
Ephemera Ephemera is offline
Guest
 
Join Date: Dec 2002
Location: Chattanooga
Posts: 14,037
I always clear out the four corners as my first four moves and work from there.
  #26  
Old 01-25-2005, 04:19 AM
Popup Popup is offline
Guest
 
Join Date: Jan 2001
Location: Central Europe
Posts: 964
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.
  #27  
Old 01-25-2005, 05:16 AM
Paladud Paladud is offline
Guest
 
Join Date: Dec 2003
Location: Los Angeles, CA
Posts: 780
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
  #28  
Old 01-25-2005, 03:09 PM
Chronos Chronos is offline
Charter Member
Moderator
 
Join Date: Jan 2000
Location: The Land of Cleves
Posts: 71,597
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.
  #29  
Old 01-25-2005, 04:48 PM
borschevsky borschevsky is offline
Guest
 
Join Date: Sep 2001
Location: Canada
Posts: 1,832
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.
  #30  
Old 01-26-2005, 12:50 AM
GilaB GilaB is offline
Guest
 
Join Date: Mar 2001
Location: New York, New York!
Posts: 2,461
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.
  #31  
Old 01-26-2005, 05:27 AM
Schnitte Schnitte is offline
Intermittently active
 
Join Date: Feb 2001
Location: Frankfurt, Germany
Posts: 3,422
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
  #32  
Old 01-26-2005, 06:17 AM
scotandrsn scotandrsn is offline
Guest
 
Join Date: Mar 2000
Location: Greater La La County
Posts: 4,218
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.

  #33  
Old 01-26-2005, 10:40 AM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
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.
  #34  
Old 01-26-2005, 12:00 PM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Location: Durham, NC, USA
Posts: 3,199
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.
  #35  
Old 01-26-2005, 12:07 PM
ultrafilter ultrafilter is offline
Guest
 
Join Date: May 2001
Location: In another castle
Posts: 18,988
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.
  #36  
Old 01-27-2005, 01:29 PM
Dead Cat Dead Cat is offline
Guest
 
Join Date: Feb 2005
Location: UK
Posts: 3,152
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
  #37  
Old 01-27-2005, 08:40 PM
GilaB GilaB is offline
Guest
 
Join Date: Mar 2001
Location: New York, New York!
Posts: 2,461
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.
  #38  
Old 01-30-2005, 05:53 AM
RM Mentock RM Mentock is offline
Guest
 
Join Date: Mar 1999
Location: Durham, NC, USA
Posts: 3,199
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

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 07:43 AM.

Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, 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 2017 Sun-Times Media, LLC.

 
Copyright © 2017