|
[技术]3BV与ZiNi浅析.精 (10/6821) |
|
|
|
|
3BV是指仅用左键扫开一个board所需的最小点击数，换言之3BV就是NF的最少点击次数；相对的，ZiNi是指用左键和右键扫开一个board所需的最小点击数，换言之ZiNi可以认为是FL的最少点击次数。
3BV在《扫雷术语介绍》(http://saolei.net/BBS/Title.asp?Id=227)中已有详细介绍，在此我就不再多说了，接下来我将对ZiNi做一个较为详细的介绍。
ZiNi算法是由Elmar Zimmermann和Christoph Nikolaus共同提出的一种探索式算法，按探索方式的不同分为Human ZiNi、Greedy ZiNi和Random ZiNi三种，其中Random ZiNi是Greedy ZiNi的扩展算法，所以下文主要是针对Human ZiNi和Random ZiNi的介绍。
Human ZiNi算法流程如下：
 .用左键点开board中所有的“空”。
 .依次分析所有已翻开的方块（令左上角坐标为(1,1)假设当前分析的方块坐标为(x,y)），如果(x,y)紧邻的八个方块中有未翻开的非雷方块，且对非雷方块右击插旗并在(x,y)处双击能够比使用左键打开更多的3BV点，则说明在该处使用标雷双击比使用左键高效。在这里定义一个参数p，p表示在(x,y)紧邻的八个方块中“标雷双击能打开的3BV点的个数”减去“仅用左键打能开的3BV点的个数”的差值（PS：如果需插旗的方块已经插旗p值应减1）。计算出每个已翻开方块的p值，找到最大的p值p_max。如果p_max>=0，则对其相应的位置进行一次标雷双击操作（注意：如果需要右击插旗的方块已经Flagged，此处仅需一次双击操作！）；如果p_max<0，则左键点开board中最左上的未翻开的方块。
 .重复执行步骤，直到board中所有非雷方块被翻开，所用的点击次数值即为ZiNi值。
Random ZiNi算法流程如下：
注：坐标设定与Human ZiNi中相同。
.依次分析board中的所有非雷方块（包括已翻开和未翻开的方块），在这里定义一个参数p，如果该方块已翻开，则p值同Human ZiNi算法中的p，表示在(x,y)紧邻的八个方块中“标雷双击能打开的3BV点的个数”减去“仅用左键打能开的3BV点的个数”的差值；如果该方块未翻开，则在前者的基础上减1，即表示在(x,y)紧邻的八个方块中“标雷双击能打开的3BV点的个数”减去“仅用左键打能开的3BV点的个数”的差值再减1（这个应该很好理解吧~）。计算出每个方块的p值，找到最大的p值p_max。
.（很显然p值为p_max的方块常常会不只一个，尤其是在board尚未扫开很多的时候）随机选择一个p值为p_max的方块进行操作。如果p_max>=0，则对其相应的位置进行一次标雷双击操作（注意：如果该方块未翻开，则先左键翻开此方块；如果需要右击插旗的方块已经Flagged，此处仅需一次双击操作！）；如果p_max<0，则左键随机点开board中未翻开的方块。
.重复执行步骤，直到board中所有非雷方块被翻开，所用的点击次数值即为ZiNi值。
 .我们称每一次执行完步骤为一次迭代，由于在执行每一次迭代的过程中存在多次随机选择，所以每一次迭代所得到的ZiNi值可能会不相同。显然迭代次数越多，越容易得到更小的ZiNi值，当然花费的时间代价也会更多。
综上，Human ZiNi算法简单，得到的ZiNi值往往不是最优ZiNi值；Random ZiNi算法所得ZiNi值受算法迭代次数的影响，得到的ZiNi值往往比Human ZiNi更优。ZiNi值可作为FL最少点击数的参考值；但是ZiNi算法得出的解法仅仅适用于已知地雷分布的board，不适用于实战。
感谢张晔提供的ZiNiCalculator V0.2源码，以及赵爽在《扫雷术语（第二版）》(http://saolei.net/BBS/Title.asp?Id=6919)提到ZiNi这个概念。
---------------------------------------------------------------------------
鉴于Random ZiNi的复杂性，此处仅以Human ZiNi来举例。
假设有如下雷区（规模8*15，23雷）：
 
此图3BV为14，有两个空。
Step 1.打开两个空
左击(8,1)
左击(1,3)
雷区变为下图：
Step 2.
分析p值，图中很容易发现(4,11)和(2,14)处p值最高，都为0，这里我们选择最左上的(4,11)开始突破，进行如下操作:
右击(3,12)
双击(4,11)
雷区变为下图：
再次分析p值，容易发现(3,11)处p之最高，为2，由于(3,12)已经标雷，所以只需要进行如下操作：
双击(3,11)
雷区变为下图：
再次分析p值，我们发现(2,11)和(2,14)处p值最高，都为0，这里我们选择最左上的(2,11)开始突破，进行如下操作:
右击(1,12)
双击(2,11)
雷区变为下图：
再次分析p值，我们发现(2,12)和(2,14)处p值最高，都为0，这里我们选择最左上的(2,12)开始突破，进行如下操作:
双击(2,12)
雷区变为下图：
再次分析p值发现最高的p值也已经是负数了，所以从最左上的(5,7)开始
左击(5,7)
剩下的依次类推，分别为
左击(4,8)
左击(5,8)
左击(1,15)
最终board cleared，如下图
总共使用：6次左击、4次双击、2次右击，ZiNi值为12
----------------------------------------------------------------------------
本人水平有限，或言语啰嗦，或有不足与疏漏之处，还望大家包涵并指出。
|
|
不错~辛苦了
有点偏重于算法的描述，我概括一下：
Human ZiNi:左键点开所有opening（空），然后通过探索法，在搜索次序上（从左到右，从上到下）若发现某处标雷双击比纯左键更有效，则标双之。每次完成一个最优化操作，依次穷尽整个局面
Greedy ZiNi:通过探索法，在搜索次序上（从左到右，从上到下）若发现某处标雷双击比纯左键更有效，则标双之。每次完成一个最优化操作，依次穷尽整个局面
Random ZiNi:通过探索法，找出当前局面标双最有效的点（cell），标双之。每次完成一个最优化操作，依次穷尽整个局面
----------------华丽丽的昏割线-----------------
Human ZiNi与Greedy ZiNi共同点是，在搜索次序上（从左到右，从上到下）实现探索到的第一个有效操作，而Random ZiNi则取当前最优有效操作，因此Random ZiNi比较慢，但比较符合真实的最小操作数值（optimum）
Greedy ZiNi与Random ZiNi的共同点是，并不事先把opening点开，Human ZiNi则恰好相反，因此Human ZiNi比较接近玩家的实际操作，这也是取名为Human ZiNi的原因吧：）
----------------华丽丽的昏割线-----------------
我感到疑惑的一点是，为什么不把Human ZiNi和Random ZiNi结合起来，那样不是更好吗？以上
|
|
关于我帖子最后提出的问题。Cryslon已经提到RH ZiNi的概念了，也就是合体的算法Random+Human。但是目前加入Random的算法实现起来有困难，除非重写randomizing程序。
另外，ZiNi也只是一个人为的数值，对于“How much work is there to be done on a specific board”并不能作出完全的衡量。ZiNi值和3BV值一样，与局面的难易度成正相关，但是若以它的某个值作为准入录像的标准，这并不会比3BV=100或者110做得更好。
以上观点部分来自http://minesweeper.info/forum/viewtopic.php?f=15&t=70
|
|
顶技术贴！总算弄懂ZiNi了……
3BV和ZiNi只是解决一个局面所需点击数的衡量，而局面难度则还有路线、猜雷数等影响因素，用3BV值作为准入制度确实无法尽善。
|
|
虽然时间有点久了，但这个技术贴还是要膜拜一下~~
仔细看了一遍算法的介绍，感觉Human Zini这个算法比较可行，但对于这个Random Zini算法就有点疑问了：如果(x,y)是未翻开的方块，那么“标雷双击能打开的3BV点的个数”以及“左键打能开的3BV点的个数”（加入我理解为操作数的话）这两个值的差，然后再减1，也就是那个参数p能否确定？因为如果(x,y)是未翻开的方块，那么它周围的八个方块是雷还是空，有可能因为在当前局面下（即方块翻开前）被包在未翻开的方块内，缺少了外界已知数字的判定条件，而无法被确定（即使在所有的Opening都被打开以后也有可能发生）。毕竟正常的开局思维应该不是建立在雷区全部已知的Cheat Mode下完成的。
顺便跪求一个有关Zini算法介绍的英文源地址或者源程序，不知明日科或者其他哪位高人能提供一些参考，多谢了~~~~
|
|
|
|
