網頁

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 的關鍵。

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

沒有留言:

張貼留言