Java实现自动扫雷AI

0.工程源码

https://github.com/Raytto/AIforMinesweeper

由于是几年前写着玩的,代码质量比较一般。但思路和运行效果个人认为还是可以的。

1.说明

整体逻辑结构如下图。

实现了全自动玩扫雷的目的,可以主要分为三步:

  1. 识别屏幕中的扫雷窗口和游戏当前的信息(如格子矩阵大小、每个格子中的数字、旗子、还是未开状态)。
  2. 策略计算,或者找到一个一定是雷的格子,或者找到一个一定非雷的格子,或者在完全无法确定任意格子时停止。
  3. 控制鼠标将一定是雷的格子查旗,或者将一定非雷的格子点开。

经过测试,可以快速完成大部分局,但有少量的情况下确实无法确定,需要靠猜

比如上图,左下角的两个格子一定有一个格子是雷,但我们完全无法确定是哪个格子。

如果全图都只剩下这种需要猜的情况时,脚本就会停下。当然,你也可以修改脚本,让它去猜。

下面从游戏识别、策略计算、控制鼠标操作三块进行说明

2.游戏识别

2.1 自动截屏

首先用代码自动截屏,截屏的代码见工程中的这个文件:

AIforMineClearance/src/tools/ScreenShotWindow.java

并将图片保存为一个 BufferedImage 实例

代码中我设置是用鼠标大致框选一个包含扫雷窗口的区域,可以略提升首次识别游戏位置的效率

2.2 识别扫雷区域

接着需要根据截屏内容找到扫雷的区域

这块的代码在工程中的 AIforMineClearance/src/ai/Recognizer.java 文件中

由于扫雷的格子特征挺明显的:格子分割线均匀分布,且分割线的像素颜色基本一致(当时用的win7的扫雷,分割线可能会有一个像素的浮动,win10 或 xp 的扫雷就老实多了,识别分割线更容易)

所以可以用这个特征进行查找。

判断某行或某列是否有分割线的逻辑,详见函数 private boolean hasDivLine(int t, boolean isWE, boolean isSN,BufferedImage image)。大致思路是找连续的灰色像素。

并且外部再用函数 public void judgeSelectedArea() 对所有行与所有列进行遍历,找出整个雷区的分割线位置。

确定了分割线的数量和坐标,格子的数量和坐标也就容易确定了。

于是可以先生成出对应大小的空矩阵。

2.3 识别雷区矩阵信息

当我们已经确定了每个格子的坐标后,就可以容易地把每个格子的图从整张截屏中切割出来。

这是我之前切割后导出的一些格子样本(基于win7版扫雷,win10的话替换一下样本即可)。

由于毕竟是游戏程序,而非手写或者照片,识别用非常简单的方式就能达到足够的效果:

将从截屏中切割出的格子的每个像素按尺寸映射(直接按尺寸缩放)到样本图中的对应像素,计算其RGB各个分量的差值,取绝对值求和,作为一个差异度量。

对样本库中每个图都进行一次差异度量,最后取差异最小的那个图作为成功匹配图,就可以得到结果。

当时由于 win7 整个界面背景是会渐变的,由浅蓝渐变至深蓝,导致有时差异过大,而匹配错误,于是我多导出了几种颜色的格子,只要有一个能最接近实际就行。

这块代码相见 AIforMineClearance/src/ai/Recognizer.java 中的函数 private int judgeImageWithSamples(BufferedImage image)

根据之前的测试,识别几乎无误。如果有兴趣也可以再替换为模糊处理、边沿识别再匹配、或者直接神经网络等等识别方式。不过对于扫雷游戏而言必要性不大。

总之,这样就识别完成后,就获得了当前雷区矩阵大小和矩阵内容等信息。

3. 策略计算

策略计算是相对比较有趣的一块,也是我当时主要想实践的部分。

核心而言就是模拟我自己玩扫雷时的策略。

相关代码主要位于 AIforMineClearance/src/ai/Executor.java

下面一步步考虑扫雷的策略应该是什么。

3.1 直接信息

由于我们的目标是确定一块没有开的方块的内容。

所以个人选择将知识的对象确立为未开的方块。

对于一个盘面而言,未开的方块的信息由其周围八格中开了的方块提供。(其实游戏提供的剩余雷数量,理论上还能提供一些信息,但个人发现遇见的绝大多数情况下此信息并无用处,所以暂时没将其考虑在策略内)

所以可以首先将整个盘面的信息整理一下,盘中每个周围有空格的数字,都可以在用其数字减去周围旗子数量后,得到如下格式知识:

  • 未开的{A,B,C}方块集合有2个雷,未开的{A,C,D,E}方块集合有3个雷….等等

个人是采用 HashMap<String, HashMap<String, Object>> cOfdotCollection 这样的比较丑的数据结构来保存这些信息

3.2 目标信息

整理完全局提供的信息后,我们可以先看看什么是我们最后想要的信息。

遇见如图情景,我们可以容易且肯定这三个空地都是雷。这是由于中间显示3而周围有且仅有3个格子。

类似的,这种情况下无论根据中间的3进行判断还时根据两边的2进行判断,都可以确定地应把这三个格子插满旗。(白色是已打开的 0)

总之,对于信息:“n个未开格子集合且其中有n个雷”可以显然地推导出此n个格子都是雷,继而达到了找确定格子的目标,完成此步策略计算。

且“对n个未开格子集合”这样的信息,往往是直接根据盘面就可以发现的。

除此之外,还有一种可以完成策略计算的信息:“n个未开格子集合且其中有0个雷”,也可以显然地去点开任意一个格子。

比如对于上图的情况,红框格子就理应无雷,可以放心点开(虽然并不显然,因为不是直接信息,需要基于直接信息进行推导)。

3.3 信息推导

如果直接得到的信息中没有 “n个未开格子集合且其中有n个雷”或“n个未开格子集合且其中有0个雷” 两种直接可用的,则需要我们去基于已有信息推导新信息。

而信息推导实际并不复杂,且个人发现,说到底可以归纳为一种推导模式

  • 如果某条信息对应的格子集合是另外一条信息的格子集合的子集,则可以推导一条关于差集的新信息

如图

基于第二行的3,可得信息:坐下三格 {A,B,C}有2雷

基于第二行的1,可得信息:{A,B}有1雷

两个信息满足子集条件,则可以作差得到新信息:{C}有1雷

又如上图

已知信息1: {A,B,C}有1雷

已知信息2:{A,B}有1雷

满足子集条件,则可以得到新信息:{C}有0雷。

如果这样推导后,得到的新信息满足目标信息格式,则可以直接用结束推导。

但有时,一次推导得到的信息依旧可能是不可用的,比如已知信息1: {A,B,C,D}有2雷,信息2:{A,B}有1雷,满足子集条件,可以得到新信息:{C,D}有1雷。无法直接使用,但没有关系,我们把这条新信息加入原有的信息集合,并使其和所有信息配对,很可能就在多次推导之后得到可用的信息。

如果某次完整的两两匹配都没有成功推导出新信息,并且也无可用信息,则意味着陷入类似二选一的命运局,也或者可能是已经玩完,不剩未开的格子了,总之这时候停止程序即可。

个人尝试下来,这种逻辑简单粗暴,但实则非常有效。主要扫雷确实也不是一个太策略的游戏。

4.控制鼠标操作

这块也不复杂,主要就是将格子的逻辑坐标转化为屏幕坐标,再调用 Window 提供的 API 操作即可。

相见函数 private int execute(int i, int j, int howToPress)

发表评论