广州鼠标价格协会

当扫雷遇上数学,神奇的事情发生了

稀奇数学2019-01-15 08:04:52

在这里,看到稀奇的数学


windows经典游戏——扫雷与数学的关系。



一、扫雷的起源与发展



(一)扫雷的起源


扫雷最原始的版本可以追溯到1973年一款名为“方块”的游戏。


1985年,“方块”被改写成了游戏“Rlogic”。在“Rlogic”里,玩家的任务是作为美国海军陆战队队员,为指挥中心探出一条没有地雷的安全路线,如果路全被地雷堵死就算输。两年后,汤姆·安德森在“Rlogic”的基础上又编写出了游戏“地雷”,由此奠定了现代扫雷游戏的雏形。


1992年,微软公司的罗伯特·杜尔和卡特·约翰逊两位工程师在Windows 3.1系统上加载了该游戏,扫雷游戏才正式在全世界推广开来。


(二)扫雷的成绩排名


随着扫雷的发展,扫雷玩家们发现可以按完成的速度进行排名。目前主要是两大排行榜:国际扫雷排行榜和中国扫雷网排行榜(据说韩国也有类似的排行榜)。前者由曾排名世界第三的Damien Moore建立,是目前全球扫雷玩家公认的最权威的世界排行。后者由扫雷爱好者张砷镓等人开发和维护。


国际扫雷排行榜


中国扫雷网排行榜


在国际扫雷综合排行榜上,包括时间在内,初、中、高三个级别一共有10项世界纪录,其中我国的郭蔚嘉占了2项,郭锦洋占了一项,其余7项由一位波兰玩家卡米尔保持。值得骄傲的是,女子排行榜的前10名均被中国玩家占领。


国内的扫雷排行榜,不乏知名学府的学霸(比如前10名中就有好几个清华、北大的,其中还有一个状元);也不乏低年龄段的玩家,比如前10名里有两个是中学生(现在都是高中生)。不仅有各项指标的排行,还有各个地区的排行(笔者暂居全国38位,四川省第2位)。根据高级成绩的不同,还分成了若干的称号,如下图所示 :



扫雷有线下的世锦赛,也有半年一度的线上贴吧赛,不过与产业化的数独相比还是不够正规。雷友们的沟通途径主要是QQ群,雷友们除了畅谈扫雷以外,也互相交流和学习。雷友张少武(SWZhang)在知乎网上写了很多进阶的教程,雷友郭锦洋在优酷网上传了“TOP NFer”系列视频,感兴趣的读者可以做进一步了解。百度贴吧“扫雷吧”每年都会举办两次扫雷比赛(春季和夏季)。前两天由雷友组织的第2届“金羊杯”扫雷比赛也顺利结束,其中有来自非洲和日本的国际雷友参加。在北上广等大城市,不定期地会有雷友聚会。关于雷友的更多故事,可参见参考文献2。


(三)扫雷的变形


经典的扫雷游戏除了初中高三个级别以外,还有自定义(custom)模式,通过更改雷区大小和雷数,来增加或降低难度(自定义模式也有专门的世界排行)


在Windows自带的扫雷游戏基础上,程序员们开发出了专业的扫雷软件(比如Minesweeper Arbiter),它们拥有录像回放、数据分析、布雷训练等很多强大的功能。为了增加有趣性,还可以把数字的颜色统一设置成黑色;或者把数字统一用圆点表示,保留彩色;更有甚者,把数字拿掉,用深浅不一的同种颜色的格子以示区分。


另外,在经典的扫雷游戏的基础上,已经发展出各式各样的变形扫雷游戏,比如挖金子(竞速)、chocolate sweeper(禁止猜雷)、天天爱扫雷(多人联合扫雷)、nonosweeper(即“数图”)、立体扫雷(最后两个刚上过最强大脑)等。



二、扫雷基础知识



(一)扫雷的规则


在一个9*9(初级),16*16(中级),16*30(高级),或自定义大小的方块矩阵中随机布置有一定数量的地雷(初级为10个,中级为40个,高级为99个)。游戏目标是在尽可能短的时间内翻开所有安全的方块。如果玩家翻开的方块有地雷,则游戏结束。



扫雷的游戏规则非常简单:方格内的数字代表其周围的八个方格中含有的地雷数。通过不断地点击新的方块来获得新的数字,从而逐步推断出地雷的位置,并点开所有不是雷的安全方块即可。


下面是一些细则:


1.左键是翻开方块,右键是标记(或取消标记)地雷。如果某个数字周围的地雷被准确地标记出来,双击(左右键一起按或连续按两次左键)这个数字,其周围所有未翻开的安全方块会自动翻开。


2.如果所点击方块周围均没有地雷,则相连的所有类似方块及它们的相邻方块同时自动翻开,也就是会出现“空地”。


3.第一下点击默认不会是地雷。为了降低难度或提高可玩性,在某些版本(比如Windows7)中,第一下点击必然会出现“空地”。


4.和数独这类有着唯一解的数字游戏不同,扫雷有一定的运气成分。可能会出现2选1等无法用逻辑判断的情况。


5.一般来说,时间超过999s(即大约17分钟),则游戏结束。


(二)扫雷术语介绍


1. 3BV(Bechtel's Board Benchmark Value):

每局将所有非雷的方块点开所需最少左键点击数,是目前普遍用来评估局面难易程度的数据。


2. 3BV/s——3BV/Time:

一局内平均每秒钟完成的3BV值,是目前普遍用来评估玩家扫雷速度的数据。


3. IOE(Index of Efficiency):3BV / Total Clicks

3BV与实际点击数的比率,是目前普遍用来评估玩家操作效率的数据。


4. RQP——Time/(3BV/s):

时间与3BV/s的比率,因加入了时间因素,比3BV/s更能说明扫雷速度。


5. NF(No Flag):

一种仅用左键点击完成游戏,不标雷的玩法。


6. LC(Lose on the last click):

打开最后一个方格时不幸踩雷。


7. Sum:

初级、中级、高级成绩相加而得出的总成绩。


8. Sub:

小于某数值,比如高级Sub50就说明高级成绩<50。


9. Sup:

大于某数值,比如高级3BV/S Sup4就说明高级3BV/S>4。

此外扫雷玩家们还自创了很多指标,比如郭锦洋的QG(=time^1.7/3bv),能够弥补现有指标的一些不足。


10. UPK:

可重新开始同一局的游戏模式,本模式保存的录像不能参与排名。


(三)扫雷的风格


根据是否标雷,扫雷风格分为两种:FL(Flag)和NF(No Flag),即插旗和不插旗。


其中FL选手又分为全标流和效率流。全标流是指将大部分的雷都标出然后双击鼠标,其优点是思维简单,缺点是标雷会花费更多的时间。这类选手的手速往往惊人,因此这一流派也被称作暴力双击流(也有极少数的选手标雷单击),典型代表有胡恩彬、齐云水等;


效率流,也叫IOE流,是指仅标出部分有用的雷,尽量做到“标一开二、标二开三、标三开四”。效率流的移动速度往往并不快,而是追求最短路线,减少废操。效率流是公认的速度最快的扫雷方式,典型代表有世界排名第一的卡米尔、国内高级第一的周丹、曾位居国际榜中国第一的张先耀、前“雷帝”杨萧杨等。


NF选手利用左键的快速点击,“看似无棋、心中有棋”。其优点是连贯,思维简单。典型代表有“雷帝”郭蔚嘉、张少武、高伟豪等。


上述选手有的是两种风格兼修,结合二者的优势,更上一层楼。


(四)扫雷的技巧


1.扫雷基本等式


所有扫雷定式的本质实际上是一个式子——扫雷基本等式:两个相邻的数字之差等于两侧的雷数差。如下图,A、B表示两个相邻方格中的数字,X、Y分别表示两侧的雷数,则有A-B=X-Y。



不妨设A>B,有以下结论:

1)对称性:如果相邻两数相等(A=B)且某一侧的雷数确定,则能确定另一侧的雷数(X=Y)。比如:



2)如果大数字一侧的雷数等于相邻两数之差(X=A-B),则能确定小数字一侧没有雷(Y=0)。比如:


3)如果两个相邻的数字相差3(A-B=3),则能直接得出数字大的一边有3个雷(X=3),数字小的一边没有雷(Y=0)。比如:

(想一想,会不会出现5和1相邻的情形?为什么?)


2.扫雷定式


扫雷定式是判雷的利器。在学习扫雷定式之后,结合一定的练习,可以条件反射地判断出哪里是雷,哪里是空。


扫雷基本定式有两个,它们组成了所有的其他定式。第一个是1-1定式,第二个是1-2定式。当出现边缘上的1-1定式时,第3个格子一定是空;

当出现边缘上的1-2定式时,第3个格子一定是雷:

1-2定式的一个更复杂的版本:

除了基本定式以外,常见的定式还有1-2-1、1-2-2-1、2-1-2等。它们其实都是1-2定式的组合,其中以1-2-1、1-2-2-1最为著名。



减法原理:当数字比较大的时候,可以在现有数字的基础上减去周围的已知雷数,转化为常见定式。



3.雷型分布


最后介绍一下雷型分布。熟悉了雷型分布,可以轻松解决大部分的初级问题。如果1个数字与其相邻的格子数相等,那么立马可以判断出这些格子都是雷。比如:



下面是各个数字的雷型分布图(一共有5组):


1)数字1与7的雷型分布

数字1周围的雷有两种情况(能够翻折或旋转得到的算一种,下同):

将雷换成空,空换成雷,可以得到数字7周围的雷也有两种情况:


2)数字2与6的雷型分布

数字2周围的雷有6种情况:

反过来,数字6周围的雷也有6种情况:


3)数字3与5的雷型分布:

数字3周围的雷有10种情况:

反过来,数字5周围的雷也有10种情况:


4)数字4的雷型分布:

数字4周围的雷有14种情况:


5)数字8的雷型分布:



三、扫雷中的数学



扫雷的设计初衷其实是为了让人们学会使用鼠标。令人意想不到的是,这个看似简单的逻辑推理游戏,竟涉及到逻辑学、运筹学、概率统计、算法理论等丰富的数学理论。而且,其背后有一个至今尚未解决的数学猜想——“NP=P?”,为此美国克莱数学研究所提供1000000美元来寻求一种扫雷的有效求解算法。


下面谈谈扫雷中的一些具体的数学问题。


(一)概率:

扫雷不是一个纯靠逻辑推理的游戏,它也会有一定的运气成分,因此便会涉及到概率。


第一,每一局的难度不同。大量统计的结果表明,高级3bv的平均值为172左右。如何判断一个图是否是好图,以及如何限制3bv的范围,就需要一定的统计和概率知识。


第二,计算表明,开局的时候点角出现空的概率是最大的,其次是边上,最后是中间。这和围棋中的“金角银边草肚皮”有相似之处。


第三,在不得不猜雷的情况下,我们一般尽量点触雷概率最小的格子(这个需要经验的积累)。关于扫雷中的概率计算,可参见参考文献9。


另外,很多新手最常问的问题就是最后二选一的时候,应该怎么办?其实这个只能硬猜,没有技巧。因此也叫死猜。最常见的死猜如下图所示。

即靠墙第三行(列)有连续的三颗雷,并且中间一颗雷与墙之间恰有一颗雷。关于猜雷的更多技巧,参见参考文献10。


(二) 最值:

下面列出几个扫雷中的最值问题,其中有的已经解决,有的尚未完全解决。


1.求证:在一个大小不限的雷区里,使数字1-8同时出现的最小雷数为15。


这个问题已经基本解决,详见参考文献11。


2.求各个级别Num(数字之和)的取值范围。


由于3bv的最小值限制,Num的最小值非常难求。相关讨论参见参考文献12。关于Num的另外一个经典问题是:求证:将所有的空换成雷,所有的雷对应换成数字,所有数字之和不变。证明非常巧妙,详见参考文献13。


3.初级的3bv为什么不可能是50,52,53?


3bv是指用左键完成游戏所需理论最小点击数。初级的3bv人为限制为不低于2(初级最快纪录为0.09s),而3bv的最大值则为8×8-10=54。如果角上有空,则3bv最多为54-4+1=51;如果是边上有空,则3bv最多为54-6+1=49;如果中间有空,则3bv最多为54-8+1=47。因此无论如何,初级的3bv都不可能是50,52,53。(想想为什么可以是48?)


更多最值问题,参见参考文献14。


参考文献:

1. 扫雷游戏的起源.张砷镓.中国扫雷网http://saolei.net/BBS/Title.asp?Id=1005

2. 扫雷中国风云录.忘川.触乐网http://www.chuapp.com/article/283141.html

3. 扫雷术语介绍.张砷镓.中国扫雷网http://saolei.net/BBS/Title.asp ?Id=227

4. 扫雷基本等式.李峰.中国扫雷网http://saolei.net/BBS/Title.asp?Id=210

5. 扫雷定式及变化.张砷镓.中国扫雷网http://saolei.net/BBS/Title.asp?Id=362

6. Strategy & Tips.国际扫雷网http://www.minesweeper.info/wiki/Strategy

7. 关于数字1-7周围8格中雷的分布的各种形状.杨萧杨.中国扫雷网http://saolei.net/BBS/Title.asp?Id=8243

8. 如何判断一个图是否是好图,为何高3bvs出现在大图.林锦帆.中国扫雷网http://saolei.net/BBS/Title.asp?Id=12902

9. 【纯学术】扫雷的概率计算.林晗.百度贴吧https://tieba.baidu.com/p/1761431400?traceid=

10. 猜雷漫谈.杨凡.中国扫雷网http://saolei.net/BBS/Title.asp?Id=14149

11. 求证一道扫雷题目.郭蔚嘉.中国扫雷网http://saolei.net/BBS/Title.asp?Id=9822

12. 高级扫雷中所有数字的和的阈值试解.杨凡.中国扫雷网http://saolei.net/BBS/Title.asp?Id=13144

13. 趣题:扫雷定理 互补棋盘上的数字和相等.顾森.http://www.matrix67.com/blog/archives/1493

14. 扫雷四大类问题总结.杨凡.中国扫雷网http://saolei.net/BBS/Title.asp?Id=14624

15. 百度百科


来源:52数学网



学好启蒙的数学

快来稀奇数学

记得分享给孩子哦

Copyright © 广州鼠标价格协会@2017