最近闲来无事，又一直喜欢写点小游戏，于是就瞄上了扫雷。原本只是想写个控制台版的自己玩玩，但想想貌似自动解扫雷也不算太难，至少我自己玩的逻辑是可以用算法描述的，所以就开始着手写一个可以解扫雷的代码。刚开始的时候还没有打算真实的玩windows的扫雷，因为数字识别的部分的确有点难度，于是先花了一天左右的时间学怎么控制鼠标和处理图像。

下面我给大家讲一下这个扫雷机完成的过程。第一步，写一个控制台版模拟扫雷小游戏。第二步，将自己玩扫雷的逻辑用代码表述出来，并检验是否能够成功。第三步，玩扫雷的逻辑已经有了，只需要将第一步中小游戏模拟鼠标单击并返回桌面数字的代码，替换为真实的鼠标点击和读取图片识别数字，那基本就完成了。

用于我本人用的是python写的，所以在这里不打算将源码全部贴出。改为使用伪代码描述算法逻辑，只要理解了算法，自己实现比照抄代码更有成就感，而且我自己的代码因为任务简单且当时考虑不够周全，有一些需要重构的地方，我也不好意思发出来让大家见笑。很多人问我python和java的区别，其实扫雷里面用到的逻辑，java都是可以实现的。我使用python只因为python的列表表达式对list的各种操作较java方便一点。

下面开始讲第一步：写一个模拟扫雷小游戏由于模拟扫雷不需要真实的GUI，所以可以省去很多工作量。大部分可以由文字表述的游戏，我都只用控制台实现。这一步应该很多人都接触过，我昨天还看见有人发帖问扫雷怎么写。这里需要一个Game类的对象以及以下的方法：
void createNewGame( row ,column,mines){
//创建一个新的游戏
this.field=new int[row][column] //真实的雷分布数据，0-8表示周围的区域雷的个数，9可以用来表示雷，因为平面扫雷中不会出现9
this.mask=new int[row][column] //玩家可见的层，初始化可用0-9以外的内容填充，python中我用'-'表示未点击格
//布置所有的雷
setMines(mines)}
void setMines(mines){
//设置一定数量的雷，如果想保证玩家第一步不至于点到雷，可将第一步的位置传入，将此位置从可布雷的区域排除
for 0-mines{
//生成一个随机位置，此算法参考扑克牌发牌算法，使用一维数组来表示所有的可用位置，每次随机取一位，并将该值从数组中移除
//将布置雷的位置周围的数字加1，注意边界检查以及避免修改原本是雷(9)的格子
}
}
int[][] getMask(){
//返回游戏的当前分布
return xxx}
至以上，一个模拟的扫雷游戏就已经初始化好了

再写一个单击和双击的方法：
单击和双击模拟就写好了，如果有兴趣，可以直接使用控制台开始玩模拟扫雷了，当然，最好加上一个显示mask的方法，方便自己看游戏进度

下面开始第二步：根据上面的mask解一个扫雷游戏，即计算出下一步点击哪里玩过扫雷的人都了解，当游戏上的信息完全无法推理出新的信息时，随机是唯一的选择。所以这里必然会使用到随机，这也是唯一可能导致游戏失败的地方。当扫雷的雷分布越密集，可获得的数字信息就越少，且随机失败的概率就越大。比如同时出现两处二选一的情况，胜率立马变成1/4.这也是为什么高级非常难的原因。目前我的解法在解初级9*9（10雷），中级16*16（40雷）的胜率在80-85左右。但高级16*30（99雷）的胜率不足15%。如果再加上图像识别误差导致的失败，这个胜率会更低一点。如果有哪位能在不影响算法效率的情况下明显的提高高级的胜率，欢迎大家分享

各位稍等。。讲起来东西有点多，请耐心等待

现在来讲解较为复杂的strategy3中的逻辑：当两个数字周围存在共有空白区域的时候，可以通过两个数字的大小等信息推断出新的信息（这两个数字可以不是紧邻着彼此，比如隔着一个格子也可以满足条件）
这里有两种情况，分别对应确定雷和排除雷的逻辑。情况1：排除雷，如果出现如下图所示，“-”代表为点击
0 1 -
0 1 -
0 3 -
图中的两个1，我用1(0,1),1(1,1)表示，这两个数字的共有区域为same=[(0,2),(1,2)].且 len(same)>0 and len(same)==len(empty((0,1)))用文字描述，即(0,1)周围的雷只能分布在两个数的共有区域。即共有区域的雷个数为1。由此可推断出，当 mines((1,1))-mines((0,1))==0 and len(same)>0 and len(same)==len(empty((0,1)))时，所有的（1,1）周围非共有区域都可以排除
情况2：
0 1 -
0 2 -
0 3 -
与上一种情况略有不同，1(1,1)变成了2(1,1).这时，mines((1,1))-mines((0,1))==x and len(empty((1,1)))-len(same)==x (x可为任意数字，即表示这两个等式的左边计算结果相等，此例中，x=1)，可推断出2(1,1)周围的非共有区域都是雷用文字描述为：same中最多只可容纳一颗雷，所以2(1,1)的剩余1格区域必然是一颗雷，此情况可推广至剩余x颗雷

以上，根据扫雷的局面来推理和解题的逻辑已经实现，如我之前所说，此解法的胜率依赖于游戏的雷分布密度，雷数量越多，分布越密集，解题效果越弱。
最后进行最后一步，将game.click替换为真实的点击方法在java中，可使用继承，直接重写click方法，rightclick可以不用重写，因为在mask上标记为雷就可以获得相应信息，避免在桌面上的右击，且不影响游戏结果其他语言中，可将方法作为参数传入solve方法，不过推荐使用面向对象的方式，将一些彼此不公用的参数分开设置

现在即将讲到最难的部分，涉及的内容也最多，就是数字图像的识别。首先，我们需要获取游戏上可点击位置的参数，比如扫雷的可点击区域左上右下角的坐标。这里由于游戏窗口的大小以及游戏的行列数据是可以人为控制的 。所以只要将这些需要事先获取，并写入代码中即可。我并不想在图片边界识别上花太多功夫，毕竟我们的目标是扫雷。其次，扫雷可能出现的图片单元较为单一，1-8的数字，代表0的白色空格，代表未点击区域的蓝色空格和两种颜色的雷。所以我们的目标就是写一个方法能够区分以上的12类图片。这里称之为12类是因为如果你仔细观察，就会发现扫雷上的图片之间并不是完全相同，加上我们的人工裁剪误差，即使人类可以一眼分辨的两个同类图片，他们的数据上的差异也会非常的明显。例如蓝色的空格中左上角的颜色最浅，右下角颜色最深，这会导致很多不必要的麻烦。

对于图片的识别，直观的角度上来讲，将获得的图片与已有的训练集图片进行比较是最容易理解的。所以第一版我也是这么做的。当然裁剪图片二值化以后的数据与训练集图片的数据不可能完全一样，这里我们就需要知道怎么计算两个图片之间的差距。当一个图片出现，我们计算出它离哪个训练集的图片越接近，那它越可能是对应的数字。这里需要先介绍一下汉明距离。这个一般是用来计算两个字符串之间的距离，即通过越少的改动将一个字符变成另一个字符，那这两个字符就越接近。（具体算法请百度）

接下来，需要对裁剪的图片做预处理并转化为只包含01的二维数组。这个二维数组组成的数据可以转化为一维数组并作为特征值用于汉明距离的计算。第一版的图片识别就是使用这个数据进行计算的。在裁剪图片的方面，我推荐裁剪的尺寸尽量的小，因为扫雷上的图片由于各种原因，存在一些阴影和黑色边框，这对我们来说都是噪音。所以我是按照整个黑框大小的80%进行裁剪的。先将图片压缩一下，大小可根据个人喜好。第一版的压缩尺寸是12*12.然后将图片灰化，python可以直接convert("L")然后getdata()。java也可以读取rgb值手动计算灰度,公式参见百度。这个时候我们获得了所有的数据点的灰度值。但这还不满足二值化的数据。现在考虑将数据转化为01。这里的方法是计算出整个图片的灰度平均值。将大于均值（颜色浅）和小于均值（颜色深）的分别记为1和0.但在这里需要注意一下，这个平均值并不能告诉我们关于图像数字的任何信息，且对于图片灰度值分布较集中的情况，会存在大量小于均值的噪音数据。这是我们需要避免的。所以我的做法是在均值上减去一个固定值作为阀值，当数据灰度小于这个阀值，说明图像的像素颜色足够深，这样的点才是我们需要保留的。这样可以过滤掉很多颜色稍微淡一点的噪音。

这样我们的预处理就完成了

有了这个01数组，我们可以开始收集训练数据了，手动点开一个扫雷，然后随机点开几个格子。调用已经写好的截屏裁剪方法，获取我们需要的那些图片。这些图片就是数字识别的训练数据。在游戏初始化时，将训练数据图片读取并预处理成二维数组保存到内存中。在游戏中，每截取一个图片，就将新图片处理成二维数组，并与训练数据中的所有图片的二维数组进行汉明距离的比较。最接近的那个最有可能是正确的数字。但这个方法有一个明显的缺点，这个二维数组的大小需要适中，设置的太小，容易导致不同图像的二维数组非常近似，例如1和2（扫雷的1上下两个横线长的吓人，非常容易与2混淆）。设置的太大，又导致数组的长度较长，而汉明距离的算法里涉及到大量的递归，数组由10*10变为12*12的时候，速度将慢超过50%。基于以上两个问题，最终这个版本的数字识别效果不算太好，首先是慢，识别一个9*9的局面，由于需要将所有图片与训练数据对比，所以耗费时间较长。大概需要10s以上。其次是准确率不高。包括但不限于上述的1和2混淆的问题。

由于对已有的识别速度和准确率不满意，我就去百度一下数字图像识别的算法。发现有一篇不错的论文。h啊哈tt啊哈p://wenku.baidu.com/view/fea1f83043323968011c925c.html%C2%A0这里面描述的切割法和边缘跟踪法给了我一些启发。这里我们先总结一下前一个识别算法的缺点：1。数组太长，速度慢 2.因为我们统计的是所有的像素点，所以导致单个图片的误差会很大，某个图片可能与其他数字的图片更加接近。针对这两个缺点，那现在最好的改进方法就是缩小特征值的个数，并且让不同数字图像特征值之间的差异足够大。这里我们参考切割法并加以利用，切割法的做法是从图像的中心，做x轴y轴的垂线，看两条垂线与图像的交叉点。并根据图像长宽和交叉点个数来区分数字。但考虑到单条垂线的交叉点数据存在重复的情况，例如 3 2 5 ，这3个数的交叉点一般都是3,1。所以我的想法是，两个轴分别使用两条垂线计算交叉点。并且垂线位置可自由调整。最终确定的是x轴上图像1/3点和3/5点做垂线，y轴上1/4和3/4等分点做垂线。到这里，可以使用训练集图片获得每个数字与垂线交叉点的特征值了。

如上图，4的特征值可以表述为(2,2,1,1)

将这个特征值代替之前的二维数组完整数据，可以将特征值的计算量从144缩短为4个。这样汉明距离的计算速度提高了不止10倍。不过到这里还不算完全成功，在实际使用中，我又发现，由于人为坐标测量的误差和裁剪压缩的误差，这4个值仍然不能保证数字的准确识别。因为有可能图像偏差了一个像素，导致了交叉点的个数发生了变化。也说明目前的训练集特征值之间的距离还不够分散，导致很小的误差就会识别错误。如下是我这里的训练集特征值数据
#1:1 1 1 1
#2:2 3 1 1
#3:3 1 1 1
#4:2 1 2 1
#5:3 2 1 1
#6:3 3 1 2
#7:2 2 1 1
#8:3 3 2 2
从上述数据可以观察出，最容易出现混淆的就是1 和3。1和4。6和8这些数字之间。因为这几组特征值之间的差距也只有一个数字的误差。所以，在这个特征值的基础上，我们需要增加特征值的差异性。而图像的形状是一个非常好的差异。于是我尝试使用像素点的分布来构建特征值。以图像的中心为原点构造坐标系，统计出4个象限的有效数据点个数，然后把4个象限的个数排序。返回类似1234这样的数字。这样，我们就获得了一个描述图像形状的特征值，碰巧，这个特征值可以很好将13,14,68这些数字区分开来。

到这里，特征值的构造已经全部完成，但是在使用中，我们仍然需要注意到那些识别错误的情况，因为训练集图片仍然是有人为误差的。不过我们可以在不断的游戏中加入新的训练集数据来让我们的数据更加准确。最终我的训练集数据中包含如下数据。其中最常见的1234数字的特征值存在多个，因为这样可以保证出现误差时，仍然确保图片与同一类图片更加接近
#训练集数据，通过预先获取对应数字的图片，或在识别过程中发现误差，将新的记录加入到训练集中 c_map={"11111320":1,"21111320":1,"23210312":2,"23110321":2,"33110213":3,"33112031":3,"33112013":3,"21110213":4,"21110231":4,"33112130":5,"33121320":6,"22113201":7,"33223120":8}

以上，数字图像识别就已经搞定。至于空格和0以及雷的识别，我只做了空格和0的识别。当出现雷和对话框这种无法识别的图片时，我的程序也正好会中断，正好游戏也成功或者失败了，所以雷的识别我没有特别处理。0和空格在进行二值化处理以后，我们得到的数据基本上全部为1.因为这两种图片里面没有出现明显的文字。因此这里我们识别到是0和空格时，可以使用灰度的大小或者颜色来判断。（0的颜色和灰度都比空格要浅，空格的颜色是蓝色）