Minei the MineSweeper Flags AI (0)

time: 2010-09-27 01:10 ~ 03:36
name: Minei the MineSweeper Flags AI (0)
body:
從何處說起呢？我想大家都知道 MineSweeper, 踩地雷。微軟另外還有一個版本，
叫做 MineSweeper Flags, 也就是可以在 MSN 上跟別人玩的版本。既然是雙人的，
遊戲玩法自然有些不同。原本的版本是要把地雷全部「標記」出來，然後不要踩到
地雷。而這 MSN 上的版本，雖然同樣是要把地雷「標記」出來，但卻反過來，是要
去踩到，如果沒踩到的話，就換人踩；反之可以繼續一直踩地雷。遊戲結束時，則
比較誰踩到的地雷比較多，多者勝。

我想遊戲的關鍵在於 -- 當一格是地雷的機率超過 50%, 則踩！若沒有任何格子的
地雷率超過 50%, 則想盡辦法讓對方下次行動時，沒有任何一格可以超過 50%.
或許是一種 minimax 演算法，不過我不熟，只是忽然想起這個名詞。

日前在 PsMonkey 的 buzz 上看到，他說寫了一個 AI 對戰的版本，看大家有沒有興趣
自己寫一個 AI 來投稿比賽。畢竟我總是覺得被時間壓迫著，所以看到很明顯會很累的
活動，雖然說有興趣參加，但想到好累好累就算了...。但是看著大家的討論熱烈，雖然
因為沒參加所以我也沒細看，但愈看真的是愈手癢，尤其我又向來喜歡這類的題目。
最後終於... 決定下海用 scala 寫一個看看。

於是開始參考《對戰電腦版踩地雷》。從來沒用過 GWT 耶。老實講，上面的說明也
寫得不是很清楚。總之我就先去抓了 GWT, 然後發現 PsMonkey 沒提供 build.xml,
我只好用 GWT 的 script 產生一個新的 app, 然後把裡面的 build.xml 拿過來改。
這應該算是我第二次用 ant, 第一次是在寫 spellbook 時。我只能說，其實 ant
是還算不錯的工具，只是用 xml 寫，實在難免會 bloat... 所以說來說去，還是 rake
比較好用啦。那時寫 spellbook 時，也本來想用 rake 自己寫 build task, 但最後
碰上很複雜的 dependency 關係，一時三刻解決不了，也只好回頭用 ant, 畢竟這是
確定可以用的，沒必要自己找自己麻煩。

或許有趣的是，ant (嚴格來說應該是裡面的 task) 幫你解決 circular dependency 的
問題，而在 C/C++ 中，這種問題需要自己解決。碰愈多東西之後愈會發覺，其實真的
很多問題是不管用什麼解決方案都一定會面臨的問題，只是有沒有人幫忙解決而已。
因此很多的爭論，我想看在很多人眼裡，真的就只是笑笑就好，如果懶得解釋的話。

成功把裡面的 RandomAI 跑起來之後，接下來就是做一個 scala 空殼 AI 了！

p.s. Mac 的 Chrome 無法跑 GWT devmode! 覺得有點可笑。我不懂這要灌 plugin 的
   道理是什麼？而 Mac 的 FireFox 真的是很慢啊！測試起來說真的有點痛苦。

-

在 build.xml 上打滾許久，總算成功把 scala-library.jar 放入 classpath,
把我的空殼 scala class 在 GWT 上跑起來，一個永遠只踩 (0, 0) 的測試 AI.
接下來在撰寫 AI 的過程裡，我改變了好幾次 build 的方式。中間過程不贅述了，
總之最後則引用 scala 本身的 ant task, 把用 scalac compile 好的 class 再
archive 成一個 jar 檔。這樣做的原因很簡單，雖然我沒用到幾個 class, 但是
scala compile 出來的結果，如果用到 closure/lambda function, 就會產生一堆
anonymous classes. 考慮到別人可能沒有 scala, 所以我得交出 binary 才行，
給一堆 class 檔的話實在超麻煩的。說真的我很討厭這種無法控制的輸出檔案，
我喜歡自己管理檔案結構，如果實作細節會影響檔案結構，覺得非常不自由。
scala 這點其實已經比 java 好很多了，但還是有不少限制。單就輸出 class 而言，
包成一個 jar 檔可能是唯一的解法，這樣看起來乾淨多了。之前看到 ruby-core
也有在討論 ruby archive 檔，我也很希望有這個功能，雖然想要的人似乎不多。

這些都敲定之後，總算可以開始安心寫著 AI 了。

一開始因為想測一些小東西，要 compile 說真的很麻煩，而 scala 很好心地提供
interprete 模式，這拿來測小東西真的很方便。缺點就是，他的行為和 compile
模式其實有一點差距...。例如定義一定要 top-down, 這造成的麻煩就是沒辦法寫
有 circular dependency 的 class! 當然可以的話盡量避免，但有時候還是會寫出。
這點應該是最頭痛的差異吧？

撰寫過程大概是這樣，一開始其實都在寫一些我需要用的工具。可以把他想像成，
我需要撰寫我用在這 AI 上的邏輯語言。最簡單的例子就是 nearby, 寫這種有格子的
程式，我一定都會想寫這樣的東西。給定一個座標，回傳這個座標周遭的座標(或格子).
類似的東西我寫過無數次了。而事實上，最大的參考程式則是 spellbook. 我得承認
太久沒碰 scala, 很多東西都忘了，所以不斷翻 spellbook 參考當初很多東西的寫法。
值得慶幸的是，九宮格真的還是比蜂窩格好寫得多，所以沒花太多時間。

而我也注意到，我現在已經變得喜歡用 TreeMap 去 model map, 而非用 2d array,
or 1d array simulate 2d array! type 是 (Int, Int) => Block. 這樣做的理由是，
我可以很輕易地管理片段的地圖。像是 sparse array 那樣。事實證明一開始這樣寫，
使得我後來很多東西都可以很簡單地寫好。

當然，我不敢說這是個好作法，至少這很符合我的思維，因此寫起來順手。

因此這部份就是先建立 map, 然後我可以建立各種其他的 map, 例如雷圖就是：

def map_mine: MineMap = map.filter(_._2 == mine)

這樣做的好處是，我可以把地圖傳進 nearby, 因此我可以輕易描述周遭的地雷，
而不是把周遭的格子都抓出來，然後再過濾地雷；或是我可以不用處理邊界問題，
沒有 array bound 的問題。

不幸的是，事後證明 map_mine 不能這樣去過濾，這造成可笑的結果...
因為地雷不是一個值，而是兩種可能的值！分別是 9 與 -9.
不知道為什麼，我一直以為是 -8... 所以上面的 mine 定義是 -8.
後來我被迫把 mine 改成 9, 然後重新定義為：

def map_mine: MineMap = map.filter(_._2.abs == mine)

好笑的結果在於，原來我原本的 AI 都是根據錯的結果去算，難怪他一直在踩完全
不可能是地雷的點，讓我覺得很沮喪，為什麼寫這麼久寫出這麼蠢的 AI, 而且我還
找不到 bug 到底在哪裡？觀察了很久，才注意到他好像根本不認得地雷！不禁懷疑
是否 PsMonkey 的踩地雷在連續踩地雷時不會更新地圖資訊？導致 AI 以為有地雷的
地方其實沒地雷？這真的追查很久，因為我發現他根本沒有去計算機率，非常怪。

好不容易從他的程式中找到 9 與 -9 才是真正的地雷，改好這邊後，忽然從很沮喪
變成很振奮，因為我隨便玩都贏的白痴 AI, 忽然間變成我要很認真才有機會贏，亂玩
的話肯定會慘敗，運氣不好也會慘敗，至少對我來說是很強的 AI 了。這樣說的原因是，
我不太熟這個遊戲，所以也只能說對我來說滿不容易贏的。接下來就可以拿出去跟其他
人驗證比較一下了。尤其我發現，用機率去算的人好像不多？確實我也還沒寫出完整的
機率計算，有些比較複雜的狀態，我忽略掉了。後面會提細節。總之這樣看起來也行。
我本來很沮喪在於，以為一定要把所有機率計算都完成才行。而複雜的還真的是很複雜。

-

回主題，除了一些地圖工具外，就是 Clue 與 ClueSet 了。這些大多都是我在上下班時
在捷運上想的。其實坐在電腦前，有些東西不太容易想，容易分心。最好的作法是拿
紙筆出來揮灑，像是我高中時那樣。那時寫過很多非常複雜，現在應該也看不懂的東西。
我覺得有點意外的是，這次我沒用多少紙筆，大多憑想像就行了。或是看著捷運地板上的
格子思考地雷的組合方式。紙筆應該還是比較好的，但看地板也行，要不問題比較簡單，
要不就是我的思考進步了，哈。

大概想好作法後，就可以回到電腦前，把想法轉化為程式。
而這之間的過程，則是先大略描繪出來，還想不清楚的地方就先亂寫，把他當成已知的
結果，先讓程式能夠 type check, 接下來再一一把實作細節填寫上去。也就是說，
一開始先是 bottom-up, 把需要的語言描繪出來，接下來再 top-down 把演算法描繪
出來，最後再重新把剛剛亂寫的「洞」給填滿。如同 Paul Graham 在《On Lisp》裡
〈Programming Bottom-Up〉提到的：

In Lisp, you don't just write your program down toward the language,
you also build the language up toward your program.

其實中間有好幾次我差點要放棄了，因為之前我寫過不少題目，都半途而廢。失敗的原因
是一開始的描繪語言寫不太好，面臨到一些設計或是實作上的困難。導致還沒真正開始
解題，就覺得很累沒什麼精神和衝動繼續寫下去。好笑的是，我也不知道當時能動的第
一版，究竟是真的寫得很爛，還是只是單純地雷格式搞錯？令人玩味的是，如果當時就
夠強了，我會繼續把他做得更完整嗎？我後來可是抱持著不信邪的固執，試著把任何
小細節都修好，也因此修掉一堆小 bug. 寫 AI 有件很困難的事，就是寫錯了，寫出有
bug 的 AI, 可能只是讓他變很笨，或是稍微變笨，不會有致命性的錯誤。也就是說，
很可能由於夠好了，而讓程式中留下許多不太妥當的錯誤。如果當初沒搞錯格式，我會
堅持下去把這些東西修好嗎？ debug 真的是又累又麻煩，尤其我又不會用 debugger.

-

離題了。

Clue 定義了 a. 總共有幾個地雷 b. 在哪幾個格子裡。ClueSet 則是一串的 Clue.
我替所有可以踩的格子，各自建立一個 ClueSet, 而這裡面的 Clue 則來自周遭的數字。
最早我是從數字去算，不過這會面臨難以合併 ClueSet, 因為格子會被重複計算。
後來改以可以踩的格子出發，就容易多了。

把 ClueSet 建立起來後，就是合併這些 Clue, 取其 overlap(intersect/conjunction).
一開始我想得非常簡單，就是把這個重疊的部份，當成最終的結果，不管其他的部份。
所以建立一個新的想像的 Clue, 地雷數是所有可能的最小值，區域則是 overlap 本身。
機率則是非常簡單的 - amount.toDouble / poses.size. 用負數是因為我希望他按照
descendant 的順序排列，這樣我能取 list 的 head, 而不是 tail 來取最有可能的。

這種作法很快就能寫好了，把 bug 清乾淨之後，大概就能動了。不過真的很弱。
雖然弱很可能只是單純因為格式搞錯。不管怎麼樣，因為那時覺得很弱，所以就開始
想換一些作法。於是我又離開了電腦，試著把情況分析地更仔細。於是我得到一個結論，
就是我需要去計算真正的機率，而不是這種簡化，試圖猜測這樣會正確的機率。

慢慢回想高中數學...

花了不少捷運時間（少看了點書），我想我大概知道真正的機率怎麼算了。
又也許好笑的是，花了不少時間寫出來後，看到結果非常不理想，覺得我應該哪裡漏
掉了。尤其有時候跑出來的結果非常怪異。去掉一些 bug 後，結果還是很怪。
然後再仔細想想，我發覺有個狀況我根本沒考慮到，就是我現在的 overlap 是算
所有 clue 的 conjunction, 但事實上其中的 clue 是可以有各自的 overlap!

但我可還真一時想不到這樣的機率要怎麼算。這真的太複雜了...
於是覺得很沮喪。或許機率真的行不通，因為我不會算。那就真的像 tkcn 所說的，
不如把精神花在如何確認絕對的地雷上，而不是去算可能算錯的機率。然後我就發現
我搞錯格式了... XD

果然機率才是王道啊 (遠目)
畢竟高中學排列組合與機率那段，可是我一生中最開心的數學課，也是成績最好的.. XD
三角函數一千多名，排列組合記得可以到一兩百名。這真的差很多...。

另一點有趣的是，改到現在，還是在用一開始的架構。或許我敏感度變高了，因為根據
經驗，通常演算法幾乎完全改掉的話，架構應該也會變。但這次幾乎是一樣的。應該證明
一開始所設想的邏輯語言大抵上是對的。

p.s. 另外整個程式裡沒有任何 state, 所以理論上應該可以很容易翻譯成 haskell.

-

總之終於有一個不那麼像白痴的 AI 了，可喜可賀，可喜可賀。
接下來就是歡樂的和別人切磋的時間了... XD 有兩種切磋方式，
一種就是實際比賽看看，另一種則是互相討論。很多討論我還沒細看，
晚點去 java 板上細看並回覆 AmosYang 的作法，因為瞥過去，我覺得
他的作法確實有些地方和我有點神似，只是名詞有那麼一點差異。
或許他是正統邏輯吧 O__Q 我只是胡亂發明名詞而已...。

下一篇詳細解說我的實作與機率計算方法。

minei-0.1.0
minei master