Re: [惡搞] 懸賞踩地雷 AI！
看板java作者AmosYang (LetMeGoogleThatForYou)時間15年前 (2010/10/09 23:00)推噓1(1推 0噓 4→)留言5則, 3人參與討論串17/21 (看更多)
※ 引述《wendly777 (小水)》之銘言：
: → AmosYang:大略地看了一下， **感覺** 與 LolAI 的想法很接近… 10/09 13:45
: → AmosYang:但 LolAI 對上 TkcnAI 勝率硬是只有三成 XD 10/09 13:46
: → AmosYang:是故…還是不能靠感覺… ... 10/09 13:53
: → tkcn:我總覺得最近都睡不好... 10/09 14:30
XD
: → wendly777:剛剛看到LolAI最新的code，抓下來PK500場，結果半小時過 10/09 14:51
: → wendly777:了還沒跑完= =，我自己跟自己PK大概45秒就跑完500場了 10/09 14:52
: → wendly777:你可能先最佳化一下比較好抓問題，可能太複雜產生bug 10/09 14:54
: → wendly777:講錯應該是500張地圖，另外GeminiAI運算速度跟我差不多 10/09 15:02
LolAI 0.5 的 perf 問題在於我一開始對整個架構的需求作了錯誤的假設
演算法本身的複雜度並不高，但實作的部分很「浪費」
所謂錯誤的假設，
1. 就是我以為物件的生命週期是 cross-session, 而非僅限於該次 "shoot"
2. 我以為棋盤的大小會是像 30*30 或 50*50 這種規模 (後來才知道是 16*16 XD)
易言之，在我一開始的想法裡，整個東西應該是這樣運作:
GameEngine 通知 AI: 「輪到你了」
-> AI check 上次計算的資料有沒有剩下來
沒有的話，AI 開始重新計算
(LolAI 的 initialization 很貴，付了很多為了把實作抽象化的稅)
-> AI 計算完成，得到 a set of "shoot" candidates
這些 candidates 肯定是地雷
-> AI 從 shoot candidates 挑一個餵給 GameEngine
剩下沒用到的部分 cache 起來
只要之前計算出來的 candidate 還沒用完， LolAI 就不用重新計算
但事實上，整個東西是這樣運作:
GameEngine 通知 AI: 「輪到你了」
-> AI 開始計算
-> AI 計算完成，得到 a set of "shoot" candidates
-> AI 從 shoot candidates 挑一個餵給 GameEngine
-> AI object 生命週期必須結束
因為 game engine 並沒有 session 的觀念
也就是說，AI 並沒有辦法針對 sesstion 來 cache 資料
所以，一開始我預期為了實作抽象化的稅應該不會太慘
且我覺得在大棋盤上，cache 資料會比每回合重新算來得好
但在現行的架構下， LolAI 每一回合都要付這些稅… perf 就炸了 XD
又，所謂「實作抽象化」就是 LolAI 可以很簡單地用來計算
不同的棋盤上的踩地雷，例如三角形格子、六角形格子
這種實作的 perf 比直接對一個 2D array 作存取來得慢，但寫起來比較爽 XD
有興趣的話可以比較看看，
「如果今天要把 AI 改寫成處理六角格的棋盤，或著是 3D
或著是更不規則的形狀，看看各種 AI 的實作有多少部分需要重寫」 :D
總結:
1. LolAI 因為對整個架構的估計錯誤， perf 就爆炸了
(但其演算法其實很簡潔…雖然 v0.5 裡有 50% 的計算是不必要的)
2. LolAI 作者對「抽象化」有異常的執著， perf 就又爆炸了
3. 不管 perf 有沒有炸， LolAI 目前只能在
「根據現有的資料判斷一定是地雷的格子」這點上與其他 AI 分庭抗禮
在「根據現有的資料判斷有可能是地雷的格子」這點上是確實輸給其他 AI 的
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 24.148.239.184
易言之， LolAI 可以說是完全慘敗
畫蛇添足的下場就是 perf 吃的比別人兇，且勝率沒有也比較高
要扭轉戰局只能砍掉重練，得先去寫個一、兩百題 ACM 把腦殘治好 XD
※ 編輯: AmosYang 來自: 24.148.239.184 (10/09 23:13)
推
10/10 02:01, , 1F
10/10 02:01, 1F
→
10/10 07:00, , 2F
10/10 07:00, 2F
→
10/10 10:59, , 3F
10/10 10:59, 3F
→
10/10 11:00, , 4F
10/10 11:00, 4F
→
10/10 11:02, , 5F
10/10 11:02, 5F
討論串 (同標題文章)