Chess_Bridge 版 (精华区)

发信人: dad (andy), 信区: Chess_Bridge
标  题: 围棋与计算机一迷宫之路
发信站: 哈工大紫丁香 (Wed Jul  7 15:48:18 1999), 转信

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

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

我们先对问题进行简化，抛开全局同型禁止再现，也不考虑三劫、
四劫、长生劫等等情况。这样在走迷宫时不必判断是否会出现回路
（就是绕了一圈又回来了），对于这种无回路的迷宫，最简单的走法
是死贴一边走（比如，一直贴左边或者一直贴右边），这就是一种遍
历搜索，术语叫深度优先遍历搜索（因为它每次都要走到头再转回来
走下一条）。按上章的计算，深度优先遍历搜索走完这个迷宫大概需
要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*搜索，就可以找到相当不错的走法。
唯一的问题是：存在可行的量化方法吗？

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: www-post@bbs.hit.edu]