《对弈程序基本技术》专题
 
策略和技巧
 
Martin Fierz */
* 瑞士Windisch应用科学学院(Aargau学院)
 
  我通过以下问题的讨论来结束这个棋类游戏程序设计的讲座。这些问题大都没有非常明确的答案,因此我作了比较深入的研究。我觉得这些问题非常有趣,希望你们也这么认为。
 
速度的需求
 
  棋类程序设计师们都对程序的速度非常关注,有些人会不顾孩子的出生而让程序再提高10%的速度,这是何苦呢?原因是速度提高了几个百分点,棋就会下得不一样,事实上这个不一样的程度会超出你的想象。Ken Thompson对他的国际象棋程序“尤物”(Belle)做了很多试验后发现,搜索每多一层棋力就增加200ELO等级分,换句话说当你的对手比你低200分的时候,平均有75%的棋局是你赢下的。很多人都在做这个试验,并且得到同样的结果。因此人们就开始预测搜索多少层才能成为世界冠军,并且预测“消亡转折”,即你在搜索到一定深度时,再多搜索一层时棋力不再有原先预计的增长。人们试图找过这个转折,但是找到它要比预期的困难得多。我用自己早期设计的西洋跳棋程序Cake++来寻找这个转折点,指定固定的搜索深度,如5层、7层、9层等等,和少搜索两层的程序比赛。以下就是试验结果,很明显可以看到消亡转折。我用Chinook做了类似的试验来作比较,由于对局数太少,数字不太确切。一些在国际象棋中很难找到的规律,在西洋跳棋里就很容易找到,因为西洋跳棋的搜索深度要多得多。
  【译注:消亡转折有着重大的理论和实际意义,它可以用来估计电脑程序能够到达的极限。因为随着计算机速度的不断提高(目前仍旧以每一年半翻一番的速度在提高),电脑可以计算的深度也越来越深(估计每两年就可多搜索一层)。而随着消亡转折的到来,即使电脑搜索得再深,棋力也不会有太大的长进,这就可能是电脑棋力的极限了。】
搜索深度 ::(Cake++) 胜率 偏差 胜率(Chinook)
5:3 196:53:33 78.9% 2.1% -
7:5 153:100:29 72.0% 2.0% 77.5%
9:7 181:75:26 77.5% 2.0% 65.0%
11:9 130:111:41 65.8% 2.1% 72.5%
13:11 134:116:32 68.1% 2.0% 58.8%
15:13 119:136:27 66.3% 1.9% 58.8%
17:15 89:165:28 60.8% 1.8% 61.3%
19:17 78:176:28 58.9% 1.8% 57.5%
21:19 60:189:33 54.8% 1.7% 57.5%
又笨又快还是又好又慢?
 
  跟消亡转折类似的问题是:程序能否通过速度来补偿知识的不足?对于这个问题,Hans Berliner做过一个很有名的试验,用他的国际象棋程序Hitech很好地回答了这个问题。他去掉了程序中大量的局面评价函数,由此产生了另一个程序,命名为Lotech。然后他用Lotech对阵Hitech,并且给Lotech多搜索一层的优势。一个令人惊奇的结果是:Lotech总是能赢Hitech。因此,有人认为一定存在一个转折点,使得Hitech能打败Lotech。在国际象棋中,这个转折点很难找到。我曾经用自己的西洋跳棋程序来找这个转折点,但是当时我发现Lotech-Cake总是能赢Hitech-Cake
  【如果计算同样深度,Hitech棋力比Lotech100分的话,但由于多搜索一层使得Lotech增加了200分,所以棋力反而比Hitech强。根据消亡转折来推断的,超过某个深度以后,多搜索一层使得程序的棋力没有太大长进,只要长进低于100分,那么这个时候Hitech就能击败Lotech了。如今电脑思考得越来越深,导致的结果就是:程序设计师们对知识的重视程度增加了。】
 
机器学习
 
  机器学习是一个很吸引人的主题。计算机程序利用前人经验的方法有很多,其中很多方法被程序作者称为“学习”(Learning),我将在这里总体介绍一下。最普遍的学习是机械学习,当你的程序输掉一局棋时,它就把这局棋记住了。这个方法可以在开局库的学习中实现,你的程序会把一个开局库着法标记为劣着,如果这个着法会输棋,那么下一盘棋它就选择别的着法。这个方法也可以用一个小的置换表来实现,输掉的棋局里的局面都以输的局面存储起来,这样,程序就不会走到这些局面里去。但是,这种学习的形式实在是太具体了,你的西洋跳棋程序会认为某个具体的局面是坏的,类似典型的局面也是坏的,你的程序却视而不见。在西洋跳棋中“牵制”(Holds)非常重要,例如你的3个兵被对手的2个兵牵制住,如果不考虑棋盘上的其他棋子,那么对手将要获胜(至少获胜的机会很大),因为它很有可能要升变了。你用最基本的机械学习会知道这种牵制的其中一种局面会输,但是还有成千上万种类似的局面呢,遇到跟这个局面有微小差别的其他局面,再下一盘还是会输。这种类型的学习不是真正意义上的学习,把这些程序称为“智能”(Intelligent)或“吃一堑长一智”(Learning from Mistakes)纯粹是糊弄人的。
  另一种类型的机器学习用来自动调整评价函数的权重,这属于遗传算法(Genetic Algorithms)的范畴,把遗传算法作用在评价理论上,就自然地得到了最适合的程序。以下就是这种算法的工作原理,你产生一个评价函数(典型的评价函数是线性的),每一项都有一个权重,因此有:
 
eval = w_1 * f_1 + w_2 * f_2 + ... + w_n * f_n
 
  fi就是局面的各个因素,例如在西洋跳棋中,你可以把f1定义为黑方有强大的底线,因此w1越大,你的程序就越会试图让底线留下棋子。因此当你选择这些因素时,就必须顺便优化相应的权重。遗传算法在一开始时使用一些随机产生的程序,然后通过它们之间的对阵来找出哪些是好的哪些是坏的。一些坏的程序被筛选掉了,合适的程序幸存下来并得到繁衍——或者是在两个好的程序之间作交换(随机地在两个好的程序中选择wi),或者随机改变一个好的程序。现在你只管继续这样的工作,指望最终能得到一个好的权重的组合。这就是上世纪50年代Arthur Samuel在他著名的西洋跳棋程序里用的方法。另外还有其他调节权重的方法,深蓝(Deep Blue)的小组用了大量特级大师的对局,然后让程序吻合这些局面。他们对程序和特级大师走出一样着法的频率作出统计,然后修改了权重再作尝试。如果程序能解决更多的局面,那么他们就保留这个修改,否则就重新修改。最近我知道的调整权重的办法,是Michael Buro在他的黑白棋(Othello)世界冠军程序Logistello中用到的。他建立了一个巨大的局面数据库,用来储存对局结果,然后他把评价函数作用在每个局面上,通过优化评价函数使得产生的分数尽可能地准确。
  所有这些方法都比机械学习更有效。如果某个程序有对西洋跳棋中类似牵制战术的评价,那么你在评价函数中提高这项的权重,会让程序认为所有类似情形的局面都是坏的,并且会避免这些局面。那么这样说来,我们是否已经学到了知识了?我认为还没有。如果你的程序本身就不包括这个评价呢?即便再怎样调节权重,也是不会有效果的。因此我们将涉及到下面的学习:
  神经网络(Neural Networks)能够发明一些评价模式,而不需要有人告诉它,它能对局面作出评价,并且结合到棋类程序中。神经网络由很多输入口,一些隐含的层次结构,以及一个出口组成。这些连接着入口和出口的层次,实际上由很多结点组成,结点有连接上一层的入口和连接下一层的出口。每个结点都可以和其他层有连接,每个连接是有强有弱的。如果同时改变连接及其强度,你就能得到一些评价模式,并确定他们的权重。
  把有评分的局面告诉神经网络,它就会得到训练,而在结合了遗传算法后,神经网络也会自我学习。有个西洋跳棋程序Blondie24,就是用这种方法实现了自我学习的,并且下得还不错。我认为这才是真正的学习,它和人类的思考很接近。Blondie的作者把他们的程序吹嘘得很过分,但对于目前大多数研究者来说,事实上就是如此,你必须大造声势来获得资金。
 
改进你的程序
 
  你花了无数时间来写你的程序,它现在下得是否还像初学者?这是很正常的现象,但是请不要失望,我会告诉你一些技巧。首先并且最重要的是,很多问题来源于代码中的错误。Alpha-Beta算法是最容易藏匿错误的,你的程序评价了成千上万个局面,而你只得到一个着法,即使10%的局面是随机评价的,你的程序仍然在大多数时间内可以走得正确。因此,你需要你需要做一些额外检查,以确认程序的每个部分都正常工作。一个最典型的技巧就是检验评价的对称性,如果同样的局面黑白交换后,你的评价函数没有返回同样的值,那么肯定有什么地方错了。如果棋盘有其他的对称性(在国际象棋的中局里你可以按d列和e列作左右镜像操作),你也可以利用这样的对称性。代码要尽可能地写得清晰,优化不要操之过急,否则就得不偿失了。在程序用Alpha-Beta算法走第一盘棋之前,不要加任何锦上添花的代码。只有当你根除了错误,才可以着手对程序进行调整。它是否太慢了?你可以用AMD CodeAnalyst这样的分析测试软件来考察程序的关键部分,并加以改进。让程序和别的程序下棋,这是个改进程序的非常有效的办法。程序下了几百盘棋以后,所有的统计数字就都有了,对你的代码修改一些地方(搜索算法,评价函数等等),然后再打很多比赛来确认你改得是否有效。如果你改变的只是着法顺序,就可以用一组对比测试来代替长时间的比赛,看看花的时间是否减少了,就知道着法顺序是否改进了。
 
  原文:http://www.fierz.ch/strategy5.htm
  译者:象棋百科全书网 (webmaster@xqbase.com)
  类型:全译加译注
  • 上一篇 其他策略——开局库
  • 下一篇 结语——国际象棋程序剖析
  • 返 回 象棋百科全书——电脑象棋
  • www.xqbase.com