国际象棋程序设计(六)：局面评估函数

　

François Dominic Laramée/文

　

　　已经六个月了，我知道你们有人觉得我不会闭嘴，但是你们错了，这是我的国际象棋程序设计连载的最后一篇。还有，我的Java象棋程序(看上去很烂)已经做好了，和这篇文章一起上传给了GameDev网站，这个程序还是可以验证这些连载内容的。

　　这个月的话题——局面评估函数——确实很特别，搜索技术大同小异，着法产生可以只根据规则来处理，而局面的评估则需要很深入彻底的分析。可以想象，如果我们不知道某个局面会导致哪方获胜，那么评价这个局面的相对强弱将是不可能的。因此，很多要讨论概念对于其他游戏来说就不是这么回事了，有的则根本不能用。对于你自己的游戏，考虑用什么样的评估方法，这是你作为程序员应该知道的。【译注：对于中国象棋要特别注意，很多概念不能从国际象棋照般，我写过《中国象棋和国际象棋比较研究》一文，详细阐述过这个问题。】

　　抓紧时间，让我们来看一些局面评价的尺度，并且需要了解它们有什么作用。

　

子力平衡

　

　　简单地说，子力平衡(Material Balance)就是指双方各有哪些棋子。根据象棋文献，后的价值是900分，车500，象325，马300，兵100，王是无价的。计算子力平衡是非常简单的，每方的子力价值就是：

　

MB = Sum (Np x Vp)

　

　　这里Np是棋盘上这种类型的子的数目，Vp是子的价值。如果你在棋盘上的子力价值比对手多，那么你的形势好。【说句提外话，外国人把“吃”说成“抓获”(Capture)，意思是棋子并非消失了，而是暂时退出战场了，所以说子力价值时一定要强调“棋盘上”。】

　　看上去非常简单是不是？但是这和象棋的局面评价还差很大距离呢。CHESS 4.5的作者估计了很多位置上的因素，例如机动性和安全性差不多接近1.5个兵。实际上，用不着考虑别的，这就足够可以下出好棋了。【注意，在把“兵值”这个概念运用到中国象棋的时候，最好也把车设成500，这时机动性和安全性的因素就可以参考国际象棋，也不超过150分。具体的子力价值可参考《中国象棋和国际象棋比较研究(二)——子力价值》一文。】

　　的确，有些情况下为了通过子力交换让局面得到进展，你必须牺牲某些棋子(甚至是后)。然而最好是通过搜索来发现，例如弃后可以导致3步杀，你的搜索函数不需要额外的代码就会找到杀棋(前提是它看得足够深远)。如果你硬是要在评价函数里写特别的代码，来确定是否应该弃子，这种事情将是噩梦。

　　很少有程序会用像我开始所说的那个评价函数。由于计算过于简单，人们会在上面增加点东西，都是这么做的。举一个众所周知的例子，当你子力上处于领先时，交换相等的子力是有利的。交换一个兵是不错的选择，因为它为你的车开放棋盘，但是你必须在棋盘上保存一些兵直到残局，以构筑防御屏障或者升变成后。最后，如果开局库里走出弃子的开局，你不用为程序担心，因此你要把“藐视因子”(Contempt Factor)加到子力平衡的评价中。例如当子力落后150分甚至更多时，你仍然让程序觉得是领先的。

　　要注意，子力平衡在象棋和西洋棋里具有很高的地位，但是在黑白棋里却是欺骗性的。的确，棋局最后你必须控制更多的格子才能赢，但是你最好在中局阶段控制子的个数。在其他游戏像五子棋【Go-Moku确实应该是五子棋，我想不出还有什么不吃子的黑白棋类了】及其变种N子棋(Connect-N)【具体怎么下我也不知道】，子力平衡是不会变化的，因为始终没有被吃的子。

　

机动性和对棋盘的控制

　

　　将死的特征之一是没有合理的着法。直觉上，好像选择余地越大约好，比如选手在30种着法内找出一步好棋，这种可能总要比限定在3步内高。

　　在象棋中，机动性是很好评估的 计算同一局面下每方的合理着法，你已经能做到了【还要复习一下《着法的产生》吗？】。然而这个数字仅仅占一小部分。为什么呢？就因为很多着法是漫无目的的。例如你每次让车向后退一格，着法是合理的，但不产生作用。另外，不惜代价试图限制对手的机动性，会让程序进行一系列漫无目的的将军，同时摧毁自己的防线。由于解除将军通常只有3到4种合理着法，所以基于机动性的程序会走出劣着去将军对方，过会儿就会发现什么事也没干成，并且自己的兵力也成一盘散沙了。【我认为这种结果的根源在于没有把将军着法考虑进“静态搜索”中，如果考虑进去了，那么将军的时候不做局面评价，根本不存在对手机动性很低的假象。】

　　但是，有些明智的机动性评估方法，会起点作用。我的程序就“坏象”给予罚分，即象的行动路线被一系列同色格的兵阻挡的情况，当马太靠近棋盘边缘时也同样处理。另一个例子是车，在开放或半开放线(即没有兵或只有一个兵的纵线)上价值更高。

　　和机动性有密切联系的是棋盘的控制能力。在象棋中，如果一方对某个格子产生攻击的棋子数量超过对方，那么这一方就控制了这个格子。走到受控制的格子通常是安全的，走到被对方控制的格子则是危险的。(有一些例外，把后走到被敌方兵攻击的格子里，不管你有多少子可以吃他的兵，这无论如何不是好主意。还有，你故意把子送到对方嘴里，但是对方有更重要的格子需要保护。)在象棋中，控制中心是开局的基本目标。但是，控制能力在某种程度上是很难计算的，它需要在任何时候都更新数据库，来记录棋盘上所有被攻击的格子。很多程序都这么做，但我的没有。

　　机动性对于象棋程序来说并不是非常重要的，但在黑白棋里却非常重要(在残局中有很少子可走的一方会陷入很深的困境)。而对围棋而言，对棋盘的控制则是胜利的标致。

　

局势发展

　

　　有个教条，下象棋时轻子(象和马)要尽早投入战斗，王要尽早易位，车和后尽量少动，直到关键时刻作出决定性的攻击。这是有很多原因的，马和象(还有兵)能控制中心，来支持后的火力，把它们调动出去能为底线疏通车的路线。随着棋局的进行，车就可以跑到第七行(即开始对对方的兵动手)，形成巨大的破坏力。

　　我的程序用了一些因子来衡量局势的发展。首先，任何王和后前没有动过的兵都要扣分，阻挡车的马和象也要扣分，这样可以让后在其他子力出动后才开始动，如果对手还有后，那么王易位到安全位置时则给予很大的加分(有易位权但是没有易位的也给予少量加分)。

　　你可以看到，局势发展的因素在开局阶段很重要，但是马上将失去意义。在大约10回合以后，要衡量的因素基本上都发生过了【即能加分的都加了，要扣分的都扣了】。

　　注意，在西洋棋之类的游戏中，倾向于局势发展可能很不好。事实上，先走的一方要空出后面一行的空位，这就已经吃亏了，而在这些地方避免局势发展，通常是不错的选择。

　

兵形

　

　　象棋大师门常说，兵是象棋的灵魂。因此新手很难体会的是，强手在对局时会因为一个兵的损失而早早认输。

　　象棋书籍中提到很多兵的类型，有些是有利的，有些是有害的。我的程序考虑了以下几点。

　　1. 叠兵或三叠兵，一方两个或多个兵在同一列上是很坏的，因为它们的移动相互阻碍了；

　　2. 对兵，双方两个兵“头碰头”互相阻挡去路，会造成很大的障碍；

　　3. 通路兵，当兵进展到不会有对方兵攻击或阻碍时【即同一列和相邻列里都不能有对方的兵】，就会变得非常强大，因为它们更容易到达底线实现升变；

　　4. 孤兵，两边都没有同伴兵保护的兵，最容易受到攻击，最需要寻求保护；

　　5. 满兵，棋盘上有太多的兵会影响机动性，为车开放一条纵线才是好主意。

　　最后兵形上要注意的是：后面跟了车的通路兵是非常危险的，因为任何吃掉它的子都会成为车的盘中餐。如果有一个车在通路兵的后面(同一列)，那么我的程序给予极高的加分。

　

王的安全和取向

　

　　我们很早就谈到过王的安全了，在开局和中局里，保护王是最重要的，易位是最好的办法。

　　但是在残局里，王身边的很多子都没了，他转眼间变成了攻击性子力！把它留在兵阵的后面简直是浪费资源。

　　“取向”(Tropism)在这里衡量的是一个子攻击对方王的难易程度，通常用距离来衡量。取向的计算规则跟兵种有关，不过通用的规则是，你越靠近对方的王，你对他的压力就越大。

　

确定权重

　

　　现在我们确定了有那些因素是需要衡量的，但是我们怎么决定它们的权重呢？

　　这是个非常有价值的问题，可以花几年时间(也确实有人在做)用线性组合的办法来调整评估函数，有时把机动性设得多一些，有时更强调安全性，等等。我当然希望有一个绝对的答案，可惜没有，因为再好的评价函数都会碰到麻烦和失误。如果你的程序足够强，那很好。如果不是，那么试试别的方案，让它和你原来的程序下，如果能赢下大多数，那么新的方案就是一个进步。

　　有三种方法可以试试：

　　1. 通过优化评估函数取得的成绩，要达到加深一层搜索所达到的同样效果，这是非常困难的。如果你很疑惑，那么宁可把评估函数设得简单些，把更多的处理器资源留给Alpha-Beta搜索。【有关资料表明，加深一层搜索大约可以使棋力提高200分(ELO)，这是相当可观的。】

　　2. 除非你想和世界冠军去比，否则你的局面评价函数不必要特别有效。

　　3. 如果你的程序确实很快，你可以花些时间用适当的算法来改进评估方法。但是对象棋来说，花上几千年时间都是有可能的。【这里指用适当的算法来调整权重，例如线性回归分析、神经网络算法等，每做一步调整，都需要用大量的对局来试验，所以工作量非常大。】

　　【最后想注明我的观点，即局面评估函数是整个象棋程序的核心。人们越来越把注意力集中到局面评估函数上，好的象棋程序往往用上万行的程序来分析局面，但它们的作者很少会透露出其中的细节。一个最简单的办法就是去看一些公开了的象棋程序，例如：Crafty的评估函数有4000多行，主要包括以下四方面的内容：

　　(1) 子力价值，仅仅是简单地把每个子的价值加在一起；

　　(2) 兵的价值，不仅考虑兵的相对位置，也考虑通路兵(特别在残局中)；

　　(3) 跟每个子位置有关的子力价值，即子力的灵活性、协调性等因素；

　　(4) 王的安全性，既考虑王周围的兵阵，也考虑可以攻击王的其他棋子。

　　以上译自Crafty源程序的第一段，其中的细节可以参考这个程序的其他片段。】

　

下一个月

　

　　好了，没有下一个月了，就这些了。

　　如果我要把这个连载拖得长一些，我可以写一些关于开局库(Opening Book)、残局库(Endgame Library)、特别针对象棋的硬件，以及很多很多其他的内容。我当然写得出来，但是我才不写呢。我打算把一部分内容保留到我今年秋天要写的书里，其他内容我也不知道到底有没有用。还有一个原因，我也懒得写下去了。

　　我希望你们喜欢看我的东西，希望你们能学到两三个有用的技巧。如果真的学到了，那么明年看我写的别的东西吧(GDC或E3)【我也不知道是什么学科，GDC好像是图形显示控制芯片，反正和象棋没任何关系】，并且在你公司里的工程师或程序员面前好好夸我，好吗？

　　太高兴了！

　

　　François Dominic Laramée，2000年10月

　

　　【译后注：总的来说Laramée写的东西还是比较浅显的，没有代码和过于专业的知识(即便是有，我也已经在译注中说明了)。但是或许是我英语水平的问题，他的某些表述并不能理解，因此即便很别扭地翻译出来了，还是要在译注中加上自己的理解，这让我非常吃力。不过总算一切都结束了。

　　与此同时，我还收集了很多专题方面的文章，大概有三十来篇，本来是想翻译的，以展示我在程序设计方面的造诣，但是没有时间了(况且在Laramée的文章里我也发挥过瘾了)。我相信读者看了这六篇连载后一定觉得还不够，至少对于想设计象棋引擎的读者来说，仅仅看这么点东西是远远不够的，因此我把这些原文放在我的网站上，相信对于学过程序设计的读者来说，看这些文章应该是没有问题的。

　　如果你读到有疑问的地方，不妨和我交流，或许你的疑问是很就价值的。如果你找到文中明显的错误(包括错别字)，一定要写信给我，我的工作是无偿为象棋爱好者和程序设计师做的，所以也需要你们的帮助。】

　

　　原文：http://www.gamedev.net/reference/programming/features/chess6/

　　译者：象棋百科全书网 (webmaster@xqbase.com)

　　类型：全译加译注

上一篇　国际象棋程序设计(五)：高级搜索方法

下一篇　概述

返　回　象棋百科全书——电脑象棋

www.xqbase.com