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 就不想讀了。