- 《对弈程序基本技术》专题
-
- 策略和技巧
-
- Martin Fierz */ 文
- * 瑞士Windisch应用科学学院(Aargau学院)
-
- 我通过以下问题的讨论来结束这个棋类游戏程序设计的讲座。这些问题大都没有非常明确的答案，因此我作了比较深入的研究。我觉得这些问题非常有趣，希望你们也这么认为。
-
- 速度的需求
-
- 棋类程序设计师们都对程序的速度非常关注，有些人会不顾孩子的出生而让程序再提高10%的速度，这是何苦呢？原因是速度提高了几个百分点，棋就会下得不一样，事实上这个不一样的程度会超出你的想象。Ken Thompson对他的国际象棋程序“尤物”(Belle)做了很多试验后发现，搜索每多一层棋力就增加200个ELO等级分，换句话说当你的对手比你低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棋力比Lotech高100分的话，但由于多搜索一层使得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)
- 类型：全译加译注
上一篇 其他策略——开局库
下一篇 结语——国际象棋程序剖析
返 回 象棋百科全书——电脑象棋
