研究背景 做这个研究的起源是一周多以前在B站上看到一个视频，是编程模拟研究扫雷的一些数据，上面提到Win7扫雷高级可以达到36%的胜率。后来看了一下代码，发现这里面只用到了一些简单的推理，逻辑不是很完善。我想我写了这么多年代码了，如果写一个逻辑更加完善的AI能不能统计出扫雷真正的极限胜率呢。 当时上网查了一下，基本都认为xp规则下高级极限胜率是38～39%，win7规则下49+% 周末的时候理清了一下思路，花一天多时间实现了一下(400+行的C++，跟我以前做ACM的时候最长的代码差不多长)，模拟自测了250000盘，胜率可以达到40.07%，win7规则下胜率可以达到52.98% 后来用系统扫雷和Arbiter做了上千盘的实测，结果都在40%以上，基本印证了模拟结果的正确性。当然这个AI还有很多参数可以调整，离真正的极限胜率还有些距离，但应该是目前世界上最好的结果了。

算法细节 1. 基本的推理 扫雷里面最基本的推理就是数雷。 如果一个格子周边没有打开的格子数 = 这个格子上的数字，那么它周边没有打开的格子全部是雷。如果一个格子周边已知的雷数 = 这个格子上的数字，那么它周边没有打开的格子全部不是雷。利用这两条规则可以在大部分情况下找出新的安全格。

2. 计算每一格有雷的概率 2.1 总体思想 假设一共有 n 个格子没有打开，那么存在至多 2^n 种可能的解，假设去除与已知格子矛盾的解后一共有 m (显然 m <= 2^n) 种可能的解。我们可以统计每一个格子在多少种解中是有雷的，然后除以 m 就得到了这一格是雷的概率。（概率为0一定不是雷，可以打开）

2.2 分块枚举 如果 n 足够小，那么直接枚举所有情况判断就可以了，但 n 比较大的时候就需要分块处理了。如果一个未知格在一个数字格周围的九宫格内，可以把这两个格子连一条边代表它们存在互相制约，连边完成后整个地图被分割成若干个联通块(有的空白格单独构成一个联通块)。不同联通块之间不存在互相制约。

这样我们可以对每一个联通块中的未知格进行枚举，大大减少了枚举量。模拟测试中，99.99+%以上的游戏都没有出现单个联通块合法方案数超过一千万的情况。

2.3 考虑剩余雷数，计算精确概率 需要注意的是，因为有剩余雷数的限制，联通块内部的概率其实是不准确的，例如

因此我们计算每格概率的时候需要考虑剩余雷数的限制。 在枚举过程中，对每个联通块我们可以统计出:

blockCnt[s] 代表这个联通块的未知格中一共有 s 颗雷的方案数。

对每个格子 x 可以统计出:

cellCnt[x][s] 代表当格子所在的联通块中一共有 s 颗雷时，多少种方案中 x 这个格子是雷。

那么我们依次考虑每个格子的胜率。除开格子本身所在的联通块不看，考虑其它所有联通块（假设一共有 n 个连通块），我们可以计算出计算 DP[i][j] 代表前 i 个连通块共 j 个雷的方案数，这里是一个典型的背包问题，转移方程

复杂度显然还可以优化，但这部分在整个算法中占比不大。 假设当前剩下 mine 个雷，枚举当前格子所在联通块的雷数 s，有 

 种可行方案，其中 

 种方案中当前格有雷，对这两个值分别求和，就可以得到当前格有雷的精确概率。

2.4 基于概率的贪心算法 这一步后可以使用贪心算法:如果没有确定无雷的格子，那么点击概率最小的格子，概率相同时先点角，角开完之后点附近5*5的地图里打开格子数最多的格子。 到这一步胜率可以达到39%了，但其实贪心的规则是可以调整的，我这里没深入尝试了，很可能存在一些贪心方法可以大幅度提升胜率。

3. 计算点击每一格的获胜概率 3.1 有雷的概率不代表胜率 我们看一个经典的例子

假设只剩一个雷。图中三格有雷的概率都是三分之一，但显然点击中间格获胜概率是三分之一，点击另外两格获胜概率是三分之二。

在一些情况下，有雷概率低的格子胜率还不如有雷概率高的格子，因此我们需要用更严格的方法计算胜率

3.2 局面表示 我们考虑用一个列表 表示每个未知格上最终的数字(或者是雷)，那么每种可能的情况称为一个解。一个局面可以表示为若干个解的集合，代表这个局面的所有可能解。例如我们用-1代表雷，那么之前的图片中

假设剩一个雷，从左到右描述每个格子，有三个可能的解：[-1, 3, 1], [4, -1, 2], [3, 3, -1]

考虑一个局面 Statu，它有 n 个未知的格子，假设我们点击第 i 个格子，我们可以计算出点击这个格子之后所有可能的后续局面，假设一共 m 种可能，第 j 种可能是以 Prob[i][j] 的概率转移到局面 Next[i][j] 。

局面的转移关系是拓扑的，满足无后效性，因此可以用状态压缩的动态规划， Win[Statu] 表示局面为 Statu 时的胜率，显然有转移方程

3.3 状态转移 最后的难点是3.2中，已知当前局面 Statu，如何计算 Next 。

对于一个局面，假设我们点开格子 i ，那么那些 i 格是雷的解就不用考虑了(直接失败)，对于其它解构成的集合，我们考虑剩下的每一个格子，如果一个格子在所有解中都不是雷，那么这个格子是安全的，可以点开。这时候，如果两个解这一格的数字不同，它们就必定不会同属一个局面了。那么我们把解集按这格拆分成若干子集，并对每一个子集递归处理，这样就得到了所有后续的局面。转移到局面 Next[i][j] 的概率为 (Next[i][j]的解数量 / Statu的解数量)

实现这一步之后，就可以根据3.2的方程计算每一格的严格胜率了。

总结 这个算法理论上是可以严格计算出扫雷胜率的，但是复杂度过于爆炸了，实际上我只能在最后状态不多的时候开启算法3的胜率计算，但也足够将胜率提升到40.07%了。虽然这应该是目前最好的结果，但大家可以看到其中很多步骤调整的空间是很大的，稍微改改可能就有不小的提升。

开源代码地址

https://github.com/ztxz16/Mine

有兴趣的同学可以随意使用，顺手给个star就更好啦。