5 ms·

Advanced Minesweeper

77 points by pcopley 14y ago

pavel_lishin 14y ago
Someone ought to write something to empirically test this assertion by clicking on the various possible locations.
- lojack 14y ago
  I'd be willing to bet that in the real world a corner is actually the worst choice. It may be the most likely to get blank spaces, but its probably also more likely to box you in, and only gives you one direction of attack.
lotharbot 14y ago
I would say the goal is not to have the highest probability of triggering a cascade, but rather, some combination of: - high probability of triggering a cascade - high probability of that cascade being "useful", that is, of being able to work outward from the cascade you opened. (Clicking on the empty corner and getting 1-3-1 on its borders means you still have to guess to escape the corner.) - high probability of not leaving difficult areas for the end. (Coin flips are most likely to occur in corners and edges; in the middle of the board, you usually have information from multiple directions. It's still possible to be forced to guess in the middle, but it happens far less often.) As a result, the strategy I've chosen on expert boards (based on experience, without particularly robust statistical backing) is to click the corners sequentially until I get one that allows me to open up more than a few squares. I occasionally lose a game on the second or third click this way, but I don't lose very many on late coin flips.
breadbox 14y ago
Speaking as someone who has spent WAY too much time playing minesweeper -- Early on I came to a similar conclusion (though without doing the actual math) and started clicking on corners initially. I soon discovered, as most people do, that corners are much more likely to expand out into a tiny opening that you can only follow for a short time before you're forced to make a "coin toss" move. If the goal is to make a _usable_ blob, clicking in the middle is best.
- pcopley 14y ago
  Do you think this is because the blob found in the middle is likely to have more perimeter squares than edge or corner selections?
  - eCa 14y ago
    A corner may be more likely to expand at least one square, but a middle click is more likely to have an immediately actionable open square. This is somewhat related though to the type of play one uses. I started out as a flagging user (the usual right-click to mark known mines), and then I always started in the lower right corner. Then (after a few years break) I started playing non-flagging (that is no right click allowed) and I find that a middle click is much more likely to give an "easy" opening. My usual opening consists of several middle clicks spread out until I get an opening (or failure). For every serious minesweeper I recommend the Minesweeper Clone: http://www.minesweeper.info/downloads/MinesweeperClone.html http://www.minesweeper.info/downloads/MinesweeperClone.html (On one sad night I got 79 seconds on expert..) Added: The cost (in seconds) of clicking corners until an opening is too high compared to the risk of getting a coin toss in a corner. Prudence isn't fast enough :)
- powrtoch 14y ago
  Speaking as the same sort of person (96 secs on expert :-) ), I agree that the most useful strategy is to click in the middle. This is because the cost of restarting is practically nothing for your first few clicks (no sunk time costs), so what you should really be optimizing is trying to get the most information about the board as soon as possible. All the more so because optimally your whole game will proceed logically from that first cascade. Bigger cascades are less likely to dead end, meaning you'll be less likely to have to guess at random again later (when you actually will have sunk time costs).
  - pessimizer 14y ago
    Wouldn't bigger cascades be more likely to deadend, due to the average density of what's leftover increasing?
slig 14y ago
There're some gems on DataGenetics' blog. Highly recommended.
- stanzyamith 14y ago
  Yes, especially: Benford's Law http://www.datagenetics.com/blog/march52012/index.html http://www.datagenetics.com/blog/march52012/index.html Hangman http://www.datagenetics.com/blog/april12012/index.html http://www.datagenetics.com/blog/april12012/index.html Yahtzee http://www.datagenetics.com/blog/january42012/index.html http://www.datagenetics.com/blog/january42012/index.html Risk http://www.datagenetics.com/blog/november22011/index.html http://www.datagenetics.com/blog/november22011/index.html Plus others ...
Zimahl 14y ago
Although I have no idea since I have never seen the code, I'm pretty sure there's no way to hit a bomb on your first click. I'm played enough (MS Windows) Minesweeper and have never, ever hit a bomb on the first click. As a side note, Minesweeper the first game I ever programmed was for my intro C class in college using SRGP[1] as the graphics library. Thinking back, it was a tough project. The Minesweeper logic wasn't so bad but doing the graphics was the most work. In hindsight, it shouldn't have taken more than a couple hours to code but took everyone a fair amount of time. Of course we didn't know what they hell we were doing. Fun stuff. EDIT: After searching around it appears there is code to prevent the first-click bomb in a rather novel way[2]. [1] http://www.niksula.cs.hut.fi/~tik86120/X_srgp.html http://www.niksula.cs.hut.fi/~tik86120/X_srgp.html [2] http://www.sanchitkarve.com/blog/2009/01/does-minesweeper-cheat/ http://www.sanchitkarve.com/blog/2009/01/does-minesweeper-ch...
- randomdrake 14y ago
  As far as I can recall, hitting a bomb on the first click is possible. But, if the source code proves my memory wrong, it certainly wouldn't be the first time.
  - archangel_one 14y ago
    I wonder if this is an enhancement in Vista Minesweeper? I'm almost certain that it used to be possible to land on a mine with your first click in older versions.
    - Aeons 14y ago
      Yes.
- thesteamboat 14y ago
  Microsoft uses a bad algorithm. The clever algorithm to prevent dying on the first click: Generate one extra mine during the random generation phase. After the first click, remove any mine the player clicks on, or, if they click on none, remove one randomly.
pessimizer 14y ago
Another priority with the first click is that you won't be entirely surrounded by mines and wires, wires being indeterminate, entangled chains of unrevealed spaces. I'm pretty sure a probability can be worked out for rate of occurrence and length of a wire - but with the corner strategy, you're minimizing the likely amount of perimeter by 3/4. That's got to make a "coin flip" situation more likely, which has to be weighed against the more likely reveal. If you don't get a reveal on the first click, you end up just clicking again a few times and restarting if you reveal a mine. Doesn't waste more than a second in any case. Not sure if that's really meaningful unless there's a no restart rule, or you're being graded by the percentage of games finished that are started.
- pessimizer 14y ago
  Realized people may not know what I'm talking about when I mention wires: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf Paper on minesweeper configurations being NP-complete. Wires in the paper are wires when approached from all directions, but I'm abusing the term a bit when I also include entangled squares around the perimeter of a minesweeper opening - which have only been approached from one direction. I think of minesweeper as a bunch of soap bubbles that are popped until you reach wires, which if they connect board boundary to board boundary, or connect to another wire that does that, or connect to themselves, end the skill game and create a probability game. Been meaning to play around with 2D areas that are surrounded by wire rings, but too lazy. The idea of randomness carved by rules creating stable shapes intrigues me. I play minesweeper too much. Expert: 78, 95 non-flagging, lawl.
webjprgm 14y ago
This seems totally wrong to me. Of course the probability of surrounding squares being all safe is higher in the corner simply because there are fewer surrounding squares! To make it more fair, calculate the probability that 3+ adjacent squares would be safe, since that's how many you get in the corner. Then the math shows that center is better because there are more neighboring squares that could be potentially blank. More useful would be the probability of having a cascade continue on past adjacent squares to squares adjacent to those, with the "winner" being whichever location is most likely to make the largest exposed bubble. My strategy is generally click a few places in the center quickly. If I die, I don't have much invested and just start over. If I find a large bubble, then I can play.
- milfot 14y ago
  Absolutely agree! ..and from my experience, three clicks is about optimum for speed and opening the board. All my sub 80s games have opened 'gashes' across the board, the three clicks gives you the best chance of jumping the 'wire' (as the other guy put it).. If you are going to have to play the odds at some point anyway, may as well do it at the start before you invest 50s of your life in some pointless activity.
mrgriscom 14y ago
I think it's nowhere near that simple. You don't just want to open up a cascade, but a _quality_ cascade that gives enough information to work with to identify which cells are mines, or, failing that, won't involve a risky guess. A '1' in the corner means each neighboring cell is a 1 in 3 risk, while a '1' in the middle is only 1 in 8. shameless plug: a minesweeper solver I wrote [http://mrgris.com/projects/minesweepr/demo/player/ http://mrgris.com/projects/minesweepr/demo/player/]
gojomo 14y ago
Would it be possible to make a 3D Minesweeper game inside Minecraft?
- jfoutz 14y ago
  depends on what you mean. you can build a monitor and computer in minecraft, you could specialize them to play minesweeper. I think you'd run into 300 block range problems (the world isn't simulated far away, you simply don't have enough room to wire up the redstone) Alternatively, mods can screw around with block ids. you could provide number textures for blocks and a few special blocks. All that's left is to swap block types as the user interacts with the blocks.
- Dove 14y ago
  Inside Minecraft proper, it would be prohibitively difficult. Redstone doesn't really support programming that complex (keeping 3D state, cleared areas, randomizing the board, etc.). With a couple new blocks, though -- a new game control, the mine blocks themselves -- it would be a moderately easy mod. Putting dynamic textures on the blocks to display numbers wouldn't be (in principle) any harder than some of the grass mods, and there's an onDestroy hook for the block you could use to clear space. I wonder how hard 3D minecraft would be. [Edit: Ha! It's been done! http://www.youtube.com/watch?v=eV6n0UWJM2Q http://www.youtube.com/watch?v=eV6n0UWJM2Q http://www.youtube.com/watch?v=DW71giahaLM http://www.youtube.com/watch?v=DW71giahaLM This is why we google things before building them.] [Edit edit: Oh, nuts. Those are both still 2D. This is why we review google results before deciding not to build something.]
  - Dove 14y ago
    I wonder how hard 3D minecraft would be. Er, wow. Hard. http://egraether.com/mine3d/ http://egraether.com/mine3d/
esalman 14y ago
My shortest time on the advanced mode of windows version is 62 seconds. I'm sure many of you'd beat that.

77 points by pcopley 14y ago

pavel_lishin 14y ago

Someone ought to write something to empirically test this assertion by clicking on the various possible locations.

lojack 14y ago
I'd be willing to bet that in the real world a corner is actually the worst choice. It may be the most likely to get blank spaces, but its probably also more likely to box you in, and only gives you one direction of attack.

lotharbot 14y ago

I would say the goal is not to have the highest probability of triggering a cascade, but rather, some combination of: - high probability of triggering a cascade - high probability of that cascade being "useful", that is, of being able to work outward from the cascade you opened. (Clicking on the empty corner and getting 1-3-1 on its borders means you still have to guess to escape the corner.) - high probability of not leaving difficult areas for the end. (Coin flips are most likely to occur in corners and edges; in the middle of the board, you usually have information from multiple directions. It's still possible to be forced to guess in the middle, but it happens far less often.) As a result, the strategy I've chosen on expert boards (based on experience, without particularly robust statistical backing) is to click the corners sequentially until I get one that allows me to open up more than a few squares. I occasionally lose a game on the second or third click this way, but I don't lose very many on late coin flips.

breadbox 14y ago

Speaking as someone who has spent WAY too much time playing minesweeper -- Early on I came to a similar conclusion (though without doing the actual math) and started clicking on corners initially. I soon discovered, as most people do, that corners are much more likely to expand out into a tiny opening that you can only follow for a short time before you're forced to make a "coin toss" move. If the goal is to make a _usable_ blob, clicking in the middle is best.

pcopley 14y ago
Do you think this is because the blob found in the middle is likely to have more perimeter squares than edge or corner selections?
- eCa 14y ago
  A corner may be more likely to expand at least one square, but a middle click is more likely to have an immediately actionable open square. This is somewhat related though to the type of play one uses. I started out as a flagging user (the usual right-click to mark known mines), and then I always started in the lower right corner. Then (after a few years break) I started playing non-flagging (that is no right click allowed) and I find that a middle click is much more likely to give an "easy" opening. My usual opening consists of several middle clicks spread out until I get an opening (or failure). For every serious minesweeper I recommend the Minesweeper Clone: http://www.minesweeper.info/downloads/MinesweeperClone.html http://www.minesweeper.info/downloads/MinesweeperClone.html (On one sad night I got 79 seconds on expert..) Added: The cost (in seconds) of clicking corners until an opening is too high compared to the risk of getting a coin toss in a corner. Prudence isn't fast enough :)
powrtoch 14y ago
Speaking as the same sort of person (96 secs on expert :-) ), I agree that the most useful strategy is to click in the middle. This is because the cost of restarting is practically nothing for your first few clicks (no sunk time costs), so what you should really be optimizing is trying to get the most information about the board as soon as possible. All the more so because optimally your whole game will proceed logically from that first cascade. Bigger cascades are less likely to dead end, meaning you'll be less likely to have to guess at random again later (when you actually will have sunk time costs).
- pessimizer 14y ago
  Wouldn't bigger cascades be more likely to deadend, due to the average density of what's leftover increasing?

slig 14y ago

There're some gems on DataGenetics' blog. Highly recommended.

stanzyamith 14y ago
Yes, especially: Benford's Law http://www.datagenetics.com/blog/march52012/index.html http://www.datagenetics.com/blog/march52012/index.html Hangman http://www.datagenetics.com/blog/april12012/index.html http://www.datagenetics.com/blog/april12012/index.html Yahtzee http://www.datagenetics.com/blog/january42012/index.html http://www.datagenetics.com/blog/january42012/index.html Risk http://www.datagenetics.com/blog/november22011/index.html http://www.datagenetics.com/blog/november22011/index.html Plus others ...

Zimahl 14y ago

Although I have no idea since I have never seen the code, I'm pretty sure there's no way to hit a bomb on your first click. I'm played enough (MS Windows) Minesweeper and have never, ever hit a bomb on the first click. As a side note, Minesweeper the first game I ever programmed was for my intro C class in college using SRGP[1] as the graphics library. Thinking back, it was a tough project. The Minesweeper logic wasn't so bad but doing the graphics was the most work. In hindsight, it shouldn't have taken more than a couple hours to code but took everyone a fair amount of time. Of course we didn't know what they hell we were doing. Fun stuff. EDIT: After searching around it appears there is code to prevent the first-click bomb in a rather novel way[2]. [1] http://www.niksula.cs.hut.fi/~tik86120/X_srgp.html http://www.niksula.cs.hut.fi/~tik86120/X_srgp.html [2] http://www.sanchitkarve.com/blog/2009/01/does-minesweeper-cheat/ http://www.sanchitkarve.com/blog/2009/01/does-minesweeper-ch...

randomdrake 14y ago
As far as I can recall, hitting a bomb on the first click is possible. But, if the source code proves my memory wrong, it certainly wouldn't be the first time.
- archangel_one 14y ago
  I wonder if this is an enhancement in Vista Minesweeper? I'm almost certain that it used to be possible to land on a mine with your first click in older versions.
  - Aeons 14y ago
    Yes.
thesteamboat 14y ago
Microsoft uses a bad algorithm. The clever algorithm to prevent dying on the first click: Generate one extra mine during the random generation phase. After the first click, remove any mine the player clicks on, or, if they click on none, remove one randomly.

pessimizer 14y ago

Another priority with the first click is that you won't be entirely surrounded by mines and wires, wires being indeterminate, entangled chains of unrevealed spaces. I'm pretty sure a probability can be worked out for rate of occurrence and length of a wire - but with the corner strategy, you're minimizing the likely amount of perimeter by 3/4. That's got to make a "coin flip" situation more likely, which has to be weighed against the more likely reveal. If you don't get a reveal on the first click, you end up just clicking again a few times and restarting if you reveal a mine. Doesn't waste more than a second in any case. Not sure if that's really meaningful unless there's a no restart rule, or you're being graded by the percentage of games finished that are started.

pessimizer 14y ago
Realized people may not know what I'm talking about when I mention wires: http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.pdf Paper on minesweeper configurations being NP-complete. Wires in the paper are wires when approached from all directions, but I'm abusing the term a bit when I also include entangled squares around the perimeter of a minesweeper opening - which have only been approached from one direction. I think of minesweeper as a bunch of soap bubbles that are popped until you reach wires, which if they connect board boundary to board boundary, or connect to another wire that does that, or connect to themselves, end the skill game and create a probability game. Been meaning to play around with 2D areas that are surrounded by wire rings, but too lazy. The idea of randomness carved by rules creating stable shapes intrigues me. I play minesweeper too much. Expert: 78, 95 non-flagging, lawl.

webjprgm 14y ago

This seems totally wrong to me. Of course the probability of surrounding squares being all safe is higher in the corner simply because there are fewer surrounding squares! To make it more fair, calculate the probability that 3+ adjacent squares would be safe, since that's how many you get in the corner. Then the math shows that center is better because there are more neighboring squares that could be potentially blank. More useful would be the probability of having a cascade continue on past adjacent squares to squares adjacent to those, with the "winner" being whichever location is most likely to make the largest exposed bubble. My strategy is generally click a few places in the center quickly. If I die, I don't have much invested and just start over. If I find a large bubble, then I can play.

milfot 14y ago
Absolutely agree! ..and from my experience, three clicks is about optimum for speed and opening the board. All my sub 80s games have opened 'gashes' across the board, the three clicks gives you the best chance of jumping the 'wire' (as the other guy put it).. If you are going to have to play the odds at some point anyway, may as well do it at the start before you invest 50s of your life in some pointless activity.

mrgriscom 14y ago

I think it's nowhere near that simple. You don't just want to open up a cascade, but a _quality_ cascade that gives enough information to work with to identify which cells are mines, or, failing that, won't involve a risky guess. A '1' in the corner means each neighboring cell is a 1 in 3 risk, while a '1' in the middle is only 1 in 8. shameless plug: a minesweeper solver I wrote [http://mrgris.com/projects/minesweepr/demo/player/ http://mrgris.com/projects/minesweepr/demo/player/]

gojomo 14y ago

Would it be possible to make a 3D Minesweeper game inside Minecraft?

jfoutz 14y ago
depends on what you mean. you can build a monitor and computer in minecraft, you could specialize them to play minesweeper. I think you'd run into 300 block range problems (the world isn't simulated far away, you simply don't have enough room to wire up the redstone) Alternatively, mods can screw around with block ids. you could provide number textures for blocks and a few special blocks. All that's left is to swap block types as the user interacts with the blocks.
Dove 14y ago
Inside Minecraft proper, it would be prohibitively difficult. Redstone doesn't really support programming that complex (keeping 3D state, cleared areas, randomizing the board, etc.). With a couple new blocks, though -- a new game control, the mine blocks themselves -- it would be a moderately easy mod. Putting dynamic textures on the blocks to display numbers wouldn't be (in principle) any harder than some of the grass mods, and there's an onDestroy hook for the block you could use to clear space. I wonder how hard 3D minecraft would be. [Edit: Ha! It's been done! http://www.youtube.com/watch?v=eV6n0UWJM2Q http://www.youtube.com/watch?v=eV6n0UWJM2Q http://www.youtube.com/watch?v=DW71giahaLM http://www.youtube.com/watch?v=DW71giahaLM This is why we google things before building them.] [Edit edit: Oh, nuts. Those are both still 2D. This is why we review google results before deciding not to build something.]
- Dove 14y ago
  I wonder how hard 3D minecraft would be. Er, wow. Hard. http://egraether.com/mine3d/ http://egraether.com/mine3d/

esalman 14y ago

My shortest time on the advanced mode of windows version is 62 seconds. I'm sure many of you'd beat that.