2013年是我高考的年份
所以在2012年的暑假我妈把家里的网给断了
所以我爱上了扫雷
2015年我写出了第一版自动扫雷代码，目的是验证逻辑可推理的极限局面。
c++写的，还不会STL，只会手撸链表，很多想要的逻辑实现起来麻烦，没有加上。
不会win32api不能读屏操作鼠标，只能在自己写的控制台扫雷游戏上呈现。
2017年寒假学习opencv，想起这茬来，幸好原来代码里留了读图的接口。写了一个粗糙的截图识图加上，在win10应用版“踩地雷”上跑起来了，高级刷到38s，怒发朋友圈：扫雷已死。
#怎么贴图？
2019年有人在知乎上邀请我回答，怎么戒掉扫雷。我回答把它解决就行了。
于是有人邀请我来这看看。
果然一个个都是人才，讲话又好听...
回首来路又看到初心，
发愿重写一个完美的自动扫雷程序，
在此立贴记录。
如有感兴趣者欢迎交流。
/****************
为避免干扰扫雷网正常秩序
我承诺：
1.机刷选手，不传录像（除非开辟单独排名的机刷区）
2.制作但不传播外挂程序
****************/
另外，谁来教教我帖子里怎么发图...
|
|
自动扫雷程序用python开发，
在扫雷网官方软件 Minesweeper Arbiter 0.52.3上运行。
我会在后面公布 <识别+操控> 接口代码，降低后来的人们开发扫雷程序的入门难度，刺激机刷扫雷事业的发展。
但完整的推理代码暂时决定不发布，只交流思想，以免有人拿来干扰手刷比赛秩序。
|
|
第一节： <识图+操作>api
自动扫雷算法：
输入：二维矩阵
输出：判定是雷/安全块，执行操作
那么自动扫雷程序首先要给自动扫雷算法提供输入输出接口
思路：
0.使用win32库
提供了windows常用api，获得窗口位置，操纵鼠标，屏幕取色都可以实现
1.识图：
经典windows扫雷的图标非常统一规整，16*16像素，可仅凭有限的像素点组合作为特征。
需要识别的图有11个：
          
程序遍历下，可知(0,0),(3,6)两点颜色可区分这11个图标，
做成dict即可简单识别。
可以使用win32gui.GetPixel(hdc, px, py )直接对屏幕取色
也可以先屏幕截图再分析。
我选用的是前者，认为效率更高。
2.鼠标操作
根据扫雷窗口坐标原点，游戏矩阵区原点，矩阵坐标，可以计算得到要操作的方块在屏幕的绝对位置
|
|
模块代码公开&说明：
链接: https://pan.baidu.com/s/1DMm1JdLYElgH8EU7dcxS2g 提取码: s3jw
import此模块，会获得扫雷窗口位置，大小。
如果没找到窗口，或者非标准 初中高级别游戏，会报错退出
未点开的方块为-1，点开的空白块为0，flag为9，其余对应1~8
供调用的函数：
showtop()
get_argument()
readblock(r,c=0)
readgrid()
flip(p)
flag(p)
clean(p)
restart()
另：
dalaytime = 0.025 #点击后的等待图像刷新的时间。设置过小会导致读图错误。
|
|
可以优化的方面：
现在对每个要识别的图标均取色两点，
实际上，一个点就能区分开8种图标，
仅另外三种需要第二个点。
先取一个，无法判断时再取另一个，是一种优化思路。
但是不能直接简单的以“让第一个点可区分的最大种类数”思路来优化，
还必须考虑到不同的点出现频率。
因此，我计划等完整逻辑编写完之后，在几局完整游戏中统计识别到各图标的频次，以决策树算法来优化识图步骤。
|
|
|
传统方法写的path、IOE等等参数一般比不过人类玩家啊。我觉得现在的前沿技术应该是用深度强化学习那种。
|
|
第二节：扫雷算法思路
太阳底下没有新鲜玩意儿，关于自动扫雷算法已经有诸多研究，
龚秋源 的帖子介绍的非常详细
http://www.saolei.net/BBS/Title.asp?Id=17576
同帖子里 第1~1.24 节所讲，
我的思路也是 [ 简单搜索 - 减法公式（类似） - 枚举剪枝 ] 三步走。
没有用到 高斯消元。
但关于减法公式，文中写：
【 减法公式亦称双集合模型。绝大部分扫雷的定式，例如边11,12公式，等等，都是基于双集合模型的，特点是只要对两个相邻的数字及其周围格子推演，就能推出哪格一定可以打开或标记，这一过程不涉及到3个或更多数字的相互纠缠。】
我的思路稍有不同，可以不只对“两个相邻的数字及其周围格子推演”（虽然大部分情况如此），而是“涉及到3个或更多数字的相互纠缠”的。
|
|
算法是基于集合的，
基本数据结构也是集合，记为Zone
1. Zone的构造 / 简单推理：
1.1 Zone构造
对于一个打开的局面，将每个数字块周边“未判定”的方块纳入一个集合zone，并记录
集合大小num，
集合中含雷数mine （数字线索减flag数）
集合中含安全块数safe （num-mine）
1.2 简单推理
当Zone满足 num>0 且 mine=0 / safe=0 时，即可用简单推理，判定zone中所有块为 安全 / 雷。
1.3 连锁反应
被处理的块（包括标旗的，点开的，被连带点开的）可能还属于其他的Zone，
对被处理的块所属的相关Zone，删除已被处理的块，
删除后，相关Zone也可能满足 1.2 中简单推理条件
即可形成简单推理的连锁反应
|
|
2. 减法公式 多集合模型（非双集合模型）
第一步完成后，会得到大量不可用简单推理的Zone，每个前沿上的未处理的块都属于一个或多个Zone
取出 n（n>1）个有重叠的Zone ∈ZC ，其交集记作common，大小记作 s
commom中可能含有的最大雷数：
maxmine = min（common大小s，ZC中每个Zone的雷数mine ）
commom中可能含有的最小雷数：
minmine = max（ ZC中每个Zone的雷数减去不属于common的方块数: mine-(num-s) ）
如果 maxmine = minmine ，则 conmon 的雷数即可确定。
则 Zone有的， common 都有了，common可构成一个新的 Zone，ZC中每个Zone减去commom也可构成一个新的 Zone。
【 Zone得自数字块，由此，Zone的概念脱离了对数字块的绑定 】
新得到的 Zone 中可能有满足简单推理条件的，可引发新一波连锁反应。
也可能没有，但是新的 Zone 可以与其他 新旧Zone 利用多集合模型推理。
因此，多集合模型推理，
不仅可以 “涉及3个或更多数字的相互纠缠”，
还涉及了 “多个推理时间步上的纠缠”
处理能力强于减法公式。
边11，12定式即可用多集合模型解释
“涉及3个或更多数字的相互纠缠”“多个推理时间步上的纠缠”的例子如有需要，后面可以给出。
|
|
续2 - 多模型集合的失败
前面1，2节内容是我2015年写第一版自动扫雷程序时的思路，基于Zone的推导。
（其实之前还有一版失败的，是定式匹配的思路）
当时我认为，确定性的推理到此为止了，下一步就能是枚举了（见龚秋源贴，枚举必不可少）。
直到我遇到了这个图：
阴影部分是点开的，线索是131，前沿方块是A~G
有兴趣的同学可以用第2节的多集合模型推导一下，是推不出来的，
原因在于,两个1与3对应的Zone取交集时，交集的最大雷数最小雷数不同，无法生成新的Zone 推动推理
而人可以轻易看出，ABC，EFG仅有1雷，则 D必是雷，AG必安全
当时写这个东西写了两个月，调通了就没心力往下捣鼓了，想着反正还有枚举兜底，就这样了。
而在2019年，我重写这个程序的时候，又有了新的东西：
非确定Zone模型
|
|
|
|
