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模型
|
|
|
|