|
[技术]基于新判雷算法的猜雷次数计算 (3/1569) |
|
|
|
|
摘要：分析了判雷的本质及其充要条件，提出一种多项式时间复杂度的判雷算法，并给出证明。基于新的判雷算法仿真计算随机雷图的猜雷次数。结果表明，由最大OP处起手的无猜率约为12%。
关键词：判雷算法、猜雷次数、矩阵论
0 引言
判雷算法一直是研究的重点。文献 在2007年提出减法公式。文献 在2009年提出高级的99颗雷非运气完成的成功率在38.7%这个结论，但是没有给出具体算法。文献 使用计算机实现减法公式，制作了自动扫雷机，并成为一个较好的范例。文献 作为经典教材之一，首次引入并分析了死猜的条件的问题。
猜雷次数是雷图的重要特征值，对于给定的雷图，理论最小猜雷次数虽然是可以用深度优先搜索算法计算，但是由于这种算法的计算结果是后验的，与人类实际操作相差甚远，所以价值不大。综上，猜雷的策略问题还有待本领域高手提出宝贵意见。
1 一种多项式时间复杂度的判雷算法
长久以来，我们关于判雷的数学原型问题争论不休。雷网有观点认为判雷是集合论（或离散数学）领域的问题，并提出各种集合相交的模型。这种方法的优点在于适合人类使用，有利于竞速；缺点在于其方法具备必要性而缺少充分性。
另一边，开发游戏的程序员大多认为判雷是整数规划的问题，可以采用枚举法或分支定界的方法。这种方法的优点在于百分之百能判断雷局是否可判；缺点在于算法的设计者误认为判雷是NP难题，给出的算法的时间、空间复杂度也均为O(2^n)。
作者认为判雷的本质是求解欠定线性方程组，属于线性代数（矩阵论的基础部分）的问题，且由于具有极其特殊的约束，存在多项式时间复杂度的算法，给出具体步骤如下：
Step1：对于给定的雷局（指部分解开、部分未解开的雷图），设解开的位置的值为xi,i=1,2,…,n，其中xi=1代表为雷，xi=0代表不为雷；
Step2：为雷局所有数字bi,i=1,2,…,m列写方程，设方程的系数矩阵为Amn¬，可得到AmnXn=Bm；
Step3：对[A_mn⋮B_m]做初等行变换，使其变为行最简式[A ̃_mn⋮B ̃_m]，则仍有A ̃_mn X_n=B ̃_m；
Step4：遍历[A ̃_mn⋮B ̃_m]的每一行，若b ̃_i>0，则记a ̃_i中大于0的元素为a ̃_(i,ti)，a ̃_i中小于0的元素为a ̃_(i,qi)，若SUM(a ̃_(i,ti) )=b ̃_i，则称a ̃_i x_i=b ̃_i为可判雷方程，此时可解出xti=1，xqi=0，可判断xti对应的位置为雷，xqi对应的位置不为雷；若b ̃_i<0，同样记a ̃_i中大于0的元素为a ̃_(i,ti)，a ̃_i中小于0的元素为a ̃_(i,qi)，若SUM(a ̃_(i,qi) )=b ̃_i，则称a ̃_i x_i=b ̃_i为可判雷方程，此时可解出xqi=1，xti=0，可判断xqi对应的位置为雷，xti对应的位置不为雷。
2 判雷算法的证明
定理一：判雷等价于求解方程AmnXn=Bm, s.t. xi=0,1。
定理一是显而易见的。值得一提的是，在大多数情况下，AmnXn=Bm是欠定的，即m<n。
定理二：能够判断xi是雷或非雷等价于矩阵[A_mn⋮B_m]能够通过有限步的初等行变换得到包含的xi可判雷方程。
定理三：定理二的否命题是成立的。
定理四：本文提出的上述方法是(能否)判雷的充要条件。
下面给出定理四的证明。
采用反证法。假设本可以判断雷而没有成功，有定理二得方程方程AmnXn=Bm可以解得可判雷方程ε_i x_i=b_i，进一步得到ε_i可由A ̃_i线性表达；另一方面，易得存在η_i，使(ε_i+η_i)可由A ̃_i线性表达，且η_i x_i=b_i不可判雷，则η_i可由A ̃_i线性表达。但是这不可能，因为行最简式每一行都包含一个每一列唯一的1。所以假设本可以判断雷，则必定会在行最简式中出现可判雷方程。另一方面，假设在行最简式中出现可判雷方程，则必定可以根据可判雷方程判雷。
上述证明可能比较晦涩，为便于更多人更好的理解，作者在附录中还给出了一个具体的例子。
3 猜雷次数计算方法
首先给出猜雷的定义：猜雷是指在缺少剩余雷数的信息的条件下，对给定雷局采用本文方法或枚举法进行判雷后，无法解得非雷位置时，为扫开雷图，接下来采取的步骤。
本文给出的猜雷定义强调了“缺少剩余雷数的信息”，是由于这样更符合玩家扫雷时的实际情况，而不代表本文给出的算法不能利用这一信息。
在上帝视角下，对于给定的雷图，是存在最小猜雷次数的。这个次数可以由本文提供的多项式时间复杂度的判雷方法结合深度优先搜索、动态规划解出。但是这个数值没有意义，即不能用来评价雷图的难度，也不能用来评价路线的优化程度。
另一种计算猜雷次数的方法是，首先在上帝视角下选取某个起手位置（本文选取的位置是最大面积的OP处）进行判雷。在猜雷时，游戏AI从上帝视角查看雷图答案，进一步根据评价函数点击在安全的位置，然后继续判雷，直到扫开结束。这种计算猜雷次数的方法的关键，就在于采用何种评价函数。本文作者采用“最大已知位置法”选取猜雷位置，具体指：选取未知、安全的位置中，周围九格中已知是雷或非雷的格子的数量最多的位置点击。
作者在附件中给出了10张判雷、猜雷的动态图片，以佐证这种方法的良好效果。当然，这个方法（评价函数）可能并不合理。作者认为雷网的高手能够提供更合理的经验与建议。
4 部分细节
实现本文算法的代码采用matlab编写。Matlab的优点在于代码的书写速度快，缺点是需要用矩阵运算代替循环以提高速度。为证明生成雷图的随机算法的正确性，现将其中产生随机雷图的代码展示如下。这个子函数用于生成一张xx行，yy列，含有num个雷；起手位置在xxx行，yyy列的雷图。该雷图中0代表不是雷，-1代表雷。
根据目前的理论及所编写的代码，只能求得无猜的概率，以及较小的猜雷次数；而不能求出最小猜雷次数，更不能求出最大开率。
5 结语
本文给出的方法完全解决了文献中的第十七章的第2问和第5问，并有助于第7问的研究。下一步，作者在玩扫雷的同时，希望能够尝试解决文献中的第1问和第4问，或者其他有趣的问题。另外限于作者水平，有些观点不一定正确，诚恳地希望读者批评指正。
参考文献
李峰.扫雷等式（进阶推理理论基础）[EB/OL].http://www.saolei.net/BBS/Title.asp?Id=210,2007-5-6.
袁飙.扫雷高级不同雷数下的成功率统计[EB/OL].http://www.saolei.net/BBS/Title.asp?Id=4364,2009-3-16.
Vespa.自动扫雷机[EB/OL].http://www.kylen314.com/archives/762,2014-1-7.
龚秋源.推理扫雷教程——扫雷解局学[EB/OL].http://www.saolei.net/BBS/Title.asp?Id=17110,2019-2-3.
附录
原雷局如图所示
A B C D E
F 2 3 3 G
H K 1 L M
N 3 1
Q
给未知区域编码
列写行列式，如第一行代表A+B+C+F+H+K=2;列写方法是图中每一个数字对应一行，重复的删去。
计算行最简式如图；分析第一行可知，D、M、N是雷，A、F不是雷。
|
|
|
链接: https://pan.baidu.com/s/1N1g3OBz_JlX-ozry5oLDSA 提取码: ix96
|
|
来说一下我的peer review
很认真的拜读了作者的文章。作者使用的思路和另一篇文章【1】类似，使用线性方程组的方法求解。每一个解出的X都是一组解（X中只能为0或1）。然而不同于文献【1】中找出所有的解中恒为1或0的格子标记或打开的方法，作者采用了通过对增广矩阵高斯消元（即行最简形矩阵化简）（相关细节可见文献【2】的2.4）来寻找解。不难理解这种方法是一定有解得必要条件，因为X中只能有0或1，要使最简矩阵满足条件的每一行成立必须满足1的1,-1的0（或相反）。作者给出了充分条件的证明，但限于我数学水平没有完全看懂，这里提出一个疑问：“行最简式每一行都包含一个每一列唯一的1”。然而文献【2】中有的行最简式中有的列有2个1，且这个条件并不是行最简式的定义。实际上作者给的图包中，图1的第6,7,8步猜雷，图6的几乎全部，图7的1、2、6步，图8的1步都是多余的，局面上完全有很明显的解，这也从侧面说明了充分的证明有所问题。还有，扫雷求解是NPC问题而不是P问题（即多项式时间解法）几乎是数学界公认的，文献【3】作为伯明翰大学数学与统计学博士的正式出版物，还是非常有可信度的。据说某数学研究所设立了100w奖金，如果你能在多项式时间内解决扫雷求解问题的话。
而且作者仅研究了是否可解的问题，并无法回答每一格具体概率、或一次性给出局面上所有的解。
此外，作者文末的举例，最后一句话中dnq是雷而不是dmn，笔误需要纠正。另外作者一些问题解释的不是太清楚，可以加入一些图例一步步讲解更为清晰。
作为作者文中参考文献4的作者，申明一下：一是死猜充要条件我引用的张少武的知乎教程【4】，单个死猜不是我首次提的，对角死猜也许是；二是我写的教程是基于玩家而不是计算机的，无解分析、成环理论也是针对玩家而言，为可由人应用的简便方法，因此计算机解并不能说是完全解决了问题。（当然，人是有极限的，希望能有更多基于人的方法，但彻底解决必须赖于计算机）
参考文献：
1 Andrew Fowler. Minesweeper: A Statistical and Computational Analysis [D]. http://www.minesweeper.info/articles/MinesweeperStatisticalComputationalAnalysis.pdf, 2004.05.01/2018.12.26.
2 舒阿秀. 行最简形矩阵在线性代数中的重要作用[J]. 廊坊师范学院学报（自然科学版）, 2014, 14(5).
3 Kaye R . Minesweeper is NP-complete[J]. The Mathematical Intelligencer, 2000, 22(2):9-15.
4 张少武 .猜雷与收尾无脑操作的简要教程 —— 别把实力当运气[EB /OL]. https://zhuanlan.zhihu.com/p/35974785 ,2018.04.22/2018.12.23.
|
|
感谢龚大佬的评审！
进一步，感谢龚大佬指出我的研究的若干问题，及时纠正了我错误的研究方向。
通过一段时间的思考，以及对诸多中外文献的阅读，我现在可以肯定两点。第一，上述文章的所述算法是错误的，其证明有不严谨的地方。第二，扫雷的确是NP难问题，不具备多项式时间算法。
以后有空还会继续研究感兴趣的问题，当然提高扫雷成绩为主，理论研究为辅。
|
|
|
|
