Re: [閒聊]最短路徑轉珠

[sitos (麥子)]

※ 引述《r5e97nk63 (yapin)》之銘言：
: 如題相信很多手速不夠快，狠，準的人視此為目標。然而相關教導文又太少，大多只能從
: 網站獲得。
: 可是之前太陽教主又認為光看解答著實困難，因此我在這想問一下，有人知道網頁最短路
: 徑的剖析順序嗎，具體一點便是它是如何被運算出來的，如果它真是模擬”所有路徑結果
: “那小弟就真的認了。（雖然我是認為這不可能啦）
: 哪怕只知道一點點，我相信這對”非常理”疊珠的分析都會有蠻大的突破。

如果以找到特定 combo 數作為目標，找最短路徑的解法，最適合的作法是 BFS 。
不過即使是 20 步左右的路徑，對於電腦而言要計算，搜尋完所有可能的解，
時間還是太長了。在不考慮斜轉的情況底下，一步最多可以有四個方向可以走，
以這個數字作粗略的計算， 20 步所產生的可能盤面有 4^20 ，也就是 2^40 ，
要作這樣的計算需要的時間其實滿長的，以此來產生最短路徑並不太實用。

另外一種作法是用 A* 演算法作搜尋，每走一步給與所產生的四個盤面一個分數，
挑分數最高的盤面再走下一步。但直接這樣做不太行得通，因為從啟始盤面只走一步，
可能產生的 combo 數很少，可能產生出來的四個盤面都沒有消任何珠，
根本沒辦法用計算分數的方式分出往哪一個方向走比較好。

因此比較實際的作法是，每走 n 步給予所有產生的盤面一個分數，
例如一個計算階段走 8 步，那麼就會產生 4^8 (2^16) 個盤面，
然後去評估這 64K 個盤面哪一個盤面最好，然後再從這個盤面繼續往下找。
這樣做的好處是每一階段的計算時間都不長，可以重複好幾次。

上述這兩種作法 (一次走一步的 A* 跟一次走 n 步的 A* ) 都不能保證找到最佳解。
而這個作法還有另外一個缺點，就是可能會卡在區域最佳解。
因為一個前幾步就產生不錯的解的路徑，不能保證後面可以產生好解。
所以還是需要某種回溯的機制，在找不到好解的時候放棄已經找到的解。
不過這樣做缺點就是馬上會增加總計算量。

另外一個可以試著改進的部份是 A* 的評分機制，最原始的作法可能是 combo 數，
但產生一個 combo 可不是亂走就可以走出來。因此為了要分辨解的好壞，
除了 combo 數以外可能還要其它的條件加進來。例如在消完以後，可能還有某些同色珠，
則可以設定同色餘珠的位置越接近的解，分數越高。因為這種盤面，
可能再走幾步就可以多產生一個 combo ，應該要比那些同色餘珠離很遠的來得高分。

至於路徑的起手位置，除了所有三十個位置都一起嘗試以外，因為整個盤面移動上，
最自由的珠就是直接被移動的珠，因此可能挑選某一個很分散的珠會是比較好的選擇，
例如有兩個水珠在最左邊，一個在最右邊，這時候如果選擇最右邊的水珠，
可能就可以把三個水珠拉在一起，相對地如果選擇其它的珠，要把最右邊的水珠運來，
可能要花的步數就會多上很多。

至於 branch and bound 或 divide and conquer 當然都可以做，
不過前者如果想要做到保證最佳解，那步數可能得要壓得很短才能夠算得完。
後者的話除了不能保證得到最佳解以外，其實得到的解可能會滿差的，
除非剛好足夠形成 combo 的珠都在同一邊，否則如何 divide 會是一個問題。

當然不同的人可能會有一些不同的 optimization 技巧，不過講下去可能太多話了，
總之 search algorithm 如果要解的問題本身沒有某些非常良好的特性，
那麼頂多就是在暴力解上面加上一些 heuristic 去縮短時間來得到次佳解，
因此一定是在某些盤面表現得不錯，在另外一些盤面表現的普普通通，
然後在某些剛好剋到的盤面，就找不太到好的解。

不過以 6*5 的轉珠盤面而言，大概要在五十步以內找出一個不錯的解，都滿有機會的。


--

        活著的目的是為主活 然後為主死

        死亡的目的是為主死 然後為主活


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.224.222.113
※ 文章網址: http://www.ptt.cc/bbs/PuzzleDragon/M.1405269219.A.817.html
※ 編輯: sitos (36.224.222.113), 07/14/2014 00:34:20
→ No278:可以斜轉有8個方向!!  (?
如果把斜轉也考慮進去，每一步就有八個方向，複雜度會高很多，
同樣是 10 步，沒有斜轉是 4^10 ，有的話則是 8^10 。
※ 編輯: sitos (36.224.222.113), 07/14/2014 00:38:24
→ Mormory:目前看過類似的東西都是直接放棄斜轉......
放棄斜轉基本上不是演算法難度的問題，因為允許斜轉更容易找到最佳解，
我想大部份相關的作品不考慮斜轉，主要是因為會需要用 sovler 的玩家，
通常都是轉珠能力比較不好的玩家，斜轉的不穩定性，手轉去執行時會產生問題。
※ 編輯: sitos (36.224.222.113), 07/14/2014 00:46:06
推 s93184s:快推                                            求翻譯
推 kashiwa27:嗯嗯 原來如此                                 看不懂
推 abab7974:麥子大竟然會降臨PAD版...
推 a062361316:原來是這樣喔         這篇是中文嗎
推 Tetralet:考慮到不可能往回走，所以其實只要計算 3 個方向 XD
→ Tetralet:若只考慮 30 步，大概只有 6000 兆種路徑... 吧 XDDD
一些細節是 (1) 往回走不用計算，所以能往下走的選擇是 3 個方向 (考慮斜轉是 7 個)
           (2) 不往下走也是一個選擇，也要計算在裡面，不過影響很小，可以忽略。
           (3) 產生重覆盤面的走法可以不去走，例如四個珠繞小圈圈繞三次...

另外雖然在計算時間複雜度的時候，主要是算產生盤面的量，不過算 combo 數，
其實也要不少時間。如果評分的時候不只考慮 combo 數，還考慮了餘珠位置等等，
時間會更久。為什麼這一點提出來講，是因為產生盤面是很好用 GPU 平行化的，
可以丟去 GPU 跑，速度應該會很快。但是計算特定盤面的 combo 數，
因為裡面的條件式太多，反而不利於用 GPU 來加速。我不知道別人的解法怎麼做，
不過我自己目前還沒有時間嘗試去用 GPU 加速，等有空再看看好了。
※ 編輯: sitos (36.224.222.113), 07/14/2014 01:04:44
推 sllwffd:推~~
推 followwar:先建立某些常見解法成路徑TABLE 先LOOKUP TABLE
→ followwar:不知道行得通嗎?!
推 Tetralet:我是覺得暴力算不太可能。個人電腦的速度還不夠看 XD
→ Tetralet:@followwar: 查表法也不太可能。記憶體/硬碟還不夠大 XD
啟始盤面的總量是 6^30 ，每個都建一個解也要非常非常久。
※ 編輯: sitos (36.224.222.113), 07/14/2014 01:11:56
推 followwar:我的意思是某些常見解交錯的方法先內建
→ followwar:遇上時直接使用解這些交錯的路徑
因為啟始盤面太多了，剛好遇到一樣盤面的機率其實滿低的。
不過當然也有可能是因為我沒有想到好的找出「相似」盤面的方法。

推 b43681477:不考慮斜轉 應該只有三個方向走可以吧，因不會往回頭走
→ b43681477:除了起手步之外
→ paulpaul99:已知目標combo數的話 有沒有可能先產生轉完的盤面 在從
→ paulpaul99:結果反推回去?
這個想法我其實有寫一篇文章討論，不過不能網址不能貼到這個板上。
基本上簡略來說就是，如果要用一種很單純的回推方法，一定可以找到路徑，
只是會很長。因為從任一盤面走成另外任一盤面是一定可能的，這可以簡單證明。
但如果同時還希望步數不要太長，甚至要求最短路徑，那還是得要作搜尋。
※ 編輯: sitos (36.224.222.113), 07/14/2014 01:58:03
推 DarkPrincex:主要是目標combo數的盤面有複數個，所以沒辦法用反推
→ DarkPrincex:的方式來做雙頭BFS加速
其實你提的作法是可以作的，問題在於要怎麼選取一個「夠像」現在盤面的目標盤面。
當然一個最直覺的作法就是找出現在盤面和目標盤面珠子的一一對應，
例如同色的珠就找最近的，然後算 Hamming distance 之類的，
差越少的算作越相似，然後找差最少的當作目標盤面，去作雙向 BFS 。

不過目前我還無法確定 Hamming distance 或類似的求差方式算出來的數字，
和兩個盤面之間的最短路徑長度是緊密相關的。因為實際上一個 20~30 步的路徑，
就可以把盤面打得很亂，所以這種計算相似度的方式可能也不是很適當。

推 dennis2030:強者推一個!
→ qiaffvvf:是麥大0.0
→ paulpaul99:先產生一定量的目標盤面 再跟目前盤面作比對 取相似度
→ paulpaul99:最高(或前幾名)的來作 這樣可以嗎
回在上面那一段了。主要的問題是「相似度高」是否就代表「路徑短」，
如果能大略證明這兩者之間的關聯度足夠，應該是可以做的。
但即使做了可以用雙向的 BFS ，可能還是要花不少的時間作搜尋才找得到解。
不過既然這種作法得到的是最佳解，比上面一大堆 heuristic 久是應該的。

推 jiko5566:為什麼要讓我想起被當的演算法orz
推 heidi61818:推，好奇這類演算法很久了
推 Arashinoon:學習了
※ 編輯: sitos (36.224.222.113), 07/14/2014 02:03:01
→ howder5566:http://shouryan.blogspot.tw/  是在討論類似這種東西
→ howder5566:的演算法嗎?
我不太清楚這個作者有沒有討論「演算法」，在快一年前我開始想這方面的演算法時，
他的 blog 基本上沒幫上什麼忙，因為沒有討論演算法，也沒有 source code 可以看。
※ 編輯: sitos (36.224.222.113), 07/14/2014 02:08:35
推 paulpaul99:查到麥大的網站了 拜讀中
因為後來就開始忙了，所以其實算是寫到一半，目前只寫非常概念的部份，
之後可能會重新整理或重寫程式，然後 blog 再寫一些比較偏實作最佳化的。
不過，這些東西可能就不能在這邊講了。
※ 編輯: sitos (36.224.222.113), 07/14/2014 02:10:18
推 Murasaki0110:有趣
推 Jackalxx:為什麼會在PAD版看到這些眼熟的名詞XDDDD
推 NicoNeco:Sito大(拜
推 zacharyptt:https://github.com/eternnoir/ToS_Bot?files=1
→ followwar:樓上的演算法超眼熟  跟這個好像阿
→ followwar:https://github.com/kennytm/pndopt
這些東西真的可以 po 嗎? XD
※ 編輯: sitos (36.224.222.113), 07/14/2014 03:57:04
→ followwar:明天被水桶就知道了?!XD  不過那是網頁
推 joy3252355:推麥子大 居然在PAD版降臨 原來能用這種文釣出來 XDD
推 zacharyptt:不知道的人還是不知道 知道的人早就知道了
推 woieyufan:邊緣的連珠權值要比較高因為比較不影響盤面運作
我沒有這樣想過，不過聽起來似乎是一個合理的作法，也許有機會我會來試試看。

推 usoko:竟然在pad板看到sitos大 XD
推 jimmycool:如果用GA/SA之類的randomized algorithm效果如何呢?
→ jimmycool:先找一個比較差的解，再慢慢mutate到比較短的路徑
GA 跟 SA 基本的預設是 encode 過的那個 string 值相近的時候，
得到的解 quality 會差不多。但在轉珠的搜尋裡面這個前提並不成立。
簡單舉個 GA 的例子，假設現在有兩條路徑都可以得到很棒的解，
第一條是「上左下左下右右右上上左左上右右下右左左左」，
另一條是「下右右上右右上左左左左下下左下右右右上左」，
把這兩條拿來作 crossover ，第一條的前半接上第二條的後半會是一組好的解嗎？
應該不會。親代的優勢無法遺傳給子代的話 GA 應該效果很差。
※ 編輯: sitos (36.224.222.113), 07/14/2014 09:02:32
推 shikiDS:竟然在PAD版看到演算法!!
推 v63718x4:Dijkstra可以保證找到最短路徑 可是計算量會爆炸...
→ v63718x4:不過感覺Dijkstra 應該不適合用在這種轉珠分析上
Dijkstra's algorithm 主要應該是用在要搜尋的點有遠有近的狀況，
用來找最短的路徑。但如果所有解的 distance 都一樣 (轉珠裡就是 1 步)，
那其實 Dijkstra's algorithm 就是很普通的 BFS 而已，也是暴力解。

推 attacksoil:專業
推 a100900:專業給推
推 smilekerr:天吶 有沒有這麼專業
→ lpdpCossette:原來如此                               !!!???!?!?
→ vup4jp6:以這CASE來說 交配跟適應函數都會跟傳統的例子有差
推 horseorange:看不懂只能推了
推 vup4jp6:直覺會想用最佳優先搜尋，修正評分函數就好
→ vup4jp6:特殊面板或者圖形可以給特定的評分函數
以最佳優先搜尋當作骨幹去變形是我目前覺得相對直覺簡單，效果又不錯的做法。
不過一切的重點都在評分函數到底要怎麼設定。為了要讓搜尋的效果更好，
在做評分函數的時候我試過一大堆不同的方法，越做越複雜。
基本上只考慮 combo 數，計算起來不會很有效率。即使是沒有形成 combo 的盤面，
那些餘珠的位置也是有意義的。評分函數甚至應該要考慮天降破壞疊珠的情況，
以及最後餘珠相連而增加天降 combo 的數量等等。不過這有點細節了。

→ vup4jp6:基因演算法的部分 交配要用你的例子 要記錄最後位置
→ vup4jp6:才能做....適應函數必須要把長度也納入考量
→ vup4jp6:至於怎調整到適應函數優化 我想要討論出來 發PAPER比較快
就算有紀錄最後位置我認為也沒什麼用，路徑裡面隨便調換某一步的方向，
對整體盤面可能就會造成很嚴重的影響。雖然有人會覺得，我只是換了一步，
頂多可能影響一部份的盤面，其它已經產生的連珠還是會產生 combo 。
但是在考慮了疊珠的情況以後，某一個原本的連珠被打斷，很有可能會造成，
後面一連串本來疊珠落下會消的 combo 全部都不見。
不過如果計算分數的時候只考慮直接消的部份，不考慮疊珠，也許可行?

推 luxaky:恩 跟我想得差不多
推 pdexter:快推 不然人家會以為看不懂
推 ZMTL:有app可以跑最大三斜轉
要跑幾個斜轉應該都可以，限制三個應該也是擔心人手轉不出來吧。
※ 編輯: sitos (36.224.222.113), 07/14/2014 13:32:56
※ 編輯: sitos (36.224.222.113), 07/14/2014 13:38:04
→ vup4jp6:基因演算法的部分你誤會我的意思了...我是說紀錄每次位置
→ vup4jp6:你在做交配的時候只會用相同位置做組合 可以省去聯不連貫
→ vup4jp6:的問題 並且還要交換最後的色珠
嗯，看來我真的沒聽懂，可能要請你多解釋一點才聽得懂了。
因為我認為即使路徑是連貫的，交配之後的路徑很可能會破壞彼此路徑得到的好盤面。

假設有 A 跟 B 兩條路徑要作交配，令 A 的前段是 A1 ，後段是 A2 ，
B 的前段是 B1 ，後段是 B2 ，且走完 A1 跟走完 B1 時，
可移動的珠的位置是相同的以確保路徑連續。
如果 A 跟 B 都可以得到很好的解，那麼 A1B2 或 B1A2 會得到很好的解嗎? 我不認為。

理由是這樣的，因為從啟始盤面走完 A1 時得到的盤面和走完 B1 時的盤面是不同的，
雖然從走完 B1 時的盤面再走 B2 會得到很棒的解，但這並不代表，
從走完 A1 時的盤面再走 B2 也會得到很棒的解。簡單地說，兩個不同的盤面，
沒道理認為對其中一個盤面好的路徑，也一定會對另外一個盤面有不錯的解。

→ vup4jp6:關於最佳優先搜尋的部分 我們可以一次考慮深度三層
→ vup4jp6:事實上多考慮幾層深度 還是要照盤面來看 但是考慮是不需要
→ vup4jp6:總之....要是考量最短路徑來看 BFS為最基本的走向
如果要用 BFS 當然可以，只是效率實在太差。暴力解可以得到最佳解，但不實用。
我基本上相信現在所有的 solver 應該沒有人用暴力解，因為應該跑不完。
所以重點在於到底要用什麼樣的 heuristic 才能平衡計算時間和解的 quality 。
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:02:39
推 r5e97nk63:感謝麥大的說明，因為我一開始真的對網頁那種近似瞬間
→ r5e97nk63:的運算感到不可思議，才會想求解答。看來結論是”漂亮
→ r5e97nk63:”的演算法與伺服器的暴力破解，這樣理解沒錯吧？
我不知道網頁解的作法是怎麼做的。但如果要我猜，我認為應該還是用很漂亮的演算法，
去作近似最佳解。但不太可能是用暴力法去求最佳解，因為 solution space 太大了，
不太可能把所有能走的路徑通通都計算進去。但演算法怎麼設計對效率影響很大，
當然我是滿希望可以和其它人討論應該要怎麼設計，不過可能不太適合在這個板討論。
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:05:24
→ vup4jp6:基因演算法的部分你是從交配開始討論，我則是把結果交負
→ vup4jp6:適應函數...簡單來說是應函數做的跟評分函數不會差太多
越聽越不懂了。 :)

我對基因演算法的質疑是，兩個在適應函數上表現良好的親代，
在轉珠裡面，大多數的時候都不能產生在適應函數上表現良好的子代，
因此不符合基因演算法對於遺傳良好性狀這個部份的預設。
不過我對基因演算法其實不那麼熟，我只是單純覺得不太可行。

→ vup4jp6:BFS的意思是說演算法對於樹的走向....不是完整的跑BFS
→ vup4jp6:因為對於路徑來說 樹的高度等於路徑的長度...
演算法對於樹的走向? 這個也沒有聽懂。 BFS 指的是搜尋節點的順序，
就是最淺的開始搜，不完整跑完那應該要怎麼跑?
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:10:35
→ vup4jp6:DFS的走向是不必要的....我想我們可以討論到更細點的部分
你可能得要用回文才能解釋你要講的東西了，推文寫起來應該滿辛苦的。謝謝啦。 :)
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:17:36
→ vup4jp6:那你等我晚點有空 基因演算法的部分先回答
你慢慢來沒關係，因為其實這兩天會滿忙的，可能也沒有空討論。
如果 GA 真的適用的話，我之後可能會實作出來看看效果怎麼樣。

→ vup4jp6:看完你回應的點 我想你是陷入交配必定產生最好的下一代
→ vup4jp6:基因演算法的順序為 交配 突變 適應函數 天擇的順序
→ vup4jp6:如果交配必定保留最好的下一代....那後面步驟都可以省略了
→ vup4jp6:結論就是.....產生的下一代不一定會最好..
我並沒有認為交配必定會產下最好的下一代，但下一代是好的下一代的機率如果很低，
那倒不如直接隨機產生路徑，反正效率也差不多。同樣突變也是，
如果每一次突變都很容易讓解變得很差，那還不如直接隨機產生解來隨便試一試。
基因演算法要套用在轉珠問題上面當然可以用，只是效率好不好的問題。

→ vup4jp6:至於如何證明近似最佳....請看黑盒子理論....
你講的這些我知道，我只是認為基因演算法在轉珠問題裡面效率不好，
因為有相似基因的解通過適應函數算出來的值可能會差異非常大。
不斷通過天擇往最佳解貼近的速度可能會很慢，所以我目前還是選用類似 A* 的作法。
因為 A* 的作法在我眼裡看起來比 GA 更適用在轉珠問題。

推 beicoles:我以為我走到計算數學版...
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:33:56
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:41:15
推 vup4jp6:基因演算法就是....不用花啥腦袋....省去證明....的方法..
→ vup4jp6:ORZ....XDDD  你明白就好了.....不然不會這麼多論文....XD
→ vup4jp6:至於你講的A* 我忽然明白我們講的差異在哪
嗯，在我的領域看到用 GA 跟 SA 的論文，大概就是去看論文怎麼把要解的問題，
model 成 GA 跟 SA 能夠解的形式，然後看看這個 model 有沒有什麼創新性。
如果單純只是硬把問題丟進 GA 跟 SA 解，那是沒什麼貢獻的。
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:50:54
→ vup4jp6:我印象中A*都有明確目標....但是在轉珠途中我並沒有
A* 的關鍵一樣在於那個評價公式的設計好壞，而且也不一定要有明確目標，
主要是要能夠引導 search 要往哪個方向去走。當然 A* 也不用作全套，可以有變形，
即使找不到最佳解，能夠很有效率地找到次佳解也是不錯的演算法。
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:53:49
→ vup4jp6:如果換成A*的方式 我所講的走向BFS 每次3曾判斷
→ vup4jp6:事實上就是A* 每次走一個3*3區域以後 在找最好的H
→ vup4jp6:GA強大的地方在於跳脫local optimal...
→ vup4jp6:其他部分我不覺得特別突出
→ vup4jp6:那就變成最佳搜尋法+登山法...A*在特定條件下
→ vup4jp6:就是BFS.....只是名稱不同
也是啦，只是它正式的名字就叫 A* ，所以我就寫 A* ，這樣別人比較知道在說啥。
不然我自己講，我會把我用的演算法稱為分段式 DFS ，然後為了跳出 local optimal ，
搭配回溯路徑與次佳解搜尋 blabla ，只是這樣也沒人知道我在講啥。
這些作法我有寫在我的 blog ，後來就有人留言說他用 A* ，
然後我看了看。嗯，其實也可以把我的作法視為 A* 的一種變型。
當然要說它是 DFS 的變型也可以，反正就是這裡混一點那裡混一點。
重點是能在夠短的時間裡面搜出夠好的解法，就是適合的演算法。
※ 編輯: sitos (36.224.222.113), 07/14/2014 15:02:58
→ vup4jp6:我會考量深度為3的情況  是假想切珠問題....
→ vup4jp6:可以想像 要以COMBO數為考量 3科一組 是必然的
→ vup4jp6:超過3科部分切掉的情況 3步內都可以完成 深度3是合理的
→ vup4jp6:不過我可沒空證明.....
我之前實際的經驗，三步太短，不容易找到好的解...
※ 編輯: sitos (36.224.222.113), 07/14/2014 15:07:28
→ vup4jp6:3步不夠有點難以想像...27張找最佳 你的H怎麼計算的?
→ vup4jp6:完整模擬完消珠疊珠結果???
不只是完整模擬完消疊珠的結果，還會避免疊珠的 combo 連消被天降打散，
以及盡可能讓同色餘珠集中在一起增加天降增加 combo 的可能性。

推 vup4jp6:如果是我做的話 3步內沒有提升我會找相同的做就是了
期待你的作品。 :)
※ 編輯: sitos (36.224.222.113), 07/14/2014 15:56:42
推 ledia:記得有個 single player monte-carlo tree search
→ ledia:也許可以試試看 (?) XD
學長現在在哪裡高就阿... 好久不見了
既然是 ledia 的建議，等我之後有空就來看看 :)
※ 編輯: sitos (36.224.222.113), 07/15/2014 15:10:38
→ shockben: tabu哩?
推 ledia:monte-carlo tree search 在電腦棋類掀起了不小的波瀾
→ ledia:不過一直都是用在互奕的棋局, 我沒有花時間去研究轉植到單人
→ ledia:game search 的差異, 不過他的好處是不用精準的 evaluation
→ ledia:看到有人在討論就拋磚引玉一下 ... XD