|
[技术]python自动扫雷程序实现思路简介和结果 (11/21483) |
|
|
|
|
非读内存作弊，非xyzzy作弊，模拟真实玩家思路解决问题！
有帮助功能。可供雷友辅助游戏、学习
软件是用的Minesweeper Arbiter，能用的策略都用了：
1.开局
角上单点开局，更大概率碰到ops
2.朴素策略
这个没得说，一般都应该有的
3.定式
实现上有点难，实际代码很丑，一堆if-else，还只能用于边上1-1定式，不过没关系，我们后面的策略可以覆盖这个
4.求解策略
其实就是解非其次线性方程组。
你能看出来的它一定能看出来！
你不能看出来的它也能看出来！
5.概率分析
受不同数字块的影响，每个未知块的概率不是像我们看到的那么直观的！
感兴趣的雷友可自行百度“编程之美 扫雷的概率”
这个策略我们要做的就是，在解不出来的时候，尽可能的点击是雷概率最小的块！
目前程序运行结果：
最快速度
高级 1.43s 中级 0.24s 初级 0.08
完成率
高级 36+% 中级73% 初级75%
没测很多局，高级100，中级200，初级500。。自己笔记本渣，开概率分析有点点耗时，网费莫得了哈哈。。。
b站传送门：
https://www.bilibili.com/video/av51093995/
ps.看到这儿的雷友直接去看p2、p3吧，自己笔记本运行回放条还有bug不忍直视
gayhub传送门：
https://github.com/wdbg/MinesweeperHelper
ps.动图有点大加载有点慢，耐心等待~
后面我会传源码。。想玩的雷友，不急哈
|
|
支持的胖友可以b站点个赞或者gayhub上star一下哈哈
弱弱问下这个帖子阔以申精吗。
|
|
作者建立了一个基于最大胜率的自动扫雷ai。不同于前人既往的工作，作者首次做到了：① 可以自动抓取Arbiter图像转换为相应数据，而不是解同一个程序临时随机生成的局面（这一步是读取内存实现的还是图像处理？）；② 可以解自定义游戏；③ 有人性化界面，并且可以辅助玩家解局，这对新手玩家有莫大的帮助（在没有确定为雷或非雷下，help能否给出最小概率的格子？）。
目前我的疑虑有以下：① 关于概率计算的原理：作者要求自行百度的标题，实际百度后有多个同名标题，且图片及符号缺失无法阅览，能否给出链接？② 能否详述非其次线性方程组求定解的原理？扫雷公认是np问题，而高斯消元是p问题。一般这个过程中每一个格子都是一个未知数，值只能为0或1；但方程组做不到让每个未知数都为0或1，只能给出无数组小数解。因此据我所知，方程组只是一个验证的工具，具体还是得靠把每个格子0或1一个个带进去试，而没法直接解出。因此想了解一下里面具体的过程。③ 在家用级计算机中，特效全开解高级平均多少时间一盘？会慢到什么程度？会不会出现计算量过大而卡死？100盘从统计学来看率的误差非常大，期待作者后续工作完善。
|
|
还有，在程序的思路上，作者按计算量分层，而不是粗暴的直接求概率解。
作者描述的有些抽象，不知我理解的层次是否正确：
① 限定开局为角开（根据既往文献，第一点不一定开空下的确角开胜率最大）
② 朴素策略：我理解的朴素是，数字周围格数等于其本身时，周围都是雷；周围已知雷数等于本身时，其他打开；
③ 定式：模拟真实玩家行为，帮助减少计算量，但目前定式尚不足够。
④ 求解策略，疑问已于上所述
⑤ 概率分析：具体实现原理同样存疑。当多个格子概率同样最小时，选哪个？
|
|
这里对龚秋源同学的疑问回复一下：
首先感谢您的观看回复和质疑！
0.对游戏局面获取，相当于是图像识别
1.当前程序可以说是比较完善了，但还并没有做到最大胜率去完成。鱼与熊掌不可兼得，胜率和速度同样如此，比如我就不会考虑去求解这样的情况（有解可能性很小很小，耗时多）：
.....
.1...
...3.
.2...
.....
↑这摆雷是这么摆的？
2.帮助，当然可以给概率啦，没问题
3.直接每个格子代 0,1是可以做的，不过是指数级时间复杂度了，不过好在可以剪枝。不过我没这么去做
4.扫雷的确是npc，对某一局面是否有，有什么确定解这个问题我这里的确是多项式时间可以求解的，对于非其次线性方程组的解方程的原理，我后面可以给个例子的，我会好好说明的
5.编程之美 扫雷概率那个问题，这里有图片
https://blog.csdn.net/gao1440156051/article/details/51721277
这里有公式
http://www.it610.com/article/4709434.htm
结合一下看吧。。哈哈哈
6.功能全开跑，少数情况会很慢呀。参见上面b站链接，初级通过率测试过程中某局，就非常慢了，11分开始左右！因为这时候已经相当于枚举了，算法并没有很好的优化，加上是实现语言是python...所以功能全开的高级没办法保证平均时间。
不过不去计算概率的话，高级的速度还是比较可观的。b站速度测试视频中也可以看到高级大概3-4s的事，当时是intel E3好像3.4GHz的cpu。拿我自己笔记本举例，奔腾N3540 2.16GHz的cpu跑，10s左右也没问题。
的确100局会有较大误差。。谢谢提醒~
7.关于我所述策略你的理解应该还是没问题的。
定式嘛，参见http://www.minesweeper.info/wiki/Strategy 第一部分pattern
概率这块。。如果剩下所有块是雷的概率都一样，那就随机呗，有啥选的，死猜就是这种情况。
那么如果同时有两个块是雷的概率都是1/50，且当前最小，那我倾向于选择一起给点了。
如果同时有两个块是雷的概率都是2/5，且当前最小，那我还是随机选其一好了
|
|
|
很棒的ai！期待跟它学一些技巧。但是也有一个担忧，会不会有人用它冒充成绩呢？所以希望能弄一个检测，比如检测到扫雷名字标识为wdbg才能运行ai
|
|
作者的ai策略分5个层次，只有在上一层次无能为力时才会开启更耗时的下一层次的搜索。
在初中级测试中五个层次全开，高级为了节省时间关闭了概率分析，只做到把可以打开的全打开，即前4个层次。只有在第五层次才会猜雷，之前都应该是100%正确不会炸的。
那么问题在于：
① 作者对第四层次的描述是：“你能看出来的它一定能看出来！你不能看出来的它也能看出来！”但在b站视频P4初级测试中，0:32,2:15在炸之前明显有肉眼可见的解（后者需要结合剩余雷数，但按照概率分析规则的链接，概率计算是结合了剩余雷数的）；11:00中右下有两个很明显的解，但计算机却选择了不断的猜。中高级中也有许多类似现象（我只分析了炸的部分，因为不知道猜的节点没法分析每一步猜是否合理），还有误标（程序为啥会误标）。也就是说，作者采用P方法求解NPC问题，速度得到了保证，但在必要性上也许存在一定缺陷，存在一些人看得出但程序看不出的情况，第四层的描述也许需要修改。期待作者的进一步举例说明。
② 多个概率同样最小的猜雷：我想问的是，在第五层的规则下，程序是怎么操作的。除了2猜1死猜外，还常见于角开但没开空（根据视频，程序会选择其他角，这无疑是正确的），以及3猜1死猜（3猜1是一种特殊的死猜，虽概率相等，但对最终胜率却不同），因此我想了解程序选择的逻辑。以及，在高级测试中并没有开启概率分析，那程序是按照什么样的逻辑猜雷的？
③ 如果能完全做到这5个层次，那我认为就是基于最大胜率的ai了（虽是否当前概率最小就是胜率最大存在争议，但现阶段可以无可厚非的这么认为）。但作者强调是兼顾了速度和胜率，这是为什么呢？是因为认识到第4、5层次中为了运算速度而存在一定不足吗？
|
|
回复龚秋源同学。
感谢你的细心！
我在之知乎上发了一篇文章，应该能解决你部分的疑惑：
https://zhuanlan.zhihu.com/p/64505834
我描述的你所说的第四层面：“你能看出来的它一定能看出来！你不能看出来的它也能看出来！”确实是有点过了，但是并不是很过分。
为什么呢？因为这是我一行一行手写的代码，我怎么设计的它的行为，我是再清楚不过的了。
你发现的3处确认都是存在问题的！问题的原因是同一个（我在知乎文章最后进行了说明）。本质上，这便是为了完成速度做出的牺牲。
而错标的情况，我的确测到过挺多次的，这样的问题偶发且难以调适，至今我也仍不太清晰为什么会出现这样的情况。在绝大多数情况下，我的代码都能正常工作，流程也无异常，我更倾向于这是sympy库的偶现bug。
如果高级没有开概率分析的话，没有解的情况，优先猜角，然后边，然后中心
对的，求概率的话，对于某些情况（约束很少的块很多），比如我文章最后最后给出的情况，要求概率，已经是指数级的复杂度了，非常耗时。虽然数量级并不非常大，要知道我有用的语言是python，而不是c++，这个问题上我便不得不做出选择
|
|
回复王俊超同学：
谢谢！
你放心，不会出现这样的问题的，就算有人拿它冒充成绩，也是审核不过的，因为鼠标移动是跳跃式的，你明白吗，从一个点突然跳到另一个点。
就算有人改程序，加上了弯弯曲曲的移动轨迹，那么他对一个局面的逻辑也十分僵硬的，审核视频的人是会发现这个问题的。
毕竟程序还是程序，哈哈哈
|
|
感谢作者的回复。通过知乎文章的阅读，我了解了大致的思路和流程。以下提出一些建议：
① 在第四层求定解的策略中，作者为了运行速度，采取高斯消元后求最值的方法，但在小部分情况下会出现程序无法识别的固定解。这一思路本质和文献【1】十分类似。文献【1】的作者制作了程序解局的动图，且每一次猜雷都有提示，所以我可以仔细观察每一步猜是否合理。同样建议作者做一个类似的视频，来仔细观察何时程序会出现这种情况。据我观察，这种情况往往出现于“排除”（即一部分格子完全包含于另一部分格子之中且两者雷数相等）这种很常见的手法。在作者视频中，很大一部分都是最后角上4格炸了不应该炸的。因此对类似情况总结，做成几种常见pattern加入到第三层，会大幅改进求解的精确性。
② 知乎里给第四层举例说明的地方，有一处x5和x6写反了，这是小问题。
③ 关于概率分析：作者概率分析的实现方法和本帖1L的外链完全不同。在链接中，空白区的格数和雷数的组合数作为加权进入了概率计算，而作者并没有加权这一过程，只是将前沿区枚举后，把概率和空白区概率取值范围进行对比并取一个阈值。关于概率具体计算及估算方法可见我的著作【2】。我将精确的概率计算分为前沿区枚举和空白区加权两步。花算力的是枚举而不是加权。加权的组合数虽然可能很大（例如300选40），但分子分母中约分后剩下的数并不大，或者使用估算法粗略估算，因此我觉得这步并不会大幅增加时间复杂度。单纯对前沿区枚举误差非常大。例如单纯前沿区枚举4,5,6,7雷的可能性分别为4,14,11,2，但结合空白区加权后实际大约为4,2.8,0.44,0.012。前沿区雷数越多，其概率呈指数衰减。
④ 这个Helper是一个很有意义的创举，作者的工作非常有意义。但鉴于以上原因，建议说明“仅供参考，不能作为判雷以及解局的金标准”，因为会有不少新人对着Helper看，Helper说啥认为就是绝对正确，在少部分情况下会产生误导。
参考文献（GB格式太烦了就随便写写了）
1 http://www.saolei.net/BBS/Title.asp?Id=17163
2 http://www.saolei.net/BBS/Title.asp?Id=17110 P104-107 & P148
|
|
|
|
，楼主对扫雷网开发有兴趣吗？有的话可以看一下这个帖子：