Solving Minesweeper – Part 5: Making Moves

Posted on by

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

Let me direct your attention to the lest “else if” statement. It means if we haven’t found yer any reasonable action, then we keep an eye out for a cell that has a lot of unknown cells compared to the amount of bombs it sees. In other words we look for a neighbor that has a low probability of being a bomb.

Our main function also received a lot of new code, but here it is the whole thing so we can recap a bit.

int main()
{
	cout << "Press Enter when ready!";
	getchar();
	gameHwnd = GetGameHwnd();
	if (gameHwnd == nullptr)
	{
		std::cout << "window not found";
		return 1;
	}
	RECT winRect;
	LPRECT lpRect = reinterpret_cast<LPRECT>(&winRect);
	GetWindowRect(gameHwnd, lpRect);
	int width = winRect.right - winRect.left;
	int height = winRect.bottom - winRect.top;
	if (width <= 0 || height <= 0)
	{
		std::cout << "invalid window size";
		return 1;
	}
	Mat img(height, width, CV_8UC4);
	HDC screenDC = GetDC(NULL);
	HDC dc = CreateCompatibleDC(screenDC);
	HBITMAP hbmp = CreateCompatibleBitmap(screenDC, width, height);
	HGDIOBJ old_obj = SelectObject(dc, hBitmap);
	while (true)
	{
		cout << "-------------" << endl;
		BOOL bRet = BitBlt(
			dc, 0, 0, width, height, screenDC,
			winRect.left, winRect.top, SRCCOPY);

		auto inf = (BITMAPINFO*)CreateBitmapInfoStruct(hbmp);
		inf->bmiHeader.biHeight *= -1;
		auto usg = DIB_RGB_COLORS;
		auto x = GetDIBits(dc, hbmp, 0, height, img.data, inf, usg);
		Mat bmp;
		cvtColor(img, bmp, COLOR_BGRA2BGR, 3);
		std::vector<Point> bombs, safes;
		Point guess;
		Analyze(bmp, bombs, safes, &guess);
		if (bombs.size() + safes.size() == 0)
		{
			std::vector<Point> vect;
			vect.push_back(guess);
			MakeAction(vect, 2, Point(winRect.left, winRect.top));
		}
		else
		{
			MakeAction(safes, 1, Point(winRect.left, winRect.top));
			MakeAction(bombs, 0, Point(winRect.left, winRect.top));
		}
		Sleep(500);
	}
}
  1. Get the HWND for the game window
  2. Get the rectangle in screen coordinates where the window lies
  3. Create the target image in which we will copy the desktop contents
  4. Get the device context associated to the desktop
  5. We go into a loop and do the following
    1. Copy the window region from the desktop into our target image
    2. Convert the image from 4 channel to 3 channel (we don’t need alpha)
    3. Call the Analyze method which we described in previous post
    4. If we don’t have any meaningful action to take we make our guess, if we have we proceed on making them
    5. Wait a bit then repeat

As I said in the last post, MarkAction was replaced with make action which looks like this:

void MakeAction(vector<Point>& points, int act, Point offset)
{
	for (auto &p : points)
	{
		auto mouseX = p.x + offset.x;
		auto mouseY = p.y + offset.y;

		SetCursorPos(mouseX, mouseY);
		Click(mouseX, mouseY, act > 0);
		Sleep(10);
	}
}

void Click(int x, int y, bool isLeft)
{
	INPUT input;
	input.type = INPUT_MOUSE;
	input.mi.dwFlags = 
		(isLeft ? MOUSEEVENTF_LEFTDOWN : MOUSEEVENTF_RIGHTDOWN);
	SendInput(1, &input, sizeof(INPUT));
	Sleep(50);
	ZeroMemory(&input, sizeof(INPUT));
	input.type = INPUT_MOUSE;
	input.mi.dwFlags = 
		(isLeft ? MOUSEEVENTF_LEFTUP : MOUSEEVENTF_RIGHTUP);
	SendInput(1, &input, sizeof(INPUT));
}

It’s quite simple. We go through each point. We place the cursor into the calculated mouse position. The offset is the top left corner of the game window since all our coordinates are relative to this. SetCursorPos is a WinAPI function. In the click function we contruct the input command that we will send. SendInput is also a WinAPI function. If we mark bombs then we use the right click but in all other cases we use the left click. And the result is the following video.

This looks very satisfying, although it was the only successful outcome in ONE HOUR of trying. I was literally going insane because every time it failed on a wrong guess. This game is cruel as F**K. Anyway, the app looks pretty nice. I will upload the whole thing as a file soon but i still want to improve it’s performance. Maybe next time we will talk about that. Take care!