要成为扫雷高手,先练好逻辑吧

科学松鼠会作者:Albert_JIAO

扫雷作为策略游戏,需要游戏者精确的判断。现在扫雷高级的官方最快纪录是33.95秒,中级则是由一个波兰玩家保持的8.5秒。而初级纪录是1秒, 世界上很多人达到了这一点。在1秒的时间里完成初级扫雷,据测算概率在0.00058%至0.00119%之间(属于运气题),最可能的方法是直接点击四 个角的方块。而本文所作的事情,则是将雷与雷之间的规律给你揪出来,并且深入思考其中的内涵。让你以后面对扫雷时,缩短与记录的差距,战无不胜!

 

从简单雷区入手

下图是一个初级的雷区,并且标注了两颗雷的位置,你能将剩下的地雷扫描出来吗?

/gkimage/0t/b9/2l/0tb92l.png

经过逐一排查,可以很轻松的确定雷区中的6颗地雷所在位置:

/gkimage/1m/jp/t1/1mjpt1.png

再来看一个简单的“雷区”:

/gkimage/nc/cx/dz/nccxdz.png

通过逐步扫描每一个方块会发现:首先最左边的和最右边的两个格子都一定是地雷,从左数第二个空格子和从右数第二个空格子也都是地雷,由于数字1的关 系,从左数第3个格子和从右数第3个格子都不是地雷,翻开一定是数字1……这样一直下去,最后你会发现最中间的两个空格子,不管有没有地雷,都和周围格子 上的数字不符。也就是说这样的雷区有bug,是无解的。

雷区中的逻辑门

怎么判断一个雷区是否有bug?又怎么判断雷区中地雷的具体位置呢?难道一定要从头到尾将雷区扫描一遍吗?

其实这些雷区里其实藏着一个规律。我们用数学方法来分析了上例的雷区:

在之前提到的这两个雷区里,把还没有翻开的格子交叉标记上字母x和x’。可以看到:当x的格子有雷时,x’格子一定没有地雷,反之亦然。如果将最左 边的空格子作为输入,把最右边的格子作为输出,输入结果和输出结果一定是一样或者相反的。如果是相反的,这相当于一个NOT(“非”)门电子元件。如果是 一样的,就有趣了,这样的一片雷区就具备了电路导线的性质!

/gkimage/kc/rj/p7/kcrjp7.png

在这里,雷区被看成了一个数字逻辑电路。执行这些“或”、“与”、“非”等逻辑运算的电路则被称为——逻辑门。任何复杂的逻辑电路都可由这些逻辑门组成。

逻辑门是集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种型号的高低电平在通过它们后产生信号。而高低电平可以 分别代表逻辑上的真假或二进制中的0和1,从而实现逻辑运算。具体到扫雷游戏里,也就是说,逻辑门可以用于判断一系列格子中的地雷的具体位置,而且它如同 电路传导一样,精确而迅速。

常见的(也是扫雷中用到的)逻辑门包括“与”门、“或”门、“非”门等。将它们组合使用就可以实现更复杂的运算——完成复杂情形下的扫雷,这种方法比按照规则缓慢推进的扫雷方法要节省很多时间。

/gkimage/uh/22/b7/uh22b7.png

复杂雷区中的精确判断

在简单的雷区中小试牛刀后,带着发现的规律,让我们进行一次实战演习。下图是高级扫雷游戏中的一个典型的雷区:

/gkimage/z8/jk/13/z8jk13.png

你能在不翻开格子的情况下,直接指出黄格子中有无地雷吗? 如果将雷区随意改变一点——左上角的一个格子下移一位,结果又如何呢?

/gkimage/dp/ny/fr/dpnyfr.png

你可能需要考量全局,从某个点开始逐步推理,将雷区全部扫描一遍,才能判断。而当雷区任意改变一点时,你都要重新来过,才能再次解答。这无疑是一种巨大成本负担。

实际上我们可以很快速地给出答案:第一个雷区的黄格子中无雷。而第二个雷区的黄格子中一定有雷。

这是怎么做到的?其实将上述的逻辑门引入到这个复杂的雷区中,一切都会变得简单而清晰起来。

/gkimage/7r/kj/9e/7rkj9e.png

雷区内靠近边界、可以直接确定是地雷的位置都插上了标示旗,剩下的位置标上了不同的字母。把一个有地雷格子看作1,没有地雷的看作0。最左面的格子(u、v)作为输入,最右面的格子(t)作为输出。按照扫雷游戏的规则,经过一步步推算,它们之间的关系就是:

( u , v , t ) = ( 1 , 1 , 1 ) 或 ( 1 , 0 , 0 ) 或 ( 0 , 1 , 0 ) 或 ( 0 , 0 , 0 )

显然,这个雷区被归纳成了一个AND门,它不仅轻松化解了这个扫雷难题,而且把雷区的规律揭示出来了。如此一来,当你掌握扫雷中这些逻辑门规律并加以练习后,就能够达到精确、快速的“机械化”扫雷水准。而到那时,一个新纪录或许就会诞生了。

数学家的扫雷研究

将扫雷问题抽象化从而缩短游戏时间的人,也不仅仅是扫雷发烧玩家。一些数学家也十分关注这个游戏背后的数学意义。

英国一位数学家用扫雷游戏中的逻辑规律构建了一系列电子元件,用电子电路模拟雷区。他试图将一个的给定的雷区图案交由计算机来判断是否可解。如果随 着格子数量的增加,电脑的计算量增长不是很快,就是P问题,如果计算量增加的很快,就是NP完全问题。计算机判断雷区是否可解,需要这类问题属于P问题才 可以。

对于几种基本的电路元件(AND、OR、NOT),如果将很多个这样的元件组合起来,相互连接,就会产生很多个输入、输出口。判断最后哪些输出结果可以产生,哪些不可以产生的这类问题,被称为SAT问题,它属于一个经典的NP完全问题。

而英国数学家的这个问题在一些时候等同于一个复杂电子电路的SAT问题,也就是NP完全问题。由此看来,面对一个上千上万个格子的巨型雷区,不要说去完成所有扫雷任务,就仅仅判断它是不是可解的,都可能会是计算机也承受不了的的大难题。

本文已发表于果壳网 死理性派主题站 《要成为扫雷高手,先练好逻辑吧》

Advertisements

死理性派恋爱法:拒绝掉前面37%的人

萝卜网

在每期《非诚勿扰》节目上,面对一位位男嘉宾,24 位单身女生要做出不止一次“艰难的决定”:到底要不要继续亮灯?把灯灭掉意味着放弃了这一次机会,继续亮灯则有可能结束节目之旅,放弃了未来更多的选择。

在 现实中,面对男生们前仆后继的表白,MM 们也少不了这样的纠结。如果遇到了一个优秀的男生,应该接受还是拒绝呢?如果接受了他,万一下一个更好的话那可就亏大了;可如果为此而拒绝掉一个又一个好 男人,也会面对着“过了这个村就没这个店”的风险。说不定白马王子们都已经擦肩而过,到最后就只剩下了猥琐男了,当初的拒绝明显得不偿失。

由 于没人能知道真正的缘分何时到来,没人能知道下一个来求爱的男生会是什么样子,接受表白的时机早晚实在很难决定。怎么办?去向《非诚勿扰》的黄菡老师和乐 嘉老师请教一下?其实你还可以向欧拉老师请教一下。你没听错。大数学家欧拉对一个神秘的数学常数 e ≈ 2.718 深有研究,这个数字和“拒人问题”竟然有着直接的联系。

“拒人问题”的数学模型
为了便于我们分析,让我们把生活中各种复杂纠纷的恋爱故事抽象成一个简单的数学过程。假设根据过去的经验,MM 可以确定出今后将会遇到的男生个数,比如说 15 个、30 个或者 50 个。不妨把男生的总人数设为 n。这 n 个男生将会以一个随机的顺序排着队依次前来表白。每次被表白后,MM 都只有两种选择:接受这个男生,结束这场“征婚游戏”,和他永远幸福地生活在一起;或者拒绝这个男生,继续考虑下一个表白者。我们不考虑 MM 脚踏两只船的情况,也不考虑和被拒男生破镜重圆的可能。最后,男人有好有坏,我们不妨假设 MM 心里会给男生们的优劣排出个名次来。

聪明 的 MM 会想到一个好办法:先和前面几个男生玩玩,试试水深;大致摸清了男生们的底细后,再开始认真考虑,和第一个比之前所有人都要好的男生发展关系。从数学模型 上说,就是先拒掉前面 k 个人,不管这些人有多好;然后从第 k+1 个人开始,一旦看到比之前所有人都要好的人,就毫不犹豫地选择他。不难看出,k 的取值很讲究,太小了达不到试的效果,太大了又会导致真正可选的余地不多了。这就变成了一个纯数学问题:在男生总数 n 已知的情况下,当 k 等于何值时,按上述策略选中最佳男生的概率最大?

如何求出最优的 k 值?
对于某个固定的 k,如果最适合的人出现在了第 i 个位置(k < i ≤ n),要想让他有幸正好被 MM 选中,就必须得满足前 i-1 个人中的最好的人在前 k 个人里,这有 k/(i-1) 的可能。考虑所有可能的 i,我们便得到了试探前 k 个男生之后能选中最佳男生的总概率 P(k):

萝卜网

用 x 来表示 k/n 的值,并且假设 n 充分大,则上述公式可以写成:

萝卜网

对 -x · ln x 求导,并令这个导数为 0,可以解出 x 的最优值,它就是欧拉研究的神秘常数的倒数—— 1/e !

也 就是说,如果你预计求爱者有 n 个人,你应该先拒绝掉前 n/e 个人,静候下一个比这些人都好的人。假设你一共会遇到大概 30 个求爱者,就应该拒绝掉前 30/e ≈ 30/2.718 ≈ 11 个求爱者,然后从第 12 个求爱者开始,一旦发现比前面 11 个求爱者都好的人,就果断接受他。由于 1/e 大约等于 37%,因此这条爱情大法也叫做 37% 法则。

不过,37% 法则有一个小问题:如果最佳人选本来就在这 37% 的人里面,错过这 37% 的人之后,她就再也碰不上更好的了。但在游戏过程中,她并不知道最佳人选已经被拒,因此她会一直痴痴地等待。也就是说,MM 将会有 37% 的概率“失败退场”,或者以被迫选择最后一名求爱者的结局而告终。

37% 法则“实测”!
37% 法则的效果究竟如何呢?我们在计算机上编写程序模拟了当 n = 30 时利用 37% 法则进行选择的过程(如果 MM 始终未接受求爱者,则自动选择最后一名求爱者)。编号越小的男生越次,编号为 30 的男生则表示最佳选择。程序运行 10000 次之后,竟然有大约 4000 次选中最佳男生,可见 37% 法则确实有效啊。

萝卜网

计算机模拟 10000 次后得到的结果

这 个问题由数学家 Merrill M. Flood 在 1949 首次提出,这个问题被他取名为“未婚妻问题”。这个问题的精妙之处在于,在微积分界叱咤风云的自然底数 e,竟也出人意料地出现在了这个看似与它毫不相关的问题中。不知道此问题发表后,Geek 男女间会不会多了一种分手的理由:不好意思,你是那 37% 的人

来源:科学松鼠会