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 沒辦法做的事情，由盤面評分演算法來補足。