一 从地球到月球
从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智能上，对于电脑超过
人脑，有人兴奋，有人担忧，但曾经几乎所有人都认为这会是真的。尤其当“深蓝”击
败卡斯帕罗夫之后，人们已经开始担忧，电脑超过人脑，会不会就发生在明天？
但这种担忧实在是来的太早了。
本世纪七八十年代,对人工智能学家们来说，就象是无忧无虑的童年。他们雄心勃勃，
甚至排出了电脑替代人脑的时间表。在表中，现在，就已经应该是电脑超过人脑的日子
了。现在，“深蓝”确实战胜了卡斯帕罗夫，但人工智能学家们的时间表早已被抛到了
脑后。有人甚至打了这样一个比喻来说明人工智能上所取得的成就：人们想登上月球，
他们造了一个梯子，用这个梯子爬上了一棵树，然后自豪地宣称：“现在，我们已向
月球前进了一大步！”
现在，电脑已经渗入到了我们生活的各个方面，在生产和生活中，我们已经有些难以
想象脱离电脑的状况了，如果说这些形形色色的电脑只不过是花里胡哨的各种梯子，
似乎实在是说不过去。
我们先看看梯子是怎么回事吧。
梯子的发明人是图灵博士。图灵在考虑可计算的机器的性质时，首先是设想一个人在
计算，他把这个人的计算行为抽象成了这样一台机器：有一条无穷长的纸带子，一个
有很多状态的机器在纸带上左右滑动，并且可以根据所读到的内容改变自己的状态或
者改写纸带的内容。这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论上都是
可以被图灵机模拟的。
请注意图灵机有一个重要的能力：改写纸带的能力。如果没有这个能力，那这台机器
叫做有穷自动机。它和图灵机间的计算能力差着三个档次呢。（注意：在一条无穷长
的纸带上读东西，在另一条纸带上写东西的机器也是有穷自动机）。
判断这些东西的计算能力用的是这些机器所能接受的语言的概念。这个语言虽然是抽
象的语言，但也和我们平时所说的语言差不多，你只要理解成这机器能听懂什么话也
就差不太多了。乔姆斯基把语言分成了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 级语言的机器听懂的。我们可以把国际象棋理解成一个上下
文无关语言。
回到围棋，当我们落下一子时，棋盘会变成什么样？如果周围全是敌子，有些敌子没了
气，那敌子全部拿走，如果周围有自己的子，敌子没被拿走，自己的子反而没
--
你背得越多，你忘得越多；你忘得越多，你记得越少；
你学得越少，你忘得越少；你忘得越少，你记得越多。
所以，呵呵。。。
三 迷宫之路
从理论上来说，围棋的每一步都会有一个或几个最佳选择。如果我们真的可以遍历围棋的
所有变化并加以比较的话，我们是可以找到这些最佳下法。只是这种遍历是实际上不可实
现的。
寻找围棋最佳下法的过程就象是在走一个庞大的迷宫，迷宫中有无数的分支岔路，有些通
向死路，有些通向幻象，还有一些路则仅仅是自己转圈。置身于这个庞大的迷宫中，当我
们知道凭一生的时间也只能走过这一迷宫的微不足道的一小部分时，我们自然会停下来，
看看这迷宫之路中有没有什么规律。
我们先对问题进行简化，抛开全局同型禁止再现，也不考虑三劫、四劫、长生劫等等情
况这样在走迷宫时不必判断是否会出现回路（就是绕了一圈又回来了），对于这种无回
路的迷宫，最简单的走法是死贴一边走（比如，一直贴左边或者一直贴右边），这就是
一种遍历搜索，术语叫深度优先遍历搜索（因为它每次都要走到头再转回来走下一条）。
按上章的计算，深度优先遍历搜索走完这个迷宫大概需要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问题还要复杂的多。
不过，解决一个问题，找不到最好的方法，退而求其次也不失为一种明智的选择。人们
对很郚P问题的态度就是：找不到最好的答案，比较好的答案也不错。“深蓝”会输给
卡斯帕罗夫一局，也说明“深蓝”找到的并非最佳下法，但它已经可以在总成绩上战胜
卡斯帕罗夫了。
在各种搜索算法中，有一个A*搜索算法，也叫做最佳搜索算法，它是对于问题的各种情
况设定一个估值函数，假设我们选择的是值最小的道路，在搜索迷宫的时候，A*算法根
据估值函数判断下一步应选择的道路，并不停地用走过的实际路线的价值加上下一点的
估值函数作为新的估值。当新的估值小于以前所做的另一条路线的估值的时候，改换到
另一路线中重新进行估值和搜索，这倒有点象人下棋时的判断：看看这样走行不行，看
到大概不行时，就换个办法再看看。
理论上，如果估值函数永远小于实际路线的价值，那么，A*算法总可以找到最优解。但
这样太困难。我们还可以有这样的想法：如果A*算法的估值函数可以做到差不离的话，
也许我们就可以找到一个比较好的走法。比如，如果A*算法能够把下一手的选择点降到
平均 6步，计算一路变化所需的步数降到平均20步，那么总的 计算量就变成了 6^20=
3.66*10^15，这就已经接近于计算机可接受的计算量了。
作者曾经设想过一个围棋AI模型：把所有的棋子以连在一起的一块为基本单位，而后再
根据棋子的形状，眼位情况，赋与它强度、影响力等属性，用力学模型来分析全局势力
范围，并据此选择下一手的大致位置。实际上这就是对A*算法估值函数的一种设想。
看起来，我们只要找到一个好的方法，把一个个围棋局面量化成适当的值，再根据这些
值进行A*搜索，就可以找到相当不错的走法。唯一的问题是：存在可行的量化方法吗？
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
计算机理论与工程 → 『 理论计算机科学 』 → 围棋与计算机
(订阅本版)
2006/5/11 0:42:00
顶端 
围棋与计算机(11032字) － wondermu，2006年5月11日
新浪微博
