Advanced Minesweeper | Hacker News Reader

Advanced Minesweeper

datagenetics.com

77 pointspcopley29 comments

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.

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.

Do you think this is because the blob found in the middle is likely to have more perimeter squares than edge or corner selections?

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

(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 :)

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).

Wouldn't bigger cascades be more likely to deadend, due to the average density of what's leftover increasing?

My fault for being ambiguous about the word "bigger", thanks for pointing this out. It's true that you're not looking for a large area per se. What you want is a large perimeter. The best starting click would be a whole lot of thin tentacles stretching out across the board, not a giant square-ish clump.

That is, you're trying to maximize information. A large rectangular area doesn't give you nearly as much information about the board as a tentacle-y one, because most of the squares don't tell you anything but their own value.

This is a definite problem on expert. I had a few female friends in college who were insanely good at Minesweeper, able to clear expert more often than not and insanely fast (under 100 seconds). When I was trying to get better and would get excited to get a big cascade, they'd just chuckle knowing that it was just going to make my chances that much more slim.

I'd say it really depends on what you're optimizing for.

When I'm going for a high score, I want the fastest time (and lost games don't count for anything). So I guess a lot, especially in the first few seconds, looking for good spreads and free information.

When I'm in the mood for a logic puzzle, I go for the best completion rate (percentage of games won). Then I click a single corner and work with whatever I get, guessing again only if my remaining options are guesses anyway. (The corner eliminates at least one bad endgame).

When I just want a fun experience, I go for most games completed in a session. In that case, I click all four corners to start to eliminate bad endgames. Those aren't a fun experience.

Yeah. On 'advanced' I got to the point where I'd click all four corners (and if that didn't work I'd try again) because it massively reduced the chances of coming to a '50/50 guess', which was the biggest difficulty of the game and most often happened near the corners...

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 [2] http://www.sanchitkarve.com/blog/2009/01/does-minesweeper-ch...

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.

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.

Yes.

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.

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.

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

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.

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.

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.

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/]

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

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.

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

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

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.

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=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.]

I wonder how hard 3D minecraft would be.

Er, wow. Hard.

http://egraether.com/mine3d/

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

Yes, especially:

Benford's Law http://www.datagenetics.com/blog/march52012/index.html

Hangman http://www.datagenetics.com/blog/april12012/index.html

Yahtzee http://www.datagenetics.com/blog/january42012/index.html

Risk http://www.datagenetics.com/blog/november22011/index.html

Plus others ...

Reply on news.ycombinator.com