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);

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.

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.

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];
				};
			}
		}
	}
}