求围棋程序的算法思想

1、求围棋程序的算法思想一 从地球到月球从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智能上， 对于电脑超过人脑， 有 人兴奋，有人担忧，但曾经几乎所有人都认为这会是真的。尤其当 “深蓝 ”击败卡斯帕罗夫之后， 人们已经开始担忧，电脑超过人脑，会不会就发生在明天？但这种担忧实在是来的太早了。本世纪七八十年代 ,对人工智能学家们来说，就象是无忧无虑的童年。他们雄心勃勃，甚至排出 了电脑替代人脑的时间表。在表中，现在，就已经应该是电脑超过人脑的日子了。现在， “深蓝 ” 确实战胜了卡斯帕罗夫，但人工智能学家们的时间表早已被抛到了脑后。有人甚 至打了这样一 个比喻来说明人工智能上所取得的成就：

2、 人们想登上月球， 他们造了一个梯子， 用这个梯子爬上 了一棵树，然后自豪地宣称： “现在，我们已向月球前进了一大步！ ”现在， 电脑已经渗入到了我们生活的各个方面， 在生产和生活中， 我们已经有些难以想象脱离电 脑的状况了，如果说这些形形色色的电脑只不过是花里胡哨的各种梯子，似乎实在是说不过去。我们先看看梯子是怎么回事吧。梯子的发明人是图灵博士。 图灵在考虑可计算的机器的性质时， 首先是设想一个人在计算， 他把 这个人的计算行为抽象成了这样一台机器： 有一条无穷长的纸带子， 一个有很多状态的机器在纸 带上左右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带的内容。 这就是大名 鼎鼎的

3、图灵机了。当前的所有计算机，在理论上都是可以被图灵机模拟的。请注意图灵机有一个重要的能力： 改写纸带的能力。 如果没有这个能力， 那这台机器叫做有穷自 动机。它和图灵机间的计算能力差着三个档次呢。 （注意：在一条无穷长的纸带上读东西，在另 一条纸带上写东西的机器也是有穷自动机） 。判断这些东西的计算能力用的是这些机器所能接受的语言的概念。这个语言虽然是抽象的语言， 但也和我们平时所说的语言差不多， 你只要理解成这机器能听懂什么话也就差不太多了。 乔姆斯 基把语言分成了 0， 1，2 ， 3 四个等级， 0 级能力最强， 3 级最差。这四个等级之间有着难以 逾越的鸿沟。这里的 3 级语言也叫做正

4、规语言，就是有穷自动机能听懂的，2级语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就可以听懂了。 1 级语言就是上下文相关的了， 也就是说机 器还得揣摩这话前后的意思。零级语言就是图灵机可以接受的语言了。我们用数数的本事就可以体会1， 2， 3 型语言的能力差别了。对于数数，有这么一个笑话：两个贵族比赛，看谁说出的数更大，第一个人绞尽脑汁，冥思苦想 十几分钟后说： 3， 轮到第二个人，他想了很久很久，最后说：你赢了。数到 3 的本事哪型语言都会，我这里说的数数本事是从一数起， 只要不老死， 数多少个都行。 3 型语言，也就是正规语言，是不会数数的。 2 型语言（上下文无关语言）会数数

5、，但同时数两 个数就不会了。 1 型语言就是数多少个数都行的了。而 0 型语言的能力又比 1 型语言强的多。也就是说，图灵机看上去简单，实际上是还是很牛的。但是图灵自己就发现了图灵机也有不照的时候了， 图灵机的停机问题： 假设当图灵机听懂了一句话， 话，问它 “你听的懂吗？ ”如果它听的懂，它会回答 会知道自己听不懂。这就是图灵机的停机问题。 我们可以这样说明 它就不再琢磨这句话了， 现在我给图灵机一句 “是 ”，但如果它听不懂，很 可能它永远也不有穷与无穷 用天梯登上月球的想法，现代人也许会觉得荒谬，但在古人眼里，未必如此。梯子可以上树、可 以上房、可以上城，甚至可以上山，为什么不能上天呢？

6、因为做梯子的原材料数量不够， 强度不够， 天梯也没有可搭的地方， 等等等等， 但古人都不清楚， 他们根本不知道地球和月球之间有多远。国际象棋八八六十四见方的棋盘，围棋纵横 361 交叉点的棋枰，它们的变化从理论上说是有限 的，因此，理论上，这些问题都是图灵机可解决的。但是，就在我们理论上严谨地一步步得出结 论时，我们早已不知不觉地越过了在实际计算意义上有穷与无穷的界限。以围棋为例， 围棋有多少种变化？比较常见的有两种估计方法，一是： 假设不会出现大家都被提光再从头再来的情况，那么，第一步有 361 种选择，第二步有 360 种选择，以后的情况大致如 此，我们就以 361 为界，那么变化数是 3

7、61! ，约为 10 的 768 次方。另一种估计方法大概是宋 朝的沈括老先生首先使用的： 棋盘上每个点有黑， 白，空三种状态， 所以围棋变化数是 3 的 361 次方，约为 10 的 172 次方，用沈老先生的说法，就是 “连书 万字四十三 ”。这虽然也很大，但 比起前面的估计值来，小的实在是太多了。如果这种估计正确，那电脑下围棋无疑轻松了许多。不幸的是， 沈老先生的估计方法是错误的。 他只考虑了这种种状态， 却没有考虑这些状态间的相 互关系。就比如数学中的图，沈老先生只考虑了顶点的总数，却忘了把连接顶点的边算进去了。如果我们不考虑边，就考虑这 “连书 万字四十三 ”的状态，如果我可以对于每

8、个状态都精确地算 出价值的话， 那么电脑只需要查价值表就可以确定该怎样下棋了， 这样， 电脑需要储存的变化数 也就是 “连书 万字四十三 ”，但问题是，这些价值是怎么算出来的？总不 会看到一个状态之后 就能猜出它的价值吧。 因此， 假设有一个电脑围棋机器， 虽然在执行的时候他可以只考虑不同状 态的价值，但为了造这台机器，我们还得把所有这些状态的关系都考虑进去。按照第一种估计方法得到的 10 的 768 次方又是个什么概念呢？宇宙中所有基本粒子的总数， 据 估计，为 10的80 次方。如果没有一些简化计算的措施， 这比宇宙中粒子总数还要大数不清倍的 数字对我们来说，又和无穷有什么区别？其实，连第

9、一种估计方法都是错误的。 围棋真正的变化数， 连 10的（3的 361次方）次方都挡不住， 大学学历的人都清楚，一旦出现指数天梯，那这个数字有多大已经是不可想象的了。这一点并不能说明围棋不是图灵机实际可解的。 不过至少告诉我们， 遍历的方法是不可行的。 所 以，我们暂时把围棋的状态当作无穷来看。 在这里， 我们用准无穷来称呼到达实际不可计算程度 的状态数。人们在谈到围棋与国际象棋的比较时， 总说围棋的变化远多于国际象棋。 但如果把这作为电脑下 围棋远难于下国际象棋的原因是不充分的， 并不是状态越多的东西越复杂， 况且国际象棋的变化 同样也是天文数字。但是，如果把国际象棋的棋盘放大， 棋子增多，

10、 使它的变化从绝对数值上来说接近甚至超过围棋， 国际象棋还是只能给人以国际象棋的感觉而不是围棋的感觉。 因为，它们的 “语法 ”有着本质的不 同。现在， 我们考虑这样一个问题： 国际象棋和围棋走子后棋局状态的变化， 分别需要判断几个位置 上的状况？国际象棋当我落下一子时， 只要考虑落子点的状态就可以了， 如果这里有我自己的子， 这步落子 无效，如果这里有敌人的子，敌子被我吃掉，如果这里空白，那么仅仅是棋子的移位。象王车易 位、吃过路兵等情况，我们可以把它看作可以遍历的特例而暂时不予考虑。让我们回想一下乔姆斯基四级语言中的 2 级：上下文无关语言。当排除了特殊情况之后，我们 可以认为，既然国际象

11、棋棋局某格的状态变化与周围无关， 那么， 它应当是可以被能听懂（专业 上叫接受） 2 级语言的机器听懂的。我们可以把国际象棋理解成一个上下文无关语言。回到围棋，当我们落下一子时，棋盘会变成什么样？如果周围全是敌子， 有些敌子没了气， 那敌 子全部拿走，如果周围有自己的子，敌子没被拿走，自己的子反而没了气，那就是自填死。听起来好象也很简单， 但棋盘的变化是需要看周围的情况而决定的。 如果只看落子点的状态， 那 我们什么结论也得不到。 也就是说， 围棋不能用上下文无关语言来等价， 至少也得用上下文有关 语言，就是会数很多数的 1 级语言 .在考虑围棋变化数的时候，劫可是不能不提。有人说 “劫乃围棋

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

13、器不是图灵机。国际象棋一盘棋结束，有三种状态：将死对方，被对方将死，和棋。和棋除了双方自愿外，还有 逼和、三次同型和， 以及六十步子数不变和等等。 这意味着国际象棋在这些都是可以直接检验的， 其步数不会超过 32*60 步。可围棋就不一样了， “全局同型禁止再现 ”，这意味着理论上围棋可 以下 3 的 361 次方数量级这么多手！这是准无穷了。即使没有这一规则，围棋可走的步数依然 是准无穷。而围棋的胜负又非要看整个棋盘的状态才能决定， 也就是说， 就算没有 “全局同型禁止再现 ”这一 规则， 我们可以用图灵机来接受围棋， 但判断每一步的好坏必须追溯到这一局棋的终点， 这意味 着这台图灵机要判断

14、它不同情况下停机时的状态！而这是图灵机所无能为力的。 这里的状态是 理论状态，它和我们实际计算时会选择的状态还不一样，围棋实际对局也很少超过 361 手，但 这已经启示我们，既然国际象棋与围棋在复杂程度上差了 3 个档次，我们能够解决国际象棋问 题的 算法 能用来对付围棋吗？三 迷宫之路 从理论上来说， 围棋的每一步都会有一个或几个最佳选择。 如果我们真的可以遍历围棋的所有变 化并加以比较的话，我们是可以找到这些最佳下法。只是这种遍历是实际上不可实现的。寻找围棋最佳下法的过程就象是在走一个庞大的迷宫， 迷宫中有无数的分支岔路， 有些通向死路， 有些通向幻象， 还有一些路则仅仅是自己转圈。 置身

15、于这个庞大的迷宫中， 当我们知道凭一生的 时间也只能走过这一迷宫的微不足道的一小部分时，我们自然会停下来，看看这 迷宫之路中有 没有什么规律。，对于这种无回路的迷宫，最简，这就是一种遍历搜 索， 术语叫深。按上章的计算，深度优先遍历搜我们先对问题进行简化，抛开全局同型禁止再现，也不考虑三劫、四劫、长生劫等等情况。这样 在走迷宫时不必判断是否会出现回路（就是绕了一圈又回来了）单的走法是死贴一边走（比如，一直贴左边或者一直贴右边）度优先遍历搜索（因为它每次都要走到头再转回来走下一条） 索走完这个迷宫大概需要 10（3361） 步 所以， 我们别无选择， 只有换种办法来走迷宫。 我们所选的办法又怎样

16、才能达到我们的要求呢？我们这里所谈论的迷宫的走法， 也就是解决一个问题的算法， 一般用是用复杂度的阶数来衡量算 法复杂度好坏的。首先，一个问题有它自己的尺度。比如国际象棋是 64 格棋盘，我们可以把国 际象棋问题的尺度定为 64 ，围棋 361 个交叉点，我们可以把围棋问题的尺度定为361。如果你愿意把它们的尺度分别定为8，19也可以，但考虑问题时显然不如64和 361 来的自然。解决一个问题的算法的复杂度是根据问题的尺度与计算步数的函数来定义的。设 n 为问题的尺 度，如果一个算法需要 n步，我们就说它的复杂度是 n，如果一个算法需要 2n步（n个 2连乘）， 我们说它的复杂度是 2n。对于

17、两种算法来说，只要他们的复杂度函数的比值不大于一个常数， 我们就称它们为同阶的。也就是说，一个需要步数为 1000n 的算法与一个需要步数为n 的算法是同阶的。 因为我的机器只要能把速度提高一千倍，第一个算法就能达到第二个算法原先的速度。但一个步数为 n2 的算法就比一个步数为 1000n 的算法复杂度高，因为不论你的机器有多快， 对于尺度很大的问题，总还是第一个算法复杂。因此，我们就用 O(n) ， o(n2) ， .， o(2n) ， . 来表示与步数为 n， n2， . ， 2n ， . 的算法同 阶的算法的复杂程度。请注意这里的2n ，一个 2n 步数的算法(其实是任何 xn(x1)

18、步数的算法)比任何一个多项式步数的算法(就是O(n),O(n2). 这类算法)都来的复杂。比如说。一个算法的步数约为 2n，第二个为 n10 ，当 n取64的时候(国际象棋尺度) ，前者需要 1.84*1019 步，而后者需要 1.15*1018 步，第一个比第二个要多花十多倍步数，如果问题尺度是361(围棋尺度)，后者需要 3.76*1025 步，而则前者需要 4.69*10108 步，这次前者比后者复杂了一千 亿亿亿亿亿亿亿亿亿亿倍 .如果说一个问题可以找到复杂度为多项式的算法，我们称它属于 P 类问题，我们需要的就是复 杂度为多项式的算法，也就是说，如果围棋是 P 类问题，我们就认为它可解。而如果我们只能 找到指数等级的算法 (O(2n). 等等 )，我们就认为它不可解。而围棋的遍历需要的步数， 是指数复杂度问题的排序问题， 它比指数复杂度的问题还要复杂的多。在人们试图用计算机解决的各种问题中，有一大类问题，包括货郎问题， 背包问题等等，总计数 百个之多，被人们称为 NP 问题。之所以说