其他策略——策略和技巧.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

face="Times New Roman">57.5%</FONT></TD></TR></TBODY></TABLE></CENTER></DIV>
<DL>
  <DT><FONT face=楷体_GB2312 size=5><STRONG>又笨又快还是又好又慢？</STRONG></FONT> 
  <DT>　 
  <DT>　　跟消亡转折类似的问题是：程序能否通过速度来补偿知识的不足？对于这个问题，<FONT face="Times New Roman">Hans 
  Berliner</FONT>做过一个很有名的试验，用他的国际象棋程序<FONT 
  face="Times New Roman">Hitech</FONT>很好地回答了这个问题。他去掉了程序中大量的局面评价函数，由此产生了另一个程序，命名为<FONT 
  face="Times New Roman">Lotech</FONT>。然后他用<FONT 
  face="Times New Roman">Lotech</FONT>对阵<FONT 
  face="Times New Roman">Hitech</FONT>，并且给<FONT 
  face="Times New Roman">Lotech</FONT>多搜索一层的优势。一个令人惊奇的结果是：<FONT 
  face="Times New Roman">Lotech</FONT>总是能赢<FONT 
  face="Times New Roman">Hitech</FONT>。因此，有人认为一定存在一个转折点，使得<FONT 
  face="Times New Roman">Hitech</FONT>能打败<FONT 
  face="Times New Roman">Lotech</FONT>。在国际象棋中，这个转折点很难找到。我曾经用自己的西洋跳棋程序来找这个转折点，但是当时我发现<FONT 
  face="Times New Roman">Lotech-Cake</FONT>总是能赢<FONT 
  face="Times New Roman">Hitech-Cake</FONT>。 
  <DT><FONT color=#0000ff>　　【如果计算同样深度，</FONT><FONT face="Times New Roman" 
  color=#0000ff>Hitech</FONT><FONT color=#0000ff>棋力比</FONT><FONT 
  face="Times New Roman" color=#0000ff>Lotech</FONT><FONT 
  color=#0000ff>高</FONT><FONT face="Times New Roman" 
  color=#0000ff>100</FONT><FONT color=#0000ff>分的话，但由于多搜索一层使得</FONT><FONT 
  face="Times New Roman" color=#0000ff>Lotech</FONT><FONT 
  color=#0000ff>增加了</FONT><FONT face="Times New Roman" 
  color=#0000ff>200</FONT><FONT color=#0000ff>分，所以棋力反而比</FONT><FONT 
  face="Times New Roman" color=#0000ff>Hitech</FONT><FONT 
  color=#0000ff>强。根据消亡转折来推断的，超过某个深度以后，多搜索一层使得程序的棋力没有太大长进，只要长进低于</FONT><FONT 
  face="Times New Roman" color=#0000ff>100</FONT><FONT 
  color=#0000ff>分，那么这个时候</FONT><FONT face="Times New Roman" 
  color=#0000ff>Hitech</FONT><FONT color=#0000ff>就能击败</FONT><FONT 
  face="Times New Roman" color=#0000ff>Lotech</FONT><FONT 
  color=#0000ff>了。如今电脑思考得越来越深，导致的结果就是：程序设计师们对知识的重视程度增加了。】</FONT> 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>机器学习</STRONG></FONT> 
  <DT>　 
  <DT>　　机器学习是一个很吸引人的主题。计算机程序利用前人经验的方法有很多，其中很多方法被程序作者称为“学习”<FONT 
  face="Times New Roman">(Learning)</FONT>，我将在这里总体介绍一下。最普遍的学习是机械学习，当你的程序输掉一局棋时，它就把这局棋记住了。这个方法可以在开局库的学习中实现，你的程序会把一个开局库着法标记为劣着，如果这个着法会输棋，那么下一盘棋它就选择别的着法。这个方法也可以用一个小的置换表来实现，输掉的棋局里的局面都以输的局面存储起来，这样，程序就不会走到这些局面里去。但是，这种学习的形式实在是太具体了，你的西洋跳棋程序会认为某个具体的局面是坏的，类似典型的局面也是坏的，你的程序却视而不见。在西洋跳棋中“牵制”<FONT 
  face="Times New Roman">(Holds)</FONT>非常重要，例如你的<FONT 
  face="Times New Roman">3</FONT>个兵被对手的<FONT 
  face="Times New Roman">2</FONT>个兵牵制住，如果不考虑棋盘上的其他棋子，那么对手将要获胜<FONT 
  face="Times New Roman">(</FONT>至少获胜的机会很大<FONT 
  face="Times New Roman">)</FONT>，因为它很有可能要升变了。你用最基本的机械学习会知道这种牵制的其中一种局面会输，但是还有成千上万种类似的局面呢，遇到跟这个局面有微小差别的其他局面，再下一盘还是会输。这种类型的学习不是真正意义上的学习，把这些程序称为“智能”<FONT 
  face="Times New Roman">(Intelligent)</FONT>或“吃一堑长一智”<FONT 
  face="Times New Roman">(Learning from Mistakes)</FONT>纯粹是糊弄人的。 
  <DT>　　另一种类型的机器学习用来自动调整评价函数的权重，这属于遗传算法<FONT face="Times New Roman">(Genetic 
  Algorithms)</FONT>的范畴，把遗传算法作用在评价理论上，就自然地得到了最适合的程序。以下就是这种算法的工作原理，你产生一个评价函数<FONT 
  face="Times New Roman">(</FONT>典型的评价函数是线性的<FONT 
  face="Times New Roman">)</FONT>，每一项都有一个权重，因此有： 
  <DD>　 
  <DD>eval = w_1 * f_1 + w_2 * f_2 + ... + w_n * f_n 
  <DT>　 
  <DT>　　<FONT 
  face="Times New Roman"><EM>f</EM><SUB><EM>i</EM></SUB></FONT>就是局面的各个因素，例如在西洋跳棋中，你可以把<FONT 
  face="Times New Roman"><EM>f</EM><SUB>1</SUB></FONT>定义为黑方有强大的底线，因此<FONT 
  face="Times New Roman"><EM>w</EM><SUB>1</SUB></FONT>越大，你的程序就越会试图让底线留下棋子。因此当你选择这些因素时，就必须顺便优化相应的权重。遗传算法在一开始时使用一些随机产生的程序，然后通过它们之间的对阵来找出哪些是好的哪些是坏的。一些坏的程序被筛选掉了，合适的程序幸存下来并得到繁衍——或者是在两个好的程序之间作交换<FONT 
  face="Times New Roman">(</FONT>随机地在两个好的程序中选择<FONT 
  face="Times New Roman"><EM>w</EM><SUB><EM>i</EM></SUB>)</FONT>，或者随机改变一个好的程序。现在你只管继续这样的工作，指望最终能得到一个好的权重的组合。这就是上世纪<FONT 
  face="Times New Roman">50</FONT>年代<FONT face="Times New Roman">Arthur 
  Samuel</FONT>在他著名的西洋跳棋程序里用的方法。另外还有其他调节权重的方法，深蓝<FONT 
  face="Times New Roman">(Deep 
  Blue)</FONT>的小组用了大量特级大师的对局，然后让程序吻合这些局面。他们对程序和特级大师走出一样着法的频率作出统计，然后修改了权重再作尝试。如果程序能解决更多的局面，那么他们就保留这个修改，否则就重新修改。最近我知道的调整权重的办法，是<FONT 
  face="Times New Roman">Michael Buro</FONT>在他的黑白棋<FONT 
  face="Times New Roman">(Othello)</FONT>世界冠军程序<FONT 
  face="Times New Roman">Logistello</FONT>中用到的。他建立了一个巨大的局面数据库，用来储存对局结果，然后他把评价函数作用在每个局面上，通过优化评价函数使得产生的分数尽可能地准确。 

  <DT>　　所有这些方法都比机械学习更有效。如果某个程序有对西洋跳棋中类似牵制战术的评价，那么你在评价函数中提高这项的权重，会让程序认为所有类似情形的局面都是坏的，并且会避免这些局面。那么这样说来，我们是否已经学到了知识了？我认为还没有。如果你的程序本身就不包括这个评价呢？即便再怎样调节权重，也是不会有效果的。因此我们将涉及到下面的学习： 

  <DT>　　神经网络<FONT face="Times New Roman">(Neural 
  Networks)</FONT>能够发明一些评价模式，而不需要有人告诉它，它能对局面作出评价，并且结合到棋类程序中。神经网络由很多输入口，一些隐含的层次结构，以及一个出口组成。这些连接着入口和出口的层次，实际上由很多结点组成，结点有连接上一层的入口和连接下一层的出口。每个结点都可以和其他层有连接，每个连接是有强有弱的。如果同时改变连接及其强度，你就能得到一些评价模式，并确定他们的权重。 

  <DT>　　把有评分的局面告诉神经网络，它就会得到训练，而在结合了遗传算法后，神经网络也会自我学习。有个西洋跳棋程序<FONT 
  face="Times New Roman">Blondie24</FONT>，就是用这种方法实现了自我学习的，并且下得还不错。我认为这才是真正的学习，它和人类的思考很接近。<FONT 
  face="Times New Roman">Blondie</FONT>的作者把他们的程序吹嘘得很过分，但对于目前大多数研究者来说，事实上就是如此，你必须大造声势来获得资金。 

  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>改进你的程序</STRONG></FONT> 
  <DT>　 
  <DT>　　你花了无数时间来写你的程序，它现在下得是否还像初学者？这是很正常的现象，但是请不要失望，我会告诉你一些技巧。首先并且最重要的是，很多问题来源于代码中的错误。<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法是最容易藏匿错误的，你的程序评价了成千上万个局面，而你只得到一个着法，即使<FONT 
  face="Times New Roman">10%</FONT>的局面是随机评价的，你的程序仍然在大多数时间内可以走得正确。因此，你需要你需要做一些额外检查，以确认程序的每个部分都正常工作。一个最典型的技巧就是检验评价的对称性，如果同样的局面黑白交换后，你的评价函数没有返回同样的值，那么肯定有什么地方错了。如果棋盘有其他的对称性<FONT 
  face="Times New Roman">(</FONT>在国际象棋的中局里你可以按<FONT 
  face="Times New Roman">d</FONT>列和<FONT 
  face="Times New Roman">e</FONT>列作左右镜像操作<FONT 
  face="Times New Roman">)</FONT>，你也可以利用这样的对称性。代码要尽可能地写得清晰，优化不要操之过急，否则就得不偿失了。在程序用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法走第一盘棋之前，不要加任何锦上添花的代码。只有当你根除了错误，才可以着手对程序进行调整。它是否太慢了？你可以用<FONT 
  face="Times New Roman">AMD 
  CodeAnalyst</FONT>这样的分析测试软件来考察程序的关键部分，并加以改进。让程序和别的程序下棋，这是个改进程序的非常有效的办法。程序下了几百盘棋以后，所有的统计数字就都有了，对你的代码修改一些地方<FONT 
  face="Times New Roman">(</FONT>搜索算法，评价函数等等<FONT 
  face="Times New Roman">)</FONT>，然后再打很多比赛来确认你改得是否有效。如果你改变的只是着法顺序，就可以用一组对比测试来代替长时间的比赛，看看花的时间是否减少了，就知道着法顺序是否改进了。 

  <DT>　 
  <DT>　　原文：<A href="http://www.fierz.ch/strategy5.htm" target=_blank><FONT 
  face="Times New Roman">http://www.fierz.ch/strategy5.htm</FONT></A> 
  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译加译注 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/other_book.htm">其他策略——开局库</A> 
<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/anatomy.htm">结语——国际象棋程序剖析</A> 
<LI>返　回　<A href="http://www.elephantbase.net/computer.htm">象棋百科全书——电脑象棋</A> 
</LI></DIR>
<DIV align=center>
<CENTER>
<TABLE border=0>
  <TBODY>
  <TR>
    <TD>
      <P align=center><A href="http://www.elephantbase.net/" target=_blank><IMG 
      height=31 src="其他策略——策略和技巧_files/elephantbase.gif" width=88 
      border=0></A></P></TD></TR>
  <TR>
    <TD><A href="http://www.elephantbase.net/" target=_blank><FONT face=Arial 
      size=2><STRONG>www.elephantbase.net</STRONG></FONT></A></TD></TR></TBODY></TABLE></CENTER></DIV></BODY></HTML>