猜雷 - putianyi889/Minesweeper-makes-me-happy GitHub Wiki
猜雷主要分为三种猜法
- 死猜：雷数已知且绝无可能避免的猜雷，遇到了应第一时间猜过去。
- 半死猜：不一定是死猜，但是也应该第一时间猜过去。
- 过程猜：雷数未知且影响猜雷策略。
- 竞速猜：竞速过程中牺牲少量胜率获得显著时间优势，或者在无法数雷时的猜法。
死猜和半死猜应无条件猜掉，一方面因为早晚要炸，早炸节省时间；另一方面猜掉它们可能提供新的判雷信息。死猜和半死猜是判雷的一部分，所以作为基础先讲。过程猜和竞速猜涉及概率计算，较复杂，仅介绍方法和若干例子。
死猜和半死猜
二选一死猜
二选一死猜的标准形式：二选一两端由雷或边界封死，见下图（图源[1]）。中腹区域或一端贴边的死猜需要三雷封死，若侧面贴边则仅需两雷。
即使没有把对侧扫完，只要确定了被封死，就形成死猜（图源[1]）。
奇数个二选一首尾相连，两端由雷或边界封死，也可以形成死猜（图源[2]）。偶数个二选一相连可以数雷解决。偶数个二选一首尾相连成环（自己把自己封死）也是死猜。
三选一甚至四选一死猜比较少见，处理逻辑也是一样，不赘述，可参考[1]。
对角死猜
对角死猜的标准形式：田字四格共两雷，四个角被雷或边界封死（图源[2]）。
对角死猜可以看作四个二选一成环形成的死猜，所以自然的，对角死猜也可以通过首尾相连等关系形成更大的死猜。
半死猜
半死猜的逻辑：若不是死猜，则A安全；若是死猜，猜A安全也是合理的猜法；总之，无论是不是死猜，猜A安全总没错。
下图（[2]）中的形状很像贴边的对角死猜。田字的右边两格至多1雷：若是0雷，则黄格安全；若是1雷，则形成对角死猜，可猜黄格安全；无论如何都可以直接猜黄格安全。
而下图（[2]）反过来了。田字的右边两格至少1雷：若是2雷，则黄格安全；若是1雷，则形成对角死猜，可猜黄格安全；无论如何都可以直接猜黄格安全。
其他死猜也可以遇到类似的情况。
半死猜和死猜都是要第一时间解决的，不要因为还有可能不是死猜就放着不管。
半死猜本质的逻辑是：安全或应猜。半死猜的结论是：应猜。所以半死猜也可以套半死猜。
例如下左图，黄格要么安全要么和蓝格形成死猜，所以这是个应猜黄格的半死猜。而下右图中，黄格要么安全，要么右侧形成下左图的形状，即应猜黄格的半死猜。所以下右图也是个应猜黄格的半死猜。
一般死猜
如果一个区域雷数固定且封闭（绝无可能获得额外信息），也形成死猜。这种局部变化丰富，出现频率低。解决这类死猜只能通过半死猜或穷举。下图是一个巨型死猜，由红绿蓝三片相互独立的格子组成。红区4雷，绿区2雷，蓝区3雷。
竞速猜
猜雷原则
-
死猜和半死猜一定要第一时间处理掉，拖延对胜率不会有任何好处。
-
一定不要猜无法提供信息的格子。尽量猜更有可能提供信息的格子。举例：开局的时候必须依赖op提供信息，而角处op概率最高，所以应当点角。
-
如果B比A安全（严格来讲是A安全可推出B安全但是B安全不能推出A安全），那么一定不要猜A。如下图，蓝格安全可以推出两个绿格安全，所以猜任何一个绿格都比猜蓝格更好，所以无论如何不要猜蓝格。
-
尽量猜可以消除死猜的格子。下图中猜黄格可以消除另一个死猜。
利用两个“一定不要”往往可以排除大量格子，剩下少数候选项，减少计算难度。下面放一些例子。
下图是一个残局，共4雷。数雷可以知道第一行前两格有1雷。
三个红格均无法提供信息，不能猜（第二条原则）。四个蓝格均存在更安全的格子，不能猜（第三条原则）。两个绿格要么都不是雷，要么是左边对角死猜的一部分，所以是半死猜，应当猜其中一个绿格（第一条原则）。
概率计算
精确计算
穷举法可以算出每种情况的概率。雷的排布符合古典概型，结合贝叶斯方法计算概率。说人话就是：
- 相同雷数的排布概率相等，不同雷数的排布概率一般不等，但是可以通过公式算出。
- 所有排布的背景概率比例等于真实概率比例。
- 所有排布的真实概率加起来等于1。
举两个简单的例子。看下图的标准拐角猜（[1]）：
这个局部一共有1种1雷排布，2种2雷排布，1种3雷排布。假设这个猜出现在30*16/99的高级且无法数雷。
- 四格中每个1雷排布的背景概率是
P1=99/480*381/479*380/478*379/477=0.10362390405； - 四格中每个2雷排布的背景概率是
P2=99/480*98/479*381/478*380/477=0.02679457149； - 四格中每个3雷排布的背景概率是
P3=99/480*98/479*97/478*381/477=0.00683966693；
所有排布的总背景概率是P=P1+2*P2+P3=0.16405271396。用每个排布的背景概率除以总背景概率就是对应的真实概率
- 每个1雷排布的真实概率是
p1=P1/P=0.63165004435； - 每个2雷排布的真实概率是
p2=P2/P=0.16332903518； - 每个3雷排布的真实概率是
p3=P3/P=0.04169188527。
验算：总真实概率是p1+2*p2+p3=1。
再看下面一个常见的过程猜。排除掉所有已知雷以后，剩下的三格有1种1雷排布和1种2雷排布。仍假设这个局部出现在高级。这个例子中我们尝试用一些小技巧简化计算。
1雷排布和2雷排布的背景概率分别是P1=99/480*381/479*380/478和P2=99/480*98/479*381/478。
已知P1:P2=381:98，又因为背景概率和真实概率成比例，所以p1:p2=381/98。又因为真实概率加起来是1，所以p1=381/479，p2=98/479。
计算的时候要注意到每个雷数可能对应不同数量的排布，如第一个拐角猜的例子。
粗略估计
在简单局部我们还可以通过穷举计算概率，遇到复杂一点的局部就只能依赖计算机精确计算概率了。在算力受限的情况下，我们只能尝试去估算概率。估算概率分为估算绝对大小和相对大小两种方式。估算相对大小用来判断有关联或者极其近似的猜法哪个更好。估算绝对大小用来判断无关联的两个猜法哪个更好。
粗略估计没有统一的方法，只有一些常用的套路。
- 如果n格总共只有1雷或者不到1雷，那么必然有某一格是雷的概率小于等于1/n。
- 若全局密度为p，一个区域不同雷数的排布，每多一个雷，概率约变为p/(1-p)。
- 如果一个局部有许多种雷的排布，但是一旦定下一个雷就可以锁定一种排布，那么这个大概率不是雷。下图中的高级局部，一旦绿格是雷则整个局部雷的位置全部确定，所以绿格大概率不是雷。软件计算出绿格安全概率超过90%。
综合炸率和提供信息，猜雷优先级为：雷数已知的封闭区域（死猜）>雷数未知的前沿区>雷数已知且密度超低的前沿区>点角>雷数已知且密度一般的前沿区。如果同时存在多个雷数未知的前沿区，依据上面的第三条套路，比较各个区域雷密度，密度越高的少雷概率越高；比较各区域最低密度和次低密度排布灵活程度，最低密度排布越多则少雷概率越高。
- 雷数已知的封闭区域和前沿区一般都可以通过穷举解决。
- 雷数未知的前沿区，猜雷数最少，可推出一些格子不是雷。
每猜测一个格子不是雷，需要检查猜雷的第2、3、4条原则。对于第三条原则，当用这格不是雷可以推出其他信息，其他信息又可以推出其他信息，形成一条链时，猜链的末端最安全。
例1
如下是高级局部。
首先把前沿区分成互不相关的两部分（黄和蓝）。黄色区域共9格，有2种3雷排布和1种4雷排布。蓝色区域共7格，有2种3雷排布和3种4雷排布。显然对于高级雷密度而言，黄色区域和蓝色区域都倾向于3雷，但是因为蓝色区域4雷排布种类更多，会导致蓝色区域3雷排布概率偏低，所以应当猜黄色区域3雷。
例2
如下是例1续，剩11雷。
首先用第三个原则得到所有红格不能猜。数雷，黄格共6雷，所以前沿区16格共6-8雷，非前沿区17格共5-3雷。根据非前沿区雷密度，点角出op概率较低。根据雷密度均匀分布的趋势，前沿区6雷概率高，7雷概率其次，8雷概率低。如果是6雷，那么绿格都是安全的。绿格中有一格是红格之一，不能猜；3下方三格都必须有一圈不是雷才能提供信息，价值不大；最终剩下了左边一格和右上两格。
如果猜橙格，只有出4或6才可判，而这两种情况下紫格也同时是安全的，所以不应当猜橙格。紫格出3或5可以推进，蓝格出1或3可以推进，提供信息角度它们接近，那么再考虑它们安全的概率。6雷时它们均安全，8雷概率极低，所以概率差距主要出现在7雷时，也就是要计算它们分别不为雷时的7雷排布数量。蓝格不为雷时有14种7雷排布，紫格不为雷时有21种7雷排布，所以紫格更安全。
例3
如下残局剩10雷。
首先将前沿区分成红蓝绿黄四片。蓝绿黄虽然是连起来的，但是逻辑上相互独立，其中一片的排布不会对另外两片造成任何影响，所以应该分开。
红色区域6格，含2至3雷。蓝色区域8格，含3至5雷。绿色区域3格固定1雷。黄色区域3格含1至2雷。非前沿区16格含至多3雷。因为非前沿区密度至多为3/16，其他区域的密度也会尽量趋于3/16或更低，即红蓝黄三片都是大概率取最少雷。
红黄两片最低密度都是1/3，最高密度分别是1/2和2/3，黄色区域高密度更高，所以比红色区域更倾向于少雷。蓝色区域的最低密度3/8稍高一点，但是其他两个密度4/8和5/8差距不大且4雷分布有很多，所以蓝色区域少雷倾向性最低。
无论如何，红黄蓝三片的少雷概率都是相当高的，显著高于绿色区域的2/3。非前沿区安全的概率也相当高，但是更难提供进一步信息。
软件计算出黄色区域1雷概率86.12%，红色区域2雷概率80.14%，蓝色区域数字4的左侧和右上是雷的概率都是77.95%。