掃雷與數學

知識 04-28

今天分享雷友寫的：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就說明高級成績

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