ToS2 程式原始碼以及概論

首先，這個 Bot 的 VS 2012 方案名稱是 ToS2 ，所以我就沿用這個名稱， Git 的 repository 名稱也叫 ToS2 。或許有人會納悶，為什麼要叫 ToS"2" 呢？原因很簡單，因為這是我寫的第二個 ToS 的 Bot 。早先寫了第一版以後，也陸陸續續在上面加上許多最佳化的功能，但是效能上的瓶頸一直無法突破。最後在經過一段時間的思考以後，我認為要進一步加速程式的計算，必須要整個搜尋的架構改成現在這個架構。而從原本的程式改寫，要改動的地方太多，不如整個重寫。因此才又開了一個新的方案，把整個程式重寫一遍。因為我在命名上實在沒什麼創意，所以第一版叫 ToS ，第二版就叫 ToS2 。我也沒有另外去想一個很好聽的名字，所以以後這個程式就叫 ToS2 吧。如果有一天又面臨大改，應該就會叫 ToS3 。基本上應該不用擔心最後數字變得很大，因為我沒有那麼多時間。

最好的情況下，我應該要把 source code 好好整理以後再放出去，但有些朋友已經在跟我要 source code ，所以我想就先把現在的樣子放出去也無妨， GitHub 的 URL 是： https://github.com/sitos/ToS2 。就跟我以往寫的大部份程式一樣，我的習慣很差，以致於所有的 function 都擠在同一個檔案裡面。基於未來我如果去上班可能要跟別人合作，接下來我「應該」會將程式碼慢慢整理，把不同功能區塊的程式碼分到不同的檔案裡面，以方便閱讀、修改與討論。但如果對實作細節很感興趣的人，也可以現在就將程式碼下載回去看，只是很抱歉裡面現在幾乎沒有任何註解。有註解的地方都是提醒我那邊的寫法可能有問題的地方，對於了解程式碼的運作應該是一點幫助也沒有。

在這篇文章的最後，我略略講一下一個 Game Bot 大致上的流程和架構，給完全沒有相關經驗或背景的人了解。基本上 Game Bot 做的事就和一個在玩遊戲的人一樣，分為三大部份。第一、了解遊戲的狀態，第二、找尋最佳的策略，第三、反應。套用在神魔之塔這款遊戲來說的話，就是讀盤面、想路徑和動滑鼠。基本上讀盤面和動滑鼠，是相對「簡單」而「直覺」的部份。我所謂的簡單指的並不是人人都會，至少在我寫第一個 Game Bot 以前，我認為那是對我而言最麻煩的部份，因為它牽涉到很多系統的 API ，沒學過或沒查過，我就不會用。所謂的簡單指的是，一旦你會用了以後，幾乎所有的遊戲都可以用一樣的方式來獲取遊戲的資訊，用一樣的方式來操作遊戲。當然，這不代表只會一種方法就是夠用的，因為遊戲可能有反應時間的限制，可能有各種動畫干擾對遊戲狀態的判斷。因為太複雜的我也不會，這部份還有待學習充實。

至於中間的想路徑這段，是我認為最有挑戰性也最有趣的一部份。我做的第一個完整的 Game Bot 是給 Facebook 上的 Bejeweled Blitz 用的 Bot ，它的策略就相對簡單很多，如果有機會我重寫那個 Bot ，應該也可以和大家分享，在這邊先跳過。但神魔之塔或龍族拼圖的策略就相對難很多。有學過演算法的人應該就知道，這種問題基本上只要作 Search ，不管是 DFS 或 BFS 都可以，就一定可以找到最佳解。問題是， Search space 實在太大了。一個粗略的算法是，假設我們可以允許的步數是 50 步，每一步有 3 個方向可以選擇(不考慮上一步的反方向，也不考慮碰到邊界的情況)，這樣總共有 3^50 步可以走。大致學過 Computer science 的人應該都知道，這通常算不太出來。所以暴力求最佳解基本上是不實用的，那麼就只能退而求其次，縮小搜尋的範圍，試著在搜尋的範圍裡面找到堪用的解。為了讓文章不要太長，我採用的搜尋方式留到下一篇文章再講。

最後，附上三四年前我做的 Bejeweled Blitz 的 Bot 的影片，其實當時最高的分數曾經有 3.8M ，我本來想要做到 4M 再收手，但當時卡在取點取色的效率不佳，最後未竟全功。等我學會新技巧的時候，沒空回頭去做。所以如果有機會的話，也許我會再把它改良一下。