這是今天(3/12)錄的影片，為了錄一個完整的零石通關影片，不僅把手上所有的魔法石都用光了，總共還打到三隻毒龍，第一次是弄錯敵人技能吃了一石通關。第二次雖然零石通關，但是畫面有不小心被擋到。然後就一直失敗，一直吃石補體，最後沒石了只好等體力慢慢回復。然後等了幾個小時以後有體力再打，又失敗。再等幾個小時以後又有體力，又再打，才好不容易錄到一個完整的。不過就算雙異界當隊長，回復力還是很不夠，只能很有耐心地慢慢把王的血磨光。過程其實還滿無聊的，如果睡不著可以看看。
2014年3月12日 星期三
神魔之塔 世界的啃蝕者/飢餓的毒龍 龍隊零石通關
這是今天(3/12)錄的影片，為了錄一個完整的零石通關影片，不僅把手上所有的魔法石都用光了，總共還打到三隻毒龍，第一次是弄錯敵人技能吃了一石通關。第二次雖然零石通關，但是畫面有不小心被擋到。然後就一直失敗，一直吃石補體，最後沒石了只好等體力慢慢回復。然後等了幾個小時以後有體力再打，又失敗。再等幾個小時以後又有體力，又再打，才好不容易錄到一個完整的。不過就算雙異界當隊長，回復力還是很不夠，只能很有耐心地慢慢把王的血磨光。過程其實還滿無聊的，如果睡不著可以看看。
2014年3月10日 星期一
ToS2 搜尋演算法概論 (3)
前情提要：區域最佳解(Local Optimal Soluion)很麻煩。
前一篇文章最後面提到，分段作 DFS 很容易就會掉到 Local optimal solution ，這個情況又會因為搜尋的步數不足，加上缺乏對盤面潛力的精確評估方式而更加嚴重。事實上上述兩者都是可以再改進的地方。當然寫在前面也就表示我還沒有什麼好的想法。想要增加搜尋的步數，最直接的作法可能是將一定不會解出好盤面的路徑捨棄不搜尋，這樣就可以在同樣的時間裡面搜尋更多的步數。不過這樣的作法面臨的挑戰還是一樣，目前我並沒有辦法對於「未完成」的盤面，對其潛力作很好的評估。因為如果想要在還沒有走完以前，就先看出某一條路徑不會解出好盤面，那麼就得利用當下這個未完成的盤面，去作一個粗略的估計。但目前我並沒有好的評估方法。簡單來說，現在的搜尋方法被限制在，只能夠對於「已完成」的盤面進行評估。這當然是一個很大的限制，如果有人有對於怎麼突破這個限制的一些想法，非常歡迎提出來討論。
基於上述的限制，因為我只能對於已完成的盤面進行評估，所以只能很努力地把搜尋範圍裡面所有的路徑都走完，看看每一條路徑最後的盤面如何。這樣當然就很容易卡在 Local optimal solution 裡面。我的作法來自兩種不同的觀念，但最後的實作其實是一樣的。這個想法可以被視為是一種 Look ahead 或者是 Roll back 。你認為哪一種比較好理解，就從那種去理解吧。 Look ahead 的想法有點像是想要給未完成盤面一個評分的方式。雖然我要搜尋的範圍是 N 步，但走到 N 步得到當時的盤面 A 以後，我再多搜尋 M 步的範圍，看看現在決定的這條路徑，之後如果繼續走，是不是可能可以得到更好的盤面 B ，來當作是這條路徑的評分，也就是評估現在這條路徑的潛力。這樣的好處是，在很多的 N 步當中，我可以得到 N+M 步當中看起來最好的解。當然馬上就會有人講說，你這樣不就是把搜尋範圍從 N 步變成 N+M 步嗎？是的，不過不一樣的地方在於，我下一次搜尋會從 N 步開始搜，而非 N+M 步開始搜。這樣就不會把當時搜尋的 Local optimal solution ，也就是 N+M 步的盤面 B ，當作起點，導致任意移動符石可能打亂已經排好的符石。而是從 N 步的盤面 A 開始找解，找看看再下一個 N+M 步有沒有更好的解，而我知道至少有一個 N+M 步的盤面 B 不錯。只是再往下搜 N 步，再加上 M 步的 Look ahead ，有可能搜到 N+(N+M) 步會有比 B 更好的解。另外一個理解的方式是 Roll back ，也就是我一開始雖然搜尋 N+M 步，得到當時最好的盤面 B ，但是我不要從 N+M 步開始下一次的搜尋。理由也是一樣，這樣可能導致打亂已經排好的符石，反而得不到更好的解。因此我 Roll back 回到第 N 步時的盤面，再往下搜尋 N+(N+M) 步， Roll back 就可以避免卡在當時的 Local optimal solution 盤面 B 。因此，只要現在還沒有到達步數的上限，那麼下一階段的搜尋，就會 Roll back 回到這一段的第 N 步時的盤面 A 繼續往下搜尋，而非在該階段看到最佳盤面的 N+M 步時的盤面 B 開始繼續搜尋。最後，假使總夠搜尋 I 個階段，那麼總步數將會是 N * I + M 步。
另一個處理 Local optimal solution 問題的方法，概念上就相對簡單。這個想法是來自 GA 裡面基因庫的概念，雖然在很多個解當中，總是會有一個最好的，但如果我們只取「一個解」，那個解後續的發展不見得好。但如果我們同時保留「多個解」，這些目前看起來不錯的解，後續的發展通通不好的機會，就相對變低了。這樣就可以讓我們整套演算法跑完以後，不致於在某些情況下得到很差的解。因此，同樣是在分段 DFS 的架構底下，第一個階段跑完以後，我會保留 K 組當時看起來最佳的解(S1， N 步)，這 K 組解各自對應到當時它們的盤面。然後從這 K 組解出發，再各自往下搜尋 N+M 步，又得到一大堆解。再從這一大堆解裡面找出 K 組最佳的解(S2， N+N 步) ，如此不斷重覆直到步數的上限。這裡的 K 越大，搜尋量也會呈現性增加，不過至少是線性的，不是指數增加。所以還算可以接受， K 大概取 8~16 效果就不錯了，會取 8 或 16 是因為我的處理器有八個 hardware thread ，剛好可以透過 openmp 平均分散工作量，平行化的部份會留到討論實作的地方再來講。
當然，這樣的作法實際上並沒有「解決」分段的 DFS 遇到 Local optimal solution 的問題，但至少表現出來的症狀已經大幅緩解，在多數的時候都可以把這些路徑不錯地串連起來，得到一個不錯的解，而且也把計算的時間壓在可以接受的範圍裡面。事實上，如果搭配一個良好的盤面評分系統，這個作法離解決 Local optimal solution 造成的問題，也是雖不中亦不遠矣。分段作 DFS 最大的困難在於，一段 DFS 結束以後，必須要選擇其中一條路徑作為下一段搜尋的起點，此時評分機制的角色就非常重要。先前有提過，我現在只能對已完成盤面作評估，但即使如此，還是可以對未完成的部份依照我們的喜好給一個粗略的分數。例如在兩個 combo 數相當的盤面，我們怎麼決定到底應該選擇哪一個當作起點，又或者我們問一個更具體的問題，如果在搜尋的步數裡面，無法完成拼圖盾，但我們的搜尋目標就是要滿足拼圖盾，在分段 DFS 的搜尋架構無法直接完成的工作，要怎麼樣透過評分機制來補足分段 DFS 的不足。寫到這裡，搜尋演算法的架構大致上是講完了，下一篇會開始討論分段 DFS 的好伙伴，也就是盤面評分的演算法。讓分段 DFS 沒辦法做的事情，由盤面評分演算法來補足。
前一篇文章最後面提到，分段作 DFS 很容易就會掉到 Local optimal solution ，這個情況又會因為搜尋的步數不足，加上缺乏對盤面潛力的精確評估方式而更加嚴重。事實上上述兩者都是可以再改進的地方。當然寫在前面也就表示我還沒有什麼好的想法。想要增加搜尋的步數，最直接的作法可能是將一定不會解出好盤面的路徑捨棄不搜尋，這樣就可以在同樣的時間裡面搜尋更多的步數。不過這樣的作法面臨的挑戰還是一樣，目前我並沒有辦法對於「未完成」的盤面，對其潛力作很好的評估。因為如果想要在還沒有走完以前，就先看出某一條路徑不會解出好盤面，那麼就得利用當下這個未完成的盤面，去作一個粗略的估計。但目前我並沒有好的評估方法。簡單來說，現在的搜尋方法被限制在，只能夠對於「已完成」的盤面進行評估。這當然是一個很大的限制，如果有人有對於怎麼突破這個限制的一些想法，非常歡迎提出來討論。
基於上述的限制，因為我只能對於已完成的盤面進行評估，所以只能很努力地把搜尋範圍裡面所有的路徑都走完，看看每一條路徑最後的盤面如何。這樣當然就很容易卡在 Local optimal solution 裡面。我的作法來自兩種不同的觀念，但最後的實作其實是一樣的。這個想法可以被視為是一種 Look ahead 或者是 Roll back 。你認為哪一種比較好理解，就從那種去理解吧。 Look ahead 的想法有點像是想要給未完成盤面一個評分的方式。雖然我要搜尋的範圍是 N 步，但走到 N 步得到當時的盤面 A 以後，我再多搜尋 M 步的範圍，看看現在決定的這條路徑，之後如果繼續走，是不是可能可以得到更好的盤面 B ，來當作是這條路徑的評分，也就是評估現在這條路徑的潛力。這樣的好處是，在很多的 N 步當中，我可以得到 N+M 步當中看起來最好的解。當然馬上就會有人講說，你這樣不就是把搜尋範圍從 N 步變成 N+M 步嗎？是的，不過不一樣的地方在於，我下一次搜尋會從 N 步開始搜，而非 N+M 步開始搜。這樣就不會把當時搜尋的 Local optimal solution ，也就是 N+M 步的盤面 B ，當作起點，導致任意移動符石可能打亂已經排好的符石。而是從 N 步的盤面 A 開始找解，找看看再下一個 N+M 步有沒有更好的解，而我知道至少有一個 N+M 步的盤面 B 不錯。只是再往下搜 N 步，再加上 M 步的 Look ahead ，有可能搜到 N+(N+M) 步會有比 B 更好的解。另外一個理解的方式是 Roll back ，也就是我一開始雖然搜尋 N+M 步，得到當時最好的盤面 B ，但是我不要從 N+M 步開始下一次的搜尋。理由也是一樣，這樣可能導致打亂已經排好的符石，反而得不到更好的解。因此我 Roll back 回到第 N 步時的盤面，再往下搜尋 N+(N+M) 步， Roll back 就可以避免卡在當時的 Local optimal solution 盤面 B 。因此，只要現在還沒有到達步數的上限，那麼下一階段的搜尋，就會 Roll back 回到這一段的第 N 步時的盤面 A 繼續往下搜尋，而非在該階段看到最佳盤面的 N+M 步時的盤面 B 開始繼續搜尋。最後，假使總夠搜尋 I 個階段，那麼總步數將會是 N * I + M 步。
另一個處理 Local optimal solution 問題的方法，概念上就相對簡單。這個想法是來自 GA 裡面基因庫的概念，雖然在很多個解當中，總是會有一個最好的，但如果我們只取「一個解」，那個解後續的發展不見得好。但如果我們同時保留「多個解」，這些目前看起來不錯的解，後續的發展通通不好的機會，就相對變低了。這樣就可以讓我們整套演算法跑完以後，不致於在某些情況下得到很差的解。因此，同樣是在分段 DFS 的架構底下，第一個階段跑完以後，我會保留 K 組當時看起來最佳的解(S1， N 步)，這 K 組解各自對應到當時它們的盤面。然後從這 K 組解出發，再各自往下搜尋 N+M 步，又得到一大堆解。再從這一大堆解裡面找出 K 組最佳的解(S2， N+N 步) ，如此不斷重覆直到步數的上限。這裡的 K 越大，搜尋量也會呈現性增加，不過至少是線性的，不是指數增加。所以還算可以接受， K 大概取 8~16 效果就不錯了，會取 8 或 16 是因為我的處理器有八個 hardware thread ，剛好可以透過 openmp 平均分散工作量，平行化的部份會留到討論實作的地方再來講。
當然，這樣的作法實際上並沒有「解決」分段的 DFS 遇到 Local optimal solution 的問題，但至少表現出來的症狀已經大幅緩解，在多數的時候都可以把這些路徑不錯地串連起來，得到一個不錯的解，而且也把計算的時間壓在可以接受的範圍裡面。事實上，如果搭配一個良好的盤面評分系統，這個作法離解決 Local optimal solution 造成的問題，也是雖不中亦不遠矣。分段作 DFS 最大的困難在於，一段 DFS 結束以後，必須要選擇其中一條路徑作為下一段搜尋的起點，此時評分機制的角色就非常重要。先前有提過，我現在只能對已完成盤面作評估，但即使如此，還是可以對未完成的部份依照我們的喜好給一個粗略的分數。例如在兩個 combo 數相當的盤面，我們怎麼決定到底應該選擇哪一個當作起點，又或者我們問一個更具體的問題，如果在搜尋的步數裡面，無法完成拼圖盾，但我們的搜尋目標就是要滿足拼圖盾，在分段 DFS 的搜尋架構無法直接完成的工作，要怎麼樣透過評分機制來補足分段 DFS 的不足。寫到這裡，搜尋演算法的架構大致上是講完了，下一篇會開始討論分段 DFS 的好伙伴，也就是盤面評分的演算法。讓分段 DFS 沒辦法做的事情，由盤面評分演算法來補足。
2014年3月8日 星期六
ToS2 神魔之塔擬人轉珠/記憶的教誨/突破界限之門/追憶旅人 零石通關/示範影片
昨天晚上看到別的玩家在玩這關，然後看到「符石風化‧改」，就知道這東西實在麻煩。昨天晚上躺在床上先想了一會，今天再花了半天的時間，耗掉大約三條體力作測試和除錯，總算是把功能先給改出來了。上面就是通關的影片。雖然還有一點點瑕疵，不過因為是一次通關的關卡，所以改了也沒辦法再測，剩下的只能等到下次再有「符石風化‧改」的關卡時才能測試了。不過因為「符石風化‧改」的應對策略和原本程式架構不太合，所以硬是把功能塞進去以後，程式碼變得很亂，可能得等有時間再來重新整理一下，現在的寫法連我自己都覺得很難理解。
2014年3月4日 星期二
ToS2 搜尋演算法概論 (2)
前情提要：先產生最佳盤面再找路徑看起來也不是很方便
既然直接產生最佳盤面，再去找一條從初始盤面一直到最佳盤面的路徑，看起來也不是很容易做到，而且甚至也不容易設計演算法，想法自然就又回到直接作搜尋。但是先前也已經提到，直接以暴力法作搜尋， Search space 實在太大，根本不可能搜得完。所以勢必要縮短搜尋的步數。先用最直覺最簡單的作法來想，神魔之塔的盤面在考慮斜轉的情況底下，每一步都可以有九種選擇，分別是上、右上、右、右下、下、左下、左、左上以及停在當時的位置。在搜尋的過程當中，除了停下不走以外，在不考慮碰到邊界的情況下，其餘的選擇都可以再接下去作原本的這九種選擇，因此若將搜尋的總步數設為 N ，那麼搜尋的時間複雜度小於 9^N ，約比 8^N 略大一點。簡單來說，這個複雜度是指數成長的。因此我們只能選擇一個很小的 N ，目前我的程式選用的 N = 8 。這個數字取決於使用者能忍受計算一個盤面花多少的時間， N 每增加 1 ，計算時間就會變為八倍，因此就算有很好的電腦協助運算，這個 N 也沒辦法再增加多少。但在上一篇文章當中，我也提到，以目前 Bluestacks 的使用狀況來看，在五秒的轉珠時間裡面，大約可以允許最多 70 步。因此，將搜尋範圍從 8^70 ，縮小到只剩下 8^8 ，這樣找到一個好的解的機會自然大大降低。如果不去比較這個數字，光從概念去想，如果只允許移動 8 次，就算把所有的可能都考慮進來，要把整個盤面整理好還是很困難。直接縮小搜尋的範圍有一個非常明顯的缺點，那就是總步數不足，根本就不可能把盤面整理好。
其實這邊的想法和人在玩的時候是很像的，人在玩的時候事實上也是在腦中作搜尋，只是可能搭配更多經驗等綜合判斷，但決策的過程還是很相像。我不知道高手的思考方式是不是不一樣，還是只是記住一些特徵來加快搜尋的速度，但至少我自己在理解這個遊戲的時候，並沒有想到什麼特別的技巧。所以，為了要解決總步數不足的問題，最簡單的作法就是多做幾次搜尋，再把一段一段的路徑接起來。簡單的想法就是，先搜尋 8 步，找到長度為 8 的路徑當中最好的一條，並將當時的盤面記下。接著再從這個盤面出發，再搜尋 8 步，再找到長度為 8 的路徑當中最好的一條。只要把這兩條路徑接起來，就可以得到一條長度為 16 的路徑。這個作法大概是我白天被問到可不可以寫神魔之塔的 Bot ，然後搭車回家的路上就想得到的第一個解法。想法很簡單，也很實用，如果有興趣的人也可以自己直接實作這個作法，會得到「還不錯」的結果，但是它的缺點也會非常明顯，那就是它會很直接地被卡在 Local optimal solution 裡面。找出來的解其實不盡理想。
接下來我會舉兩個簡單的例子來表達這個概念，在這些例子裡面，我們先假設所謂最好的路徑就是可以形成最多 combo 的路徑。假設我們一開始有的盤面是這樣。
盤面的左半邊看起來是比較容易形成 combo 的區域，所以在 8 步以內找到的最佳解可能是這樣。
對於上述的狀況，有種極端的例子。假設在疊珠疊很多層的情況底下，走 9 步就可以完成整個疊珠，可以得到很高的 combo 數。但是在 8 步的時候，就是沒辦法將最下層啟動的符石擺好，導致這個盤面最後連 1 combo 都沒有。在這樣的情況底下，即使只差 1 步，還是無法求得這個很棒的解。那麼這樣的問題要怎麼解決呢？或許有些人會覺得，那我就多搜尋 1 步就可以了，這個想法很直覺，但沒有用。因為不管搜尋幾步，總是有那種差一兩步就得到好解的情況會發生，但每多搜尋 1 步，複雜度就變成原本的 8 倍，因此實際上搜尋的範圍就只能被限縮在短短的幾步之內。要跳出 Local optimal solution 也有一些現成的搜尋演算法可以用，例如 Simulated Annealing (SA ，模擬退火法)或者是 Genetic Algorithm (GA ，基因演算法)，但這兩種很厲害的技巧(我認為發明的人真的很厲害，不過用這兩種演算法解問題倒不用什麼高深的學問)，在轉珠問題裡面似乎也派不上用場。 SA 和 GA 的作法都是隨機變動一部份的參數來看看整體解是否能夠得到改進， GA 則是混合目前不錯的解的不同部份來得到一組新的解。如果今天要解的問題有某種「區域性」，也就是改變一部份的參數，影響只會在特定的範圍之內，那麼這種嘗試方式就很有用，我們可以透過累積部份的改進，來達到整體的改進。但轉珠問題只要走的路徑有 1 步不一樣，最後的結果可能就大不相同，特別是在疊珠當中，只要在前期中斷，後面所有的 combo 都沒辦法產生。因此透過 SA 或 GA 這種帶有亂數變動的演算法來試著跳出轉珠問題當中的 Local optimal solution ，似乎也不是很恰當。當然如果有對這兩個演算法有深入了解的人，有想到套用的方式，也很歡迎分享。不過在我目前的理解之下，我認為這種先進的演算法似乎不適合這個問題，所以最後還是回到比較傳統的作法。因為篇幅的原因，怎麼處理困在 Local optimal solution 的作法就下篇再講了。
既然直接產生最佳盤面，再去找一條從初始盤面一直到最佳盤面的路徑，看起來也不是很容易做到，而且甚至也不容易設計演算法，想法自然就又回到直接作搜尋。但是先前也已經提到，直接以暴力法作搜尋， Search space 實在太大，根本不可能搜得完。所以勢必要縮短搜尋的步數。先用最直覺最簡單的作法來想，神魔之塔的盤面在考慮斜轉的情況底下，每一步都可以有九種選擇，分別是上、右上、右、右下、下、左下、左、左上以及停在當時的位置。在搜尋的過程當中，除了停下不走以外，在不考慮碰到邊界的情況下，其餘的選擇都可以再接下去作原本的這九種選擇，因此若將搜尋的總步數設為 N ，那麼搜尋的時間複雜度小於 9^N ，約比 8^N 略大一點。簡單來說，這個複雜度是指數成長的。因此我們只能選擇一個很小的 N ，目前我的程式選用的 N = 8 。這個數字取決於使用者能忍受計算一個盤面花多少的時間， N 每增加 1 ，計算時間就會變為八倍，因此就算有很好的電腦協助運算，這個 N 也沒辦法再增加多少。但在上一篇文章當中，我也提到，以目前 Bluestacks 的使用狀況來看，在五秒的轉珠時間裡面，大約可以允許最多 70 步。因此，將搜尋範圍從 8^70 ，縮小到只剩下 8^8 ，這樣找到一個好的解的機會自然大大降低。如果不去比較這個數字，光從概念去想，如果只允許移動 8 次，就算把所有的可能都考慮進來，要把整個盤面整理好還是很困難。直接縮小搜尋的範圍有一個非常明顯的缺點，那就是總步數不足，根本就不可能把盤面整理好。
其實這邊的想法和人在玩的時候是很像的，人在玩的時候事實上也是在腦中作搜尋，只是可能搭配更多經驗等綜合判斷，但決策的過程還是很相像。我不知道高手的思考方式是不是不一樣，還是只是記住一些特徵來加快搜尋的速度，但至少我自己在理解這個遊戲的時候，並沒有想到什麼特別的技巧。所以，為了要解決總步數不足的問題，最簡單的作法就是多做幾次搜尋，再把一段一段的路徑接起來。簡單的想法就是，先搜尋 8 步，找到長度為 8 的路徑當中最好的一條，並將當時的盤面記下。接著再從這個盤面出發，再搜尋 8 步，再找到長度為 8 的路徑當中最好的一條。只要把這兩條路徑接起來，就可以得到一條長度為 16 的路徑。這個作法大概是我白天被問到可不可以寫神魔之塔的 Bot ，然後搭車回家的路上就想得到的第一個解法。想法很簡單，也很實用，如果有興趣的人也可以自己直接實作這個作法，會得到「還不錯」的結果，但是它的缺點也會非常明顯，那就是它會很直接地被卡在 Local optimal solution 裡面。找出來的解其實不盡理想。
接下來我會舉兩個簡單的例子來表達這個概念，在這些例子裡面，我們先假設所謂最好的路徑就是可以形成最多 combo 的路徑。假設我們一開始有的盤面是這樣。
盤面的左半邊看起來是比較容易形成 combo 的區域，所以在 8 步以內找到的最佳解可能是這樣。
但是再往下搜尋 8 步，可能就找不到更多的 combo ，因為會破壞原本已經形成的 combo 。但事實上在 16 步之內，可以形成更多的 combo ，例如這樣。
只要先把右上角整理好，再去走原本的路徑，就可以多得到 1 combo 。但先往右上角整理的走法，在 8 步以內可能沒有足夠的步數走到左半邊形成 4 combo ，因此這條路徑在搜尋第一個 8 步的時候，就會被捨棄。簡單地說，這種作法會捨棄很多一開始看起來不好，但實際上很好的走法。再舉另外一個例子，假設在第一個 8 步之後，可以把盤面整理成這樣。
我們用眼睛看會覺得超棒，因為只要再動七步，就可以形成漂亮的 6 combo 。
但是這個盤面本身卻連 1 combo 都沒有，因此它也會被捨棄。在某些搜尋的問題裡面，困在 Local optimal solution 裡面，可能不是太嚴重，因為只要大部份的地方都得到不錯的解，那麼最後的解也不會比最佳解差太多。但在神魔之塔這樣的轉珠遊戲裡面，這個問題相對較為嚴重，因為每一次的移動都有副作用，導致在得到一個 Local optimal solution 以後，對於那些會拆掉現有的 combo 以追求更高 combo 的路徑，在下一次搜尋範圍之內，若是無法將原有的 combo 組合回來，那麼得到的解將比原本的更差，這些很有潛力的路徑就被捨棄了。
對於上述的狀況，有種極端的例子。假設在疊珠疊很多層的情況底下，走 9 步就可以完成整個疊珠，可以得到很高的 combo 數。但是在 8 步的時候，就是沒辦法將最下層啟動的符石擺好，導致這個盤面最後連 1 combo 都沒有。在這樣的情況底下，即使只差 1 步，還是無法求得這個很棒的解。那麼這樣的問題要怎麼解決呢？或許有些人會覺得，那我就多搜尋 1 步就可以了，這個想法很直覺，但沒有用。因為不管搜尋幾步，總是有那種差一兩步就得到好解的情況會發生，但每多搜尋 1 步，複雜度就變成原本的 8 倍，因此實際上搜尋的範圍就只能被限縮在短短的幾步之內。要跳出 Local optimal solution 也有一些現成的搜尋演算法可以用，例如 Simulated Annealing (SA ，模擬退火法)或者是 Genetic Algorithm (GA ，基因演算法)，但這兩種很厲害的技巧(我認為發明的人真的很厲害，不過用這兩種演算法解問題倒不用什麼高深的學問)，在轉珠問題裡面似乎也派不上用場。 SA 和 GA 的作法都是隨機變動一部份的參數來看看整體解是否能夠得到改進， GA 則是混合目前不錯的解的不同部份來得到一組新的解。如果今天要解的問題有某種「區域性」，也就是改變一部份的參數，影響只會在特定的範圍之內，那麼這種嘗試方式就很有用，我們可以透過累積部份的改進，來達到整體的改進。但轉珠問題只要走的路徑有 1 步不一樣，最後的結果可能就大不相同，特別是在疊珠當中，只要在前期中斷，後面所有的 combo 都沒辦法產生。因此透過 SA 或 GA 這種帶有亂數變動的演算法來試著跳出轉珠問題當中的 Local optimal solution ，似乎也不是很恰當。當然如果有對這兩個演算法有深入了解的人，有想到套用的方式，也很歡迎分享。不過在我目前的理解之下，我認為這種先進的演算法似乎不適合這個問題，所以最後還是回到比較傳統的作法。因為篇幅的原因，怎麼處理困在 Local optimal solution 的作法就下篇再講了。
2014年2月27日 星期四
ToS2 神魔之塔擬人轉珠/濾珠、存珠、儲珠 示範影片
昨天晚上實作了濾珠(或稱存珠、儲珠)的功能，也就是刻意保留特定種類的符石。目前效果還不是讓我很滿意，主要是因為裡面還是有因為天降導致要被存的符石被消掉的情況出現。當然，某些很極端的情況下，被天降消掉應該是無法避免的，但演算法最好能夠盡量最小化被天降消掉的機會，或者讓存好珠需要的回合越少越好。只不過越是要避免天降消掉要存的珠，就代表要保留越多的符石來隔開要存的珠與新掉下來的珠，這也代表能消的符石越少。目前我心裡面已經有一點想法，所以應該會再試著加以改進。就先把第一版的影片擺出來，也許有人會給我一些意見(不過我應該還是會先實作我已經想到的作法)。有趣的是，加上這個功能，在原有的程式碼之中，扣掉變數定義、初使化或給值以外，真正與演算法相關的程式碼只多了 57 行。
ToS2 搜尋演算法概論 (1)
前情提要：暴力搜尋跑不完。
先前已經提過，要用暴力搜尋，把所有可以走的路徑都走過一遍來找最佳解，基本上是無法實作的。因為複雜度太大，在現在的電腦上面執行，不太可能跑得完。當然有量子電腦或者是大量的雲端計算，也許有機會。但前者的問題是我根本不知道它是怎麼運算的，當然也不會寫讓量子電腦計算的程式。而對於後者，我沒那麼多錢，所以也就不考慮了。在不考慮永遠超大量計算資源的情況底下，那麼減少計算量就是勢在必行的工作。我曾經想過不只一個作法，在這邊我會先介紹被我捨棄，最後沒有被實作的方法。倒不是我特別喜歡賣關子，而是因為我認為沒有失敗，或者每一個一開始被認為不可行的作法，在高度抽象的概念階段，都還是很有價值的。很多事光用想像，不可能真的知道孰優孰劣，因此不論是好的想法或差的想法，都有被紀錄的價值。
當我思考到透過搜尋去嘗試所有可能的路徑計算複雜度太高之後，在我腦海當中出現的念頭是，其實我們並不需要找到「所有的路徑」去得到最佳解，我們只需要找到「一條路徑」去得到最佳解，就可以了。好的，那什麼是「最佳解」呢？雖然在不同的情境之下，同一個盤面能產生的最佳解可能不一樣，例如追求有拼圖盾和沒有拼圖盾的情況下，最佳解就很有可能不一樣。但是，一旦消除符石的目標確定了以後，什麼樣的解是「最佳解」，事實上是很容易得到的。當然，「最佳解」可能也會有很多個，不過同樣地，我們還是只需要「其中一個」。為了要幫助大家理解，我應該要畫一些圖，但是我實在太懶得畫圖，所以就利用別人做的網頁吧。簡單舉個例子，如果我們有一個盤面像這樣，盤面上總共有三個火珠、六個木珠、五個水珠、四個光珠、七個暗珠、五個心珠。經過簡單的計算以後，我們知道這個盤面最大的 Combo 數是 8 Combo 。我們把能作出來的消除，依消除符石的數量從多到少排序並把同色錯開可以得到 5 水、 5 心、 4 暗、 4 光、 3 暗 、3 木 、 3 火、 3 木。接著試著把這些消除的串列塞進盤面裡面，大的先塞比較好塞，經過幾次的嘗試以後就可以得到這樣的盤面。雖然要很直覺得找到一個可以擺放的盤面可能有點困難，但如果同樣作搜尋，要找到一個稱得上是最佳解的盤面，絕對比找到一個 8 Combo 且能夠把所有符石通通消光光的盤面要簡單得多。
那麼，在有了啟始盤面以及最終的最佳解之後，下一個任務就是要找到一條從啟始盤面「通往」最佳解的「路徑」。如果這條路徑沒有任何限制，那麼這條路徑其實也不會太難找。我們可以先將在啟始盤面與最終最佳解當中同色的符石編號對應，也就是紀錄哪一個符石最後要移動到哪裡去，然後開始照著我們想要的來移動。讀到這裡，你可能會想說「慢著，哪有你想怎麼動就怎麼動這麼簡單，移動特定一個符石的時候可是會影響到其它符石的」。接下來我要證明的就是，「從任意盤面必定存在一條路徑可以移動成另一個任意盤面」。有自己設計過一些演算法並證明有效性的人讀到這裡，應該已經知道大概證明的方向。首先，我先假定這條路徑一開始拿起來的符石最後會落在盤面的最右上角。接著我會從左而右，從下而上，把指定要的符石移動到那個位置上。舉例而言，從初始盤面，要變成最終盤面，我必須要把一個水珠移到最左下角。為了節省時間，就用離左下角最近的水珠，也就是 (3, 3) 這個水珠，而我應該要拿起來的是最後擺在右上角的木珠，一樣假定是離右上角最近的木珠，就是 (6, 5) 這顆。那麼我的路徑會是這樣，接著我再去移動心珠過來擺，一樣找最近的，我的路徑會是這樣。最下面一列，由左而右分別是心珠和暗珠。然後，把最下一列排好的路徑是這樣。看到這裡，一定會有人說，要是能這樣轉，那我也會。的確，其實只要有無限的時間，慢慢轉一定可以把盤面轉成我們要的樣子。但是問題就在於「沒有無限的時間」。
所以，相對於先前提到的搜尋法(我隨便取個名字)，因為計算複雜度太高導致於會根本「算不完」。最終盤面建構路徑法(還是一樣，名字是隨便取的，請不要放在心上)，要找到一個最終盤面是最佳解不難，要找到一條路徑也不難。但是很可能根本走不完。反應快一點的人應該已經發現機會是什麼。雖然人的手有手速的限制，很可能無法在五秒之內轉完這麼複雜的路徑(剛剛排最下面一排就已經花掉 52 步，如果要排完整個盤面可能要 200 步以上)。但是如果是給程式去排，要在五秒之內送出一大堆的滑鼠訊號，絕對是做得到。想到這裡，我就滿懷著希望打開 Bluestacks (or Genymotion) ，想要試試看是不是我拼命狂送訊號，模擬器也會把這些訊號如實地傳遞給在其中執行的 App 。不過一試馬上就知道，完全不能用。雖然我不太確定背後的原理是什麼，但是模擬器或其中的 App 處理滑鼠訊號有它的極限間隔，在兩次處理的間隔時間之內的滑鼠動作，有可能會直接被忽略。舉個簡單的例子，假使我送出向左再向下的動作，但在左邊那格停留的時間不夠長，以至於沒有被偵測到，就已經往下的話，那麼動作實際上就會變成是直接往左下斜轉，而不是先往左再往下。
在經過很多次的實驗以後，我測到的數據是以我的電腦執行 Bluestacks ，這個間隔時間大約在 70ms 到 80ms 左右，如果兩次動作隔的時間比這個時間還要短，就有機會有動作會沒有被偵測到。這個數據代表的意義很明顯，即使是程式在玩這個遊戲，一樣有嚴格的步數上限。即使這個步數的上限可能隨著使用的模擬器的順暢度或實作方式有所不同，但可走的步數並不是「無限」的。當然，這並不代表「最終盤面建構路徑法」就不能用，只是它可能需要搭配一個可以找到最佳解，但是該最佳解與啟始盤面的路徑又不會太長的演算法。一旦我們增加了這些條件在裡面，那麼這個演算法就不再像剛剛示範的那麼簡單，裡面勢必也要作一些搜尋，進而增加它的運算複雜度。當然，這個「最終盤面建構路徑法」的複雜度一定還是遠比暴力搜尋求解要低得多。如果可走的步數不是壓在 70 步這麼短的步數裡面(剛剛光是排一列就已經花掉超過 50 步)，這個演算法應該是大有可為。但是因為對步數的要求，對這個演算法而言其實相當嚴苛，所以最後在幾經思考之後，我還是決定暫時放棄這個演算法，還是試著從搜尋路徑的方向來著手。
因為文章有越寫越長的趨勢，所以這一篇就先停在這裡，免得有人一點進來看到旁邊的 scroll bar 就不想讀了。
那麼，在有了啟始盤面以及最終的最佳解之後，下一個任務就是要找到一條從啟始盤面「通往」最佳解的「路徑」。如果這條路徑沒有任何限制，那麼這條路徑其實也不會太難找。我們可以先將在啟始盤面與最終最佳解當中同色的符石編號對應，也就是紀錄哪一個符石最後要移動到哪裡去，然後開始照著我們想要的來移動。讀到這裡，你可能會想說「慢著，哪有你想怎麼動就怎麼動這麼簡單，移動特定一個符石的時候可是會影響到其它符石的」。接下來我要證明的就是，「從任意盤面必定存在一條路徑可以移動成另一個任意盤面」。有自己設計過一些演算法並證明有效性的人讀到這裡，應該已經知道大概證明的方向。首先，我先假定這條路徑一開始拿起來的符石最後會落在盤面的最右上角。接著我會從左而右，從下而上，把指定要的符石移動到那個位置上。舉例而言，從初始盤面，要變成最終盤面，我必須要把一個水珠移到最左下角。為了節省時間，就用離左下角最近的水珠，也就是 (3, 3) 這個水珠，而我應該要拿起來的是最後擺在右上角的木珠，一樣假定是離右上角最近的木珠，就是 (6, 5) 這顆。那麼我的路徑會是這樣，接著我再去移動心珠過來擺，一樣找最近的，我的路徑會是這樣。最下面一列，由左而右分別是心珠和暗珠。然後，把最下一列排好的路徑是這樣。看到這裡，一定會有人說，要是能這樣轉，那我也會。的確，其實只要有無限的時間，慢慢轉一定可以把盤面轉成我們要的樣子。但是問題就在於「沒有無限的時間」。
所以，相對於先前提到的搜尋法(我隨便取個名字)，因為計算複雜度太高導致於會根本「算不完」。最終盤面建構路徑法(還是一樣，名字是隨便取的，請不要放在心上)，要找到一個最終盤面是最佳解不難，要找到一條路徑也不難。但是很可能根本走不完。反應快一點的人應該已經發現機會是什麼。雖然人的手有手速的限制，很可能無法在五秒之內轉完這麼複雜的路徑(剛剛排最下面一排就已經花掉 52 步，如果要排完整個盤面可能要 200 步以上)。但是如果是給程式去排，要在五秒之內送出一大堆的滑鼠訊號，絕對是做得到。想到這裡，我就滿懷著希望打開 Bluestacks (or Genymotion) ，想要試試看是不是我拼命狂送訊號，模擬器也會把這些訊號如實地傳遞給在其中執行的 App 。不過一試馬上就知道，完全不能用。雖然我不太確定背後的原理是什麼，但是模擬器或其中的 App 處理滑鼠訊號有它的極限間隔，在兩次處理的間隔時間之內的滑鼠動作，有可能會直接被忽略。舉個簡單的例子，假使我送出向左再向下的動作，但在左邊那格停留的時間不夠長，以至於沒有被偵測到，就已經往下的話，那麼動作實際上就會變成是直接往左下斜轉，而不是先往左再往下。
在經過很多次的實驗以後，我測到的數據是以我的電腦執行 Bluestacks ，這個間隔時間大約在 70ms 到 80ms 左右，如果兩次動作隔的時間比這個時間還要短，就有機會有動作會沒有被偵測到。這個數據代表的意義很明顯，即使是程式在玩這個遊戲，一樣有嚴格的步數上限。即使這個步數的上限可能隨著使用的模擬器的順暢度或實作方式有所不同，但可走的步數並不是「無限」的。當然，這並不代表「最終盤面建構路徑法」就不能用，只是它可能需要搭配一個可以找到最佳解，但是該最佳解與啟始盤面的路徑又不會太長的演算法。一旦我們增加了這些條件在裡面，那麼這個演算法就不再像剛剛示範的那麼簡單，裡面勢必也要作一些搜尋，進而增加它的運算複雜度。當然，這個「最終盤面建構路徑法」的複雜度一定還是遠比暴力搜尋求解要低得多。如果可走的步數不是壓在 70 步這麼短的步數裡面(剛剛光是排一列就已經花掉超過 50 步)，這個演算法應該是大有可為。但是因為對步數的要求，對這個演算法而言其實相當嚴苛，所以最後在幾經思考之後，我還是決定暫時放棄這個演算法，還是試著從搜尋路徑的方向來著手。
因為文章有越寫越長的趨勢，所以這一篇就先停在這裡，免得有人一點進來看到旁邊的 scroll bar 就不想讀了。
2014年2月26日 星期三
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 再收手，但當時卡在取點取色的效率不佳，最後未竟全功。等我學會新技巧的時候，沒空回頭去做。所以如果有機會的話，也許我會再把它改良一下。
最好的情況下，我應該要把 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 再收手，但當時卡在取點取色的效率不佳，最後未竟全功。等我學會新技巧的時候，沒空回頭去做。所以如果有機會的話，也許我會再把它改良一下。
ToS2 神魔之塔擬人轉珠/獅子宮/拼圖盾 示範影片
我在看網路上的其它影片時，發現大部份的功能大家做的都差不多。而我的程式相比之下，亮點可能就是我已經把解拼圖盾也一併實作完了。所以這裡的第一個影片，就先擺上解拼圖盾的示範影片。因為我很希望可以得到一些回饋，特別是技術上的回饋，所以我還在考慮要怎麼分享這個專案。目前還沒有很確定的想法。所以就只先放上影片。
訂閱：
文章 (Atom)