Re: [惡搞] 懸賞踩地雷 AI！
看板java作者AmosYang (LetMeGoogleThatForYou)時間15年前 (2010/09/24 14:22)推噓1(1推 0噓 1→)留言2則, 2人參與討論串8/21 (看更多)
LolAI 的設計
1. 對每一格作以下的分析
a. IF 這一格已經被標為地雷 OR 已知這一格是空白 (數字零)
THEN 略過這格 (因為這格並不能告訴我們什麼資訊)
b. IF 這一格是未知狀態 AND 所有的鄰居中沒有任何已知格
THEN 把這格加入 wagCandidate 這個 collection 後結束對這格的分析
(因為我們沒辦法作任何 educated guess,
所以把這格加入 Wild Ass Guess Candidates XD)
c. (如果我們到了這裡，代表這格通過了前面兩個檢查
易言之，這一格沒有地雷，但我們知道他的鄰局裡有地雷 (這一格有非零的數字)
這一格可以提供有用的資訊)
c.1 計算這一格的鄰居裡確實有多少地雷
* 我們知道這格的數字 (代表著他的鄰居裡總共有幾顆雷)
* 我們看得到這格所以的鄰居的狀態 (所以我們知道有哪幾個鄰局是未知，
有哪幾個鄰居是已知雷)
-> 是故，我們知道「這格的未知鄰居裡有幾個雷」
例: ? ? ?
? 3 _
X _ _
X 代表已知雷
_ 代表空白格
? 代表未知格
那我們就知道那四個 ? 中有至少兩個雷，且，至多兩個雷
c.2 把 c.1 的計算結果用以下的方式記錄起來
{ min <= [? ? ? ... ?] <= max }
那些 ? 是 (x,y) 的形式，也就是該 ? 格的座標
易言之，我們可以用上面這個方式把我們對目前棋盤上的狀態通通寫下來
以 c.1 裡的例子而言，我們寫下來的 clause 就會像這個樣子
{ 2 <= [ (0,0) (0,1) (1,0) (2,0) ] <= 2 }
用中文說的話，上面這個 clause 就代表
「在 (0,0) (0,1) (1,0) (2,0) 這幾格中，有至少兩個雷，有至多兩個雷」
我們會把場面上所有數字不為零的格子都如此分析一次
然後把所有的 clause 都存起來
這些 clause 就是 LolAI 表示「資訊」的方式
=========================================================================
2. 用 deduction 的方式，從所有已知 clause 中萃取出最重要的資訊
假設有以下的情形
_ _ ?
_ 1 ?
_ 2 ?
_ _ ?
當我們用上述第一節裡提到的方法分析這個棋盤時
我們會從 (1,1) 這格得到這個 clause: { 1 <= [ (2,0) (2,1) (2,2) ] <= 1}
我們暫且將此 clause 稱作 C1
我們會從 (1,2) 這格得到這個 clause: { 2 <= [ (2,1) (2,2) (2,3) ] <= 2}
我們暫且將此 clause 稱作 C2
以下我將解釋 deduction 的演算法， LolAI 的成敗就在於此演算法上
為了簡化文字描述，我將 clause 的表示方法以 Java code 定義如下
class Clause
{
int min;
int max;
Set<Cell> cells; // 注意，這是個 set , 等一下我們將會利用 set 的計算
}
以 C1 為例，
C1.min == 1
C1.max == 1
C1.cells == [ (2,0) (2,1) (2,2) ]
從 C1 與 C2 這兩個 clause 裡，我們可以知道三件事
#1 在 C1 與 C2 共有的格子 (cell) 中，至少及至多有幾個雷
#2 在 C1 獨有的格子中，至少及至多有幾個雷
#3 在 C3 獨有的格子中，至少及至多有幾個雷
易言之，
#1 代表 C1.cells ∪ C2.cells 的部分
#2 代表 C1.cells - C2.cells 的部分
#3 代表 C2.cells - C1.cells 的部分
易言之，從 C1 及 C2 這兩個 clause 中，我們可以算出三個新的 clause
讓我們稱他們為 N1, N2, N3
在這裡我將先略過數學上的推演，直接告訴你最後推導出來的算式
因為我已經打字打得快發瘋了 XD
如果你能獨立的推導一次來驗證這個算式的話，那是再好也不過的了
N1.cells = intersection(C1.cells, C2.cells)
N2.cells = C1.cells - C2.cells
N3.cells = C2.cells - C1.cells
N1.min = max(0, max(C1.min - N2.cells.size, C2.min - N3.cells.size))
N1.max = min(N1.cells.size, min(C1.max, C2.max))
N2.min = max(0, C1.min - min(N1.cells.size, C2.max))
N2.max = min(N2.cells.size, C1.max - max(0, C2.min - N3.cells.size))
N3.min = max(0, C2.min - min(N1.cells.size, C1.max))
N3.max = min(N3.cells.size, C2.max - max(0, C1.min - N2.cells.size))
OMG... 在重新檢視這段 code 時，我找到 LolAI 之前的 bug 了…
又是個天殺的 copy&paste error... orz
現在 LolAI 的 clause deduction 就應該完全正確了… orz
如果我沒有打錯字的話，用這個演算法，從 C1 與 C2 你會得到
N1.cells = (2,1) (2,2)
N2.cells = (2,0)
N3.cells = (2,3)
N1.min = 1
N1.max = 1
N2.min = 0
N2.max = 0
N3.min = 1
N3.max = 1
易言之
N1: { 1 <= [ (2,1) (2,2) ] <= 1 }
N2: { 0 <= [ (2,0) ] <= 0 }
N3: { 1 <= [ (2,3) ] <= 1 }
用中文說出來的話，就是
N1: 在 (2,1) (2,2) 裡，至多有 1 雷，至少有 1 雷
N2: 在 (2,0) 裡，至多有 0 雷，至少有 0 雷
N3: 在 (2,3) 裡，至多有 1 雷，至少有 1 雷
至此，我們已經從 C1 與 C2 中萃取出了更重要的資訊
所以，把所有的 clause 互相進行 deduction 的動作後
我們可以找出這些 clause 一開始沒有直接告訴我們的事
在這裡我略去了「把所有的 clause 互相進行 deduction 的動作」的詳細步驟
重點是，必須一直把新生出來的 clause 正確地與現有的 clause 融合
然後重覆進行這步驟，直到沒有新的 clause 可以從已知的 clause 被算出來
還要適當地丟棄完全無用的 clause
這一段是吃 CPU+memory 最重的地方，我為了 optimize 這段花了不少心力
甚至生出了一些 bug
所以我先不想多談這部分的架構 (而誤導你)，或許你獨立生出來的架構會更好
========================================================================
3. 我想，看到這裡你已經了解接下來要作什麼了
第二節所提到的是 AI 的腦的肉體
而第三節 (也是我之前沒有足夠時間徹底研究的) 則是 AI 的靈魂 (人格)
首先，以上述我們知道的 N1 N2 N3 來看
很明顯地 N3 是已知解 ( N3.min == N3.cells.size == N3.max )
所以我們應該先把 N3.cells 裡的格子先餵給 game driver
而比較 N1 與 N2 可以知道，在 N1 裡面挑一個猜至少有 50% 的命中率
所以我們應該先猜 N1.cells 裡的東西
而 C1 與 C2，如果你的 deduction engine 寫得正確的話，應該要被丟掉
因為他們沒有比 N1 N2 N3 來得嚴謹
當你把所有最精萃的 clause 找到時，
此 AI 就具有人類玩家在這遊戲裡的思考能力
不能必勝，但 This is the best it can get.
而現在回頭來看，LolAI 的慘敗並是應該的
因為 LolAI 並沒有適當地丟掉無用的 clause
且 LolAI 並沒有正確地在 wagCandidate 與非已知解的 clause 中做出正確的選擇
是故， LolAI 死好 XD
如果要作出最強的 AI ，
這一部分的重要性不輸給上面第二節所提到的 clause deduction
易言之，就是當 AI 把所有已知解都餵給 game driver 後
接下來 AI 如何從不確定解裡挑出最好的 guess, 這就是決定勝負的地方
===============================================================
如同 tkcn 所說的，如果能合作寫 AI 的話將會是一大樂事
希望上述對 LolAI 的解析能派上用場，提供給讀者一個優良的踏腳石
(歡迎索取我的程式碼作參考 :) 不用擔心什麼智財權什麼鬼的，想怎麼用就怎麼用
LolAI 程式碼直接釋出在 public domain)
(如果可以的話，我希望在這個聯合 AI 的製作過程中先不要去 winmine 找資料
我想要 beat winmine 板板友 fair and square :) )
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 65.87.177.87
※ 編輯: AmosYang 來自: 65.87.177.87 (09/24 15:09)
※ 編輯: AmosYang 來自: 65.87.177.87 (09/24 15:27)
※ 編輯: AmosYang 來自: 65.87.177.87 (09/24 15:36)
→
09/24 15:40, , 1F
09/24 15:40, 1F
推
09/24 16:44, , 2F
09/24 16:44, 2F
討論串 (同標題文章)