其他策略——策略和技巧

《其他策略——策略和技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《对弈程序基本技术》专题策略和技巧MartinFierz*/文*瑞士Windisch应用科学学院（Aargau学院）我通过以下问题的讨论来结朿这个棋类游戏程序设计的讲座。这些问题大都没有非常明确的答案，因此我作了比较深入的研究。我觉得这些问题非常有趣,希望你们也这么认为。速度的需求棋类程序设计师们都对程序的速度非常关注，有些人会不顾孩子的出生而让程序再提高10%的速度，这是何苦呢？原因是速度捉高了几个百分点，棋就会下得不一样，事实上这个不一样的程度会超出你的想彖。KenThompson对他的国际象棋程序“尤物”（Belle）做了

2、很多试验后发现，搜索每多一层棋力就增加200个ELO等级分，换句话说当你的对手比你低200分的时候，平均冇75%的棋局是你赢卜的。很多人都在做这个试验，并且得到同样的结果。因此人们就开始预测搜索多少层才能成为世界冠军，并月•预测“消亡转折”，即你在搜索到一定深度时，再多搜索一层时棋力不再有原先预计的增长。人们试图找过这个转折，但是找到它要比预期的困难得多。我用自己早期设计的西洋跳棋程序Cake+4-来寻找这个转折点，指定固定的搜索深度，如5层、7层、9层等等，和少搜索两层的程序比赛。以下就是试验结果，很明显可以看到消亡转折。我用

3、Chinook做了类似的试验来作比较，由于对局数太少，数字不太确切。一些在国际象棋屮很难找到的规律，在西洋跳棋里就很容易找到，因为西洋跳棋的搜索深度要多得多。【译注：消亡转折有着重大的理论和实际意义，它可以用来估计电脑程序能够到达的极限。因为随着计算机速度的不断提高（冃前仍旧以每一年半翻一番的速度在提高），电脑可以计算的深度也越来越深（估计每两年就可多搜索一层）o而随着消亡转折的到来，即使电脑搜索得再深，棋力也不会有太大的长进，这就可能是电脑棋力的极限了。】搜索深度胜:和:负(Cakt++)胜率偏差胜率(Chinook)5:31

4、96:53:3378.9%2」％■7:5153:100:2972.0%2.0%77.5%9:7181:75:2677.5%2.0%65.0%11:9130:111:4165.8%2.1%72.5%13:11134:116:3268.1%2.0%58.8%15:13119:136:2766.3%1.9%58.8%17:1589:165:2860.8%1.8%61.3%19:1778:176:2858.9%1.8%57.5%

5、

6、21:1960:189:3354.8%1.7%57.5%又笨又快还是又好又慢?跟消亡转折类似的问题是：程序

7、能否通过速度来补偿知识的不足？对于这个问题，HansBerliner做过一个很冇名的试验，用他的国际象棋程序Hitech很好地回答了这个问题。他去掉了程序中大量的局面评价函数，由此产生了另一个程序,命名为Lotecho然后他用Lotech对阵Hitech，并且给Lotech多搜索一层的优势。一个令人惊奇的结果是：Lotech总是能赢Hitecho因此，有人认为一定存在一个转折点，使得Hitech能打败Lotecho在国际象棋屮，这个转折点很难找到。我曾经用自己的西洋跳棋程序來找这个转折点，但是当时我发现Lotech-Cake总是

8、能赢Hitech-Cakeo【如果计算同样深度,Hitech棋力比Lotech高100分的话,但由于多搜索一层使得Lotech增加了200分，所以棋力反而比Hitech强。根据消亡转折来推断的，超过某个深度以后，多搜索一层使得程序的棋力没有太大长进，只要长进低于100分，那么这个时候Hitech就能击败Lotech了。如今电脑思考得越來越深，导致的结果就是：程序设计师们对知识的重视程度增加了。】机器学习机器学习是一个很吸引人的主题。计算机程序利用前人经验的方法有很多，其屮很多方法被程序作者称为“学习"(Learning),我将在

9、这里总体介绍一下。最普遍的学习是机械学习，当你的程序输掉一局棋时，它就把这局棋记住了。这个方法可以在开局库的学习屮实现，你的程序会把-个开局库着法标记为劣着，如果这个着法会输棋，那么下一盘棋它就选择别的着法。这个方法也可以用一个小的置换表来实现，输掉的棋局里的局面都以输的局面存储起來，这样，程序就不会走到这些局而里去。但是，这种学习的形式实在是太具体了，你的四洋跳棋程序会认为某个具体的局面是坏的，类似典型的局面也是坏的，你的程序却视而不见。在西洋跳棋屮“牵制”(Holds)非常重要，例如你的3个兵被对手的2个兵牵制住，如果不考虑

10、棋盘上的其他棋子，那么对手将要获胜(至少获胜的机会很大)，因为它很有可能要升变了。你用最基木的机械学习会知道这种牵制的其中一种局而会输，但是述冇成T上万种类似的局而呢，遇到跟这个局而冇微小差别的其他局面，再下一盘还是会输。这种类型的学习不是真正意义上的学习，把这