網頁

2010年10月15日 星期五

對戰踩地雷 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),應該會有不錯的成果。

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