作者Baseba11 (背湿霸壹壹)
看板GO
标题Re: [问题] 九路围棋该贴多少目合理，甚至是十九路 …
时间Sun Jun 26 17:46:05 2011
其实我不知道为什麽只要讨论到AI就一定有人要提穷举
事实上考虑一下围棋的规则 我们就可以发现一个很明显的现象
当一串棋子被提吃之後所形成的空 除非只有一目
否则很明显的这块空可以再被填入棋子
再考虑最极端的例子 整个盘面除了一个点之外被其中一个颜色填满
下一手就只有 1.吃掉全部的祺 2.pass 3.认输
如果选择1.这时後会发现盘面上的情况回到跟第一手的情形一样
如果又考虑三劫的问题又更复杂了
所以穷举围棋的走法是不可能展开成一个有限的 没有回圈的分支树
结论是不论原原po说得哪一种算法都有点问题
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.202.44
1F：推 ddavid:在有严谨规则下可以有限，如下不完的三劫会被给和局，不会 06/26 17:58
2F：→ ddavid:无限往下展开。 06/26 17:59
3F：→ ddavid:就算你很刻意的使用排满剩一眼→被吃掉，每次都把眼排在不 06/26 18:00
4F：→ ddavid:同的地方或排的顺序不同，但这个排法的可能性终究是有限的 06/26 18:01
5F：→ ddavid:，所以在同型反覆的规则下终究会撞到同型同手顺就是，也一 06/26 18:02
6F：→ ddavid:样没有无限展开......，虽然那会是很变态大的树就是（会比 06/26 18:02
7F：→ ddavid:(n^2)!还远大就是，可能大略是(2*(n^2)!)!这个等级XD 06/26 18:03
这样的树好像有回圈 如果又考虑同棋形下双方的提子数
则可以展开成没有回圈 但是单一棋形下有无限个分支
所以还是穷举不完所有的情况 刚刚吃饭的时候想到的
以前曾经想做一个穷举机器人 做了很久之後才发现这个蠢问题 :S
※ 编辑: Baseba11 来自: 140.114.202.44 (06/26 18:30)
8F：推 kohttp:同型重覆的判断,不用其中每一步顺序都一样 06/26 23:02
9F：→ kohttp:只要计算总盘面变化数再补上前一手如果是提劫的位置 06/26 23:03
10F：→ kohttp:此数字将小於3^(全盘点数) 因为要扣掉死子未提的盘面 06/26 23:06