求围棋程序的算法思想

一 从地球到月球

从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智能上，对于电脑超过人脑，有人兴奋，有人担忧，但曾经几乎所有人都认为这会是真的。尤其当“深蓝”击败卡斯帕罗夫之后，人们已经开始担忧，电脑超过人脑，会不会就发生在明天？

但这种担忧实在是来的太早了。

本世纪七八十年代,对人工智能学家们来说，就象是无忧无虑的童年。他们雄心勃勃，甚至排出了电脑替代人脑的时间表。在表中，现在，就已经应该是电脑超过人脑的日子了。现在，“深蓝”确实战胜了卡斯帕罗夫，但人工智能学家们的时间表早已被抛到了脑后。有人甚 至打了这样一个比喻来说明人工智能上所取得的成就：人们想登上月球，他们造了一个梯子，用这个梯子爬上了一棵树，然后自豪地宣称：“现在，我们已向月球前进了一大步！”

现在，电脑已经渗入到了我们生活的各个方面，在生产和生活中，我们已经有些难以想象脱离电脑的状况了，如果说这些形形色色的电脑只不过是花里胡哨的各种梯子，似乎实在是说不过去。

我们先看看梯子是怎么回事吧。

梯子的发明人是图灵博士。图灵在考虑可计算的机器的性质时，首先是设想一个人在计算，他把这个人的计算行为抽象成了这样一台机器：有一条无穷长的纸带子，一个有很多状态的机器在纸带上左右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带的内容。 这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论上都是可以被图灵机模拟的。

请注意图灵机有一个重要的能力：改写纸带的能力。如果没有这个能力，那这台机器叫做有穷自动机。它和图灵机间的计算能力差着三个档次呢。（注意：在一条无穷长的纸带上读东西，在另一条纸带上写东西的机器也是有穷自动机）。

判断这些东西的计算能力用的是这些机器所能接受的语言的概念。这个语言虽然是抽象的语言，但也和我们平时所说的语言差不多，你只要理解成这机器能听懂什么话也就差不太多了。乔姆斯基把语言分成了0， 1，2 ， 3四个等级，0 级能力最强，3 级最差。这四个等级之间有着难以逾越的鸿沟。

这里的 3级语言也叫做正规语言，就是有穷自动机能听懂的， 2级语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就可以听懂了。1 级语言就是上下文相关的了，也就是说机器还得揣摩这话前后的意思。零级语言就是图灵机可以接受的语言了。

我们用数数的本事就可以体会1，2，3 型语言的能力差别了。

对于数数，有这么一个笑话：两个贵族比赛，看谁说出的数更大，第一个人绞尽脑汁，冥思苦想十几分钟后说：3， 轮到第二个人，他想了很久很久，最后说：你赢了。

数到 3 的本事哪型语言都会，我这里说的数数本事是从一数起，只要不老死，数多少个都行。3 型语言，也就是正规语言，是不会数数的。 2 型语言（上下文无关语言）会数数，但同时数两个数就不会了。1 型语言就是数多少个数都行的了。而 0型语言的能力又比 1型语言强的多。也就是说，图灵机看上去简单，实际上是还是很牛的。

但是图灵自己就发现了图灵机也有不照的时候了，这就是图灵机的停机问题。我们可以这样说明图灵机的停机问题：假设当图灵机听懂了一句话，它就不再琢磨这句话了，现在我给图灵机一句话，问它“你听的懂吗？”如果它听的懂，它会回答“是”，但如果它听不懂，很 可能它永远也不会知道自己听不懂。

--------------------------------------------------------------------------------

二 有穷与无穷

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

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

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

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

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

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

按照第一种估计方法得到的10的 768次方又是个什么概念呢？宇宙中所有基本粒子的总数，据估计，为10的80次方。如果没有一些简化计算的措施，这比宇宙中粒子总数还要大数不清倍的数字对我们来说，又和无穷有什么区别？

其实，连第一种估计方法都是错误的。围棋真正的变化数，连10的(3的361次方)次方都挡不住，大学学历的人都清楚，一旦出现指数天梯，那这个数字有多大已经是不可想象的了。

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

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

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

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

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

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

回到围棋，当我们落下一子时，棋盘会变成什么样？如果周围全是敌子，有些敌子没了气，那敌子全部拿走，如果周围有自己的子，敌子没被拿走，自己的子反而没了气，那就是自填死。

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

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

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