《对弈程序基本技术》专题
 
开局库
 
Martin Fierz */
* 瑞士Windisch应用科学学院(Aargau学院)
 
  不管你是否喜欢,开局库在很多棋类中都是非常重要的。很多棋类已经被人类积累了大量知识(例如国际bck体育官网手机版、西洋跳棋等),而有些棋类是新诞生的(或是因为不普及)因而没什么发展。对于人类非常精通的棋类(例如国际bck体育官网手机版),建立开局库有个非常简单的办法,即手工产生,选择高手走的棋。这种方法不是我们感兴趣的,而对于一些没有理论可寻的,或者电脑足以战胜人类(例如西洋跳棋)的棋类,用这个方法是不可取的。我们将会关注一种没有人工干预的生成开局库的方法。
 
从数据库自动生成
 
  要生成开局库,有个简单的方法就是找一个对局数据库,根据对局结果来选择可靠的着法。我的国际bck体育官网手机版程序的开局库就是这样生成的,很多国际bck体育官网手机版程序也都使用这种方法。对于国际bck体育官网手机版来说,有高质量的数据库,其中包括很多高等级分棋手下的,因此你可以决定仅仅使用高等级分棋手的对局。对于每个局面,可以生成所有着法的统计数字,例如这步着法的分数,下这步着法的棋手平均等级分,这步着法得到的平均结果,以及用结果衡量和用棋手等级分衡量的不同之处。有的对局会以符号“!(好着)或“!!(妙着)作评论,把这种评论考虑进去也是可行的,但我不知道是否有人这么做。我的国际bck体育官网手机版程序的开局库只参照统计数字,采用棋手等级分最高的着法。
 
由“脱离棋谱的扩展”自动生成
 
  如果没有人类积累的棋类理论,那么你就不得不自己计算开局库了。任何计算开局库的方法,都需要用称为“博弈树”的图来表达,图上的每个结点代表一个局面。对于每个局面,你需要计算所有可能着法的值,因此每个候选着法都要扩展。跟这个图表相应,你还必须找到一个方法来决定哪些结点是需要展开的,也就是说,图表上的哪个叶子结点需要再添加结点。这里我将介绍一个称为“脱离棋谱的扩展”(DOEDrop-out Expansion)的方法,它是由Thomas Lincke发明的。DOE的基本思想就是产生一个开局库,使得比赛时可以尽可能迟地脱离棋谱。建立开局库时有个策略,每个局面的一些好的着法需要扩展,然后从扩展出的局面继续,这样总是会在当前结点处扩展出一些着法(例如固定数量的着法,或者和跟最好着法的评价差距在一定程度内的这些着法)。但是这个策略在遇到不恰当的局面时往往很糟糕,采用这种开局库的程序通常只会走开局库中最好的着法,而对手会犯错误(要注意对手所谓的错误可能也是好的着法,仅仅是对于你的开局库而言是错误的)。因此,开局库生成器只能对一方生成最好的一些着法,而对方应该能走好的或不好的着法。首先,DOE生成器会需要产生一个图表,它对每个结点的后续着法都有一个评价。然后需要一个优先函数,对每个可能的路径(DOE限制下,一方只走最好的着法)都可以给出一个优先值,对优先级高的路径的叶子结点作扩展。这个策略使得它要做很烦琐的并行计算,如果你有计算机集群,那么你可以在主机上运行DOE生成器,而众多子机上对每个局面做精确的计算。路径优先级的计算相对来说比较随意,你可以用类似下面的方法来做:
 
delta = sum_of_errors(path);
depth = length(path);
priority = -delta - CONST * depth;
 
  这个优先函数会使对手的好的着法搜索得深一些,对手犯错误的着法搜索得浅一些。你可以在优先级的计算中加入其他因素,例如衡量结点重要性的因素。Thomas Lincke在他的优先函数中使用过“策略数”(Conspiracy Number),我的程序则衡量结点的单一性(Singularity),也就是说,最好和次好的着法差距很大,这条路线就搜索得深一些。
 
DOE的现状
 
  DOE是一个比较新的技术,在西洋跳棋(我和Ed Gilbert的程序)Awari(Thomas Lincke的程序)中用得比较成功。我的西洋跳棋的DOE生成器已经在一台单机上运行了近2年了,生成的开局库基本上不再有差错了(在一台很快的个人电脑上计算了1年半以后),或许还能够纠正人们对这种棋类在开局上的错误认识。我之所以说“基本上”,是因为目前我知道的着法中没有错误,但是也有可能开局库的成千上万个着法里会隐藏着几个坏的着法。半年前我和Ed Gilbert让我们的引擎比了624盘棋,我的程序Cake战绩是31负,其余620盘是和棋,和棋率是那么的高!输的那局揭示了我的开局库里的一个问题,现在已经修补好了。
 
  原文:http://www.fierz.ch/strategy4.htm
  译者:bck体育官网手机版百科全书网 (webmaster@xqbase.com)
  类型:全译
  • 上一篇 其他策略——残局库
  • 下一篇 其他策略——策略和技巧
  • 返 回 bck体育官网手机版百科全书——电脑bck体育官网手机版
  • www.xqbase.com