第十章 计算机——未来的象棋之王
算法是一种巧妙的求值方法,可以让计算机无需求出每种可能棋势的值就能选择它所要走的棋步。然而令人惊奇的是,所选择的棋步正是计算机考虑了每一种续步后所要走的同一步棋。这怎么可能呢?
假设计算机首先在一定范围内探索称之为A的某一特定棋步的所有后续棋步。设想两方都走最佳的弈法,计算机给A定的极小极大值比方说为1。(在这种方案中,正值相当于计算机所具有的优势,而负值相当于计算机所处的劣势。优势值为1,表示比对手多一兵,其他条件都相同。)现在,计算机开始对另一个叫做B的可选棋步求值,B是特别愚蠢的一步棋,表示将后置于可以立即被对手的弱兵捉住的方格中。如果计算机现在分析对手的正常应着棋步——以兵捉后,并排除掉一种微小的可能性,即为了一次锐不可挡的进攻而英勇牺牲了后,那么,计算机将定这个棋势的数值为-9,它表示其对手已具有强大的优势。
现代的计算机国际象棋靠的是极小极大值法:所走的棋步应使对手的可能最大增益降至最小程度。假设计算机可选择的棋步为A和B。它看出了对手对A的最佳反应是走一步棋a(图中的数目表示按照计算机的观点所产生的棋势的优劣程度如何)。这时计算机又考虑棋步B,并看出了对手将应以d,从而能保证时B取得比对A更好的结果。这时计算机有足够理由选择A,而对手反应e或f的结果是什么都无关紧要。
计算机不需要考虑所有其他应着棋步的结果,其中也包括对手不能吃后,因为计算机已能识别对手的走棋路线是确保它自己对B步棋的应步能优于对A步棋的应步。因此,计算机根据自己的观点,知道走A步棋比走B步棋更为可取。
要有效地执行a-β算法,计算机必须按顺序考虑各种棋步:在上述例子中,它必须先检验A,再检验B,并且在分析B时,必须先检验捉后的棋步,再考虑其他的应步。审查各种棋步的顺序取决于各种不同的探试法或一般经验。
例如,捉子探试法指令程序对那些涉及捉子的各种棋步给予最优先考虑。(这样捉子成为一着好棋的机会将更多一些,特别是如果被捉的子未受到保护时。这种方法还能帮助计算机减轻负担,对机器大有稗益。而棋盘上少了一个子,计算机考虑的应着棋步也就相应减少。)
杀子探试法始终监视着对手的哪一步棋被杀或被驳倒(一种特殊的棋步)。当计算机仔细考虑了另一步棋时,首先要研究杀方的反应。现举一特殊例子。计算机发现它所考虑的捉对方车的一步已被对手弈出将军棋步所驳倒,在仔细考虑替代的棋步时,它将首先决定是否要走避免被将军的棋步。换句话说,杀子探试法可用来识别并监视这种威胁,这里所指的是能立即将军的致命威胁。另一次探试优先考虑那些能将军的棋步,从而应了一句古老的格言:“常将,就能将死。”简单地说,这时计算机的做法就有些更像人了。
在全方位搜索法中,要是采用渐进地深入考虑所有的续步,而不是每次一步地充分考虑这些续步,那么就能做到省时省事。从棋盘上的某种棋势着手,首先分析所有可能的续步,然后分析某一特定的棋步,根据目前所进行的搜索,就能看到最佳的一步棋。再从这步棋开始,对其余的所有续步进行有效的分析,一直到两着棋的深度,并且再次找到其中最佳的一步棋。这种过程叫做迭代深化法,它不断重复下去,直到达到所期望的深度时为止。
有一种表记录了计算机已经求出值的棋势、对这些棋势所给定的数值、以及迄今已搜索到的最佳一步棋,通过这个表就可以提高全方位搜索法的有效性。在全方位搜索法中,各种棋势都往往会不止一次地出现,只要程序设计好,查找所求的数值的时间自然比重新计算的时间少,因此,这种表在节省时间方面是很有用的。