登录 [F2] | 注册 | 找回密码 | 软件下载 | 更新历史 | 关于本站 | 管理团队
首页 排行榜 录像 雷界 论坛 教程 雷神殿 我的地盘 新手上路
第 11 楼
 [布衣] 朱鹏飞 回复于 2019年7月8日
3. 非确定Zone模型 

在2的推导中,把common生成新Zone的条件定为:
common中雷数可确定 (最大最小雷数相等)

为什么这么做?抛开细节追寻思路:
因为先有的 Zone,后有的 common,所以我自然想要把common往Zone上靠
而 Zone 是由数字线索得来的,雷数已经确定
所以我只接受 雷数可以确定的 common 转化为 Zone 加入

那么,如果不这么做,来看看 common 有什么? 
未知方块集合,最大可能雷数,最小可能雷数 —— 这些信息难道不也是有用的吗?

如果把 Zone 的概念往这上面靠会怎样?
Zone 的确定雷数,不过是 最大可能雷数 等于 最小可能雷数 的特殊情况而已!

3.1
由此,更改Zone定义,将mine,safe参数改为 maxmine,minmine(非确定Zone)
由数字块初始构建的非确定Zone,maxmine=minmine,简单推理规则不变

3.2
基于非确定Zone 的 多集合模型,
同样,
取出 n(n>1)个有重叠的非确定Zone ∈ZC ,其交集记作common,大小记作 s

commom中可能含有的最大雷数:
       maxmine = min(common大小s,ZC中每个Zone的最大雷数maxmine )
commom中可能含有的最小雷数:
       minmine = max( ZC中每个Zone的最小雷数减去不属于common的方块数: minmine-(num-s) )

无需任何条件,
common 即是一个新的 非确定Zone,
把它加入推导,就能生成新的非确定Zone,
直到有 满足 简单推理条件 的Zone产生

上一楼的贴图情况,即可利用本方法解决。有兴趣者可自行推导。

另:
本方法只完成了理论推导,还没有实现在代码里,
本人近期也有些别的事儿忙活,
算法思路介绍完了,这个事儿可能也要先放一放了
希望能对其他想做自动扫雷算法的朋友有所启发
欢迎交流
第 12 楼
 [布衣] 朱鹏飞 回复于 2019年7月8日
4. 枚举方法

最后一点写完吧。

枚举必不可少,见龚秋源贴

枚举要符合两个约束:
一是数字线索约束,如果结合前面的介绍的方法,就是满足得到的所有Zone的约束
二是剩余雷数的约束

因此可以不用生硬的以 2^n (n是剩余方块数)的数据量枚举,
而是选一个Zone,做个假设(判定某块是雷),然后用前面方法推理得到剩下的
推理中断时继续假设
推理中不满足约束了立即返回上一个假设点

这算是一种比较高校的剪枝方式吧。

得到全部的满足约束枚举结果后,所有结果中相同的块即可判定。
判定完有了新线索,继续推理。
推理不出来,再枚举,直到没有相同的块。
我第一版的自动扫雷程序即到此为止。


剩下的就是猜雷了,我在群里和人讨论过,
初步的思路就是,
假设所有满足约束的枚举结果的概率是相同的,
即可得到每个块是安全的概率
选择安全概率最大的点开,以得到新线索

但是这个假设是否正确,还有待进一步探讨。


而我这个帖子,暂时就到这里了...
第 13 楼
 [布衣] 朱鹏飞 回复于 2019年7月8日
贴几张图,前面没贴成的
感谢 胡恩彬 教我怎么贴图

这是15年写的自动扫雷程序,
不会调windowsapi,只能写个控制台扫雷在上面跑解法





这是17年加上识图和操控之后,在win10应用“踩地雷”上跑的
识图的效率很低,所以时间超长


这是前不久用python重构后在 Minesweeper Arbiter 上运行的
主要是提高了识图和操作效率,速度明显上去了
但逻辑不完整,导致通过率低(架不住我快可以几百局的试啊哈哈)


因为在本地把游戏文件夹多拷贝了几个,导致数据不一样了。不重要。

这个帖子就到这啦,版主能给加个精不

溜了溜了
第 14 楼
 [雷神] 王嘉宁 回复于 2019年7月8日
可以看出楼主对扫雷发自内心的、持久的热爱,所以何不上传几个录像
第 15 楼
 [布衣] 朱鹏飞 回复于 2019年7月8日
楼上王嘉宁同学问我为啥不发视频。。
因为我是纯纯的机刷选手,手刷很菜啊哈哈哈
手刷高级最快才到过200+

机刷视频嘛,,发了怕被打

要是有个单独排名的机刷榜就好了
除了速度,还可以以不同的优化方式来拼各种其他参数
最重要的是通过率,这个是手刷比赛不咋提的
第 16 楼
 [布衣] 朱鹏飞 回复于 2019年7月8日
另外,阅读了前面我写的自动扫雷算法的话
会发现我的自动扫雷算法是纯为计算机编程准备的,
递归思想,数据碰撞产生新数据,枚举...
手刷不太好直接借鉴思路
手刷顶多能模拟 一两层的多集合模型
多了就不好记了

谨以一个程序员的方式表达对扫雷的热爱。
第 17 楼
 [状元] 龚秋源 回复于 2019年7月8日
简单回复一下
1. 确定Zone的思想
这层的发动条件是共有部分最大雷数等于最小雷数。据我所知,最大雷数等于最小雷数有且只有两种情形,一是构成减法的情形,二是拆分的情形。所以这一层的思路比减法多了一个拆分的操作。实际上只要2个集合互相交错就够了,感觉三个及以上没啥意义
*拆分指,已知ab有1雷,abcd有2雷,cde有2雷,则把abcd拆分为ab和cd各有1雷,e必为雷,类似这样的操作。

2. 不确定Zone的思想
这一步的思路和真人在分析复杂局面时类似,对某一个共有部分限定雷数取值范围,不断地做不等式,推到其他集合去,最后发现矛盾,不等式只能取等号,发现解。但这一步最大的问题是如何找到那一组做不等式的集合。如果三个集合互相完全交错,就会产生7个单独的Zone,更何况局面很多集合互相交错动辄几十个,产生Zone的数量十分膨大,用什么样的顺序,怎么样去找去推,我对这一点表示疑问。

3. 猜雷的概率问题及验证
概率怎么算是非常确定的。先对前沿区枚举,再把空白区的组合数加权上去。我那篇综述里相关描述的参考文献讲的非常详细。

4. 建议附上几个例子以说明你思路的工作原理,干看文字有点难看懂,可以整理成word或者pdf上传,的确编辑很麻烦


第 18 楼
 [布衣] 朱鹏飞 回复于 2019年7月9日
回复  龚秋源 :

1.“实际上只要2个集合互相交错就够了,感觉三个及以上没啥意义”

我第一版代码里,Zone构成一个链表,只能两两比较求交集,复杂度O(n^2),所以并没有再跟第三个比。
重构代码时,
我给每个Zone都设了一个不重复的索引,
对应每个前沿块维护一个链表,存放了其属于的Zone的索引,根据索引能找到所有相关Zone,复杂度O(1)
这给多集合求交集提供了可能性,我才把三个乃至更多集合求交集块加上。
双集合解不了而多集合能解的例子,需要跑对比实验才能找到,等忙过这阵子我会尝试找找


2.“但这一步最大的问题是如何找到那一组做不等式的集合。如果三个集合互相完全交错,就会产生7个单独的Zone,更何况局面很多集合互相交错动辄几十个,产生Zone的数量十分膨大,用什么样的顺序,怎么样去找去推”

还是上面说的,
推理顺序并不盲目,因为我们能以O(1)复杂度找到有交集的Zone
而且我们并不在乎找到一个Zone是否有直接效果,这一轮没有,生成了新的Zone可以加入下一轮推理过程,这就是“多个推理时间步”上的纠缠。

至于数据量的问题,Zone复合简单推理执行操作后,是要被销毁的。
这点数据量,对计算机来说,炸不了。
我可以跑个实验证明运行过程中最多同时有多少Zone,我推测高级也不超过1000

3.猜雷概率我估计我的想法是对的,没有证明而已。待我详细阅读下你的文章

  共 18 篇回复  首页 | 上一页 | 下一页 | 末页  现在是第 2/2 页
楼主信息
Copyright @ 2008 扫雷网 Saolei.wang 版权所有 陕ICP备19026089号-1