這是兩個(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ī)。。。
玩掃雷還有什么技巧?科學(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ú)難事,只要肯放棄
卸載也行
休閑益智
120MB
休閑益智
107MB
休閑益智
79.58MB
休閑益智
13.7MB
飛行射擊
84.41MB
戰(zhàn)爭(zhēng)塔防
12MB
游戲輔助 | 4.5GB
2024-04-24
動(dòng)作格斗 | 20GB
2024-04-23
角色扮演 | 3.2GB
2024-04-22
角色扮演 | 500MB
2024-04-22
休閑益智 | 30.17MB
2024-04-18
生活服務(wù) | 144.35MB
2024-04-18
生活服務(wù) | 144.35MB
2024-04-18
生活服務(wù) | 144.35MB
2024-04-18
學(xué)習(xí)教育 | 24.26MB
2023-11-08
系統(tǒng)工具 | 6.78MB
2023-11-08
游戲輔助 | 4.5GB
動(dòng)作格斗 | 20GB
卡牌策略 | 19.6MB
動(dòng)作格斗 | 98.31MB
卡牌策略 | 78.64MB
休閑益智 | 35.93MB
休閑益智 | 150.45MB
休閑益智 | 114MB
休閑益智 | 12.8MB