突然有种把小时候玩过的游戏们写成代码的冲动，但是实现个单纯的游戏实在无趣，大部分都是画界面的活，对基本的算法能力考察接近于零。于是决定实现游戏的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则在程序结束后才释放，导致分配给进程的内存不足，这个坑了我久。
点击效果
在实现时用左键双击代替单击，因为鼠标的单击效果只有在焦点指定在当前窗口时有效，否则第一次单击只能改变焦点窗口，而无法形成翻块效果。
主要代码
后记
之前写的代码太挫，于是又重构了一遍，看得顺眼了一点。
试着拿着代码去xp的扫雷下面跑，惊奇地发现扫雷在win10下和xp下的单元格相对位置是不一样的，差1到2个像素点！更惊奇地发现Win32获取屏幕某个点RGB值的API在两个操作系统下的效率有着肉眼可见的时间差（大约100倍吧），大xp完胜！
另外xp的扫雷和win10的难度也是有差别的：同样的代码win10跑了1个半小时终于跑出一把高级，而xp下基本每5分钟就能出一把。这并不是识别模块效率的锅，而是xp下的中后期很稳，翻开大部分基本就赢定了，而win10到后面总会有那种靠人品的局面，而且这种局面下往往都是猜错的。不知这其中有没有啥不可描述的猫腻。
唯一的遗憾是数学能力实在有限，无法实现概率扫雷。