What i will attempt in this multi part post, is to write an application that will be able to play and solve Microsoft Minesweeper. I know it feels ambitious but i think we can make it happen. Since this is my first post where i don’t actually know how and what will i do, i cannot promise i won’t change technologies or frameworks in the meantime. So strap yourselves in and lets think it through.

I approach this like any other larger scale work i need to do, i break it down to smaller more manageable items, then devise an approach for each of them.

1. I need to get the current image of Minesweeper. Whenever you press ALT + PRINTSCR in a window, the contents of that window gets copied into the clipboard. I know i will find something in WinAPI that will help me with that.
2. I need to analyze the image and extract the current state of the board. I can approach this by doing pattern matching on the image either writing it myself or using an image analysis library like OpenCV
3. I need to write the logic which detects where the mines are. I will probably use an approach like what i used in the Solving Sudoku post.
4. I need to make actions in the game. In the past i worked with moving the mouse and issuing click commands from my application using WinAPI

A lot of time past since my last post and you probably think i was slacking off. It’s nothing like that. I had this idea a while ago and i spent some time researching each problem we need to solve, in my after work and after family hours.

I’m looking forward to this and see you soon.

In my last post I told you about the steps we need to be able to make in order to solve Minesweeper. I spent some time to achieve the first step, but it was a roller-coaster of emotions, mainly involving anger.

My initial approach was to write a C# console application that:

• 1. Search through the processes where the name matched Microsoft Minesweeper.
• 2. Read the handle to it’s window through the MainWindowHandle property on the ProcessInfo object.
• 3. DllImport the GetWindowRect function from WinApi and use it to find the screen-coordinates of that window
• 4. Create a Bitmap object with the appropriate size
• 5. Attach a Graphics object to the bitmap with the Graphics.FromImage function and use CopyFromScreen to, well copy the game window content into the Bitmap

Let me start by saying, playing around with OpenCV was a lot of fun. I’m genuinely impressed by it and I consider it a very useful resource to have it on your tool belt. What I tried to achieve in this part is having the game state in a processable manner. Currently what I get from the game is an image. We humans understand it perfectly well but in order to write an algorithm which will make some decision based on the game state. I need to extract the meaning out of it. Here is where OpenCV comes in.

My plan is simple.

1. Cut out each cell the game can have on board into a separate png.
2. Iterate over the cutouts and check where do they turn up in the image.
3. Extract the findings into an array which I can process further

To shortcut testing I loaded up a print screen of the game and analyzed that instead of the image that comes from the game. We will handle wiring everything together in a different post. This I what our input looks like.

The following code might look complicated but the process is actually simple.

Last time we reached the point where we had an in memory representation of the game. Today we are going to make some decisions based on the game state. Basically we will decide about an empty field if it is a bomb or it is safe. Let’s consider the following input image (I’ve cut out the excess, the rest is just empty squares).

If you are an experienced player, you will instantly spot that there are a lot of information available here. This is how the magic happens.

So last time we analysed the information in the game state, and we made decisions regarding the cells where we had sufficient information to decide which is a bomb and which is safe. In this post i show you how i implemented the last part and at the end i will show you a video, but first…

Let me start by saying F**K THIS GAME. I thought it is a lot more deterministic, but it turns out it takes a lot of guessing. I needed to implement the ability to guess if there is no concrete action we can take. The best place to add this was in the ScanGame function, because we already traverse the whole game. Now it looks like this:

void ScanGame(int* game, set<int>& bombs, set<int>& safes, int* g)
{
	int maxNeighbor = 0;
	for (int i = 0; i < SIZE; i++)
	{
		int z = game[i];
		if (z > 0 && z < BOMB)
		{
			vector<int> unk;
			int b = 0;
			ScanCell(game, i, &b, unk);
			int u = unk.size();
			int outcome = 0;
			if (z == b && u > 0)// not bomb
			{
				safes.insert(unk.begin(), unk.end());
			}
			else if (z != b && z - b == u) // bomb
			{
				bombs.insert(unk.begin(), unk.end());
			}
			else if (safes.size() + bombs.size() == 0 && u > 0)
			{
				auto possibilities = u - (z - b);
				if (maxNeighbor < possibilities)
				{
					maxNeighbor = possibilities;
					(*g) = unk[0];
				};
			}
		}
	}
}

The end of the last post was very satisfying for me, I was very proud of myself. The problem is, we could have done a better job. If you check out the last video you can clearly see that between rounds, our algorithm takes multiple seconds to start making decisions. This is because the Imaging Analysis part has some inefficiencies. After thinking about it I came up with a following issues.

1. We analyse the whole image even though the game grid is only a sub-part of it.
2. We keep scanning for cells and we don’t take advantage of the fact that once a cell was discovered, it’s value cannot change.
3. We calculate the centers each time even though cells are always in the same place.
4. We are scanning over areas that previously were detected as other values

Lucky all of these things can be improve by rethinking our strategy a bit. There are some values we need to extract only once and never again, and there are some things that we need to do every time. Let me show you how does the beginning of our application look like.

Last time we managed to greatly optimize the image analysis part of our little solver. That is great, however we only managed to run into bomb a lot faster. In Part 5 i was very, very … VERY frustrated about the amount of guesses needed to solve a table. I was wrong!

A couple of very good friends told me that there are situations where analyzing only one cell doesn’t result in any additional moves, but switching our attention to a specific area can help us uncover more detail. Let’s look at the following image.

If light speed isn’t fast enough, you can still go into ludicrous speed but keep in mind, you risk going into plaid. If you don’t know what I’m talking about, don’t worry and watch this funny sequence from the cult classic, Spaceballs. In other words, i managed to improve the speed, yes i know, i’m obsessed with performance.

To be honest, i didn’t make the algorithm run faster. Last time we introduced a 200ms delay so we wait for the animations to end. Setting a timeout is always a tricky system, especially if it would be hardware dependent. Luckily in our case it’s not, however we all still running faster than the game to catch-up. In our case sometimes having the timeout makes sense, other times it doesn’t.

To get rid of that 200ms delay, we need to detect when there are animations running. If animations are running, in my case, there will be cells which cannot be analysed. So what i did was to go into a loop, until i was able to successfully analyze all the cells that were still not discovered.

int tries = 0;
while (tries < 10)
{
	tries++;
	Sleep(25);
	gm.GetImageInto(imageAnalyzer.img.data);
	if (imageAnalyzer.Analyze())
		break;
}
if (tries == 10) // timeout
	break;
set<int> b, s;
decisionMaker.GetDecisions(b, s);

“So what happened?”, you might ask. Remember Columbo? Remember how he used to ask that final question, just before leaving the suspect alone and walking out the door, later having a big significance in solving the case? This is a classic case of planning to do something and ending up doing a totally different thing.

Before I was closing down this series, for my final trick I was going to solve the issue of size. Our solution till now is great don’t get me wrong, but if you try to solve a 9X9 or a 30X24 grid, it will fail. The issue is that the templates I use now, were extracted from the 30X16 sized grid. I though I will get away very quickly just by doing the following.

1. Detect the Cell Size
2. Scale the templates according to the cell size
3. Use the scaled templates in analysis
4. Open the champagne

Well it didn’t go as planned. The issue was that I already apply a threshold in order to find the perfect match. Scaling the templates meant that the quality of the match will be even worse. I tried adjusting the threshold, but I got more incorrect detection and misbehavior. Shit!

The solution lies in the content of the cells. The game scales the whole grid to have a good visual representation, so size always changes. What doesn’t change is the contents (the numbers). Since i’m too lazy to apply OCR on it, I needed to resort to the other thing that is constant. The color of the characters. Each cell has a different dominant color if we don’t count gray. But how do we do that?

Last time we parted ways I explained, that in order to tackle grids of various sized, I needed to adapt my matching logic. At the end of that post, the algorithm did the grid detect just by getting the cell size, than scaling the matching template, and dropping down the matching threshold to 60. Obviously that wasn’t an elegant solution, plus it didn’t work in all cases. It is time to change that!

Let’s consider these input images. For the sake of simplicity i kept the windows the same size (also it looks better this way). In real life we can even get smaller grids and in the 30X24 case, that can really be problematic. But let’s jump into it, shall we?