UselessGameDev logo UselessGameDev title

Crushing Minesweeper

Thu 02 February 2023 #GameDev'sRevenge
This text is a written version of the video above, with future plans to incorporate graphics and figures for illustration.
As I'm working my way through the backlog of videos that were published before this website, I suggest reading the article alongside the video for a comprehensive experience.

Hello everybody, welcome back. Today I want to talk about Minesweeper. A game that fascinated me when I was a child, and I only started playing seriously a couple years ago.

The thing is, I’m not very good at minesweeper. But as Mark Rober would say, I’m also an engineer, which makes me very good at minesweeper.

So kick back, relax, lemme put on my black sweatshirt, because it’s time for some Game Dev’s Revenge

Minesweeper

Super quick reminder of what Minesweeper is, for our younger audience. There’s a grid of tiles, in our case we are going to focus on the Expert grid, which is 30 by 16. Behind those hidden cells are 99 mines.

If you click on a cell you can reveal what’s under it, and to win you need to reveal all non-mine cells without clicking on a mine cell.

To help you, revealed cells will show how many immediate neighbors are mines. You can then use logic (or luck!) to deduce where the mines are, and right click on them to flag them as mines.
If you click on a cell that does not have any mine in its direct neighbors, it reveals them also, which can cascade into pretty patterns.

That’s it. It’s easy to learn, hard to master, it’s surprisingly engaging despite its simplicity. It’s a nice game, if you haven’t played it you should give it a try.

But today we are going to destroy it.

Computer Vision

The sensible thing to do, would be to create my own version of minesweeper first. That’s what most people on the internet who write a minesweeper solver seem to do. Being able to interface my code with the game code, it would allow me to know the state of each tile, easily execute actions like revealing or flagging tiles, etc.
All within the same program that I made.

But I don’t want to beat my own minesweeper. I want to be able to beat any minesweeper.

So I have a proper game of minesweeper running here, and I have no access to the game code, I just have my mouse, and what’s displayed on screen, That’s it.
So it’s time for some good ol’ Computer Vision.

I set up a janky way of streaming the content of my screen into Unity. Unity isn’t really necessary but it’s what I’m most familiar with, and it’s great for manipulating Textures and Colors.

So I’m in Unity, with a Texture2D that looks like the game.
To parse the grid, I need to know where the origin pixel of the first cell is, and how many pixels are in a single cell.

Then it’s pretty straightforward to get all the pixels in a cell, remove some padding for performance then all the gray pixels.

What’s left is a bunch of colored pixels, from which I get the average Hue and Brightness.
I take an average because there might be compression or streaming artifacts that make almost every cell unique.

Then it’s just a matter of playing with these values and certain thresholds, for instance, if when attempting to identify a cell, the average Hue is around .67, then it’s a blue cell, which is either a 1 or a 4. Then looking at the brightness, you can tell them apart.

It took a long time calibrating these values, especially with the 7 being black like mines, and the flag being red-ish, but also black. iiiit wasn’t very interesting.

But we’re here now and can parse the grid into my own Grid model. Nice.

Inputs

So the program knows how to parse the game state. Now it needs to be able to send inputs. For this I use the C# input-simulator library, which works in Unity, and allows me to move the mouse, click, right click, and other features that I don’t need right now.

Put together a few utility functions like ClickCell or FlagCell, and we’re off to the races, with an AI that can play at... random.

Making it smart

It’s finally time for the proper thing, that is, writing a solver for Minesweeper.

Let’s look at this example.

This 1 is located in a way that the only neighbor available has to be a mine. There’s one mine, one neighbor. Quick math.

Same thing with this configuration where the bottom 2 has exactly two neighbors left, and no flag around it, therefore they must both be mines.

Generalizing this, we get the first rule of our solver :

If the number on the tile is the sum of flag neighbors and undiscovered neighbors, then all remaining undiscovered neighbors are mines. They can safely be flagged.

And then similarly, the second rule:

If enough neighbors have been flagged as mines, the remaining undiscovered neighbors can be revealed.

It’s enough to go quite far, but in expert mode, not enough. So we need to break out the bigger math.

A pattern players learn to recognize early on is the 1-2-1 pattern:

If we look at all possible arrangements for mines, only one works, where the mines are on the sides. Because the number of mines in this section is equal to the number of cells in the set difference of the neighbor sets of the 1s.

We have those logic rules, but still there’s always a moment where we run out of options, so for now, if we don’t know what to do, we’ll simply take a purely random pick.

Speedsweeper

This version does OK but is super slow.

The first improvement we can make is to batch moves. The thing that takes a lot of time is getting and parsing the image of the board. Then we play one move, then we parse the result. But most of the time there are multiple moves available at once, so what we could do instead, is to play all of them before parsing the new result. This saves a ton of time. And since we made multiple moves before parsing again, there’s even more new stuff to see then.

Then I turned on the profiler and I got to optimizing the rest of the code. Removing debug stuff like logs, lowering the waiting time between clicks to a minimum, turning off my second monitor for some reason, caching values when possible, using Arrays instead of Lists, and soon, there I had it.

A minesweeper solver that goes very fast, and gets me on the leaderboard as the fastest player in the world.

It only wins about 10% of games though, so it still loses a lot, but it loses very fast.

In the end my best score was just under 6 seconds, and about 90% of the time was spent fetching the image of the board, parsing it, and sending moves back. The remaining 10% was the actual solving strategy. So it would have been a lot faster to make this in my own version of minesweeper, but again, not the real minesweeper!

Probabilities

To somewhat improve its reliability, we can take a look at what it does when it doesn’t know what to do: a random pick between all undiscovered tiles.

A better approach would be to calculate the probability of each cell to be a mine, and then click on the cell with the lowest probability.
To do this, we need to bust out the probability math, finding all possible arrangements of mines, using combinations, binomial coefficients, all of this stuff you learn when you’re sixteen and think “Aw gee I’m never going to use that in my life, I’m gonna be a Youtuber”.

Well, after an excruciatingly painful evening of recursive functions, I had a list of all tiles, sorted by the probability of each being a mine. Phew.

Unsurprisingly it adds quite some time to the computation, I never broke the 7s barrier again, but the solver is now a lot more reliable as it now wins on average 35% of games! Considering the top players in the world win about 55%, I’d say that’s decent enough. At least it’s way better than the previous 10%.

Conclusion

I’d say I got my revenge. I achieved super speeds and scores I could never have dreamt of, and my thirst for high speed minesweeping has been quenched.

Have a great day, and nobody talks to me about arrangements ever again!

Check these out

Music Credits