PTT遊戲區 / PuzzleDragon (龍族拼圖)

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

看板PuzzleDragon (龍族拼圖)作者 (麥子)時間10年前 (2014/07/14 00:33), 10年前編輯推噓41(41推 0噓 65→)
留言106則, 41人參與, 最新討論串2/2 (看更多)
※ 引述《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
→
07/14 00:34, , 1F
可以斜轉有8個方向!! (?
07/14 00:34, 1F
如果把斜轉也考慮進去，每一步就有八個方向，複雜度會高很多， 同樣是 10 步，沒有斜轉是 4^10 ，有的話則是 8^10 。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 00:38:24
→
07/14 00:43, , 2F
目前看過類似的東西都是直接放棄斜轉......
07/14 00:43, 2F
放棄斜轉基本上不是演算法難度的問題，因為允許斜轉更容易找到最佳解， 我想大部份相關的作品不考慮斜轉，主要是因為會需要用 sovler 的玩家， 通常都是轉珠能力比較不好的玩家，斜轉的不穩定性，手轉去執行時會產生問題。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 00:46:06
推
07/14 00:48, , 3F
快推 求翻譯
07/14 00:48, 3F
推
07/14 00:49, , 4F
嗯嗯 原來如此 看不懂
07/14 00:49, 4F
推
07/14 00:52, , 5F
麥子大竟然會降臨PAD版...
07/14 00:52, 5F
推
07/14 00:52, , 6F
原來是這樣喔 這篇是中文嗎
07/14 00:52, 6F
推
07/14 00:52, , 7F
考慮到不可能往回走，所以其實只要計算 3 個方向 XD
07/14 00:52, 7F
→
07/14 00:54, , 8F
若只考慮 30 步，大概只有 6000 兆種路徑... 吧 XDDD
07/14 00:54, 8F
一些細節是 (1) 往回走不用計算，所以能往下走的選擇是 3 個方向 (考慮斜轉是 7 個) (2) 不往下走也是一個選擇，也要計算在裡面，不過影響很小，可以忽略。 (3) 產生重覆盤面的走法可以不去走，例如四個珠繞小圈圈繞三次... 另外雖然在計算時間複雜度的時候，主要是算產生盤面的量，不過算 combo 數， 其實也要不少時間。如果評分的時候不只考慮 combo 數，還考慮了餘珠位置等等， 時間會更久。為什麼這一點提出來講，是因為產生盤面是很好用 GPU 平行化的， 可以丟去 GPU 跑，速度應該會很快。但是計算特定盤面的 combo 數， 因為裡面的條件式太多，反而不利於用 GPU 來加速。我不知道別人的解法怎麼做， 不過我自己目前還沒有時間嘗試去用 GPU 加速，等有空再看看好了。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 01:04:44
推
07/14 00:57, , 9F
推~~
07/14 00:57, 9F
推
07/14 01:09, , 10F
先建立某些常見解法成路徑TABLE 先LOOKUP TABLE
07/14 01:09, 10F
→
07/14 01:09, , 11F
不知道行得通嗎?!
07/14 01:09, 11F
推
07/14 01:10, , 12F
我是覺得暴力算不太可能。個人電腦的速度還不夠看 XD
07/14 01:10, 12F
→
07/14 01:11, , 13F
@followwar: 查表法也不太可能。記憶體/硬碟還不夠大 XD
07/14 01:11, 13F
啟始盤面的總量是 6^30 ，每個都建一個解也要非常非常久。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 01:11:56
推
07/14 01:15, , 14F
我的意思是某些常見解交錯的方法先內建
07/14 01:15, 14F
→
07/14 01:16, , 15F
遇上時直接使用解這些交錯的路徑
07/14 01:16, 15F
因為啟始盤面太多了，剛好遇到一樣盤面的機率其實滿低的。 不過當然也有可能是因為我沒有想到好的找出「相似」盤面的方法。
推
07/14 01:21, , 16F
不考慮斜轉 應該只有三個方向走可以吧，因不會往回頭走
07/14 01:21, 16F
→
07/14 01:21, , 17F
除了起手步之外
07/14 01:21, 17F
→
07/14 01:28, , 18F
已知目標combo數的話 有沒有可能先產生轉完的盤面 在從
07/14 01:28, 18F
→
07/14 01:29, , 19F
結果反推回去?
07/14 01:29, 19F
這個想法我其實有寫一篇文章討論，不過不能網址不能貼到這個板上。 基本上簡略來說就是，如果要用一種很單純的回推方法，一定可以找到路徑， 只是會很長。因為從任一盤面走成另外任一盤面是一定可能的，這可以簡單證明。 但如果同時還希望步數不要太長，甚至要求最短路徑，那還是得要作搜尋。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 01:58:03
推
07/14 01:34, , 20F
主要是目標combo數的盤面有複數個，所以沒辦法用反推
07/14 01:34, 20F
→
07/14 01:34, , 21F
的方式來做雙頭BFS加速
07/14 01:34, 21F
其實你提的作法是可以作的，問題在於要怎麼選取一個「夠像」現在盤面的目標盤面。 當然一個最直覺的作法就是找出現在盤面和目標盤面珠子的一一對應， 例如同色的珠就找最近的，然後算 Hamming distance 之類的， 差越少的算作越相似，然後找差最少的當作目標盤面，去作雙向 BFS 。 不過目前我還無法確定 Hamming distance 或類似的求差方式算出來的數字， 和兩個盤面之間的最短路徑長度是緊密相關的。因為實際上一個 20~30 步的路徑， 就可以把盤面打得很亂，所以這種計算相似度的方式可能也不是很適當。
推
07/14 01:35, , 22F
強者推一個!
07/14 01:35, 22F
→
07/14 01:36, , 23F
是麥大0.0
07/14 01:36, 23F
→
07/14 01:40, , 24F
先產生一定量的目標盤面 再跟目前盤面作比對 取相似度
07/14 01:40, 24F
→
07/14 01:41, , 25F
最高(或前幾名)的來作 這樣可以嗎
07/14 01:41, 25F
回在上面那一段了。主要的問題是「相似度高」是否就代表「路徑短」， 如果能大略證明這兩者之間的關聯度足夠，應該是可以做的。 但即使做了可以用雙向的 BFS ，可能還是要花不少的時間作搜尋才找得到解。 不過既然這種作法得到的是最佳解，比上面一大堆 heuristic 久是應該的。
推
07/14 01:44, , 26F
為什麼要讓我想起被當的演算法orz
07/14 01:44, 26F
推
07/14 01:47, , 27F
推，好奇這類演算法很久了
07/14 01:47, 27F
推
07/14 01:56, , 28F
學習了
07/14 01:56, 28F
※ 編輯: sitos (36.224.222.113), 07/14/2014 02:03:01
→
07/14 02:00, , 29F
http://shouryan.blogspot.tw/ 是在討論類似這種東西
07/14 02:00, 29F
→
07/14 02:00, , 30F
的演算法嗎?
07/14 02:00, 30F
還有 46 則推文
還有 16 段內文
→
07/14 14:21, , 77F
看完你回應的點 我想你是陷入交配必定產生最好的下一代
07/14 14:21, 77F
→
07/14 14:22, , 78F
基因演算法的順序為 交配 突變 適應函數 天擇的順序
07/14 14:22, 78F
→
07/14 14:22, , 79F
如果交配必定保留最好的下一代....那後面步驟都可以省略了
07/14 14:22, 79F
→
07/14 14:23, , 80F
結論就是.....產生的下一代不一定會最好..
07/14 14:23, 80F
我並沒有認為交配必定會產下最好的下一代，但下一代是好的下一代的機率如果很低， 那倒不如直接隨機產生路徑，反正效率也差不多。同樣突變也是， 如果每一次突變都很容易讓解變得很差，那還不如直接隨機產生解來隨便試一試。 基因演算法要套用在轉珠問題上面當然可以用，只是效率好不好的問題。
→
07/14 14:24, , 81F
至於如何證明近似最佳....請看黑盒子理論....
07/14 14:24, 81F
你講的這些我知道，我只是認為基因演算法在轉珠問題裡面效率不好， 因為有相似基因的解通過適應函數算出來的值可能會差異非常大。 不斷通過天擇往最佳解貼近的速度可能會很慢，所以我目前還是選用類似 A* 的作法。 因為 A* 的作法在我眼裡看起來比 GA 更適用在轉珠問題。
推
07/14 14:26, , 82F
我以為我走到計算數學版...
07/14 14:26, 82F
※ 編輯: sitos (36.224.222.113), 07/14/2014 14:33:56 ※ 編輯: sitos (36.224.222.113), 07/14/2014 14:41:15
推
07/14 14:46, , 83F
基因演算法就是....不用花啥腦袋....省去證明....的方法..
07/14 14:46, 83F
→
07/14 14:47, , 84F
ORZ....XDDD 你明白就好了.....不然不會這麼多論文....XD
07/14 14:47, 84F
→
07/14 14:48, , 85F
至於你講的A* 我忽然明白我們講的差異在哪
07/14 14:48, 85F
嗯，在我的領域看到用 GA 跟 SA 的論文，大概就是去看論文怎麼把要解的問題， model 成 GA 跟 SA 能夠解的形式，然後看看這個 model 有沒有什麼創新性。 如果單純只是硬把問題丟進 GA 跟 SA 解，那是沒什麼貢獻的。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 14:50:54
→
07/14 14:48, , 86F
我印象中A*都有明確目標....但是在轉珠途中我並沒有
07/14 14:48, 86F
A* 的關鍵一樣在於那個評價公式的設計好壞，而且也不一定要有明確目標， 主要是要能夠引導 search 要往哪個方向去走。當然 A* 也不用作全套，可以有變形， 即使找不到最佳解，能夠很有效率地找到次佳解也是不錯的演算法。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 14:53:49
→
07/14 14:51, , 87F
如果換成A*的方式 我所講的走向BFS 每次3曾判斷
07/14 14:51, 87F
→
07/14 14:52, , 88F
事實上就是A* 每次走一個3*3區域以後 在找最好的H
07/14 14:52, 88F
→
07/14 14:53, , 89F
GA強大的地方在於跳脫local optimal...
07/14 14:53, 89F
→
07/14 14:53, , 90F
其他部分我不覺得特別突出
07/14 14:53, 90F
→
07/14 14:55, , 91F
那就變成最佳搜尋法+登山法...A*在特定條件下
07/14 14:55, 91F
→
07/14 14:55, , 92F
就是BFS.....只是名稱不同
07/14 14:55, 92F
也是啦，只是它正式的名字就叫 A* ，所以我就寫 A* ，這樣別人比較知道在說啥。 不然我自己講，我會把我用的演算法稱為分段式 DFS ，然後為了跳出 local optimal ， 搭配回溯路徑與次佳解搜尋 blabla ，只是這樣也沒人知道我在講啥。 這些作法我有寫在我的 blog ，後來就有人留言說他用 A* ， 然後我看了看。嗯，其實也可以把我的作法視為 A* 的一種變型。 當然要說它是 DFS 的變型也可以，反正就是這裡混一點那裡混一點。 重點是能在夠短的時間裡面搜出夠好的解法，就是適合的演算法。 ※ 編輯: sitos (36.224.222.113), 07/14/2014 15:02:58
→
07/14 15:04, , 93F
我會考量深度為3的情況 是假想切珠問題....
07/14 15:04, 93F
→
07/14 15:05, , 94F
可以想像 要以COMBO數為考量 3科一組 是必然的
07/14 15:05, 94F
→
07/14 15:06, , 95F
超過3科部分切掉的情況 3步內都可以完成 深度3是合理的
07/14 15:06, 95F
→
07/14 15:06, , 96F
不過我可沒空證明.....
07/14 15:06, 96F
我之前實際的經驗，三步太短，不容易找到好的解... ※ 編輯: sitos (36.224.222.113), 07/14/2014 15:07:28
→
07/14 15:11, , 97F
3步不夠有點難以想像...27張找最佳 你的H怎麼計算的?
07/14 15:11, 97F
→
07/14 15:11, , 98F
完整模擬完消珠疊珠結果???
07/14 15:11, 98F
不只是完整模擬完消疊珠的結果，還會避免疊珠的 combo 連消被天降打散， 以及盡可能讓同色餘珠集中在一起增加天降增加 combo 的可能性。
推
07/14 15:19, , 99F
如果是我做的話 3步內沒有提升我會找相同的做就是了
07/14 15:19, 99F
期待你的作品。 :) ※ 編輯: sitos (36.224.222.113), 07/14/2014 15:56:42
推
07/15 12:50, , 100F
記得有個 single player monte-carlo tree search
07/15 12:50, 100F
→
07/15 12:50, , 101F
也許可以試試看 (?) XD
07/15 12:50, 101F
學長現在在哪裡高就阿... 好久不見了 既然是 ledia 的建議，等我之後有空就來看看 :) ※ 編輯: sitos (36.224.222.113), 07/15/2014 15:10:38
→
07/15 22:46, , 102F
tabu哩?
07/15 22:46, 102F
推
07/17 17:37, , 103F
monte-carlo tree search 在電腦棋類掀起了不小的波瀾
07/17 17:37, 103F
→
07/17 17:38, , 104F
不過一直都是用在互奕的棋局, 我沒有花時間去研究轉植到單人
07/17 17:38, 104F
→
07/17 17:38, , 105F
game search 的差異, 不過他的好處是不用精準的 evaluation
07/17 17:38, 105F
→
07/17 17:39, , 106F
看到有人在討論就拋磚引玉一下 ... XD
07/17 17:39, 106F
‣ 更多 sitos 的文章
文章代碼(AID): #1JmhJZWN (PuzzleDragon)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
PuzzleDragon 近期熱門文章
更多 近期熱門文章 >>
PTT遊戲區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sitos 的文章
文章代碼(AID): #1JmhJZWN (PuzzleDragon)