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