作者stimim (qqaa)
看板java
標題GeminiAI 的設計邏輯 (下)
時間Wed Sep 29 09:25:18 2010
其實在大約兩年前我曾經寫過一個自動玩 遊樂場 中的踩地雷程式
程式Demo:
https://www.youtube.com/watch?v=8H5izBQEB7U
而這次的 AI 中的機率計算基本上也是用之前的大架構，
只是實作上比較OO (之前是很多Global Variable和錯縱複雜的function call...)
--------------------
在上一編中，我對每一格 NumberedSquare 都做了 checkNeighbor 的動作，
在每一個 NumberedSquare 和 UnknownSquare 中，都有一個HashSet neighbors：
numberedSquare.neighbors 是一些 UnknownSquare ，代表受他限制的
UnknownSquare 有哪些
unknownSquare.neighbors 是一些 NumberedSquare ，代表他受哪些
NumberedSquare 限制
而checkNeighbor 就是在建立這些關係：
Ex1:
1 ? // ? 是 UnknownSquare
1 ?
1 ?
1.neighbors = {
? ,
? }
?.neighbors = {
1 ,
1 }
1.neighbors = {
? ,
? ,
? }
?.neighbors = {
1 ,
1 ,
1 }
1.neighbors = {
? ,
? }
?.neighbors = {
1 ,
1 }
當所有的 NumberedSquare 都呼叫過 checkNeighbor 後，這些關係就建立好了
接下來則是要把地圖分成幾個區塊 (在我的程式中稱為section)
為什麼要畫分 section 呢？因為在地圖上並不是所有的格子都會互相影響：
Ex2:
1 . 2 . // . 是 UnknownSquare
. . . . 可以發現，
綠色區的炸彈分佈方式並不會影響
黃色區的炸彈分佈
. . . .
綠色區有6種可能的排列，
黃色區有3種，分開算的話就只要算9
2 . . . 種，一起算的話則是 6*3 = 18 種，當地圖越大時，差別越明顯
numberedSquare.belongsTo 是一個 Set 的 Reference ，代表他屬於哪一個section
belongsTo 的初始值為 null ，建立 section 的方式為：
unknownSquare.unionNeighbors() 這個方法會把 unknownSquare.neighbor 中的
NumberedSquare 合並到同一個 Section
對 UnknownSquare v 來說 若 u1, u2 都屬於 v.neighbor
則 u1 , u2 屬於同一個 Section ，因為他們的鄰格會互相影響
unionNeighbors:
對 u 屬於 v.neighbor
result = u.belongsTo 的 size > result 的 size
result = u.belongsTo
如果所有的 u.belongsTo 都是 null ：
result = new Set
把 v.neighbor 中的其他 section 加到 result 中
// 也就是：result.addAll( u.belongsTo )
對 u 屬於 result ：
u.belongsTo = result
現在我們有了一些 section 了以後，就可以藉由枚舉所有可能來計算未知格是炸彈
的機率：
computeProb( section ):
對於 NumberedSquare v 屬於 section
如果 v.makeAssumption() 成功：
如果 section 中的所有格子都已經有 assumption 了：
計錄現在的 assumption
否則：
前往下一個 v
否則：
到目前為止的 assumption 是有問題的，回到上一個 v
當以上的假遞迴跑完了以後，我們應該就計錄了一些 assumption ，這些都是可能的
分佈方式，由此可以算出 unknownSquare 是炸彈的機率
unknownSquare 是炸彈的 assumption 數
p = -------------------------------------
全部的 assumption 數
------------------------
PS:
畫分 section 的做法是在兩年前想到的，因為 16 x 30 的地圖很大，當開出來的
格子變多時，如果還是當成同一個 section 來算機率，會慢很多
如果 section A 有 50 種可能
section B 有 50 種可能 => 分開: 100 種 ， 合起來: 2500 種…
不過，這次比賽的地圖只有 16 x 16 ，就算全部一起算也不會慢太多就是了。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.182