對戰踩地雷 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 設計。