《对弈程序基本技术》专题
　
评价函数
　
David Eppstein */文
* 加州爱尔文大学(UC Irvine)信息与计算机科学系
　
整体考虑
　
　　在你的程序中，评价函数综合了大量跟具体棋类有关的知识。我们从以下两个基本假设开始：
　　(1) 我们能把局面的性质量化成一个数字。例如，这个数字可以是对取胜的概率作出的估计；但是大多数程序不给这个数字以如此确定的含义，因此这仅仅是一个数子而已。
　　(2) 我们衡量的这个性质应该跟对手衡量的性质是一样的(如果我们认为我们处于优势，那么反过来对手认为他处于劣势)。真实情况并非如此，但是这个假设可以让我们的搜索算法正常工作，而且在实战中它跟真实情况非常接近。
　　评价可以是简单的或复杂的，这取决于你在程序中加了多少知识。评价越复杂，包含知识的代码就越多，程序就越慢。通常，程序的质量(它棋下得怎样)可以通过知识和速度的乘积来估计：
　
　
　
　　因此，如果你有一个快速而笨拙的程序，你通常可以加一些知识让它慢下来，使它工作得更好。但是同样是增加知识让程序慢下来，对一个比较聪明但很慢的程序来说，可能会更糟；知识对棋力的增长作用会减少的。类似地，你增加程序的速度，到一定程度后，速度对棋力的提高作用也会减少，你最好在速度和知识上寻求平衡，达到图表中间的位置。平衡点也会随着你面对的对手而改变；对于击败其他电脑，速度的表现更好，而人类对手则善于寻找你的程序中对于知识的漏洞，从而轻松击败基于知识的程序。【译注：如果你的程序要和人类棋手比，那么最好给程序加上足够多的知识。】
　
实现方法
　
　　就评价方法而言主要有两个类型。第一个是“终点评价”(End-Point Evaluation)，即用你擅长的评价算法，简单地评价每个局面，而不受其他局面的影响。这通常会给出好的结果，但是非常慢。因此一些程序设计师用了下面的诀窍，称为预先计算(Pre-Computation)，一阶评价(First-Order Evaluation)，或棋子-格子数组(Piece-Square Tables)。
　　在我们对一个局面搜索最佳着法之前，我们认真检查棋局本身，在数组T[格子，棋子类型]中保存计算值。在搜索过程中评价任何局面，只要简单地把棋子在数组中的值加起来就行了。我们不必每一步都重新计算它们的和，在把棋子从一个格子移到另一个格子时，可以用下面的公式更新评价值：
　
score += T[新的格子，棋子] - T[旧的格子，棋子]
　
　　下面就举一个例子说明国际象棋中的棋子-格子数组：当王被易位到棋盘的角落时，王前面的几个兵对防御来说是非常有用的。它们前进后防御能力就变差。因此，如果搜索的开始局面王在角落里，我们就应该为这些兵建立一个棋子-格子数组，其值如下：
　
... ... ... ... ...
... 1 1 1 1
... 1 1.1 1.1 1.1
... 1 1.2 1.2 1.2
... - - - -
　
　　在王前的三列中，为了使兵尽量离王近些，就在距离近的时候给它们更高的值。
　　不幸的是棋子-格子数组会很快失效，如果你要通过棋子-格子数组来增加一些知识，那么这种方法会显得非常愚蠢。在棋子-格子数组建立之初，这些联系就根据棋子的原始位置粗略计算好了，因此它们不能建立起几个移动过的棋子之间的联系。因此，如果我们搜索很长的一系列着法，例如王走到了棋盘的另半边，那么原来的棋子-格子数组的值就会非常不准确，因为它只是让兵防御王原来待的地方，而不是防御王本身。
　　用棋子-格子数组的程序通常需要结合终点评价。另一个建立棋子-格子数组的策略，就是把数组的建立延迟到后面的搜索中。例如，你要搜索9步后续着法，那么可以在5步的后续着法下建立数组，为剩下的4步搜索作准备。如果你想这么做，就应该使一个5步着法产生的数组和其他着法产生的数组保持一致，使得所有的评价值都有可比性。在我的课上O. Dave提出另一个改进的建议：用增量的办法修改棋子-格子数组，例如当王走掉时，对王前几个兵的奖励值也去掉了。这看上去是个不错的思想，但是我不知道如何来实现，也不知道如果实现了，效果会是怎样。
　
如何组合评价要素
　
　　把评价要素组合起来，通常就和上面所说的一阶评价一样，评价函数是很多项的和，每一项是一个函数，它负责找到局面中的某个特定因素。为什么要用加法呢？因为这种简单的组合信息的方法在实践中非常好用。
　　我自己感觉，棋类程序应该充分尝试各种可能的评价函数：把各种胜利的可能性结合起来，包括很快获胜(考虑进攻手段)，很多回合以后能获胜，以及在残局中获胜(国际象棋中就必须考虑通路兵的优势)的可能性，然后把这些可能性以适当的方式结合起来。如果黑方很快获胜的可能性用bs表示而白方用ws，在很多回合以后获胜(即不是很快获胜)的可能性是bm或wm，而在残局中获胜的可能性是be或we，那么整个获胜的可能性就是：
　
bs + (1 - bs - ws) * bm + (1 - bs - ws - bm - wm) * be，或者
ws + (1 - bs - ws) * wm + (1 - bs - ws - bm - wm) * we
　
　　我想，通过和类似上面的公式把若干单独概率结合起来，在评价函数中或许是个很好的估计概率的思路。每种概率是否估计得好，这就需要用程序的估计来和数据库中棋局的真实结果来作比较，这就需要让程序具有基本判断的能力(判断某种攻击是否能起到效果)。但是这纯粹是我的假想，并没有在程序中测试过，如果你只用加法将不会犯多大的错。
　
评价函数中要加入哪些信息？
　
　　典型的评价函数，要把下列不同类型的知识整理成代码，并组合起来：
　
　　(1) 子力(Material)：在国际象棋中，它是子力价值的和，在围棋或黑白棋中，它是双方棋盘上棋子的数量。这种评价通常是有效的，但是黑白棋有个有趣的反例：棋局只由最后的子数决定，而在中局里，根据子力来评价却是很差的思路，因为好的局势下子数通常很少。其他像五子棋一样的游戏，子力是没有作用的，因为好坏仅仅取决于棋子在棋盘上的位置，看它是否能发挥作用。
　
　　(2) 空间(Space)：在某些棋类中，棋盘可以分为一方控制的区域，另一方控制的区域，以及有争议的区域。例如在围棋中，这个思想被充分体现。而包括国际象棋在内的一些棋类也具有这种概念，某一方的区域包括一些格子，这些格子被那一方的棋子所攻击或保护，并且不被对方棋子所攻击或保护。在黑白棋中，如果一块相连的棋子占居一个角，那么这些棋子就不吃不掉了，成为该棋手的领地。空间的评价就是简单地把这些区域加起来，如果有说法表明某个格子比其他格子重要的话，那么就用稍复杂点的办法，增加区域重要性的因素。
　
　　(3) 机动(Mobility)：每个棋手有多少不同的着法？有一个思想，即你有越多可以选择的着法，越有可能至少有一个着法能取得好的局势。这个思想在黑白棋中非常有效，国际象棋中并不那么有用。(它也曾被使用，但现在国际象棋程序设计师们把它从程序中去掉了，因为它看起来对整个局面的评价质量没什么提高。)
　
　　(4) 着法(Tempo)：这和机动性有着密切的联系，它指的是在黑白棋或连四子棋中(以及某些国际象棋残局中)，某方被迫作出使局面变得不利的着法。和机动性不同的是，起决定作用的是着法数的奇偶而不是数量。
　　例如，考虑下面的连四子棋局面：
　
　
　　【连四子棋的规则是：每个着子都必须位于某列的最底下一个空格，获胜条件是直线、横线或斜线有四个子相连。可以把连四子棋想象成带重力的五子棋。】
　　1、3、4、7列已经填满，因此只能在2、5、6列落子。第6列的着子是中立的，哪方都不能利用该列得胜或失利。黑方控制第2列，即红方不能在这里落子，因为这样可以让黑连成四子【注意第3列到第5列，已经有3个黑子形成斜线】。任何一方都不能在第5列着子，因为对方可以马上胜利【注意该列倒数第3行的空格，任何一方走到该格，都会在第4列到第7列(红方斜线，黑方横线)连成四子】。如果接下来是红先走，那么在第6列走了3步之后，黑方被迫走第2列放弃对该列的控制，又是3步后只能走第5列让红方取得胜利。但是如果下一步是黑走，那么3步之后会迫使红方输棋。
　　像这种连四子棋的残局中，偶数空格的列是无关紧要的，重要的是计算只有一方可以走的奇数列。如果一方控制更多的奇数列，那么他就可能赢。如果双方控制的奇数列一样多，如上面的棋盘所示(没有一列受红方控制，而黑方只控制一个偶数列)，那么中立列的数量就非常重要了——如果它是奇数那么先走的一方会赢，如果它是偶数那么先走的一方会输。当然，这个简单的分析是建立在掌握复杂局势的基础上的，需要知道一方是如何控制某列上方的格子的。
　　像围棋这样的游戏，并不存在这样严格的奇偶规则，但是哪方有“主动权”【即“先手”】仍然很重要，一方能选择走哪里，而另一方只能在同一个地方被迫应对。走一系列着子，每步都赢得一块小的地盘并让对手被迫应着，然后再来走棋以取得大地盘并让对手获得主动权，这通常是个好的思路。【这里指的是在收官阶段，先走先手的小官子，然后再走后手的大官子。】
　　【这里有一个中国象棋的排局，也包括类似奇偶性的主动权问题：
　
　
　　在这个局面中，双方的兵(卒)都不能离开原位，否则对方平帅(将)即可造成铁门栓杀。双方的中炮不能离开中线，而三七路炮也不能离开该线，否则对方就会有闷宫杀。这样的棋型只能有一种取胜方法——用自己的两个炮顶住对方的两个炮，迫使对方让开兵(卒)或三七路炮。
　　这就衍生出一个数学游戏：有两堆石子，双方轮流从石子中拿去几颗，每次只能从一堆石子中拿走至少一颗石子，先拿完最后一堆者获胜。这个游戏的诀窍是：始终让对方面临两堆石子一样多的窘境。上面这个象棋局面中，两路炮之间的空格就好比两堆石子的数量，现在先走一方占有主动，因为两堆石子数量不一样多，他只要走一步让两堆石子数目一样就可以了。以红方先走为例，红方杀法及其黑方最顽强的抵抗如下：
　
1. 炮七进四 炮３进１
2. 炮五进一 炮３进１
3. 炮五进一 炮３进１
4. 炮五进一 炮３进１
5. 炮五进一 炮３退１
　　若黑走炮３平５，则仕五进六、前炮平２、炮七平五做杀无解(若黑走炮２平５解杀则构成长将)。
6. 炮七进一 炮３退１
7. 炮七进一 炮３退１
8. 炮七进一 炮３退１
9. 炮七进一 卒６平７
10. 帅五平四 卒７进１
11. 帅四进一 卒７平８
12. 兵四进一
　
　　红方第一步若不走炮七进四，不管进哪个炮，主动权都让给了黑方，走炮七进八可以守和，其他着法都会让黑取胜。可见，主动权这一问题在很多棋类中都是存在的，然而这个知识写入棋类程序中很有难度。】
　
　　(5) 威胁(Threat)。对手是否会有很恶劣的手段？你有什么很好的着法？例如在国际象棋或围棋中，有什么子可能要被吃掉？在五子棋或连四子棋中，某一方是否有可以连起来的子？在国际象棋或西洋棋中，有没有子将会变后或变王？在黑白棋中，一方是否要占角？这个因素必须根据威胁的远近和强度来考虑。
　
　　(6) 形状(Shape)。在围棋中，如果连起来的一串子围成两个独立的区域(称为“眼”)，那么它们就是安全的。在国际象棋中，并排的兵通常要比同一列的叠兵强大。形状因素是非常重要，因为局面的长远价值在几步内不会改变，也不会因为搜索而变化，这正是形状因素需要衡量的。(搜索可以找到短期的手段来改进局面，所以评价本身需要包括更多的长远眼光，使得搜索可以察觉到。)【在中国象棋中，空头炮(指被对手摆空头炮)和窝心马是不好的形状，不太深的搜索不会察觉到它们的坏处，但是长远来看是这些形状会存在严重弊端，大多数程序的评价函数会直接对空头炮和窝心马进行罚分。】
　
　　(7) 图案(Motif)。一些常见的具有鲜明特点的图案，蕴涵着特殊的意义。例如在国际象棋中，象往往可以吃掉边兵，却会被边上的兵困住。当象被困住时，对手可能还需要很多步才会吃掉它，因此被困的情形不容易被计算机的搜索程序所发现。有些程序通过特殊的评价因素来警告电脑，吃掉那个边兵可能会犯错误。在黑白棋中，在角落的邻近格子上放一个子来牺牲一个角，往往是非常有用的，这样当对手占领这个角时，就可以在这个子的边上放一个提不掉的子，从而在另一个角上取得优势。
　
　
　　上图中，白方牺牲了右下角。
　　当黑方走右下角时，白方在边上走子，然后赢得了左下角。【黑方只得到一个角，而白方得到了一个角连同边线上的6子，白大优。】
　　对这种牺牲做特别的评价也许是很有必要的，它可以决定是否需要做牺牲，或者来衡量边线上的子是否能抵挡这种牺牲手段。
　
　　原文：http://www.ics.uci.edu/~eppstein/180a/990114.html
　　译者：象棋百科全书网 (webmaster@xqbase.com)
　　类型：全译加译注
  • 上一篇　高级搜索方法——搜索的不稳定性
  • 下一篇　局面评估函数——简介(二)
  • 返　回　象棋百科全书——电脑象棋
    •

    www.xqbase.com