《棋战顺序基本手艺》专题
 
评定函数
 
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,在许多回合以后失利(即不是很快失利)的能够性是bmwm,而在残局中失利的能够性是bewe,那末悉数失利的能够性就是:
 
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)这和灵活性有着亲切的联系,它指的是在是非棋或连四子棋中(以及某些国际象棋残局中),某方自愿作出使局势变得晦气的着法。和灵活性分歧的是,起注定功用的是着法数的奇偶而不是数目。
  譬喻,斟酌下面的连四子棋局势:
 
 
  【连四子棋的划定礼貌是:每一个着子都必需位于某列的最底下一个空格,失利条件是直线、横线或斜线有四个子相连。能够把连四子棋想象成带重力的五子棋。】
  1347列以前填满,因而只能在256列落子。第6列的着子是中立的,哪方都不能应用该列失利或失利。黑方掌握第2列,即红方不能在这里落子,由于如允许以让黑连成四子【注重第3列到第5列,以前有3个黑子组成斜线】。任何一方都不能在第5列着子,由于对方能够立时胜利【注重该列倒数第3行的空格,任何一方走到该格,都邑在第4列到第7(红方斜线,黑方横线)连成四子】。若是接上去是红先走,那末在第6列走了3步以后,黑方自愿走第2列抛却对该列的掌握,又是3步后只能走第5列让红方取得胜利。然则若是下一步是黑走,那末3步以后会迫使红方输棋。
  像这类连四子棋的残局中,偶数空格的列是无足轻重的,主要的是盘算只需一方能够走的奇数列。若是一方掌握更多的奇数列,那末他就能够够赢。若是双方掌握的奇数列一样多,以下面的棋盘所示(没有一列受红方掌握,而黑方只掌握一个偶数列),那末中立列的数目就异常主要了——若是它是奇数那末先走的一方会赢,若是它是偶数那末先走的一方会输。固然,这个简朴的剖析是竖立在掌握庞大形势的根蒂基本上的,要求知道一方是怎样掌握某列上方的格子的。
  像围棋这样的游戏,其实不存在这样严厉的奇偶划定礼貌,然则哪方有“自动权”【即“先手”】依然很主要,一方能选择走那里,而其余一方只能在统一个中央自愿敷衍。走一系列着子,每步都赢得一块小的土地并让对手自愿应着,然后再来走棋以取得大土地并让对手取得自动权,这一般是个好的思绪。【这里指的是在收官阶段,先走先手的小官子,然后再走先手的大官子。】
  【这里有一其中国象棋的排局,也包孕相似奇偶性的自动权问题:
 
 
  在这个局势中,双方的兵()都不能脱离原位,否则对方平帅()就可以引发铁门栓杀。双方的中炮不能脱离中线,而三七路炮也不能脱离该线,否则对方就会有闷宫杀。这样的棋型只能有一种取胜要领——用自身的两个炮顶住对方的两个炮,迫使对方闪开兵()或三七路炮。
  这就衍生出一个数学游戏:有两堆石子,双方轮替从石子中拿去几颗,每次只能从一堆石子中拿走最少一颗石子,先拿完最终一堆者失利。这个游戏的窍门是:一直让对方面临两堆石子一样多的逆境。下面这个象棋局势中,两路炮之间的空格就例如两堆石子的数目,现在先走一方占有自动,由于两堆石子数目纷歧样多,他只需走一步让两堆石子数目一样就能够够了。以红方先走为例,红方杀法及其黑方最顽强的反抗以下:
 
1. 炮七进四 炮3进1
2. 炮五进一 炮3进1
3. 炮五进一 炮3进1
4. 炮五进一 炮3进1
5. 炮五进一 炮3退1
  若黑走炮3平5,则仕五进六、前炮平2、炮七平五做杀无解(若黑走炮2平5解杀则组生长将)
6. 炮七进一 炮3退1
7. 炮七进一 炮3退1
8. 炮七进一 炮3退1
9. 炮七进一 卒6平7
10. 帅五平四 卒7进1
11. 帅四进一 卒7平8
12. 兵四进一
 
  红方第一步若不走炮七进四,不论进哪一个炮,自动权都让给了黑方,走炮七进八能够守和,其他着法都邑让黑取胜。可见,自动权这一问题在许多棋类中都是存在的,然则这个知识写入棋类顺序中很有难度。】
 
  (5) 要挟(Threat)对手是否是会有很拙劣的手腕?你有甚么异常不错的着法?譬喻在国际象棋或围棋中,有甚么子能够要被吃掉?在五子棋或连四子棋中,某一方是否是有能够连起来的子?在国际象棋或西洋棋中,有无子将会变后或变王?在是非棋中,一方是否是要占角?这个重点要点必需依据要挟的远近和强度来斟酌。
 
  (6) 形状(Shape)在围棋中,若是连起来的一串子围成两个自力的区域(称为“眼”),那末它们就是平安的。在国际象棋中,并排的兵一般要比统一列的叠兵壮大。形状重点要点长短常主要,由于局势的长远价值在几步内不会改动,也不会由于搜索而转变,这正是形状重点要点要求权衡的。(搜索能够找到短时间的手腕来革新局势,以是评定自身要求包孕更多的长远眼光,使得搜索能够发觉到。)【在中国象棋中,空头炮(指被对手摆空头炮)和窝心马是欠好的形状,不太深的搜索不会发觉到它们的坏处,然则长远来看是这些形状会存在严重毛病,大少数顺序的评定函数会直接对空头炮和窝心马停止罚分。】
 
  (7) 图画(Motif)一些容易看到的具有显著特性的图画,蕴涵着稀奇的意义。譬喻在国际象棋中,象往往能够吃掉边兵,却会被边上的兵困住。当象被困住时,对手能够还要求许多步才会吃掉它,因而被困的状况不随意纰漏被盘算机的搜索顺序所发现。很多若干顺序经由历程稀奇的评定重点要点来正告计算机,吃掉谁人边兵能够会出毛病。在是非棋中,在角落的相近格子上放一个子来牺牲一个角,往往长短常有用的,这样当对手占有这个角时,就能够够在这个子的边上放一个提不掉的子,从而在其余一个角上取得优势。
 
 
  上图中,白方牺牲了右下角。
  当黑方走右下角时,白方在边上走子,然后赢得了左下角。【黑方只失掉一个角,而白方失掉了一个角连同边线上的6子,白大优。】
  对这类牺牲做稀奇的评定多是很有需要的,它能够注定是否是要求做牺牲,也许来权衡边线上的子是否是能招架这类牺牲手腕。
 
  原文:http://www.ics.uci.edu/~eppstein/180a/990114.html
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 低级搜索要领——搜索的不稳固性
  • 下一篇 局势评价函数——简介()
  • 返 回 象棋百科全书——计算机象棋
  • www.xqbase.com