计算机与围棋

围棋与计算机

本文是biggenie发表在中国围棋网棋人棋事的系列文章,版权归biggnie所有
作者为文章起名"胡说五道" :-), 其实文章非常精妙,故我将其改成上面的名字

一从地球到月球

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

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

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

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

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

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

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

判断这些东西的计算能力用的是这些机器所能接受的语言的概念。这个语言虽然是抽象的语言，但也和我们平时所说的语言差不多，你只要理解成这机器能听懂什么话也就差不太多了。乔姆斯基把语言分成了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型语言也接受不了围棋了。

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

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

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

三迷宫之路

从理论上来说，围棋的每一步都会有一个或几个最佳选择。如果我们真的可以遍历围棋的所有变化并加以比较的话，我们是可以找到这些最佳下法。只是这种遍历是实际上不可实现的。

寻找围棋最佳下法的过程就象是在走一个庞大的迷宫，迷宫中有无数的分支岔路，有些通向死路，有些通向幻象，还有一些路则仅仅是自己转圈。置身于这个庞大的迷宫中，当我们知道凭一生的时间也只能走过这一迷宫的微不足道的一小部分时，我们自然会停下来，看看这迷宫之路中有没有什么规律。

我们先对问题进行简化，抛开全局同型禁止再现，也不考虑三劫、四劫、长生劫等等情况。这样在走迷宫时不必判断是否会出现回路（就是绕了一圈又回来了），对于这种无回路的迷宫，最简单的走法是死贴一边走（比如，一直贴左边或者一直贴右边），这就是一种遍历搜索，术语叫深度优先遍历搜索（因为它每次都要走到头再转回来走下一条）。按上章的计算，深度优先遍历搜索走完这个迷宫大概需要10^(3^361)步。

所以，我们别无选择，只有换种办法来走迷宫。我们所选的办法又怎样才能达到我们的要求呢？

我们这里所谈论的迷宫的走法，也就是解决一个问题的算法，一般用是用复杂度的阶数来衡量算法复杂度好坏的。首先，一个问题有它自己的尺度。比如国际象棋是64格棋盘，我们可以把国际象棋问题的尺度定为64，围棋 361个交叉点，我们可以把围棋问题的尺度定为 361。如果你愿意把它们的尺度分别定为 8，19也可以，但考虑问题时显然不如64和 361来的自然。

解决一个问题的算法的复杂度是根据问题的尺度与计算步数的函数来定义的。设 n为问题的尺度，如果一个算法需要 n步，我们就说它的复杂度是 n，如果一个算法需要 2^n步(n个2连乘)，我们说它的复杂度是 2^n。对于两种算法来说，只要他们的复杂度函数的比值不大于一个常数，我们就称它们为同阶的。也就是说，一个需要步数为 1000n的算法与一个需要步数为 n的算法是同阶的。因为我的机器只要能把速度提高一千倍，第一个算法就能达到第二个算法原先的速度。但一个步数为 n^2的算法就比一个步数为 1000n的算法复杂度高，因为不论你的机器有多快，对于尺度很大的问题，总还是第一个算法复杂。

因此，我们就用 O(n)，o(n^2)，...，o(2^n)，... 来表示与步数为n，n^2，...，2^n，... 的算法同阶的算法的复杂程度。请注意这里的 2^n，一个 2^n步数的算法（其实是任何x^n(x>1)步数的算法）比任何一个多项式步数的算法（就是O(n),O(n^2)...这类算法）都来的复杂。比如说。一个算法的步数约为 2^n，第二个为n^10，当 n取64的时候（国际象棋尺度），前者需要1.84*10^19步，而后者需要1.15*10^18步，第一个比第二个要多花十多倍步数，如果问题尺度是 361（围棋尺度），后者需要3.76*10^25步，而则前者需要 4.69*10^108步，这次前者比后者复杂了一千亿亿亿亿亿亿亿亿亿亿倍.

如果说一个问题可以找到复杂度为多项式的算法，我们称它属于 P类问题，我们需要的就是复杂度为多项式的算法，也就是说，如果围棋是 P类问题，我们就认为它可解。而如果我们只能找到指数等级的算法 (O(2^n)..等等)，我们就认为它不可解。

而围棋的遍历需要的步数，是指数复杂度问题的排序问题，它比指数复杂度的问题还要复杂的多。

在人们试图用计算机解决的各种问题中，有一大类问题，包括货郎问题，背包问题等等，总计数百个之多，被人们称为NP问题。之所以说它们是一类是因为人们已经证明了只要其中一个问题可计算（就是有多项式算法），其他的问题就都可以计算，但现在，比起找这些问题的多项式算法，人们倒宁愿去证明它们不存在多项式算法。

围棋是NP问题吗？不知道，好象不是，但既然NP问题都有指数复杂度的解法，而围棋连指数复杂度的解法都找不到，看起来，围棋似乎比NP问题还要复杂的多。

不过，解决一个问题，找不到最好的方法，退而求其次也不失为一种明智的选择。人们对很多NP问题的态度就是：找不到最好的答案，比较好的答案也不错。“深蓝”会输给卡斯帕罗夫一局，也说明“深蓝”找到的并非最佳下法，但它已经可以在总成绩上战胜卡斯帕罗夫了。

在各种搜索算法中，有一个A*搜索算法，也叫做最佳搜索算法，它是对于问题的各种情况设定一个估值函数，假设我们选择的是值最小的道路，在搜索迷宫的时候，A*算法根据估值函数判断下一步应选择的道路，并不停地用走过的实际路线的价凵希绻乐岛涝缎∮谑导事废叩募壑担敲矗珹*算法总可以找到最优解。但这样太困难。我们还可以有这样的想法：如果A*算法的估值函数可以做到差不离的话，也许我们就可以找到一个比较好的走法。比如，如果A*算法能够把下一手的选择点降到平均 6步，计算一路变化所需的步数降到平均20步，那么总的计算量就变成了 6^20=3.66*10^15，这就已经接近于计算机可接受的计算量了。

作者曾经设想过一个围棋AI模型：把所有的棋子以连在一起的一块为基本单位，而后再根据棋子的形状，眼位情况，赋与它强度、影响力等属性，用力学模型来分析全局势力范围，并据此选择下一手的大致位置。实际上这就是对A*算法估值函数的一种设想。

看起来，我们只要找到一个好的方法，把一个个围棋局面量化成适当的值，再根据这些值进行A*搜索，就可以找到相当不错的走法。唯一的问题是：存在可行的量化方法吗？