微信红包扫雷群贴吧

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

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

例如上图，标旗的一格必定有雷，下面两格必定没有雷。

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

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

例如上图中，被分成了四个连通块，可以分别处理

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

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

仅考虑这个联通块，一共有5种可能的解，其中3种解最左边的格子有雷，概率为60%。但假设整个地图只剩下两个雷，那么大概率这个连通块中只有一个雷，所以最左边的格子有雷的概率很小

因此我们计算每格概率的时候需要考虑剩余雷数的限制。在枚举过程中，对每个联通块我们可以统计出:b谁有qq红包扫雷群lockCntsblockCnt_{s}代表这个联通块的未知格中一共有ss颗雷的方案数。对每个格子xx可以统计出:

cellCntx,scellCnt_{x,s}代表当格子所在的联通块中一共有ss颗雷时，多少种方案中xx这个格子是雷。那么我们依次考虑每个格子的胜率。除开格子本身所在的联通块不看，考虑其它所有联通块（假设一共有nn个连通块），我们可以计算出计算DPi,jDP_{i,j}代表前ii个连通块共jj个雷的方案数，这里是一个典型的背包问题，转移方程

D谁有qq红包扫雷群Pi,j=∑s=0maxDPi−1,j−s∗blockCntsDP_{i,j} = \sum_{s = 0}^{max}{DP_{i-1, j-s} * blockCnt_s}复杂度显然还可以优化，但这部分在整个算法中占比不大。假设当前剩下minemine个雷，枚举当前格子所在联通块的雷数ss，有blockCnts∗DPn−1,mine−sblockCnt_s * DP_{n-1,mine - s}种可行方案，其中cellCntx,s∗DPn−1,mine−scellCnt_{x, s} * DP_{n - 1, mine - s}种方案中当前格有雷，对这两个值分别求和，就可以得到当前格有雷的精确概率。

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

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

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

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

十元红包扫雷群

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

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

考虑一个局面S谁有qq红包扫雷群tatuStatu，它有nn个未知的格子，假设我们点击第ii个格子，我们可以计算出点击这个格子之后所有可能的后续局面，假设一共mm种可能，第jj种可能是以Probi,jProb_{i,j}的概率转移到局面Nexti,jNext_{i,j}。局面的转移关系是拓扑的，满足无后效性，因此可以用状态压缩的动态规划，WinStatuWin_{Statu}表示局面为StatuStatu时的胜率，显然有转移方程

WinStatu=max(∑j=1mProbi,j∗WinNexti,j),i=1→nWin_{Statu} =max( \sum_{j = 1}^{m}{Prob_{i,j} * Win_{Next_{i,j}}}), i = 1\rightarrow n

3.3 状态转移谁有qq红包扫雷群最后的难点是3.2中，已知当前局面StatuStatu，如何计算NextNext。对于一个局面，假设我们点开格子ii，那么那些ii格是雷的解就不用考虑了(直接失败)，对于其它解构成的集合，我们考虑剩下的每一个格子，如果一个格子在所有解中都不是雷，那么这个格子是安全的，可以点开。这时候，如果两个解这一格的数字不同，它们就必定不会同属一个局面了。那么我们把解集按这格拆分成若干子集，并对每一个子集递归处理，这样就得到了所有后续的局面。转移到局面Nexti,jNext_{i, j}的概率为局面的解数量局面的解数量(局面Nexti,j的解数量÷局面Statu的解数量)(局面Next_{i, j}的解数量 \div 局面Statu的解数量)实现这一步之后，就可以根据3.2的方程计算每一格的严格胜率了。

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

开源代码地址

微信禁抢红包群赚钱吗

https://github.com/ztxz16/Mine

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

红包群1.6倍扫雷群规

...