Botting Google Minesweeper
Tags: programming, python, ai, project
Published: 2022-04-30 22:04:28

During the pandemic, I had to find ways to entertain myself even when I didn't really feel like reading or booting up a game like Apex Legends. I found quick online games like Solitaire and Google Minesweeper as the best candidates as I could finish a game quickly and be back to doing work after that. It was near the end of my second academic year when I needed a small project to keep myself busy and to distract me from actual work. I figured what better project I can do than to make a bot that plays and wins Google Minesweeper.

This may have been done previously by others, but I always like a new challenge and figured it would be a simple thing to make. This was not the case.

In this blog post, I want to outline the process I took in making this bot, some of the challenges I faced, and some of the algorithms I used. Maybe this might inspire some of you to take on your project like this!

## Tools used
My language of choice for this project was Python. Partly because I already had an idea of some of the libraries I'd be using but as well, I'm already somewhat proficient in Python, I'd be able to make progress and debug problems much more quickly than I would have if I had written this bot in another language.

I made use of the [pyautogui](https://pyautogui.readthedocs.io/en/latest/) library. Pyautogui allows you to programmatically move your mouse on the screen which will be essential for playing Google Minesweeper.

I also needed a way to quickly grab some mouse coordinates from my screen. The [coords](https://addons.mozilla.org/en-US/firefox/addon/coords/) extension for Firefox made this a lot simpler. 

Note though, that pyautogui works on mouse positions relative to the resolution of the monitor where as the coords extension displays the coordinates relative to the browser window not including the search bar. This means that the Y coordinate recorded by the coords extension was off by around 100 pixels. Not a difficult fix, just something I had to keep in mind.

## The algorithm
The high-level explanation of the algorithm that I came up with is this.

- Click the center tile to get the game started
- Do a full sweep of the board and perform any trivial actions that can be done given the information of a tile and those adjacent to it (this will get explained later)
- If a change is made from any of these actions, add the tiles adjacent to it into a list of tiles to be searched after the initial sweep is done. (think breadth-first search)
- Continue to search these tiles until no changes are made, then sweep the board again. This is because clicking an empty tile will cause all adjacent empty tiles to be revealed. These tiles aren't added to the list because they may not be directly adjacent and it's not deterministic when and how this occurs.
- If no changes are made after the second sweep perform advanced searching (will also get explained later)
- Continue until the board is solved or guessing is required

This algorithm went through many iterations of testing, but this is the one that I'm happy with and that works both well and fast enough.

## Gathering information
Now before being able to do anything, I need a way of gathering information from the board.

So how does the bot figure things out? I've seen other bots that use computer vision libraries such as [OpenCV](https://opencv.org/) to take screenshots of the board and make decisions that way. I decided to take a more basic approach that still works great albeit with its own set of challenges.

Pyautogui has the functionality to take screenshots of specific regions of the screen. From there, I'm able to analyze the pixel colors and their frequency in that screenshot and determine what type of tile it is.

Any tile that contains the color of a number must be that number since each color is unique and always the same. This logic can also be applied to identifying flagged tiles, dirt, and grass tiles.

This, on paper, works out great. It's simple and requires no overkill CV libraries. In practice, I started to encounter a very annoying issue. 

There would be times during testing when the bot would misidentify a tile as grass or dirt. This had further repercussions on which tiles the bot searched and would often leave the bot hanging. 

If you're interested in the full saga of this issue, I documented it all [here](https://github.com/EliasJRH/EZSweeper/blob/master/Challenges.md#ignoring-tiles). The TL;DR is that in Google Minesweeper, every time a tile is clicked, an animation of the tile flying away is played. _Sometimes_ this tile flies directly in the coordinates of where the bot is trying to search and _sometimes_ this caused the bot to misidentify the tile has grass or dirt.

## Trivial actions
Now that I have a way of gathering information, I can start doing trivial actions.

What is meant by trivial actions? Essentially these are actions that can be performed from minimal information. Understanding these require knowledge of how to play minesweeper, so if you're unfamiliar with the game, I'd quickly give [this](https://www.wikihow.com/Play-Minesweeper) a read.

The first trivial action is simply to click all adjacent tiles if the bot has flagged bombs around a tile equal to the number of the tile itself. 

For example, if the current tile the bot is on is a 2 and the bot has flagged two tiles adjacent to the current tile, then click the remaining adjacent tiles as there will be no more bombs around it.

Conversely, the second trivial action is to flag all adjacent tiles if the number of grass tiles is equal to the number of bombs surrounding a tile.

For example, if the current tile the bot is on is a 2 and the bot observes that there are exactly 2 adjacent grass tiles, then the bot will flag those tiles.

Pretty simple stuff so far. Using these strategies alone might win you the majority of games on a relatively small board, but I really wanted to conquer the hardest difficulty, which is where - for lack of a better term - advanced searching comes into play.

## Advanced searching
I think the best way to describe "advanced searching" is with some examples. Consider the following scenario

![An image of a segment of a minesweeper board displaying how advanced searching can be used to determine which tiles don't have mines](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0goxt11umbepzmk0lfkf.png)

We can see that the 1 in the bottom corner has one mine adjacent to it remaining and the 3 above it also has one mine adjacent to it remaining. Playing as you would normally, it might seem like there are no moves to make here, nothing is outright obvious. However, let's look at this a bit. 

The 1 in the bottom corner has exactly one mine in the two squares next to it. The 3 above it has exactly one mine in the 3 squares next to it

![An image of a segment of a minesweeper board displaying how advanced searching can be used to determine which tiles don't have mines with more detail](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mq77f81g4fhbeq7p8arx.png)

If one mine has to be in the two tiles marked with a blue x and one mine has to be in the three tiles marked with a red x, then it is impossible for the mine to be in the tile in the top corner. Think of it as just being extra, if we can get rid of those extra tiles, we can uncover more information about the board which might in turn, allow us to progress further along the board than we could. 

Advanced searching techniques like this are pretty much necessary to beat Google minesweeper on hard difficulty. Rarely have I played games where I've never had to use them and won.

These kinds of techniques can also be applied to find mines where it might not be obvious, consider this scenario

![An image of a segment of a minesweeper board displaying how advanced searching can be used to determine which tiles have mines](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h5ca9i5zh07bwt5tgm12.png)

The two in the bottom right corner has one adjacent mine remaining in the two tiles next to it. The two above it has two adjacent mines remaining in the three tiles next to it. 

There's definitely a mine somewhere, but it may not be entirely obvious, again we take a closer look

![An image of a segment of a minesweeper board displaying how advanced searching can be used to determine which tiles have mines with more detail](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ync4vlz2zz8zriguru1s.png)

The two in the bottom left corner must have exactly one mine in the tiles marked with a red x. The two above it must have exactly two mines in the tiles marked with a blue x. Since we know that there is exactly one mine in the two tiles marked with a red x and exactly two mines in the tiles marked with a blue x, then there must be exactly one mine in the tile marked only with a blue x.

With these two techniques under the bot's belt, in addition to the trivial actions described previously, the bot was able to win nearly every single game it played, provided that no additional guessing was involved.

## Last thoughts
I really enjoyed working on this, I really enjoy working on a lot of things like this. It was very difficult for me to balance the work on this project with school work (so much so that this blog post is a year in the making), and I often needed to remind myself that I am also doing a degree and should probably study for my exams instead of studying ways to mark tiles in Minesweeper. 

Despite this, I learned a lot while working on this, and I've learned even more since I finished. This wasn't the first project of this kind that I've worked on, and I'm pretty sure it won't be the last.

The source code for this project can be found [here](https://github.com/EliasJRH/EZSweeper/tree/master).