自动扫雷

King

突然有种把小时候玩过的游戏们写成代码的冲动，但是实现个单纯的游戏实在无趣，大部分都是画界面的活，对基本的算法能力考察接近于零。于是决定实现游戏的AI，在代码中注入我曾经玩游戏时的逻辑。

某一时刻，突然想起了“扫雷”，一直被称作是经典益智游戏，时不时看到几个无聊的同学会在实验室没法联网的xp古董机上面兴趣盎然地扫雷。打开电脑，惊奇地发现win10居然不带扫雷，无奈之下只能另觅他处。于是惊喜地发现之前只是装着玩玩的xp虚拟机终于派上用场了，不光能玩扫雷，直接把虚拟机里的exe拖到win10下面居然也能跑起来。想想也对，向后兼容嘛。

成果

高级模式

英雄榜

介绍

扫雷是Windows平台下的经典益智游戏。要顺利完成游戏，必须要有缜密的逻辑能力，很多时候还需要一点运气。

内存读雷法

通俗地讲就是“作弊”，顺着进程去读取游戏中雷的分布数据。

这种方法效率最高，且成功率100%，再难的局也能从容应对。不过这么做显然失去了游戏的乐趣，等于变魔术的人找了个托，骗骗外行够用，自己本身并没有太大的成就感。

逻辑扫雷法

模拟人的逻辑推理，找出未知块中一定是雷和一定非雷的块，将非雷的块都翻开，再重新分析新局面，直到找出所有的雷。

缺点是总会产生无确定安全块的局面，即剩下的所有块都有是雷的可能。这种情况下可以参考“人品避雷法”和“概率蒙雷法”。

人品避雷法

随机点击未知块，凭借强大的人品完美的避开所有雷块获得游戏胜利。

这种方法获胜概率不高，但玩游戏的代价也极低，完全不用动脑，且理论上确实存在获胜的可能性。

概率猜雷法

适合与逻辑判断法混合使用以达到最佳效果。很多局面下无法明确雷的具体分布，但是各个位置上有雷的概率（以下简称“雷率”）往往是不同的。考虑以下简单局面：数字“1”周围8个未知块，数字“7”周围也是8个未知块，两部分未知块间并无交集且暂无其他有效信息——虽然这16个块都有雷的可能，但是显然点击“1”的邻块较为安全。每次选取未知块中雷率最小的并点击。

需要说明的是此法无法保证100%，只能通过概率的推算提高大样本数据下的胜率，单独一盘游戏的某个局面完全可能存在“雷率最小的块是雷”这一事件，所以还是只能叫“猜”雷，而不是“扫”雷。

此法需要强大的排列组合推算能力，技术含量极高，据说是微软的面试题。我勉强可以推算出一些简单情况的雷率，对于复杂情况无法估计，也很难编程实现。当然也有“所有未知块是雷的概率完全相等”的情况，例如开局或者盘末的“生死雷”（如图），这时请继续参考“人品避雷法”。

分析

谈回“扫雷”本身，既然是个游戏，则必然有其内在的逻辑，把逻辑转换成代码就能完成自动扫雷，当然逻辑的转换完成度决定了算法的优劣以及游戏的胜率。其次，图像识别也是其中的关键，既然咱不屑去读内存，必然只能通过GUI，即扫雷的窗口获取当前局面信息。

考虑采用“逻辑扫雷法”和“人品避雷法”，整个流程大致思路如下：

获取当前局面；
建模后在未知块中选择所有必非雷的块，若无此类块，则在未知块中选择一块除必雷块外的随机块；
点击所有选中的块；
判断当前局面是否结束（胜利或失败），若未结束则返回步骤1。

局面分析

其中2是整个AI中的关键一步，若能在算法中注入所有人类能做出的推断，则称得上是个完美算法。接口的输入为局面信息，输出为三个集合：未知块必雷集合，未知块必非雷集合以及余下未知块集合。

线性方程组

考虑其细节实现，已知信息为已知块中的数字，其意义为已知为中心的九宫格（边角超出部分不计）中的块中雷的个数。这显然是个数学问题，如果把位于第(i)行第(j)列的块作为一个未知量(x_{ij})，很容易想到根据每个已知数字都可以列出一个不定方程。

(x_{01} + x_{02} + x_{10} + x_{12} + x_{22} = 4)
(x_{10} + x_{12} + x_{22} + x_{31} + x_{32} = 4)

这样列出的若干个方程似乎已经包含了局面已知的所有信息。一开始觉得这不就是解个线性方程组么，高斯消元法一下就搞定了。试着解一解才发现事情并没有想象中那么简单，因为还有一个隐藏的条件并没有用上——每个(x)的取值只能是(0)或者(1)。我们在构造线性方程组的时候并没有限定未知数的取值，所以要加入这个约束。是否可以构造一些新的线性方程组来间接约束(x)只能等于(0)或者(1)？考虑后得知这并不容易，因为我们都知道，线性方程组的解的情况只有三种——无解、有唯一解或者有无穷多解，并不可能构造一组n元的线性方程组有(2^n)个解。于是因为少了一个约束条件导致解线性方程组方法失效，其只有在唯一解的情况下可以求出这个解，即只要有一个未知块不确定，该法就不适用，而基本上每个局面都会有无法判断的未知块。

SAT

需要解决的问题是给出一些未知bool变量和若干个与这些变量有关的等式，需要给这些变量一一赋值，以满足所有等式，有一定算法基础的人不难联想到这是个SAT问题。SAT问题是个经典NP完全问题，这似乎意味着高成功率的自动扫雷无法实现？但是扫雷的逻辑看起来很简单，且数据量很小，通过搜索+剪枝应该也能完成这个工作。通过查找相关资料并自己分析，发现可以尝试着解决SAT的子问题2-SAT。

2-SAT问题在参加ACM竞赛时有过了解，也做过几道模板题。与它的父问题SAT的区别是他的判定式通常最多只含有两个未知变量，且常以bool运算的形式存在，常见的有 (xland y = true)、(xlor y = false)、(xoplus y = true)，(lnot x = false)等。通过式子可以在两个元素间建立一定联系，如当(xoplus y = true)时可推出两个逻辑命题：

(xtolnot y)
(lnot xto y)

在扫雷问题中，我们也可以从已知信息中推出一些逻辑命题，将SAT“转化”为2-SAT问题，使之存在多项式时间复杂度的解决方法，主要是以下8类：

(数字-周围已知雷数=周围未知块数Longleftrightarrow周围未知块均为雷)
(数字-周围已知雷数=0Longleftrightarrow周围未知块均非雷)
(数字-周围已知雷数=周围未知块数-1Longleftrightarrow当周围未知块中某一块非雷时，则剩余块均为雷)
(数字-周围已知雷数=1Longleftrightarrow当周围未知块中某一块为雷时，则剩余块均非雷)
(雷总数-已知雷数=未知块数Longleftrightarrow未知块均为雷)
(雷总数-已知雷数=0Longleftrightarrow未知块均非雷)
(雷总数-已知雷数=未知块数-1Longleftrightarrow当未知块中某一块非雷时，则剩余块均为雷)
(数字-周围已知雷数=1Longleftrightarrow当未知块中某一块为雷时，则剩余块均非雷)

看起来似乎把这个SAT问题转化成了P问题，难道网上那些“扫雷是NP完全问题”的证明是错的？其实不然，这8个逻辑命题并没有涵盖所有的信息，即存在某种情况理论上可以推断出的雷我们却没有将它注入算法中。举个简单的例子：

(x_1+x_2+x_3+x_4=2)
(x_1+x_2+x_3+x_5=3)

逻辑正常的人类不难作出(x_4=0)和(x_5=1)的推断，但是参照之前的转化方案，我们无法将第一个式子转化为有效且简单的逻辑命题，因缺少了部分信息而导致无法作出正确推断。或许可以说“当其中任意两个为雷时则剩余两个均非雷”，这是个正确的推断，但这只是考虑等式右边为2的情况，还需考虑3，4，5等更大数字，无疑会大大增加算法时空复杂度和编码复杂度。

实践证明以上8条逻辑推断对于一个并不追求完美的算法已然够用。

随机扫雷

当局面焦灼时，即无非雷块可选择时，则不得不采用随机数大法，从未知块中随机挑选一个，把命运交给老天爷。

实践证明这个方法在初级和中级的扫雷中屡试不爽，完全够用，但是到了高级就没那么幸运了。

图像识别

这看起来似乎是个麻烦的模块。我需要程序知道每个数字长啥样，然后告诉分析模块当前局面是什么以便他作出推断。截屏再做数字识别？好像工程量略大，我并不需要通用的AI，只要能在我的电脑上跑起来就行，直觉告诉我应该可以偷偷懒。

Win32的API给我们提供了很多接口，可以获取某个窗口的句柄，也可以获取屏幕上某点的RGB值。不难想到可以先通过像素点获取局面每一格的信息，再抓住各格的不同特征来获取当前格内的信息。不难发现，每个数字颜色不同，在某个相对位置，我们可以在几个拥有特殊RGB值的像素点上作文章。

执行动作

这其实相当于UI，是向外界展示我的算法成果，即可以实现鼠标自动点击。这看起来最厉害，意料之中的是，这是最简单的，同样是直接调用Win32的API对某个像素点实现自动点击功能。

需要说明的是，完整的扫雷动作库其实应有左键单击，右键单击，左右键一起单击等，而我们的目的是获得游戏胜利，右键标雷等功能对人可能有用，但对程序来讲无任何帮助，故程序只实现了左键单击功能。

实现

数据结构

对局面的存储，主要用两个值来表示每个单元格，一个bool值表示是否被翻，一个int值表示具体的值。

算法

采用经典的2-SAT算法模型构图，把每个单元格拆成两个点，必雷点(x)和非雷点(x’)，对于每个逻辑判断添加有向边：

(x必为雷Longleftrightarrow添加x’to x边)（学过离散数学的应该明白这句话与(x’=false)等价）
(x非雷Longleftrightarrow添加xto x’边)
(若x为雷，则y非雷Longleftrightarrow添加xto y’边)
(若x非雷，则y为雷Longleftrightarrow添加x’to y边)

构图后依次判断每个未知块：

(xto x’可达Longleftrightarrow x=false)，即非雷
(x’to x可达Longleftrightarrow x’=false)，即必雷

实践发现高级模式计算时间基本都在1秒之内，所以算法时空复杂度的计算意义不大，但出于对算法的尊重，还是初步估算一下。

时间复杂度

用N表示单元格的总数，由于最后需要判断每个x和x’的连通性以及x’和x的联通性，外层复杂度为N，判断联通性时可用数组标记访问过的点，因此最多需要经过所有点N，每次局面分析的时间复杂度为(O(N^2))。考虑最多需要N次局面分析，则最坏时间复杂度为(O(N^3))。

空间复杂度

考虑用邻接表存储图的复杂度为(O(V+E))，但考虑的边数是由顶点数决定的，一个数字块最多可能产生16条推断式，即16条边，虽然很大，但也是个常数，所以总时间复杂度为(O(N))。

单元格识别

通过相关API获取扫雷窗口句柄，再通过一系列小实验得出各单元格在扫雷窗口中的相对位置和数字、空格、未知块在几个特征像素点上的RGB值。

需要注意的是Win32的API中每个GetDC之后需要DeleteDC，否则程序长时间运行后容易出现RGB值读取错误的情况，推测是每个GetDC都需要分配空间，若不Delete则在程序结束后才释放，导致分配给进程的内存不足，这个坑了我久。

点击效果

在实现时用左键双击代替单击，因为鼠标的单击效果只有在焦点指定在当前窗口时有效，否则第一次单击只能改变焦点窗口，而无法形成翻块效果。

主要代码

知识兔td>

const int ROWS = 9;
const int COLUMNS = 9;
const int MINES = 10;
const int DIRECTIONS = 8;
const int VERTEXS = (ROWS * COLUMNS) << 1;
const int DX[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
const int DY[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
RECT rect;
COLORREF (Point p) {
	HDC hdc = ::GetDC(NULL);
	COLORREF color = GetPixel(hdc, p.x, p.y);
	DeleteDC(hdc);
}
struct Point {
	int x, y;
	bool isValid() {
		return x >= 0 && y >= 0 && x < ROWS && y < COLUMNS;
	}
	void Click() {
		int X = y, Y = x;
		int beginX = rect.left + 16 + X * 16;
		int beginY = rect.top + 102 + Y * 16;
		SetCursorPos(beginX + 7, beginY + 7);
		mouse_event(MOUSEEVENTF_LEFTDOWN | MOUSEEVENTF_LEFTUP, 0, 0, 0, 0);
		mouse_event(MOUSEEVENTF_LEFTDOWN | MOUSEEVENTF_LEFTUP, 0, 0, 0, 0);
		Sleep(200);
	}
	int GetVertexID(bool isMine) {
		return (x * COLUMNS + y) << 1 | isMine;
	}
};
struct Cell {
	Point point;
	bool isCovered;
	int value;
	
	true(Covered): -1, 0, 1
	false(Uncovered): -1, 0, 1, 2, 3, 4, 5, 6, 7, 8
	-1: mine
	*/
	bool isCoveredAndSafe() {
		return point.isValid() && isCovered && value == 1;
	}
	bool isCoveredAndUnknown() {
		return point.isValid() && isCovered && value == 0;
	}	
	bool isCoveredAndMine() {
		return point.isValid() && isCovered && value == -1;
	}
	bool isUncoveredAndNumber() {
		return point.isValid() && !isCovered && value > 0;
	}
	bool UpdateCellValue() {
		int X = point.y, Y = point.x;
		int beginX = rect.left + 16 + X * 16;
		int beginY = rect.top + 102 + Y * 16;
		COLORREF color = GetColor(Point{ beginX, beginY });
		if (color == RGB(255, 255, 255)) {
			isCovered = true;
			return true;
		}
		isCovered = false;
		COLORREF color = GetColor(Point{ beginX + 7, beginY + 7});
		switch (color) {
		case (RGB(0, 0, 255)):value = 1; return true;
		case (RGB(0, 128, 0)):value = 2; return true;
		case (RGB(255, 0, 0)):value = 3; return true;
		case (RGB(0, 0, 128)):value = 4; return true;
		case (RGB(128, 0, 0)):value = 5; return true;
		case (RGB(0, 128, 128)):value = 6; return true;
		case (RGB(128, 128, 128)):value = 8; return true;
		case (RGB(192, 192, 192)): break;
		default:
			//printf("(%d, %d, %d)n", GetRValue(color), GetGValue(color), GetBValue(color));
			return false; break;
		}
		COLORREF color = GetColor(Point{ beginX + 7, beginY + 8 });
		if (color == RGB(0, 0, 0)) {
			value = 7;
		}
		else if (color == RGB(192, 192, 192)) {
			value = 0;
		}
		else {
			return false;
		}
		return true;
	}
};
struct MineSweeper {
	vector <vector<int>> Graph;
	vector <Cell> cells;
	MineSweeper() {
		cells.resize(ROWS * COLUMNS);
		Graph.resize(VERTEXS);
		for (int i = 0; i < ROWS; ++i) {
			for (int j = 0; j < COLUMNS; ++j) {
				cells.at(i * COLUMNS + j) = Cell{ Point{ i, j }, true, 0 };
			}
		}
	}
	Cell GetCellStatus(Point p) {
		int index = p.x * COLUMNS + p.y;
		assert(p.isValid() && index >= 0 && index < cells.size());
		return cells[index];
	}
	int Check() {
		int cnt = 0;
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCoveredAndSafe()) {
				cells[i].point.Click();
				printf("Safe Click: (%d, %d)n", cells[i].point.x, cells[i].point.y);
				++cnt;
			}
		}
		return cnt;
	}
	bool Fetch() {
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCoveredAndSafe() || cells[i].isCoveredAndUnknown()) {
				if (!cells[i].UpdateCellValue()) {
					return false;
				}
			}
		}
		return true;
	}
	void AddEdge(int u, int v) {
		assert(u >= 0 && v >= 0 && u < VERTEXS && v < VERTEXS);
		Graph[u].push_back(v);
		//Point p1{ u / 2 / COLUMNS, u / 2 % COLUMNS };
		//Point p2{ v / 2 / COLUMNS, v / 2 % COLUMNS };
		//bool b1 = (u % 2 == 1), b2 = (v % 2 == 1);
		//printf("if (%d, %d) is%sMine, then (%d, %d) is%sMinen", 
			//p1.x, p1.y, b1 ? " " : " not ", p2.x, p2.y, b2 ? " " : " not ");
	}
	void GetAdjacentCells(Cell cell, vector<Point>&mines, vector<Point>&unkonwns) {
		mines.clear();
		unkonwns.clear();
		int cnt = 0;
		if (cell.point.x == 7 && cell.point.y == 6) {
			++cnt;
		}
		for (int i = 0; i < DIRECTIONS; ++i) {
			Point p{ cell.point.x + DX[i], cell.point.y + DY[i] };
			if (p.isValid()) {
				Cell adj = GetCellStatus(p);
				if (adj.isCoveredAndUnknown()) {
					unkonwns.push_back(adj.point);
				}
				else if (adj.isCoveredAndMine()) {
					mines.push_back(adj.point);
				}
			}
		}
	}
	void GetAllCells(vector<Point>&mines, vector<Point>&unkonwns) {
		mines.clear();
		unkonwns.clear();
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCoveredAndUnknown()) {
				unkonwns.push_back(cells[i].point);
			}
			else if (cells[i].isCoveredAndMine()) {
				mines.push_back(cells[i].point);
			}
		}
	}
	void AssertAll(vector<Point> adjs, bool isMine) {
		for (int i = 0; i < adjs.size(); ++i) {
			AddEdge(adjs[i].GetVertexID(!isMine), adjs[i].GetVertexID(isMine));
		}
	}
	void AssertIfOneThenElse(vector<Point> adjs, bool isMine) {
		for (int i = 0; i < adjs.size(); ++i) {
			for (int j = 0; j < adjs.size(); ++j) {
				if (i != j) {
					AddEdge(adjs[i].GetVertexID(isMine), adjs[j].GetVertexID(!isMine));
				}
			}
		}
	}
	void Reason() {
		vector<Point>mines, unkonwns;
		for (int i = 0; i < VERTEXS; ++i) {
			Graph[i].clear();
		}
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isUncoveredAndNumber()) {
				GetAdjacentCells(cells[i], mines, unkonwns);
				assert(cells[i].value - mines.size() >= 0 && cells[i].value - mines.size() <= unkonwns.size());
				if (cells[i].value - mines.size() == 0) {
					AssertAll(unkonwns, false);
				}
				if (cells[i].value - mines.size() == unkonwns.size()) {
					AssertAll(unkonwns, true);
				}
				if (cells[i].value - mines.size() == 1) {
					AssertIfOneThenElse(unkonwns, true);
				}
				if (cells[i].value - mines.size() == (int)unkonwns.size() - 1) {
					AssertIfOneThenElse(unkonwns, false);
				}
			}
		}
		GetAllCells(mines, unkonwns);
		assert(MINES - mines.size() >= 0 && MINES - mines.size() <= unkonwns.size());
		if (MINES - mines.size() == 0) {
			AssertAll(unkonwns, false);
		}
		if (MINES - mines.size() == unkonwns.size()) {
			AssertAll(unkonwns, true);
		}
		if (MINES - mines.size() == 1) {
			AssertIfOneThenElse(unkonwns, true);
		}
		if (MINES - mines.size() == (int)unkonwns.size() - 1) {
			AssertIfOneThenElse(unkonwns, false);
		}
	}
	bool isAccessible(int u, int v) {
		if (u == v) {
			return true;
		}
		queue <int> q;
		vector <bool> vis(VERTEXS, false);
		q.push(u);
		vis[u] = true;
		while (!q.empty()) {
			int t = q.front();
			q.pop();
			for (int i = 0; i < Graph[t].size(); ++i) {
				if (vis[Graph[t][i]] == false) {
					if (Graph[t][i] == v) {
						return true;
					}
					q.push(Graph[t][i]);
					vis[Graph[t][i]] = true;
				}
			}
		}
		return false;
	}
	bool Judge() {
		for (int i = 0; i < VERTEXS; ++i) {
			unique(Graph[i].begin(), Graph[i].end());
		}
		bool flag = false;
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCoveredAndUnknown()) {
				if (isAccessible(cells[i].point.GetVertexID(true), cells[i].point.GetVertexID(false))) {
					flag = true;
					cells[i].value = 1;
				}
				else if (isAccessible(cells[i].point.GetVertexID(false), cells[i].point.GetVertexID(true))) {
					flag = true;
					cells[i].value = -1;
				}
			}
		}
		return flag;
	}
	bool FindAllMines() {
		int cnt = 0;
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCoveredAndMine()) {
				++cnt;
			}
		}
		assert(cnt <= MINES);
		return cnt == MINES;
	}
	bool RandomClick() {
		vector<Point> mines, unknowns;
		GetAllCells(mines, unknowns);
		if (unknowns.size() == 0) {
			return false;
		}
		srand(time(0));
		int r = rand() % unknowns.size();
		unknowns[r].Click();
		printf("Random Click: (%d, %d)n", unknowns[r].x, unknowns[r].y);
		return true;
	}
	void Print() {
		for (int i = 0; i < cells.size(); ++i) {
			if (cells[i].isCovered) {
				printf("?");
			}
			else {
				printf("%d", cells[i].value);
			}
			if (i % COLUMNS == COLUMNS - 1) {
				puts("");
			}
		}
	}
};

知识兔td>

后记

之前写的代码太挫，于是又重构了一遍，看得顺眼了一点。

试着拿着代码去xp的扫雷下面跑，惊奇地发现扫雷在win10下和xp下的单元格相对位置是不一样的，差1到2个像素点！更惊奇地发现Win32获取屏幕某个点RGB值的API在两个操作系统下的效率有着肉眼可见的时间差（大约100倍吧），大xp完胜！

另外xp的扫雷和win10的难度也是有差别的：同样的代码win10跑了1个半小时终于跑出一把高级，而xp下基本每5分钟就能出一把。这并不是识别模块效率的锅，而是xp下的中后期很稳，翻开大部分基本就赢定了，而win10到后面总会有那种靠人品的局面，而且这种局面下往往都是猜错的。不知这其中有没有啥不可描述的猫腻。

唯一的遗憾是数学能力实在有限，无法实现概率扫雷。

参考

经典证明：扫雷是NP完全问题

解扫雷 - 2-sat新用法

原文:大专栏自动扫雷

计算机

2022年1月23日