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 步以內找到的最佳解可能是這樣。

但是再往下搜尋 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 的作法就下篇再講了。