PTT數位生活區 / Programming

[問題] 找出最短必勝棋步

看板Programming作者 (LaPass)時間12年前 (2012/12/18 22:32), 編輯推噓4(4推 0噓 58→)
留言62則, 5人參與, 最新討論串1/1
已知，五子棋執黑方證實有必勝法 現在，我打算把必勝法的棋步窮舉出來寫進資料庫 並找出白色能持續棋局的最大步數 (例如，白方45步內必敗這樣) 請問，該如何找出必勝法的棋步？ 有方法的關鍵字嗎？ 現在我已經寫出一個還不錯的AI 已經可以把可能的步數壓到很低(10步內) 只是，要如何才能知道，找出來的必勝法的路徑是最短的？ 以及，在窮舉路徑的時候，要如何知道那一條是黑方必勝的路徑？ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.38.87.100
→
12/18 23:06, , 1F
Alpha-Beta?
12/18 23:06, 1F
→
12/18 23:40, , 2F
Alpha-Beta是找最佳路徑的，但是必勝就....
12/18 23:40, 2F
→
12/18 23:55, , 3F
..........
12/18 23:55, 3F
→
12/18 23:55, , 4F
我認真想看看把全部路徑翻過一遍的方法好了
12/18 23:55, 4F
→
12/19 09:55, , 5F
你是有搞清楚還是沒搞清楚問題?
12/19 09:55, 5F
→
12/19 09:55, , 6F
你要全部翻, 就只要將所有走步都展開即
12/19 09:55, 6F
→
12/19 09:56, , 7F
可,不要剪枝. 暴力法.
12/19 09:56, 7F
→
12/19 10:09, , 8F
就是不會剪枝啊 orz....
12/19 10:09, 8F
→
12/19 10:40, , 9F
Alpha-Beta 本身就在做剪枝啊......
12/19 10:40, 9F
→
12/19 10:40, , 10F
你是有搞清楚Alpha-Beta 嗎?
12/19 10:40, 10F
→
12/19 10:41, , 11F
沒的話, 去wikiiiiiiiii 一下吧.
12/19 10:41, 11F
→
12/19 10:41, , 12F
但 這種search 法, 會跟move ordering
12/19 10:41, 12F
→
12/19 10:41, , 13F
有直接的影響, 所以你要最短, 最佳解
12/19 10:41, 13F
→
12/19 10:42, , 14F
最好還是暴力解, 簡單的說, 將所有解
12/19 10:42, 14F
→
12/19 10:42, , 15F
生成檔案, 再從中找出所有答案
12/19 10:42, 15F
→
12/19 10:45, , 16F
中的最短最佳解.
12/19 10:45, 16F
→
12/19 10:47, , 17F
有論文說, 五子棋的複雜度約10^70而已
12/19 10:47, 17F
→
12/19 10:47, , 18F
買顆大一點的硬碟, 存得完的.
12/19 10:47, 18F
→
12/19 10:50, , 19F
wiki早就看過好幾遍了..... = =
12/19 10:50, 19F
→
12/19 10:52, , 20F
Alpha-Beta在裁的是，評價上不太可能的棋步
12/19 10:52, 20F
→
12/19 10:52, , 21F
但我怎麼能確定，那到底是不是必勝法的棋步
12/19 10:52, 21F
→
12/19 10:53, , 22F
?
12/19 10:53, 22F
→
12/19 11:01, , 23F
而且，即使把整顆樹展開好了，我要怎麼從樹
12/19 11:01, 23F
→
12/19 11:03, , 24F
中確定是哪一條？用Alpha-Beta或許可以知道
12/19 11:03, 24F
→
12/19 11:04, , 25F
哪一步是不錯的步數，但是，是不是真的必勝
12/19 11:04, 25F
→
12/19 11:04, , 26F
還是得再窮舉一次吧？
12/19 11:04, 26F
→
12/19 11:09, , 27F
AB 只要寫對勝的條件, 而你的深度又夠深
12/19 11:09, 27F
→
12/19 11:09, , 28F
Lordaeron說得沒錯，阿法被塔就是再剪枝
12/19 11:09, 28F
→
12/19 11:09, , 29F
深到可以達到勝利的條件, 哪就一定是勝
12/19 11:09, 29F
→
12/19 11:09, , 30F
我是指，找必勝法的一方走算出來的最佳棋步
12/19 11:09, 30F
→
12/19 11:09, , 31F
可能你 wiki 還要再多看幾次 XD
12/19 11:09, 31F
→
12/19 11:10, , 32F
記住我的前題"寫對勝的條件"
12/19 11:10, 32F
→
12/19 11:10, , 33F
及"深度"
12/19 11:10, 33F
→
12/19 11:10, , 34F
，另一方窮舉所有棋步，這樣證明必勝
12/19 11:10, 34F
→
12/19 11:11, , 35F
而且如果你要最短路徑，其實你就不能剪枝
12/19 11:11, 35F
→
12/19 11:11, , 36F
你只要寫得對, AB 走出來, 都是最佳走步
12/19 11:11, 36F
→
12/19 11:11, , 37F
你要用暴力法全部掃過 :|
12/19 11:11, 37F
→
12/19 11:11, , 38F
這件事, knuth 證明過了. 你可以不用去
12/19 11:11, 38F
→
12/19 11:11, , 39F
猜測了
12/19 11:11, 39F
→
12/19 11:12, , 40F
ok，那我先這樣試試看
12/19 11:12, 40F
→
12/19 17:31, , 41F
我搞懂我在AB上哪裡搞錯了 XD
12/19 17:31, 41F
推
12/19 18:30, , 42F
在怎饃樣也搜不到最深阿..
12/19 18:30, 42F
→
12/19 23:23, , 43F
你不是已經看AB 好幾遍了?現在又才搞懂?
12/19 23:23, 43F
→
12/20 00:23, , 44F
嗯~ 之前搞錯傳回值的設計方式
12/20 00:23, 44F
→
12/20 00:24, , 45F
算盲點吧.... 搞通這一點後，要改成找必勝
12/20 00:24, 45F
→
12/20 00:25, , 46F
的棋步，或是最短必勝路徑就很簡單了，可以
12/20 00:25, 46F
→
12/20 00:25, , 47F
把砍樹的原則改成找必勝路徑的
12/20 00:25, 47F
推
12/20 01:32, , 48F
恭喜恭喜～
12/20 01:32, 48F
→
12/20 09:30, , 49F
砍樹的原則本來就是找勝利路徑啊,你在
12/20 09:30, 49F
→
12/20 09:30, , 50F
講什麼?
12/20 09:30, 50F
→
12/21 09:14, , 51F
昨天試了一下，沒辦法在合理時間內找出結果
12/21 09:14, 51F
→
12/21 09:15, , 52F
沒設限深度的狀況下，跑不完....
12/21 09:15, 52F
→
12/21 09:17, , 53F
還有，問題不是找「最有可能獲勝」的棋步，
12/21 09:17, 53F
→
12/21 09:18, , 54F
而是找「一定會獲勝」的棋步。雖然兩者大致
12/21 09:18, 54F
→
12/21 09:19, , 55F
一樣。把ab改一下就可以去求證是否必勝，但
12/21 09:19, 55F
→
12/21 09:21, , 56F
是，算不完....
12/21 09:21, 56F
→
12/21 12:00, , 57F
看棋的複雜度, 但AB 求解己經被暴力快了
12/21 12:00, 57F
→
12/21 12:00, , 58F
你要在合理時間內找出, 就不是AB 可以
12/21 12:00, 58F
→
12/21 12:01, , 59F
做的,哪你就發明一個新ALGO 來合理吧.
12/21 12:01, 59F
推
12/21 16:01, , 60F
呃，算不完是正常的啦... orz
12/21 16:01, 60F
推
12/21 18:34, , 61F
想知道你這個求解有考慮黑方先手禁著嗎？
12/21 18:34, 61F
→
12/21 20:38, , 62F
不考慮
12/21 20:38, 62F
‣ 更多 LaPass 的文章
文章代碼(AID): #1Gq7vao7 (Programming)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 LaPass 的文章
文章代碼(AID): #1Gq7vao7 (Programming)