如何编写一个扫雷的 AI
发表于2016-07-29
不久前，我写了一个扫雷的AI。我之前打算发表一个新手教程，无奈大学生活和各种考试过于忙碌，没有时间去写。但我刚刚结束了我的第一学期的学习，我有时间去写一个我这个AI中做了什么的正式的概述。
这是AI动作30秒的简短视频：
一、如何玩扫雷：
如果你是一个玩过扫雷的有经验玩家，你完全可以跳过这个部分。如果你没有玩过扫雷，我将会给一个快速简单的介绍，讲解一下一些我们可以用来解决简单扫雷游戏的基础攻略。
我们从10X10的新手网格开始，然后点击中间的方块：
我们可以快速地标记一些地雷。当数字“1”在一个空的方块周围时，我们可以知道这周围有一个地雷。
让我们继续标记这些地雷：
下一个攻略：如果有一个地雷与“1”相邻，那么我们可以知道与“1”相邻的其他方块都不可能是地雷。
所以，我们可以继续点击我们知道不可能是地雷的方块：
按相同做法如下做下去。在这种情况下，这两个策略足以解决新手（初级）的格子了：
二、AI路线图
所有这些看起来足够简单。这是我们接下来需要做的：
１、读取板块。如果我们用一个截屏函数，我们可以获取到在板块上所有像素的一个位图。我们仅仅需要从屏幕中去“读取”那个数字。幸运的是，数字都有不同的颜色：1是蓝色，2是绿色，3是红色等等。
2、计算。运行计算，计算出那些地雷在哪里。这里不重复说了。
3、点击板块。这个步骤比较简单。在JAVA中，我们可以用标准类库中的Robot类去发送鼠标点击事件给屏幕。
三、读取区域
这里没有太多的步骤，所以我们将快速地过一下。
在运行之前，当我们有一个完整的空格子的时候，我们调用了一个校准程序-一个可以截屏和寻找看起来像地雷格子的程序。使用启发式，糨将可以定位格子的位置和方块格子的大小，在板块的坐标等等类似的信息。
现在我们知道方块在哪里了，如果我们想读取方块的，我们剪切截屏的一小部分然后把它传到检测程序，检测程序将在这些少数的像素中计算广场中的是什么数字。
与此同时在检测中存在一些缺陷：
1、数字“1”的颜色与一个没有打开的方块的颜色非常相近：都是深蓝色。为了区分他们，我对比了斑点颜色与平均斑点颜色之间的“差异”。
2、数字3与数字7的颜色完全一样。在这里，我使用了一个简单的边缘检测程序。
四、简单算法
普通的简单算法实际上已经可以在很短的时间内很好地去解决初始难度和中级难度的关卡。有时候，如果我们幸运的话，这个算法也可以用来解决一些高级的关卡。
当人们玩扫雷的时候，我们会尽可能最快地去完成扫雷。所以我们不介意为了每个游戏的胜利而失败了20次游戏：只有胜利的才算。
这是一个非常清晰的傻瓜式衡量标准，当我们看成是一个机器人时，我们的点击速度可以像我们想像中的一样快。相反的，我们会用一个更有趣的衡量标准来挑战我们自已。
赢得更多的游戏
考虑到下面的情节：
使用简单算法，我们将会被卡住。
到此为止，每当我们标记一个方块为有雷或者安全的时候，我们只需要考虑一个3X3的大方块。这个攻略使我们失败在这里：解决窍门是使用多方块算法---一次可以读取多个不同的方块。
从最下面的2，我们可以知道在红色圈圈中的两个方块中有一个是地雷，其中一个不是地雷。我们只是不知道哪个是地雷而已：
此刻，虽然不能告诉我们什么，我们可以结合此信息下一步：我们可以推断出这两个黄色的方块是空的。（表示没有地雷）
让我们可以肯定的点击他们。
看吧， 他们是空的（没有地雷）。 这个难题迎刃而解，我们已经做了推论，这两个方块是空的。
五、坦克求解算法
我们很难可以让计算机像我们一样去推测。但这里有一个方法，可以不用推论思考也可以达到同样的效果。
坦克算法的思想是枚举所有可能的地雷位置的组合，然后看看在这些位置组合中有什么共同点。
在这个例子中，这里有两个可能的组合：
你可以为自己检查一下，这里没有别的组合可以行得通了。我们可以推测：那些有X的方块肯定有地雷，其他3个白色阴影部分的肯定没有地雷：
这个比人为推测更加有效率。
我们总是最先尝试去用简单算法，只有当我们被卡住了，我们才会使用坦克算法。
为了实现坦克算法，我们首先要做一个镶边瓷砖列表：所有我们不确定但有部分信息的方块列表。
现在我们有一个列表T。如果我们考虑到每个组合的可能性，这里有2^T个组合。利用回溯法，这些数字可以减得足够少可以为这个算法变得有实用性，但我们可以弄一个重要的最优化。
这个最优化是使这些列表分成几个不相交的区域：
如果你看得很细心，不管发在绿色区域发什么什么都对粉红色的区域发生什么没有任何影响---我们可以有效地把他们分开考虑。
我们得到了多少的速度提升呢？在这个种情况下，绿色区域有10个方块，粉红色的有7个。把他们结合起来，我们需要搜索 2^{17}组合。在分离开的情况下，我们只需要 2^{10} + 2^7次：大约提升了100倍的速度。
事实上，最优化使算法暂停了几秒的时间（有时候几分钟）去思考，然后马上给出解决方案。
六、概率：做最好的猜测
我们现在完成了么？我们的AI可以尽职地100%准确地解决我们给它的所有扫雷格子了吗？
毫不令人意外的是，不可以：
两个方块当中有一个地雷。这个地雷在其中一个方块中，存在的概率都相等。无论我们写的AI有多聪明，我们都不能在50-50的猜测中做得很好，实在抱歉。
坦克算法在这里行不通了，毫无疑问。在什么情况下使用坦克算法会行不通呢？
如果失败了，这意味着每个方块中，这里一些组合存在地雷，一些组合是空的。否则坦克算法可以解决这些特殊的方块。
换句话说，如果它失败了，我们不得不进行猜测。但在我们随意猜测之前，我们可以做一些分析，以便能够更可能地猜中。
试试这个。如下图所示：
从中间的3我们可以知道：上面3个都是地雷，然后我们可以标记。但是标记这些地雷不会给我们带来任何一些关于广场的新信息：为了获取新的信息，我们必须去打开上些方块。在这13个可能的方块中去打开它，这里我们并不清楚哪一个是最好的。
用坦克算法可以解决发现11个可能的组合。如下：
在这11个组合中的每一个组合都是等可能性的---所以我们可以为每一个方块中分配一个可能存在地雷的概率，通过计算有多少组合（在这11个组合中）包含地雷：
我们最好的猜测是点击那些标记了“2”的方块：在这些可能性中，我们有82%的机率是正确的！
七、两个残局战术
到目前为止，我们没有利用过这个家伙：
地雷数量。通常，这个信息对我们没有多大的用途，但是在一些残局中，可以保证我们猜测的安全性。
比如：
这里，我们有一个50-50的猜测，两个可能性都相等。
但如果地雷数量是1呢？此时双雷组合被淘汰了，只剩下一个可能性。我们可以安全地打开那周边的3个方块。
现在进入我们最终的攻略。
到目前为止，我们假设我们只有一个在一个数字的旁边方块的信息。大多数情况下 ，这是正确的。如果你选择了一个在一些遥远的未知的角落的方块，谁会知道那有没有地雷呢？
异常可以出现在残局里面：
地雷数量是2.每个圆圈区域里面都给我们50-50的机会---且坦克算法不能在这里用了。
当然，中间那个方块是安全的！
为了修改算法去实现这些场景，当这里没有剩下任何方块的时候，在所有保留的方块中做一个递归，而不仅仅只是边上的方块。
这两个技巧共享了一个属性：他们都依赖于地雷计数器。然而读取地雷计数器不是一个直接的任务，我不会去尝试；相反地，这个程序在编写的时候记录了总的地雷数，然后在内部记录了剩余的地雷数。
八、总结，结果和源代码
此时此刻，我确信这里已经没有可以再提升胜率的做法了。该算法利用每一块信息，然后只有当它证明地确信猜测是必要的时候才会失效。
这运行起来怎么样呢？我们会用高级关卡的胜率来作为一个基准。
简单算法不可以解决它，除非我们非常幸运。
坦克算法概率性地猜测用大概20%的时间解决他。
附加的两个残局技巧把胜率提升到了50%。
这是证据：
现在我完成了；如果谁想要这个项目的源代码，可以在Github上下载到:https://github.com/luckytoilet/MSolver