Algorithmic Approaches to Playing Minesweeper (2015) | Hacker News Reader

Algorithmic Approaches to Playing Minesweeper (2015)

dash.harvard.edu

95 pointslainon32 comments

I did some work on a minesweeper solver [1], I'm surprised my work is not mentioned. The best version of their algorithm wins on expert 32.9% of the time, whereas my AI achieves about 50% win rate. My AI uses the connected components decomposition that they did, but also some endgame tactics that significantly improved win rate (that they didn't consider).

[1]: https://luckytoilet.wordpress.com/2012/12/23/2125/

Thanks for the interesting write-up!

You say here yours wins around 50% of the time on expert, whereas your linked article says 50% of the time on advanced - is this a typo, and/or what's your success rate on expert?

Same thing -- 16x30 with 99 mines.

Thanks!

One question: does your algorithm account for the possibility that a non-border square could have a lower odds of being a mine when you reach the last-resort safest guess approach? It looks like you only consider the odds of mines in the borders, but not that a complete unknown square could have lower odds. You do mention the situation where you know that particular square has no mines, but not where you know the odds are lower than in any of the border squares.

It's pretty rare, but in my minesweeper obsession days I would occasionally see it happen.

Edit: upon further reflection, it's actually pretty common in the early stages, esp. in lower difficulty games. You will occasionally on the first click get a high-ish number and are much better off clicking a non-neighbor as the next guess. You must be doing this or couldn't achieve 50%, I'd guess.

Yes, I do this as an endgame tactic. In some situations, knowledge of the mine counter can help you deduce that a non-border square is empty. (Details in the last part of the article)

Hey, another question. In your write-up you mention enumerating the possibilities when no deduction is possible, and picking one of the lower ranked cells found like this. However, a couple of improvements come to mind.

First you could weight each possible configuration by the number of mines it contains per square vs the average remaining over the whole board (so a very mine heavy configuration is less likely if not many mines remain).

Another thing you mention is that once you find the counts per square, picking any one of the lower counted ones is the same. This doesn't look true for me. One would also want a click to reveal as much information as possible, so clicking in an area with low density of mines is better. In your example clicking into the middle right 2 next to the three ones would likely reveal more info than clicking on the top right 2.

Did you consider these as possible improvements?

Indeed, those are good ideas for improvements! It's hard to say whether they will improve the AI, as in both cases you're replacing one heuristic with another heuristic. You'd need to implement it and experiment with it -- and I haven't done so for my AI.

> Each of these 11 configurations should be equally likely to be the actual position.

This is not true. For calculating the odds of a configuration you need to take into account the non-border squares and the number of the remaining mines too.

Example (3 remaining mines):

    1111
    *22*
    xxxx
    xxxx

The * represents the marked mines, 'x' represents the unmarked squares.

There are three border configurations:

    1. mine, empty, empty, mine
    2. empty, mine, empty, empty
    3. empty, empty, mine, empty

But actually the first one is actually is 4 global configurations, as the remaining one mine can be anywhere on the remaining squares. The second and third are 6 and 6 global configurations respectively as the remaining two mines can be anywhere on the remaining 4 squares (4 choose 2).

The probabilities of a border squares to be empty are 3/4, 5/8, 5/8 and 3/4 respectively as opposed to 2/3, 2/3, 2/3 and 2/3 that your rule gives. The probability for a non-border square to be empty is 9/16, slightly more than 1/2.

One can argue that when the number of the remaining unmarked squares is large compared to the border squares this gives little difference. But it's not true, this gives significant differences even when this is the case.

[1] http://nothings.org/games/minesweeper/ "Counting unencountered mines"

That's a fair objection. You can view my rule as a heuristic that's easy to compute and gives good guesses in most situations, rather than calculating the mathematically correct probability.

My AI does actually account for this, but only in the endgame when there are a small number of squares left -- then it considers the global configuration instead of just local. This works out because the endgame is where this problem is the most significant, it's computationally expensive unless there's a small number of squares remaining.

Then I suggest an improved heuristics for mid-game.

You can actually calculate the number of global configurations for each border configuration, they are just (n choose k) type calculations. It's somewhat more sophisticated when there are multiple disjoint border regions.

Alternatively for a mid-game heuristic you can approximate the initial uniform distribution of the fixed amount of mines on the playing field with another distribution: Each square having an independent probability of having a mine or not. This could potentially simplify the calculation but it wouldn't be accurate when there are not so many mines left.

”It's somewhat more sophisticated when there are multiple disjoint border regions.”

I don’t see why that would be the case. Can you explain?

That assumes those three border configurations are equally likely. In this case, I think that is true, but in general, I don’t think it is true that all possible border configurations are equally likely.

For example, if you add a fifth row of xxxx to your example, ignoring what we know of the third row, the expected number of mines in each row would be one. That would make the first configuration, with two mines, less likely than each of the other two.

Similarly, if, in your example, there are only 2 remaining mines, the first option is less likely, if there are 5 missing mines, the first is more likely, and if there are 6 missing mines, the second and third cannot happen.

Things get even more complicated if one assumes the mines aren’t placed uniformly, for example because the programmer wants to avoid areas of the field completely separated by mines.

Well, it has been a while since the last time, but a ritual is a ritual and it has to be followed.

Whenever someone says "minesweeper", I have to post my implementation.

Here goes: 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

Well, you've successfully distracted me for a good ten minutes. Really like the UI.

Like it - did you get the job?

Obviously not.

But it is totally understood. You can't expect a leading tech startup like Thumbtack to lower the bar for a 40+ yo self taught programmer like myself. They only hire the best!

I can't not plug Peter Divianszky's implementation at https://hackage.haskell.org/package/minesweeper which has the awesome property that the board is generated as you play, in such a way that you never have to guess (in the sense that if a field is not forced by currently shown clues to have a mine, then it won't have one when you click on it).

For anyone who wants to play Minesweeper without the hassle of trying to track down a known-good *.exe, I recommend Minesweeper X [0]. The board size isn't limited plus a ton of other features. It also works perfectly under WINE with Winetricks.

[0] http://www.curtisbright.com/msx/

I’ll join you and show off mine as well! Runs in terminals, and also has a rougelike adventure mode where you navigate the board with a character.

https://github.com/accatyyc/terminal-mines

Minesweeper X isn't mine (just a happy user), but yours is cool too, thanks!

If you're using linux, there's Gnome Mines,

http://linux.softpedia.com/get/GAMES-ENTERTAINMENT/Puzzle/GN...

KDE of course has its clone too: https://www.kde.org/applications/games/kmines/

And as always with old XP era exes: ReactOS has its own compatible copies and you can use them in Windows and they will usually work (minesweeper from ReactOS does work on Windows 10, I just checked).

Here's my command-line minesweeper solver, in c++. It is not optimal, but does a pretty good job of solving expert sized minefields. I never worked out what percentage of minefields it solves, because I planned on doing some more work on end game scenarios. That was about ten years ago. The code is quite readable, so may be of interest to fellow coders, and anyone is welcome to extend it if they wish.

https://github.com/tomcdonnell/minesweeper_solver_text_cpp

I'll add another implementation, Mines from the great sgt-puzzles collection.

https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

It has an option to "ensure solubility" similar to the one @gergoerdi mentions above.

This paper is wrong in section 4.1:

>The first click of a Minesweeper game deserves special attention since it is rather unique. >Namely, the opener is always a guess because the player starts with a covered board. >In addition, the challenges associated with the opening move are unavoidable and are shared among all solvers. Thus, finding an optimal policy for dealing with the initial click will benefit every approach

The first click of a Minesweeper game is always safe[1]

[1]http://www.minesweeper.info/wiki/Strategy#First_Click

I think what the author meant is: It's a guess where the best position is for the first click.

You can't fail with the first move but you can have different outcomes and it's advisable to choose a position where the expected information gain is optimal.

In the original game, yes. Not every clone.

I went out of my way to lookup the way that the original minesweeper handled this case, as you can see from that link it does have a perceptible effect on the game.

Ah, let me throw my take on Minesweeper into the ring as well: http://magnushoff.com/minesweeper/

My final variant is like the original Minesweeper except that when you are provably stuck, the game will help you to move on.

For a nice minesweeper variant, try Mamono Sweeper.

It has the same mechanic as minesweeper, but instead of bombs you are sweeping for monsters, which have a level (1 to 9).

A clue in a cell is the sum of the monster's levels surrounding it.

You can kill monsters of level 1, and eventually you level up and are able to kill bigger monsters.

I've long wanted to mak an "always possible" variant of minesweeper. This is equivalent to only presenting the player with a board that a "perfect" algorithm can solve.

it's funny that there's a whole section (4.1) on picking a starting move that increases the probability that that first cell is a 0-cell when in fact the game guarantees that your first click will do that.

It guarantees that the first cell is not a mine. You could still just get a number there.

Reply on news.ycombinator.com