- 《对弈程序基本技术》专题
-
- 开局库
-
- Martin Fierz */ 文
- * 瑞士Windisch应用科学学院(Aargau学院)
-
- 不管你是否喜欢，开局库在很多棋类中都是非常重要的。很多棋类已经被人类积累了大量知识(例如国际象棋、西洋跳棋等)，而有些棋类是新诞生的(或是因为不普及)因而没什么发展。对于人类非常精通的棋类(例如国际象棋)，建立开局库有个非常简单的办法，即手工产生，选择高手走的棋。这种方法不是我们感兴趣的，而对于一些没有理论可寻的，或者电脑足以战胜人类(例如西洋跳棋)的棋类，用这个方法是不可取的。我们将会关注一种没有人工干预的生成开局库的方法。
-
- 从数据库自动生成
-
- 要生成开局库，有个简单的方法就是找一个对局数据库，根据对局结果来选择可靠的着法。我的国际象棋程序的开局库就是这样生成的，很多国际象棋程序也都使用这种方法。对于国际象棋来说，有高质量的数据库，其中包括很多高等级分棋手下的，因此你可以决定仅仅使用高等级分棋手的对局。对于每个局面，可以生成所有着法的统计数字，例如这步着法的分数，下这步着法的棋手平均等级分，这步着法得到的平均结果，以及用结果衡量和用棋手等级分衡量的不同之处。有的对局会以符号“!”(好着)或“!!”(妙着)作评论，把这种评论考虑进去也是可行的，但我不知道是否有人这么做。我的国际象棋程序的开局库只参照统计数字，采用棋手等级分最高的着法。
-
- 由“脱离棋谱的扩展”自动生成
-
- 如果没有人类积累的棋类理论，那么你就不得不自己计算开局库了。任何计算开局库的方法，都需要用称为“博弈树”的图来表达，图上的每个结点代表一个局面。对于每个局面，你需要计算所有可能着法的值，因此每个候选着法都要扩展。跟这个图表相应，你还必须找到一个方法来决定哪些结点是需要展开的，也就是说，图表上的哪个叶子结点需要再添加结点。这里我将介绍一个称为“脱离棋谱的扩展”(DOE，Drop-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战绩是3胜1负，其余620盘是和棋，和棋率是那么的高！输的那局揭示了我的开局库里的一个问题，现在已经修补好了。
-
- 原文：http://www.fierz.ch/strategy4.htm
- 译者：象棋百科全书网 (webmaster@xqbase.com)
- 类型：全译
上一篇 其他策略——残局库
下一篇 其他策略——策略和技巧
返 回 象棋百科全书——电脑象棋
