|
三 迷宫之路
从理论上来说,围棋的每一步都会有一个或几个最佳选择,如果我们真的可以遍历围棋的所有变化并加以比较的话,我们是可以找到这些最佳下法,只是这种遍历是实际上不可实现的.
寻找围棋最佳下法的过程就象是在走一个庞大的迷宫,迷宫中有无数的分支岔路,有些通向死路,有些通向幻象,还有一些路则仅仅是自己转圈.置身于这个庞大的迷宫中,当我们知道凭一生的时间也只能走过这一迷宫的微不足道的一小部分时,我们自然会停下来,看看这迷宫之路中有没有什么规律.
我们先对问题进行简化,抛开全局同型禁止再现,也不考虑把三劫,四劫,长生劫等等情况.这样在走迷宫时不必判断是否会出现回路(就是绕了一圈又回来了),对于这种无回路的迷宫,最简单的走法是死贴一边走(比如,一直贴左边或者一直贴右边),这就是一种遍历搜索,术语叫深度优先遍历搜索(因为它每次都要走到头再转回来走下一条).
按上章的计算,深度优先遍历搜索走完这个迷宫大概需要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*算法的估值函数可以做到差不离的话,也许我们就可以找到一个比较好的走法.比如,如果A*算法能够把下一手的选择点降到平均6步,计算一路变化所需的步数降到平均20步,那么总的计算量就变成了6^20=3.66*10^15,这就已经接近于计算机可接受的计算量了.
作者曾经设想过一个围棋AI模型:把所有的棋子以连在一起的一块为基本单位,而后再根据棋子的形状,眼位情况,赋与它强度,影响力等属性,用力学模型来分析全局势力范围,并据此选择下一手的大致位置.实际上这就是对A*算法估值函数的一种设想.
看起来,我们只要找到一个好的方法,把一个个围棋局面量化成适当的值,再根据这些值进行A*搜索,就可以找到相当不错的走法.
唯一的问题是: 存在可行的量化方法吗?
|
