Solving Minesweeper and making it better (2015) | Hacker News Reader

Solving Minesweeper and making it better (2015)

magnushoff.com

271 pointsmaggit73 comments

The Simon Tatham version [1] is great because the puzzle generator eliminates situations that requires random guesses.

1) https://www.chiark.greenend.org.uk/~sgtatham/puzzles/ (scroll down to "Mines")

There's a point of view where this transforms it from a game into a task. Execute the algorithm as quickly as possible.

Couldn't we argue that about all games? Particularly no or low randomness games (such as sudoku, or euro board games, respectively). But even games with randomness might be winnable by following an algorithm. The trance of executing those "algorithms" (playing, basically) is also part of the fun. Solitaire card games, for example. The gambling part of playing the odds against randomness is just one diension of fun!

What's a euro board game?

https://en.wikipedia.org/wiki/Eurogame

I guess something like this?[0]

[0] https://boardgamegeek.com/wiki/page/Eurogame

Broadly, they have indirect player interaction and abstract physical components (eg Ticket to Ride), but more importantly in this context, they are board games that often do not use dice or a spinner to introduce randomness. Strategy then becomes a "boring" matter of executing an algorithm.

(There are many exceptions that do use die/dice, but for those that have not played board games invented after Monopoly, the idea of a board game that does not have die-introduced randomness may be quite foreign.)

Some of them have larger amounts of player interaction, at which point the game becomes "modify your strategy on the fly to deal with an ever changing situation".

Ticket to Ride has randomness in the train card deck. You can effectively gamble by drawing off the deck rather than choosing one of the face up cards.

The term relates to a specific style of rule design.

They are usually sitting right in the middle between entirely abstract games like backgammon and "simulation" games like Risk or Monopoly. There is usually some theme, but gameplay considerations (mostly revolving around keeping the game interesting for those not on an obvious path to victory and balancing luck vs skill, hence the mention in this thread) are far more important in the design than adhering to that theme. Sometimes it even seems as if the theme was not serving as inspiration for the rules but it's only a skin pasted over the bare rules after the gameplay had been tweaked to perfection.

Sudoku is where the pattern stood out starkly for me. Essentially trivial solvers are better than all humans.

I guess that depends on what "trivial" means. Given that it is np-complete any true solver needs to be able to go into exponential time (assuming p != np) which I wouldn't generally consider to be "trivial" unless its a brute force solver.

And using trivial deductions (based on the numbers in the column, row, and square there is only one possibility) is not sufficient to be better than me (and I don't consider myself to be good).

The "classic" boards (9 by 9) are all easily solved by straightforward methods. Maybe "trivial" is a step too for for the 'eliminate' and 'search' functions here, but they aren't a lot of code either:

http://norvig.com/sudoku.html

There's at least the metagame of discovering the algorithm. Also, the Simon Tatham Minesweeper is only mechanistic up to the last ten mines. After that, it can require (by design) reasoning across all remaining mines and spaces.

Whereas otherwise, it's "execute as fast as possible, to try your luck as often as possible within a given timeframe". Almost the same, but I fully agree, one is just a task, whereas the other is still a game. Kind of like a form of gambling, where the stake is the work put into executing the algorithm and the pot is a solved board with a fast time.

Many years ago I used to be quite addicted. The unconscious pattern matching went far enough to detect unknowable situations and do even the switch back and forth between guessing and solving without spending a conscious thought. The goal was not to solve as many boards as possible with a timeframe, but to get the best time so there was a kind of triage going on between trying to solve possible solvable large scale situations and failing fast. The strategic level was finding the right cutoff.

My favorite examples of this are Picross (aka nonograms, https://www.puzzle-nonograms.com/) and Slither Link (https://www.puzzle-loop.com/). Both can be made difficult enough to require advanced planning ahead and some trial-and-error, but the simpler ones are nice to zone out to.

Many games (by common definition) are strictly execution based. For example, most rhythm games (e.g. Osu!, Beatmania, DDR, Guitar Hero, etc) do not have any element of randomness or strategic requirements, yet some people find them very fun.

It does so by eliminating a much larger number of situations. Essentially, it guarantees that you can always make progress by looking at at most two numbers and their surrounding revealed/unrevealed squares, until you reach the last ten mines, after which it allows board-spanning reasoning. In doing so, it eliminates a very large number of puzzles that might be solvable with deeper logic.

So the version described in the article, where it generates purely random setups and you can ask for help if it's truly impossible to make progress without guessing, will actually give more interesting puzzles, sometimes.

A more ideal version would even take into account probabilities, so that to get help you'd have to point it at one of the squares with the lowest probability of having a mine in it. (Or, as another commenter points out, a square with the highest probability of useful progress.)

Simon's puzzles are all really well done, and run in the browser, OS X, Linux and Windows. The code base is very cleanly written C and he has extensive developer documentation: https://www.chiark.greenend.org.uk/~sgtatham/puzzles/devel/

He is also the person behind PuTTY.

> He is also the person behind PuTTY

I thought I recognised that name from somewhere. I once had to hack the PuTTY sources for an internal project and it was quite an enjoyable experience due to how cleanly written the code was. I was always a fan of PuTTY but I'd gained a new appreciation for it that day.

Love it when two such unrelated things are the same person. Like the antivirus guy Graham Cluley who wrote a tetris clone with a spreadsheet program built in I got obsessed with as a kid

> The Simon Tatham version

The Android version [0] of Simon Tathams games is most likely the best puzzle compilation you can get for your phone!

It is small, free, fully offline and does not contain any ads. I literally spend hundreds of hours playing this game over the last few years.

[0] https://play.google.com/store/apps/details?id=name.boyle.chr...

There's an iOS version as well for those of us on the other side of the smartphone aisle, which is similarly free and ad-free: https://itunes.apple.com/us/app/simon-tathams-portable-puzzl...

Oh nice, it's on FDroid too!

Minesweeper got me into development, my first real project was building a minesweeper clone for Android using web technologies. It only sold 3 copies, but it got me a new job making more than twice as much as I made doing graphic design.

My version is called Swine Peeper, and you're trying to find pigs in a field. It's now free if you're interested: https://play.google.com/store/apps/details?id=com.ionicframe...

I guarantee this is both the most literary, and most pun-filled version of minesweeper available.

To anyone who has just barely gotten their feet wet in programming, building a minesweeper clone is a great next step after something like a text-based blackjack game.

Do yourself a favor, don't look up any of the standard solutions for building it. Try weird things, figure it out. I made several completely different systems for propagating clicks through empty squares before I came up with a simple, reliable, and performant solution. If anyone had given me a hint I would have learned half as much.

Wow. My Minesweeper clone was called Swine Meeper, and the premise was similarly bonkers (interstellar livestock pig shipment infected with alien parasite, the player "meeps" them to find the infected hosts). Wrote it in Java way back but never got it on Android.

My version was originally going to be called Swine Meeper! However, after googling it I found this version here: http://www.karaffeltut.com/MineSweeper/minesweeper1.html

I'm guessing that's not yours, as it doesn't seem to have anything to do with pigs. Since it lacked actual pigs I carried on with my idea and just modified the title.

If I'd seen yours I might have come up with some other silly theme.

Small world, at least three different programmers spoonerized Minesweeper. No, mine is not online, nor will it ever be - it was jacked-up student-written Java, I had no idea how to structure code at the time. It's amazing it ever worked at all.

Minesweeper has an interesting metagame that gets lost with these "improvements". The metagame is played over many boards and the goal is to get the fastest record. Part of doing that efficiently is quickly identifying boards that require guesses, and immediately making those guesses (to avoid wasting time on the board when that time could be spent on a different board).

The flip side of that is if you're playing a large board quickly and the need to guess only emerges towards the end of a good run, sometimes you might want that last "help" button to save the last mine being a 50/50 shot

The final version of the game with the automation turned off actually plays identically bar that option.

When the mental pattern matching includes quick identification of known unknowables you can often identify some of the 50/50s of a given board quite early in the game. There is no point in postponing those decisions. Failing fast gives you more boards per minute.

On this level the game becomes 95% dexterity and 4% the "metagame" OP was talking about, which is triaging probable unknowables between guessing early and hoping for more information. The tiny rest is occasionally waking up from pattern matching autopilot mode to apply some logic to very rare patterns.

The metagame is theoretically more interesting than that. Is it more efficient to initiate the game with one random guess (as people usually do), or is it more efficient to initiate the game by rapidly clicking N random squares and accepting the danger? If so, which N is optimal? :)

Hmm... I'm tempted to say you should be looking at the number of squares uncovered, M.

If you got a good first click, you wouldn't want to waste it on unnecessary risk. If you got a bad first click, you'd want to keep guessing until you either died or uncovered another large section.

IIRC my N settled at around N=2.7, which means that a lucky first click would abort the queued random clicks between clicks two and three.

After that, the most important decisions for a fast match were deciding which mines not to tag because the final auto-tag would get them anyway and which empty fields not to uncover because they would be uncovered faster with an "uncover all surrounding" click on a saturated number. Clicking was definitely the bottleneck for me, so the main goal of the eye/pattern match was to keep the click-queue filled at all times. The eyes would always focus somewhere close but not too close to where the clicking happened, so that the pattern match could work on a stable image. Or sometimes just rest for a few clicks, when the hand could not keep up.

Fond memories of stupid things.

This is a great example of interactive writing. The playable demos are thoughtfully chosen. One of them even made me laugh.

Kudos to the author.

Thank you, that's a nice compliment :)

My inspiration for the format is Red Blob Games (https://www.redblobgames.com/), truly a marvel of interactive writing. (https://www.redblobgames.com/grids/hexagons/ is my all-time favorite)

Red Blob Games is incredible! Thanks for share. I hadn't seen it before. I enjoyed Polygonal Map Generation (http://www-cs-students.stanford.edu/~amitp/game-programming/...) most so far.

Any idea why the AI in your minesweeper sometimes doesn't declare it to be a local consideration that the one uncleared square adjacent to a 1 marker must be a mine? It's a funny hole in the final version of the game. I can't characterize exactly when it happens, but it seems related to cases when the seven non-mine revealed squares around the 1 have numbers in them.

My only other complaint is that it sometimes tries far too hard to derive facts in cases where a higher-level consideration makes it obvious there are none to be found. Try starting by clicking on 6 wildly disconnected locations, and getting a number on all of them. Requesting help at that point is very, very slow.

Regardless, this is a lot of fun, and actually requires some new reasoning. Most minesweeper variants just use the same set of 10 rules I memorized 20 years ago. It's nice to stretch instead.

>Any idea why…

No idea. It's a bug that I haven't been able to straighten out.

>My only other complaint…

Sure. As noted in the article, this is unescapable. For the situation you describe it would be possible to segment the constrained squares into distinct "islands" and then consider these independently of each other, reducing the complexity of the solver in these situations.

But it is proven that it is always possible to get into degenerate situations which no solver can ever hope to figure out.

I think my implementation is sufficient to demonstrate the concept and illustrate the article :)

I disagree with the overall thesis here-- that somehow abstracting away all the randomness of minesweeper makes it less "mechanical." Oftentimes, 1 square's outcome is less likely or even much less likely then another. Even better, sometimes 2 outcomes will be equally plausible, but 1 of them might be expected to reveal more information or to reduce entropy more. After playing enough, most plays become ingrained in you and mechanical-- the problem solving element comes in comparing probabilities.

A small comment for clarification; my remark about making the game less mechanical is for the part of the game that automates the simple, purely deterministic, constaints. So there are two things: Automation of simple deterministic things, that makes the game less mechanical, plus "Request help" that makes the game less random. The two are separate.

I don't think this speaks to your central point, however :)

Oh, completely forgot about that part. When you have to guess, and both choices would be equally bad when guessing wrong, focus on which would bring the bigger benefit when guessing right. It almost has a "motivational poster deep wisdom" quality, heh.

Was skeptical, but the version at the bottom is quite good. Made me realize how much I can improve my logic in the game.

Absolutely, click "No extra automation" on the last version and play it normally. It makes you question everything you previously thought was a random guess. Makes the game vastly better, because you're richly rewarded for thinking through every possibility. And you're incentivized to spend time thinking because you're not punished when it ends up being a truly random choice. Great, great work. Too bad minesweeper is not suited to mobile devices because I'd play this version all the time.

Turning this into pure reasoning over educated guesses is a nice twist on Minesweeper gameplay. What I want now from it is a way to be able to easily work out the logic "on paper".

So one thing I do is work everything out "as if" I placed a flag or or cleared a spot. I want to be able to put a ghost flag down so that I don't have to remember what the current state of the particular path I'm trying to rule out is.

Otherwise I forget about it the second I look away or it gets complicated.

I can't play sudoku without the ability to put in shadow options, or better yet, have the game do it for me. One can argue that the keeping track in your head is a worthwhile aspect of the game, I think it's not.

Shadow options are the only way I can play Sudoku as well; this is also potentially why I don't enjoy playing Sudoku. It always feels like the only way to make progress is by making a number of informal suppositions and waiting for a contradiction to reveal itself. This is surely true of a large class of games, but the only type of constraint you have in Sudoku is "no direct collisions" (i.e. two instances of the same number can't appear in the same row, column or subregion). Since all of these constraints are essentially of the same class, I can't keep any more than one or two of them in my head at a time, hence "shadowing". When I compare this to a game like KenKen, where there are a number of different classes of constraint (i.e. all of Sudoku's, as well as the mathematical constraints introduced by KenKen's rules), I find that I can hold a larger number of those constraints in my head at once, even when they have non-local effects.

I only know a couple strategies for Minesweeper, so it was pretty cool to see this writeup make distinctions between local and global approaches, not to mention calling out explicit situations where guessing is necessary.

"It always feels like the only way to make progress is by making a number of informal suppositions and waiting for a contradiction to reveal itself."

Sounds a bit like the scientific method =) Make hypotheses and try to falsify them

Somewhat shameless and off-topic, but I think I might have the unofficial world record in Minesweeper. I played it obsessively as a teenager on a Windows 95 Packard Bell. I was able to get 17 seconds on the largest board.

I never told anyone about it because I didn't think it was a big deal, but a couple of years ago I decided to look up the current world record and it's 23 seconds.

Unfortunately I can't prove it, but anytime Minesweeper comes up in discussion I'm obligated to annoyingly mention it.

Well, you should try again and screencast it, so you'd finally have proof.

My times were 2/8/20 on an old computer, but my family doesn’t believe me. :) To be fair, it’s most likely I am misremembering the medium and large times.

"The following is a small, but interesting and illustrative example of a game state that has only one logical solution, but you need to take into account the entire game state to find it:"

Is that really true? You can induce that the squares in the corners are free just by looking at their surroundings.

It's impossible to determine the corner squares are free solely from their immediate surroundings.

For instance, take the 2x2 section in the top-left of the board. Although the top-right and bottom-left squares of this section are mined, it could also be the top two, or alternatively the left two.

Therefore a more complex algorithm is required to solve this board.

You can't do it using a 2x2 section, but you can using a 3x4 section. Still, that doesn't require looking at the entire board.

A version of minesweeper I used to play was called stormsweeper. I think it was written in BBC Basic and ran on RISC OS. Instead of flagging mines, you got to remove them, and the numbers of the already revealed squares were updated. Every few seconds (time depended on what level you were playing) all the numbers were covered back over and all the remaining mines moved up to one square each. Blank squares stayed blank, and they were safe to click on as a mine could not move 2 squares.

Once you had cleared a bit of the screen, if you then got stuck, you could wait for the next storm then some of the mines would likely have moved to a solvable position.

I used to play the game Mined-out on the Dragon 32. You have a start and an exit, and have to tread a path one square at a time travelling between, with clues about how many adjacent mines there are. To spice things up, you get a beast chasing you after a while, down previous paths you've trodden.

Author: http://www.crashonline.org.uk/16/andrew.htm

Walkthrough: https://www.youtube.com/watch?v=VqFWdqaoQPw

Recently I got asked to build a Minesweeper game during an interview onsite for a senior front end position and it was incredibly fun to build. If anyone wants a challenge, try building minesweeper in an hour! Here's my solution: http://jsbin.com/yapifag/1/edit?html,js,output

No one has mentioned this version, but I've been addicted to it for years. It adds an extra level of complexity by giving levels to the mines (monsters) and the player:

http://www.hojamaka.com/game/mamono_sweeper/html5/en.html

> While situation 1 above is kind of neat, it is hardly satisfying to play many such games

Not everyone finds the same things fun; situation 1 is actually quite fun to me! See the rise of interactive comic "video games" which are closer to movies with a small number of branching points, or particle simulators (eg Uzu on iOS).

That final game is crazy hard.

The logical steps needed to solve it requires crazy amounts of concentration.

Make an assumption about where there is a mine, follow its implications until you find an inconsistency and then you know there is NOT a mine there. (however if everything checks out and then you know there COULD be mine there)

see also: (infinite) Minesweeper is turing complete http://web.mat.bham.ac.uk/R.W.Kaye/minesw/infmsw.pdf

A fun way to play minesweeper is to not use marker flags. Instead, start to recognize patterns, and sense the landscape of mines mentally as you go. One nice side effect: Lots less clicking needed.

xyzzy + shift + enter made me look quite smart back in the day.

about the two square playfield: iirc there was a rule that the first click could never be a mine.

Yeah, I disabled that rule for that specific game :]

Another rainy Friday morning, another shameless plug time!

Someone says "minesweeper", I post my implementation - “bugsweeper”. It's an established ritual.

Here go: http://www.ronilan.com/bugsweeper/

Few notes:

1. This is dated January 2014. It is a job interview homework.

2. The HN community has detected a bug and indicated that it should be fixed. That was done March 2017.

3. There are currently no known bugs.

4. The goal of the game is to find the unknowns.

5. No puns intended.

6. Code: http://www.ronilan.com/bugsweeper/js/bugsweeper.js

7. Have a great weekend everyone!

That seems like a huge problem for a pre-interview question. I usually refuse to take interviews if the pre assignment is going to take more than an hour or two.

Repeatedly posting the same link with the same copy-pasted text just based on a keyword doesn't seem any more acceptable just because you've declared it a "ritual".

I’ve declared it a “shameless plug” and winked it was a “ritual”. None of those makes it neither acceptable nor unacceptable.

Why I posted it?

I posted it, as a comment, mainly because it is fun for a couple of hundred people to play every couple of months. Not everyone seen it before and I think it came out a good game.

This has a point: https://xkcd.com/1053/

Why I think it is acceptable?

I personally think it is acceptable because it always raises some interesting discussion about something.

That’s what comments are for.

I think you should redo this project and see how your coding style have changed. I went through your code and I could see myself doing something similar at the time, but I would code it up very differently now.

I am pretty sure I would write it differently if I gave it a go, but I don’t think I’d change anything in the UX. Obviously nothing is going to change in the game play also.

So why a software rewrite?

For myself.

But, if I’m writing something for myself, I might as well write something new and interesting, and since I’m no longer interested in working at Thumbtack, and they weren’t interested in hiring me anyway, the uinverse is now balanced.

And that was a rumble about rewrites :)

Great points, thank you for sharing. Personally though, I have a few projects that are very well scoped that I redo over once in a while and it was interesting to experiment with different approaches on a project you know well.

2015

Thanks! Updated.

Reply on news.ycombinator.com