Python script beats Minesweeper in seconds (30+% success on expert)

I have written a Minesweeper solver in Python. In this video let's see how I did it, what strategies can be used and what results can be achieved.

Speaking of results, my bot successfully can solve 81%, 75% and 30% of beginner, intermediate and expert games (measured by letting my AI playing 1000 games using Minesweeper X).

UPDATE: latest version of the solver reached 36% expert success rate by adding CSP to determining lowest probability of a mine.

UPDATE 2: Refactored version there too. This one does not work with Minesweeper X, but rather generate and solve minesweeper games in the program. One small improvement there, but the success rate is still just above 36%.

UPDATE 3: I am rewriting the whole thing from scratch, aiming for the better solvability and performance. And it is going to be multi-dimensional too.


––––––––––––––––––––––––––––––
Creative Commons — Attribution 3.0 Unported — CC BY 3.0
––––––––––––––––––––––––––––––

[neuralwarp]

You missed a trick. When you're forced to guess, with an equal chance of death, some choices can give you more information, if successful, than others. Particularly, a cell one square away from a row of 1s can open up a new cavity if it shows the cells between are already allocated to the row of 1s.

[MonBlanc-jktr]

I geniuenly don't understand how you're not getting atleast 1k sub a day, this is actually quality content! It's the first ever time I've ever clicked on an ad!

[odedsayar]

I would argue that those risky 50% guesses are often better, since they give you good info that adds up well with what you've gathered so far, thus pushing the next guess you'll need to make further away. I'd improve on that by estimating whether we have a few or a lot of mines left (#mines÷#cells is greater in the totals or in the remaining), in the former case I'll guess that the mine is near the wall and in the latter it's away from the wall (for a more "efficient" use of mines). If I found the time I'd try comparing it to guessing at the lowest risk

[kooobnet]

Minesweeper was actually available in Windows 286 and Windows 386 (prior to windows 3), IF you had the expansion pack (2 extra floppies).

[justingolden]

Thank you for sharing. I personally have used all of those strategies except the equation one (which I have pondered but never used), but I'm curious to see what you did differently from these other ones where the other ones were better on expert.

[chengleeng]

8:00 the left picture is actually not a 50/50. if the top left square of the box is a mine, only 1 mine will be required to satisfy the 1, 2 and 3. However, if the bottom square is the mine, then another mine (to the bottom right if the 3) is required to satisfy the 3. Since the mine density of most boards is less than 50% (12.35% for 9x9/10 beginner, 15.63% for 16x16/40 intermediate, and 20.63% for 30x16 expert), unless the unsolved part of the board is unusually dense with mines, it is much more likely that the 1, 2 and 3 share a mine in the top left corner. So, instead, when calculating probability, it is much to calculate if the said square is a mine, how many ways are there to fill in the rest of the (unopened) board with mines, and compare that to if the said square was safe.

side note: this box pattern is a 50/50 only if there are 2 mines left in that box (via minecounting), maybe the example could have been made more accurate by using a simpler example like this at a corner (x is a mine, o is unopened)

x 3 1 |
x o o |

[porglezomp]

When comparing yourself to all those papers, do you know if there's a chance they were using different minesweeper implementations that might've generated slightly easier / slightly harder puzzles? It seems like if you're using CSP + counting I would expect you to be able to do just about as well as anything.

[moooseman]

This was interesting to see after trying the problem myself. I used a site that guarantees the minesweeper board is solvable, so I didn't implement guessing. My approach used the basic and counter strategies, and then did a recursive search on subsequent boards until those strategies yielded a known tile. I'll have to look into CSP, since calculating that system of equations upfront seems more efficient than guessing and checking.

[adurks]

I'm curious how fast this would be if the game was stored fully digitally and it didn't need to interact with an actual game

[DanielBerke]

This is really neat. For calculating win rates (either your calculation or in the papers), does clicking a mine on the first click count as a loss? Because to me it feel like those results shouldn't count, since you have zero information for that first click and just got unlucky; i.e., it's a "loss" but it doesn't actually reflect on the strategy of the solver. (Anything after the first click should be fair game though, since you have _some_ information to make a decision on, even if that decision is a guess.)

[eitansegev]

lol I watched all your Minesweeper videos and I don't even know what are the rules of the game.

[stevenliang]

That was so inspiring! Can you share some idea about how did you implemented the grouping part? ( with lower complexity ). I am thinking about checking knowledge base entailment, but that has a worst case of NP-hard right?

[pantherplatform]

Wow. Only 142 subs. More like 142k or 142B

[EebstertheGreat]

If your "CSP" strategy seldom gets results, you probably coded it wrong. Whenever I play Minesweeper casually, a large number of cells get revealed in this way. The example you show at 7:15 is totally standard, although the green cell at the bottom is mislabeled. You don't have to do much work, just recognize a few patterns and do them one at a time. Even at high speed, this type of strategy is usually necessary.

[creeperthecat]

I recently got into Minesweeper, and now I want to make something like this that would play as good as a true pro, and then I can make a replay of it and pretend I'm superhuman, if only for a brief moment.

[AssemblyWizard]

How about using CSP to get more accurate chances to be a mine? It might give more accurate chances to the wilderness rather than 24% to all of them

[PlufferPalen]

14 subs only?
*let's make it 15 cuz I can*

[Feuergraf]

I was hoping you would run through the "analyse screenshot" part

[reinholdsgrintals]

Hai, me and a few of my friends are playing a game where within the game there is a minesweeper, we tryed to edit your code to work on it, but we failed, would you be interested to adjust your script to work on our minesweeper for a reward? можно и так

[mrballou]

Can we still get the "old" version (shown in the video) to be able to play on minesweeper x?