Chess_Bridge 版 (精华区)

发信人: dad (andy), 信区: Chess_Bridge
标  题: 围棋与计算机一有穷与无穷
发信站: 哈工大紫丁香 (Wed Jul  7 15:46:30 1999), 转信

用天梯登上月球的想法，现代人也许会觉得荒谬，但在古人眼里，
未必如此。梯子可以上树、可以上房、可以上城，甚至可以上山，
为什么不能上天呢？

因为做梯子的原材料数量不够，强度不够，天梯也没有可搭的地方，
等等等等，但古人都不清楚，他们根本不知道地球和月球之间有多远。

国际象棋八八六十四见方的棋盘，围棋纵横361交叉点的棋枰，它
们的变化从理论上说是有限的，因此，理论上，这些问题都是图灵机
可解决的。但是，就在我们理论上严谨地一步步得出结论时，我们早
已不知不觉地越过了在实际计算意义上有穷与无穷的界限。

以围棋为例，围棋有多少种变化？比较常见的有两种估计方法，一是：
假设不会出现大家都被提光再从头再来的情况，那么，第一步有361
种选择，第二步有360种选择，以后的情况大致如此，我们就以361
为界，那么变化数是361!，约为10的768次方。另一种估计方法大
概是宋朝的沈括老先生首先使用的：棋盘上每个点有黑，白，空三种
状态，所以围棋变化数是3的361次方，约为10的172次方，用沈老
先生的说法，就是“连书‘万’字四十三”。这虽然也很大，但比起前
面的估计值来，小的实在是太多了。如果这种估计正确，那电脑下围
棋无疑轻松了许多。

不幸的是，沈老先生的估计方法是错误的。他只考虑了这种种状态，
却没有考虑这些状态间的相互关系。就比如数学中的图，沈老先生
只考虑了顶点的总数，却忘了把连接顶点的边算进去了。

如果我们不考虑边，就考虑这“连书‘万’字四十三”的状态，如果
我可以对于每个状态都精确地算出价值的话，那么电脑只需要查价值
表就可以确定该怎样下棋了，这样，电脑需要储存的变化数也就是“
连书‘万’字四十三”，但问题是，这些价值是怎么算出来的？总不会
看到一个状态之后就能猜出它的价值吧。因此，假设有一个电脑围棋
机器，虽然在执行的时候他可以只考虑不同状态的价值，但为了造这
台机器，我们还得把所有这些状态的关系都考虑进去。

按照第一种估计方法得到的10的768次方又是个什么概念呢？宇宙中
所有基本粒子的总数，据估计为10的80次方。其实，连第一种估计
方法都是错误的。围棋真正的变化数，连10的(3的361次方)次方都
挡不住，大学学历的人都清楚，一旦出现指数天梯，那这个数字有多
大已经是不可想象的了。

这一点并不能说明围棋不是图灵机实际可解的。不过至少告诉我们，
遍历的方法是不可行的。所以，我们暂时把围棋的状态当作无穷来看。
在这里，我们用准无穷来称呼到达实际不可计算程度的状态数。

人们在谈到围棋与国际象棋的比较时，总说围棋的变化远多于国际
象棋。但如果把这作为电脑下围棋远难于下国际象棋的原因是不充
分的，并不是状态越多的东西越复杂，况且国际象棋的变化同样也
是天文数字。

但是，如果把国际象棋的棋盘放大，棋子增多，使它的变化从绝对
数值上来说接近甚至超过围棋，国际象棋还是只能给人以国际象棋
的感觉而不是围棋的感觉。因为，它们的“语法”有着本质的不同。

现在，我们考虑这样一个问题：国际象棋和围棋走子后棋局状态的
变化，分别需要判断几个位置上的状况？

国际象棋当我落下一子时，只要考虑落子点的状态就可以了，如果
这里有我自己的子，这步落子无效，如果这里有敌人的子，敌子被
我吃掉，如果这里空白，那么仅仅是棋子的移位。象王车易位、吃
过路兵等情况，我们可以把它看作可以遍历的特例而暂时不予考虑。

让我们回想一下乔姆斯基四级语言中的2级：上下文无关语言。当
排除了特殊情况之后，我们可以认为，既然国际象棋棋局某格的状
态变化与周围无关，那么，它应当是可以被能听懂（专业上叫接受）
2级语言的机器听懂的。我们可以把国际象棋理解成一个上下文无
关语言。

回到围棋，当我们落下一子时，棋盘会变成什么样？听起来好象也
很简单，但棋盘的变化是需要看周围的情况而决定的。如果只看落
子点的状态，那我们什么结论也得不到。也就是说，围棋不能用上
下文无关语言来等价，至少也得用上下文有关语言，就是会数很多
数的1级语言.

在考虑围棋变化数的时候，劫可是不能不提。有人说“劫乃围棋精
华”，可对于1型语言来说，劫实在是要命的东西。1型语言的基本
要求是它的语言产生式左边不长于右边，但对于劫来说，并非如此。
有了劫，就意味着1型语言也接受不了围棋了。

更要命的还在后面。象三劫循环、四劫循环、长生劫等等，在现在
的围棋规则中，都简单地判为“无胜负”。其实，如果用“全局同型
禁止再现”，都可以从理论上解决，并且也不如人们想象中的那么复
杂（以后我可能会另写文章介绍多劫循环的规律）。全局同型禁止再
现也很圆满地解释了劫。但是，全局同型禁止再现对于用图灵机模
拟围棋，可以说是致命的一击。因为，这意味着这台图灵机得把以
前的所有状态都存储起来，而具有无限种状态数的机器不是图灵机。

国际象棋一盘棋结束，有三种状态：将死对方，被对方将死，和棋。
和棋除了双方自愿外，还有逼和、三次同型和，以及六十步子数不
变和等等。这意味着国际象棋在这些都是可以直接检验的，其步数
不会超过32*60步。可围棋就不一样了，“全局同型禁止再现”，这
意味着理论上围棋可以下3的361次方数量级这么多手！这是准无
穷了。即使没有这一规则，围棋可走的步数依然是准无穷。

而围棋的胜负又非要看整个棋盘的状态才能决定，也就是说，就算
没有“全局同型禁止再现”这一规则，我们可以用图灵机来接受围
棋，但判断每一步的好坏必须追溯到这一局棋的终点，这意味着这
台图灵机要判断它不同情况下停机时的状态！而这是图灵机所无能
为力的。这里的状态是理论状态，它和我们实际计算时会选择的状
态还不一样，围棋实际对局也很少超过361手，但这已经启示我们，
既然国际象棋与围棋在复杂程度上差了3个档次，我们能够解决国
际象棋问题的算法能用来对付围棋吗？

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: www-post@bbs.hit.edu]