自動踩地雷：之三

先前寫了兩回踩地雷，不過都沒有引發任何回應。

或許是大家都太忙碌，但更可能的原因是：這類討論實在太無趣了。

當然，無趣也很可能是因為自己表述能力不佳，寫起東西來既嚴肅又無聊。在這個忙碌的時代，除了寫作業、交期末報告，大家哪有時間、哪有閒情逸致來討論「或許有些趣味的益智遊戲」？

但既然寫了「之一」、「之二」，似乎總該再來個「之三」，順便充充版面。但無病呻吟也沒什麼意思，還是有些內容才好。

嗯... 有了。在先前的討論中，缺漏了一項「或許很重要」的資訊。

在 Windows 的踩地雷遊戲中，系統除了提供「被開啟方格周遭的地雷總數」外，其實還有一項資訊，就是所有方格內的地雷總數。例如，右圖左上方的紅色數字，就提示說「盤面上總共有 10 枚地雷」。

這樣的資訊，在什麼狀況下才能派上用場呢？

自動踩地雷：之二

這一篇文章，是延續上週〈自動踩地雷：之一〉的討論。

MPH 在回應裡說，他找出程式碼之後，發現已經「看不懂」了，僅記得當初用到的規則相當簡單。我想，他說到軟體工程、或者軟體開發的一個大問題了。人會遺忘、溝通會失真、軟硬體會演進、需求會改變。該怎樣做，才能妥當地處理這類問題？

扯遠了，還是回到主題吧。

上回曾經提到，從下圖的提示中，我們可以推論出 (0,0) 與 (0,2) 的方格中有地雷。為什麼呢？


因為「如果 (0,0) 是安全的，那麼從 (1,0) 的提示（它周圍恰有一個地雷）可知，(0,1) 必然內含地雷。但是，由於 (1,2) 提示它的周圍恰有一個地雷，因此 (0,2) 必然是安全的。但如此一來，(1,1) 的周圍就只有一個地雷，與系統所給的提示（有兩個地雷）相抵觸。」

因此，在上圖中，(0,0) 必然內含地雷。

類似地，若我們假設 (0,1) 含有地雷，也可以推導出矛盾。因此，(0,1) 格子必然是安全的。

這樣的推論方式，其實就相當於邏輯證明中的「歸謬法」（Proof by Contradiction）。先假設某個方格 C 有（或沒有）地雷，如果可以推導出矛盾，那麼就可以知道 C 不含（或含有）地雷（因為 C 的狀態滿足排中律：它要嘛「有地雷」、要嘛「沒有地雷」，沒有其他的可能）。

雖然有向學弟們提到這個想法，但他們都以為程式寫起來會頗複雜。為了「證明」它並不如想像中「那麼」複雜，我用 PHP5 把這個想法實作了一下，結果只需增加不到 10% （大約三十幾）行的程式碼。

對上圖的提示，這個程式會先假設 (0,2) 是安全的，然後得到矛盾。於是，將 (0,2) 標示有炸彈後，套用上回提到的簡單演算法，就可以判斷出 (0,1) 是安全的：


再來一個「看似更困難」的問題。從下圖的提示裡，我們是否能夠知道那些格子是安全的？


它其實並沒有更困難。運用歸謬法和上回所提到的簡單演算法，我們是可以推得，上圖有提示的格子周遭多數格子的屬性（含有、或不含地雷）。

自動踩地雷：之一

實驗室有幾位學弟，在上學期修了人工智能 (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) 的格子必然有炸彈。

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

8-puzzle

解 8-puzzle 是一個古老的益智問題。

年少時對解這類「益智問題」，總有著那麼些興趣。學生時期，在人工智能 (AI: Artificial Intelligence) 的課程裡，教授們介紹 searching methods 時，有時也可以看到這個問題。可惜的是，或許是因為當時的課程內容太豐富，反倒沒有機會真的將這個程式寫出來玩玩。


這一陣子想整理一些從前感興趣的小程式，偶然間就想起 8-puzzle（或者更大盤面的「15-puzzle」）來。於是，花了些時間用 PHP5 把它實作出來。

演算法是採用 IDA* (Iterative Deepening A*)，因此理論上求得的應該是最佳解_{（什麼時候不是最佳解？就是我程式寫錯的時候啦）}。上圖左方的盤面，程式花了 22 步才走到右方的目的地。

產生迷宮的另一種方法

約一年多以前，曾寫了些關於「如何產生迷宮」的 Blogs。

前些時日，在書店亂逛，無意間看到一本關於資料結構與演算法的書，裡頭提到利用 Set Union 來產生迷宮的方法_{（Weiss: Data Structures and Algorithm Analysis in C++, 3rd edition, pp.331-334）}。

這個方法的概念很簡單：

1. 首先，將地圖中的每個單位 (cell) 視為個別的小集合，然後將這些集合的 collection 稱為 C。


2. 隨意從 C 裡抽出兩個集合 x, y。若這兩個集合「打掉一面牆」之後可以連通，那麼就將這兩個集合聯集 (union) 成集合 z，並將 z 放入 C 中。


3. 反覆執行步驟二，直到最後 C 只含有一個集合為止。

我覺得這個演算法很漂亮。

春假期間騰出一些時間，用 PHP5 把它實作出來。（為了避免無效率地從 C 中挑選元素，我先將所有「可被打破的牆」排序並打亂後，逐一檢視每一面牆「若被打掉後，是否相當於將 C 裡的兩個元素作聯集的動作」。）


產生的迷宮「效果」如何？我覺得還算不錯。它似乎比「稍微有些曲折的迷宮」的結果來得有變化，但並沒有「更為曲折的迷宮」所產生的迷宮那麼蜿蜒。