作者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