對戰踩地雷 AI 設計 (3)

當初開始寫這系列文章時，我只打算用二至三篇文章介紹我所使用的方法，第一篇是辨識出確定的地雷，第二篇則是使用機率去猜比較有可能是地雷的格子。然而在我開始著手第二篇文章時，我發現我在程式中所使用的機率完全不正確，既然如此，似乎也沒有什麼寫出來的必要？因此我在第二篇中另闢戰場，用正確的機率做了些簡介，並且在文章結尾埋了令人玩味的梗：最強 AI 設計！。

這裡的最強當然不是指此次比賽的結果，我設計的 AI 在比賽結束後不久即已被超越(詳見 PTT Java 板踩地雷系列文章)，並且也被人類玩家慘電，實在距離所謂的 "最強" 非常遙遠。既然如此，我所說的最強指的是什麼呢？這個最強必須建立在一個難以達到的前提之下：如果我能夠知道每一個格子為地雷或各數字的的機率。

在上一篇文章中可以看到，只要不是在開場的兩步之內，想要計算出完全正確的機率是非常困難的。但是，如果我假設能夠算得出來呢？

如果我能夠知道目前地圖上每一個格子為地雷及各數字的機率，我便能夠算出「假如我猜錯了，我的對手猜中地雷的機率」，甚至繼續計算「如果我的對手也猜錯了，我這次猜中的機率是多少」，然後再繼續……。雖然可以一直算到遊戲結束，不過以踩地雷這遊戲的特性來看，算到兩、三步之後意義應該就不大了。

我們用期望值來表示，下在 A 猜中地雷的期望值設為 E[A]，而在這一步之後對手利用 A 的數字猜中地雷的期望值為 E'[A]，於是一個理想的 AI 便誕生了：

雖然這公式看起來很簡單，並且可能還存在漏洞，但是我認為已經足夠了。

註：由於我並沒有考慮到第二步的情形，因此當 E[A] > E'[A] 成立時，有可能 E'[A] > E''[A]，此時反而會讓自己進入不利情況。反過來看，當 E[A] > E'[A] 不成立時，也有可能出現 E'[A] < E''[A]，使得自己的情況比對手更好。

幻想完了，讓我們回到現實，雖然沒有辦法計算出完全正確的機率，但有沒有辦法取得估計值呢？我認為 PTT Java 板 stimim 的文章(#1CefM1Hg)是個很好的出發點，如果能夠正確解決我所提出的問題(#1CerxcHD)，應該會有不錯的成果。

這系列文章到此算是暫時的告一段落，未來如果還有文章，應該會是我照著上述策略實作時的心得或是其它發現吧。

對戰踩地雷 AI 設計 (2)

在套用機率來設計 AI 之前，讓我們來看看機率能夠做到什麼程度。

先來考慮最簡單的場景: 開局，在開局的第一手裡，無論下在哪，踩中地雷的機率都是 51/256 = 0.199219。但若是沒有踩中地雷呢？我們考慮以下三種情形:

1. 下在角落: k=3
2. 下在邊緣: k=5
3. 下在其他位置: k=8

註: k 為鄰居數量

代入公式 C(k, n) * C(256-k-1, 51-n) / C(256, 51)
我們可以算出下了第一步之後，出現各種數字的機率，便可以得到以下的表格:

各數字出現機率:

數字	角落(n=3)	邊緣(n=5)	其他(n=8)
0(空白)	0.408787	0.259806	0.130630
1	0.309626	0.331252	0.270543
2	0.076263	0.164802	0.239116
3	0.006106	0.039977	0.117756
4	0.000000	0.004726	0.035327
5	0.000000	0.000218	0.006608
6	0.000000	0.000000	0.000752
7	0.000000	0.000000	0.000048
8	0.000000	0.000000	0.000001

根據經驗，開局時有兩種情形特別糟糕，一是點出的數字剛好等於 k，這表示對手要收下這 k 枚地雷了，好在這種情形發生的機率並不高。第二種情形是點到空白，這時候通常都會炸出一片空地，雖然不是絕對，但對手多半也是能輕鬆取分。

而根據上面的表格，只要第一步下在角落、邊緣以外的位置，就能將發生這兩種情形的機率降到最低。因此機率告訴我們的第一件事，就是開局時不要下在角落和邊緣。


接下來換到對手的角度，如果對方(開局者)第一步沒有踩到地雷，又該如何應對？
註: 此處我們假設對手也知道第一手不下在外圈比較好，所以僅考慮此種情形之機率。

如果出現的數字為 n，且考慮只下在此數字的八個鄰居時，踩中地雷的機率為 n/8。
踩該數字上下左右四個鄰居而該位置是空白的機率: (C(3,n) * C(244,51-n)) / (C(8, n) * C(247,51-n))
而下在斜角位置卻是空白的機率則為: (C(5,n) * C(242,51-n)) / (C(8, n) * C(247,51-n))
計算之後將可得到以下表格:

數字	踩中地雷機率	踩數字上下左右炸開機率	踩數字斜角炸開機率
1	0.125000	0.189666	0.199619
2	0.250000	0.055024	0.117023
3	0.375000	0.009311	0.060020
4	0.500000	0.000000	0.024623
5	0.625000	0.000000	0.006313
6	0.750000	0.000000	0.000000
7	0.875000	0.000000	0.000000
8	1.000000	0.000000	0.000000

但這時候如果另闢戰場去踩新的區域:
踩中地雷機率為: (51-n) / (256-9)
炸開機率為: C(256-9-9, 51-n) / C(256-9, 51-n)

數字	踩中地雷機率	炸開機率
1	0.202429	0.125727
2	0.198381	0.131714
3	0.194332	0.137954
4	0.190283	0.144454
5	0.186235	0.151225
6	0.182186	0.158277
7	0.178138	0.165620
8	0.174089	0.173264

機率教會我們的第二件事，就是當出現數字為 1 時，請選擇另闢戰場；其餘情況則猜上下左右。


沒有數字和只有一個數字的情況我們已經考慮完了，該是時候面對現實了，來看看兩個數字的情形吧:

在上圖左上角的三個未開區域中，可能的解共有兩組，分別是 "左右兩邊各一枚地雷" 和 "只有中間有地雷"，
假設在這地圖上共剩下 27 個未開點 (含左上角那三個)，並還有 10 個未找出之地雷。

此時在三格中出現一個地雷的組合數是: C(3,1) * C(24,9)，機率為: 0.640000，
而出現兩個地雷的組合數是: C(3,2) * C(24,8)，機率為: 0.360000，
雖然在這個例子中地雷出現在中間的機率較高，但是一旦猜錯將立刻奉送對手兩枚地雷，因此在猜與不猜之間仍需仔細拿捏。


再來看看更複雜的例子:

在上圖的場景中，可能的解變得更多了，A,B,C 區塊各自的地雷數量可能是: (2,0,3), (1,1,2), (0,2,1)。

只要分別找出數字 2 和 3 他們共有的鄰居(B)及獨有的鄰居(A 和 C)，並且使用前面提過的機率公式，我們一樣能夠計算出每一種解出現的機率，並且推測出最有可能是地雷的位置。然而這些公式都是建立在我們能夠算出其餘未開區域出現各種地雷數量之機率的前提下，但是在實際對戰中，這種情形幾乎不可能出現。而數字的牽扯也經常不只有兩個，更多的數字將會讓公式變得非常複雜。

到此為止，真實機率的計算可說是宣告失敗了，所以這篇就在此打住吧，不過下一篇將會看到機率的反擊: 最強 AI 設計。

對戰踩地雷 AI 設計 (1)

日前 PTT Java 板舉辦了一場懸賞踩地雷 AI 的活動，我也被主辦人 PsMonkey 脅迫參加，開發了自己的 AI，並且在 AI 之間的 PK 獲得了不錯的成績。然而當對戰於真人對手時，所有人的 AI 都明顯屈居下風，面對人類高手時，甚至是被打得毫無招架之力。(參看排行榜)

為了促進 AI(s) 的進步，在這篇文章中我將會分享我的想法與程式碼，歡迎隨意取用。


在開始之前，先讓我做些定義:
    num(x,y): 表示在地圖 (x,y) 位置所顯示的數字，也代表在其周圍九宮格內的地雷數量。
    numUnknown(x,y): 表示地圖 (x,y) 周圍九宮格內 "未開" 的數量。
    numCommonUnknown(x1,y1,x2,y2): 表示地圖上 (x1,y1) 和 (x2,y2) 共同鄰居中未開的數量。
    numMine(x,y): 表示地圖 (x,y) 周圍九宮格內，"已經被點開" 的地雷數量。

而關於圖形的說明如下:

    灰色格子: 表示尚未點開
    白色空格: 表示周圍無地雷
    數字k: 表示周圍有 k 個地雷
    ?: 表示已經點開，但究竟是空格或著數字是多少我們並不關心
    X: 表示已經點開的地雷


我將踩地雷 AI 的任務分成兩個部份，第一個部份是試著找出確定為地雷的位置，在這個部份中，一旦能夠確認出地雷位置，就可以肆無忌憚的選取該位置。而當地圖上的資訊不足以確切的判斷出地雷的位置時，我將這種情況歸類為第二部份。

此篇文章將只說明第一部份，第二部份留待下一篇文章。

場景1:

在第一個部份中，最簡單的狀況就像是上圖這樣: 當 num(x,y)-numMine(x,y) 等於 numUnknown(x,y) 時，表示這些未開都是地雷。

這種情況在 AI 的實作非常直覺，因此就略過不提。

場景2:
然而並不是每個情境都這麼簡單，例如下面這張圖。

在上圖中，單考慮數字 2 並沒有辦法辨別出那一個位置才是剩餘的地雷，然而連數字 1 也一起考慮時，我們便能夠確定位置 (1,2) 一定不是地雷，進而確定地雷的位置在 (1,1)。

遇到這種情況時，我的處理方式是，找出所有確定不是地雷的位置，並且將它們做上標記，如此一來就有機會將場景 2 變為場景 1。

到目前為止，處理第一部份的 Pseudo Code 會是這樣:

    do{
        // 處理場景 1
        // 處理場景 2
    } whlie 當場景 2 辨識出新的 "確定不是地雷的未開區域" 時繼續

場景3:
接下來這種場景也很容易見到，但就不是那麼容易處理了。

只看數字 2 時，我們只能知道位置 (1,1), (1,2), (1,3) 之中有兩個地雷，卻沒有辦法得知究竟是哪兩格。然而考慮數字 1，我們能判斷出在位置 (1,2) 和 (1,3) 中只有一格是地雷，因此可以確定 (1,1) 也是地雷。

在這個場景中，因為數字 1 的所有鄰居也都是數字 2 的鄰居，並且數字 1 沒有其他未開鄰居，因此雖然我們並不知道在這些共同鄰居中，哪些點才是地雷，但是卻能知道其中地雷的數量有多少。利用這些資訊，就能夠算出數字 2 獨自擁有的鄰居中有多少地雷，如果地雷數等於獨自擁有的未開鄰居數，那麼...bingo! 這些數字 2 獨有的未知鄰居全都是地雷。

程式部份我是這樣寫的，首先我掃遍地圖中所有位置為數字的格子 A，對每一個符合的格子再進一步找出另一個可能與它有共同鄰居的數字格子 B。(很顯然，A 與 B 的距離一定是兩步之內，因此我只需要掃的 A 週邊共 24 個格子即可。)接下來只要檢查 numUnknown(A)-numUnknown(A,B) 是否等於 num(A)-num(B)，如果成立，則表示 A 獨有的鄰居都是地雷，讓 AI 隨便從中選一個吧！

加上場景三，Pseudo Code 變成這樣:

    do{
        // 處理場景 1
        // 處理場景 3
        // 處理場景 2
    } whlie 當場景 2 辨識出新的 "確定不是地雷的未開區域" 時繼續

以上就是我設計的 AI 對於第一部份的處理。

根據我開發時的測試，我認為場景三的處理是我的 AI 能夠領先其他 AI 的關鍵。

下一篇將繼續討論第二部份，當無法找出確定地雷時的策略與機率。