網頁

2010年9月30日 星期四

對戰踩地雷 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.4087870.2598060.130630
10.3096260.3312520.270543
20.0762630.1648020.239116
30.0061060.0399770.117756
40.0000000.0047260.035327
50.0000000.0002180.006608
60.0000000.0000000.000752
70.0000000.0000000.000048
80.0000000.0000000.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))
計算之後將可得到以下表格:

數字踩中地雷機率踩數字上下左右炸開機率踩數字斜角炸開機率
10.1250000.1896660.199619
20.2500000.0550240.117023
30.3750000.0093110.060020
40.5000000.0000000.024623
50.6250000.0000000.006313
60.7500000.0000000.000000
70.8750000.0000000.000000
81.0000000.0000000.000000

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

數字踩中地雷機率炸開機率
10.2024290.125727
20.1983810.131714
30.1943320.137954
40.1902830.144454
50.1862350.151225
60.1821860.158277
70.1781380.165620
80.1740890.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 設計。

2010年9月26日 星期日

對戰踩地雷 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 的關鍵。

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