玩掃雷還有什么技巧？科學(xué)家的玩游戲方法你絕對(duì)想不到

有時(shí)，小編回憶起童年和青春，眼前總是浮現(xiàn)出一片碧藍(lán)碧藍(lán)的天空和嫩得出水的草地，以及以前在那上面和小伙伴們度過(guò)的愉快的時(shí)光……

當(dāng)然，你們別想錯(cuò)了

我說(shuō)的藍(lán)天和草地是指這個(gè)

為了防止被打小編選擇提前爆頭蹲防

WindowsXP確實(shí)承載很多的記憶，而且XP這個(gè)系統(tǒng)也是真的經(jīng)用。WindowsXP于2001年8月24日正式發(fā)布，微軟在2014 年 4 月 8 日才停止了對(duì) Windows XP 桌面版系統(tǒng)的支持服務(wù)，一直到這周二，2019 年 4 月 9 號(hào)，運(yùn)行在嵌入式設(shè)備上的最后的一批WindowsXP才失去微軟的官方支持。XP們終于正式對(duì)我們saygoodbye了。[1]

經(jīng)典的掃雷游戲

提起 XP，不得不說(shuō)操作系統(tǒng)自帶的諸如掃雷，紙牌這一類的經(jīng)典游戲真的經(jīng)典，好玩又殺時(shí)間。如果可以統(tǒng)計(jì)全人類花在這上面的時(shí)間，估計(jì)肯定是一個(gè)天文數(shù)字。。。不過(guò)盡管掃雷大家玩的時(shí)間很長(zhǎng)，玩的次數(shù)也很多，但是我猜99%的玩家肯定沒(méi)思考過(guò)，自己玩掃雷為啥那么容易就死了。。。

對(duì)比一下別人家的孩子玩掃雷的速度

圖片經(jīng)過(guò)加速。如果你想看真正目前世界上掃雷最快的記錄的話，可以去[2]圍觀

再看看自己玩掃雷的樣子…

差不多就是這種水平，剛點(diǎn)到掃雷圖標(biāo)雷就已經(jīng)炸了

雖然XP已經(jīng)離我們而去，但是萬(wàn)幸的是Win10系統(tǒng)還能夠在商店中直接搜索「minesweeper」下載官方重置了的掃雷游戲，重新體會(huì)以前的經(jīng)典。

其實(shí)吧，掃雷這個(gè)游戲很多科學(xué)家也愛(ài)玩。不過(guò)一般人玩掃雷如果死得快，就不斷重開(kāi)重開(kāi)重開(kāi)直到碰到一個(gè)好的開(kāi)局（然后又快速地死掉）?？茖W(xué)家就不一樣，如果他們玩掃雷死得快，他們不會(huì)重開(kāi)，他們會(huì)直接證明「這個(gè)游戲通關(guān)概率為 0」。

掃雷畢竟已經(jīng)有這么長(zhǎng)的歷史了，分析掃雷游戲求解概率的論文都有一大堆。作為一個(gè)熟練點(diǎn)擊掃雷重開(kāi)鍵的手殘掃雷玩家，今天我就來(lái)和大家系統(tǒng)地聊一聊掃雷的背后的故事。

掃雷秘籍

Minesweeping cheat sheet

天下武功，無(wú)堅(jiān)不摧，唯快不破！

從數(shù)學(xué)上來(lái)看，掃雷就相當(dāng)于一個(gè)不斷給你已知條件不斷求解的過(guò)程，就像一個(gè)不斷增加條件的應(yīng)用題。你可以通過(guò)左鍵點(diǎn)開(kāi)確定不是雷的塊，右鍵標(biāo)記你認(rèn)為是雷的區(qū)域。如果你點(diǎn)開(kāi)的這一塊不是雷，那么它會(huì)告訴你這塊區(qū)域周圍八格內(nèi)有幾顆雷。只要你點(diǎn)得足夠快，雷就追不上你。

通過(guò)很簡(jiǎn)單的反證法，我們可以推出來(lái)很大一部分雷所在的位置。[3]

角落上的情形

所謂反證法，就是反過(guò)來(lái)想這個(gè)問(wèn)題。如果存在這么一個(gè)向內(nèi)凹的角，內(nèi)部的都是空白，但是角落上是一個(gè)1，那么這個(gè)角上一定會(huì)有一顆雷。因?yàn)槿绻@個(gè)地方再不是雷的話，那中間的1所指的雷就只能去流浪了。。。同理，一條邊上如果有3的話，那和3挨著的這三個(gè)一定是雷。畢竟地雷兄弟們也不能擠一擠挪到一個(gè)格子上去。

位于邊界時(shí)候的情形

除了這個(gè)反證法以外，在掃雷里還有很多固定的「套路」。學(xué)會(huì)這個(gè)套路，保證你掃雷功力大增，殺進(jìn)小區(qū)掃雷五百?gòu)?qiáng)。

聽(tīng)起來(lái)好像很厲害的樣子

在掃雷的時(shí)候其實(shí)經(jīng)常會(huì)遇到一些固定的數(shù)字，比如三個(gè)連續(xù)的數(shù)字為 121，此時(shí)想都不用想，就可以直接在 121 兩個(gè) 1 的正對(duì)方向標(biāo)上雷?；蛘咚膫€(gè)連續(xù)的數(shù)字1221，此時(shí)兩個(gè) 2 的正對(duì)方向上也一定是雷。

121情形下，由于左側(cè)1的限制，在黃色區(qū)域內(nèi)只能有一格雷，但是中間的2至少要求2格雷，所以粉色的那顆一定是雷。同理證明另外一側(cè)

1221情形下，和上面證明過(guò)程相同，由于1的限制導(dǎo)致在黃色區(qū)域內(nèi)只能有1格雷，所以另一個(gè)2正對(duì)的方格一定是雷。

「小編小編，我有個(gè)問(wèn)題，那121221呢？按照秘籍填雷的話中間那個(gè)1附近有兩顆雷誒？」

似乎有問(wèn)題的秘籍？

「這種情況是不可能的！左邊數(shù)起三個(gè)1已經(jīng)覆蓋了上面的所有未知空格，所以地雷數(shù)至多只有3個(gè)。但下方顯示地雷數(shù)為1+2+2+1+2+1，在只有中間5個(gè)格子重復(fù)計(jì)數(shù)的情況下都到了7，大于3的2倍。所以這種圖形是不可能存在的！」

咳咳，把思路收回來(lái)，如上所述，掃雷確實(shí)是有一些套路的。每日熟讀此掃雷秘籍，假以時(shí)日，掃雷技藝必將大成。

掃雷還是運(yùn)氣活

Lucky or not，it’s a question

玩掃雷，你必須要接受，這是一款拼人品的游戲。

雖然人生已經(jīng)如此地艱難，但我還是要無(wú)情地拆穿這一點(diǎn)。想必你此時(shí)已經(jīng)熟練掌握了掃雷的套路，不過(guò)在有些時(shí)候你還是要面對(duì)猜雷這種事情，而且一招不慎，滿盤(pán)皆輸。。。

猜猜黃色部分的雷應(yīng)該是怎么分布的？

圖中黃色部分就是典型的需要猜的掃雷難題。根據(jù)角落里面的數(shù)字，我們都只能知道 1×2 的黃色部分里面一定只有一個(gè)雷，不過(guò)我們并不知道哪個(gè)才是雷。如果沒(méi)有其它信息的話，我們辛辛苦苦大半個(gè)棋盤(pán)，最后通過(guò)這個(gè)地雷陣的概率還是只有1/8。

這種簡(jiǎn)單的判斷還好，有些時(shí)候還會(huì)遇到一些藏得更加隱晦的猜的時(shí)候。

掃雷判斷題

假設(shè)在我們的掃雷過(guò)程中遇到了這么一個(gè)圖案，確實(shí)是一件欲哭無(wú)淚的事情。不知道怎么哭的可以先把眼淚準(zhǔn)備好，小編馬上就告訴你們?yōu)樯兑?。。。從左邊開(kāi)始，假設(shè)第一個(gè)空位有雷，那么第二個(gè)空位沒(méi)有雷，因?yàn)榭瘴恢虚g1的存在從而第三個(gè)空位有雷，依次類推。但是如果是第一個(gè)空位沒(méi)有雷，而第二個(gè)空位有雷，我們也說(shuō)得通。都要踩地雷了，還整個(gè)這么復(fù)雜的難題，至于么。。。

別急，后面還有更加復(fù)雜的。這里的x和之后的*號(hào)上是否有雷的情況一直相同，所以這個(gè)地雷陣就像一根傳遞信號(hào)的導(dǎo)線一樣。在掃雷的地圖上，我們不僅僅能夠做出這種簡(jiǎn)單的傳遞信號(hào)的導(dǎo)線，其實(shí)還能夠?qū)崿F(xiàn)所有的電子電路中的邏輯門的操作。[4,5]

非門電路

或門電路

這是兩個(gè)「簡(jiǎn)單」的邏輯門，分別實(shí)現(xiàn)了將信號(hào)翻轉(zhuǎn)的非門和將兩路信號(hào)做或操作的或門。在另一個(gè)也很著名的沙盒游戲——《我的世界（Minecraft）》里面，玩家也可以通過(guò)游戲中的材料，紅石（其實(shí)在此之前的 Windows 10 操作系統(tǒng)的每一年的更新代號(hào)就是用紅石來(lái)命名），實(shí)現(xiàn)各種各樣的復(fù)雜邏輯操作，更有玩家利用紅石在Minecraft里制造出了真正能運(yùn)行的計(jì)算機(jī)。。。

紅石計(jì)算機(jī)，具有完整的寄存器，加法器等部件 [6]

算了，我已經(jīng)不敢想象掃雷會(huì)變成什么樣了。。。

判斷有沒(méi)有解都是一件很難的事情

Find solution

回到文章最開(kāi)始，我們?nèi)巳テ平庖粋€(gè)掃雷問(wèn)題的話，很容易就會(huì)死掉了，那把這個(gè)問(wèn)題交給計(jì)算機(jī)來(lái)做會(huì)怎么樣？然而很遺憾的是，一般情況下，計(jì)算機(jī)目前對(duì)掃雷這個(gè)問(wèn)題還是無(wú)能為力。。。

難過(guò)

稍微值得慶幸的是，在我們平時(shí)玩的比較小的棋盤(pán)下，計(jì)算機(jī)還可以通過(guò)搜索得到答案。

為了了解計(jì)算機(jī)處理問(wèn)題難度的幾個(gè)級(jí)別，有必要先知道一個(gè)概念——多項(xiàng)式時(shí)間。對(duì)于同一個(gè)算法，根據(jù)處理問(wèn)題大小的不同，計(jì)算機(jī)一般來(lái)說(shuō)需要不同的時(shí)間進(jìn)行計(jì)算。用最直觀的例子來(lái)說(shuō)，小明要去洗衣服，他洗 1 件衣服的時(shí)間為 2 分鐘，洗 5 件衣服的時(shí)間為 10 分鐘，洗 10 件衣服的時(shí)間為 20 分鐘，處理問(wèn)題的時(shí)間隨問(wèn)題規(guī)模的變化為線性關(guān)系，一次多項(xiàng)式?，F(xiàn)在我們假設(shè)小明還是要洗衣服，只不過(guò)現(xiàn)在的衣服比較特殊，他洗1件這種衣服的時(shí)間為2分鐘，但洗5件的時(shí)間變?yōu)?2分鐘，洗10件的時(shí)間變?yōu)?024分鐘，這個(gè)時(shí)候就是指數(shù)關(guān)系的，而不再是多項(xiàng)式了。評(píng)價(jià)一個(gè)算法，隨著問(wèn)題規(guī)模的增大，計(jì)算時(shí)間怎么增長(zhǎng)是一個(gè)十分重要的指標(biāo)。

在計(jì)算機(jī)里面，對(duì)于多項(xiàng)式級(jí)別的時(shí)間，我們還是認(rèn)為很快的。如果把問(wèn)題按照求解的難度來(lái)進(jìn)行分類的話，P 是指能夠用多項(xiàng)式時(shí)間求解的問(wèn)題，俗話說(shuō)就是算起來(lái)很快的問(wèn)題。NP 是指算起來(lái)不一定快，但是任何答案我們都可以檢查起來(lái)很快的問(wèn)題。NP完全問(wèn)題，是比所有NP問(wèn)題都要難的NP問(wèn)題。雖然人們有個(gè)美好的想法，總覺(jué)得驗(yàn)算起來(lái)很快的應(yīng)該可以找到辦法讓他算起來(lái)很快，但目前還是個(gè)未知數(shù)。。。[7]

很不幸，求解一個(gè)掃雷游戲的解，正好是一個(gè)NP完全問(wèn)題——在能夠輕松驗(yàn)證結(jié)果是否正確的問(wèn)題里面最難的那一類。這一類問(wèn)題目前為止人們還沒(méi)有發(fā)現(xiàn)多項(xiàng)式時(shí)間的求解算法，通常只有指數(shù)級(jí)甚至階乘級(jí)的搜索算法來(lái)解決。

用來(lái)顯示液晶數(shù)字的邏輯電路。我們可以很方便地一個(gè)一個(gè)試，但是反過(guò)來(lái)卻很難，尤其是在這個(gè)邏輯電路非常龐大的時(shí)候

掃雷游戲?qū)儆谝粋€(gè)如此困難的問(wèn)題，其原因就出在上一章提到的，可以把掃雷游戲看做一個(gè)個(gè)邏輯門進(jìn)行運(yùn)算的邏輯電路。給定一個(gè)邏輯電路，在已知輸出結(jié)果的情況下，能否確定每個(gè)輸入的值？這個(gè)問(wèn)題被稱為SAT 問(wèn)題，是世界上第一個(gè)被證明其為 NP 完全的問(wèn)題。[8]這種問(wèn)題驗(yàn)證起來(lái)非常容易，你只需要把結(jié)果代入到邏輯電路中，馬上能知道是否符合要求，但倒過(guò)來(lái)想要計(jì)算符合結(jié)果的輸入就極端地麻煩。

求解掃雷游戲的結(jié)果，利用那些構(gòu)造的邏輯門，恰恰等價(jià)于求解SAT問(wèn)題。[9]

掃雷還和滲透有關(guān)系

Precolation

液體，圖片來(lái)自 Giphy，Michael Shillingburg

其實(shí)我們?cè)谕鎾呃子螒虻臅r(shí)候覺(jué)得很難，其實(shí)還有另外一個(gè)原因。這個(gè)原因和物理里面的滲透還有關(guān)系。

在上個(gè)世紀(jì) 60 年代，科學(xué)家們 [10] 發(fā)現(xiàn)在流體流過(guò)多孔的介質(zhì)的時(shí)候，介質(zhì)中的空洞總是會(huì)被堵塞，有時(shí)候就會(huì)影響流體流出。更為奇怪的是，當(dāng)這些多孔的介質(zhì)的孔隙被隨機(jī)堵塞的比例逐漸增大而達(dá)到某一值時(shí)，一開(kāi)始一直能夠流動(dòng)的流體就突然被完全堵住。在孔洞被隨機(jī)堵住的概率發(fā)生變化時(shí)，液體流過(guò)的比率也會(huì)發(fā)生一個(gè)突變。

這種現(xiàn)象被稱為逾滲（precolation）。[11]

遇到這種情況，你該怎么下手

在掃雷里面，也存在類似逾滲的現(xiàn)象。當(dāng)一盤(pán)游戲里面的地雷密度特別低的時(shí)候，我們差不多隨便點(diǎn)，都不會(huì)點(diǎn)到地雷，而是點(diǎn)到大片大片的空白，一下子就把問(wèn)題解決了。但是當(dāng)?shù)乩酌芏仍龈咭院螅谠龃蟮揭欢ǔ潭纫院?，即使我們理性地分析，從不瞎猜，也不可能把掃雷?wèn)題做對(duì)了。

針對(duì)不同的棋盤(pán)大小，有人計(jì)算了在不同地雷密度情況下獲勝的概率。三角形對(duì)應(yīng)的曲線為初級(jí)8×8，正方形為15×13，菱形為高級(jí)，30×16。這里的能否求解實(shí)際上不包括第一次隨機(jī)點(diǎn)擊的時(shí)候踩中雷的概率。[12]

我們把流體通過(guò)多孔介質(zhì)逾滲的模型抽象出來(lái)的話，其實(shí)對(duì)應(yīng)著點(diǎn)逾滲，也就是把整個(gè)介質(zhì)想象成一個(gè)網(wǎng)絡(luò)，流體在經(jīng)過(guò)每個(gè)網(wǎng)格時(shí)，有概率p的可能通過(guò)。如果不能流過(guò)的網(wǎng)格在網(wǎng)絡(luò)中連成了片，流體就不能流過(guò)了。

不嚴(yán)格地來(lái)說(shuō)，求解掃雷問(wèn)題其實(shí)和逾滲模型很類似，我們求解的過(guò)程其實(shí)也像推土機(jī)一樣，不斷地利用已有的知識(shí)將已知區(qū)域向外一層一層地推進(jìn)。如果游戲中某處雷的密度越大，那么越有可能出現(xiàn)可解部分被雷分開(kāi)的情況，地雷密度和逾滲參數(shù)起到了一樣的作用。如果被分隔到無(wú)法連接整個(gè)棋盤(pán)，那就無(wú)法繼續(xù)推理了。更為嚴(yán)格的證明可以參考ElchananMossel的論文。[13]

推土機(jī)，圖片來(lái)自網(wǎng)絡(luò)

隨著網(wǎng)格的不斷增大，這條勝率曲線中間部分也變得越來(lái)越陡峭，掃雷問(wèn)題越來(lái)越向兩個(gè)極端發(fā)展：要不就根本解不出來(lái)，要不就是很容易地就能解出來(lái)。在高級(jí)模式下，地雷的密度其實(shí)已經(jīng)到了99/480=0.2，能夠解出來(lái)的概率已經(jīng)不到1/4，這還不算手抖了點(diǎn)錯(cuò)了，開(kāi)局不好重開(kāi)之類的情況，真的不算是友好了。

結(jié) 論

Conclusion

emoji 版本掃雷 [14]

相信看到這里的人

一定已經(jīng)躍躍欲試想要玩一下掃雷了

我相信你們

天下無(wú)難事，只要肯放棄

卸載也行