自動踩地雷：之一

實驗室有幾位學弟，在上學期修了人工智能 (Artificial Intelligence) 的課程。這門課學期末的 project，是開發一個「自動踩地雷」的演算法與程式。

由於這個遊戲也算是「小益智遊戲」，加上有學弟在旁煽風點火，我對寫一個「自動踩地雷」的演算法，其實頗有些躍躍欲試的感覺。

但坦白說，自己一開始的想法是「偷懶」。想說 MPH 是踩地雷的高手，印象中他曾經寫過一支在 Windows 下自動踩地雷的程式，或許可以先問他是怎麼寫的。接著，又想到踩地雷是個很普遍的小遊戲，應該有很多人都寫過自動踩地雷的程式，或許可以利用搜尋引擎找找看...

簡單地搜尋了一下，真的可以找到一些可資參考的程式。只是，解問題的特性就是這樣：「看到答案」其實也代表趣味的蒸發。那麼，我為什麼不自己寫一個來玩玩？

於是，五月底抽空寫了一部份程式。基本的概念很簡單：

1. 如果找得到一些安全的格子，就從這些格子中，隨意挑選一個來開啟。
2. 如果找不到安全的格子，就隨便找一個格子來開啟。

因此，主要的問題就是：如何得知「安全的格子」，又如果真的找不到「確定是安全」的格子，那麼是否能夠找到「有較高安全機率」的格子？

在一些狀況下，可以很簡單地利用系統的提示資訊（格子周遭的地雷數目），算出安全（沒有地雷）的格子。方法是這樣的：

1. 對有系統提示的每個格子，推測其周遭的格子屬性（含地雷、不含地雷、或者未知）。
2. 假設目前所檢視的格子，其提示的地雷數目為 B，而根據推測，它的周圍有 m 個有地雷方格，n 個安全方格，p 個未知方格。
3. 推測未知方格的屬性。
   • 若 B = m，則所有（p 個）未知方格都可以推測為安全的，回到步驟 1。
   • 若 B > m，且 B-m=p，那麼所有（p 個）未知方格都可以推測含有地雷，回到步驟 1。

例如，下圖左方的提示圖，就可以依照上述的簡單方法，得到右方的推測圖（標示「B」表示此格子有地雷，標示「O」表示此格子不含地雷，而標示「#」代表下一步打算開啟的安全格子）：


有時，會遇到比較複雜的狀況，無法用上述的簡單方式推測方格的屬性。下圖就是一個例子：


對上方這張提示圖，用些腦筋就可以知道，左上方有兩個地雷，分別位於 (0, 0) 與 (0, 2) 的格子上（兩個「1」的正上方）。

據說，上個學期修課的學生，幾乎都只做到上述的簡單演算法；他們頂多是加上一些權重的方式，猜測方格可能含有炸彈的機率。換句話說，大家的方法，都沒有能夠確切地推論出 (0, 0) 與 (0, 2) 的格子必然有炸彈。

那麼，要怎麼讓程式自動算出這樣的結果呢？今天寫得有些沒力了，就下回再繼續討論吧。