解剖大象的眼睛——中国象棋程序设计探索(四)：启发算法.htm

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

  face="Times New Roman">)</FONT>记录到<FONT 
  face="Times New Roman">KillerMoves[Ply]</FONT>。由此产生的效果，就是当亲兄弟结点没有杀手着法时，会找到堂兄弟结点的杀手着法。 

  <DT>　　大多数程序会为每层分配<FONT face="Times New Roman">2</FONT>个杀手着法，并采用先进先出的方式管理，即： 
  <DD>　 
  <DD>if (CutMove != KillerMoves[Ply][0]) { 
  <DD>　KillerMoves[Ply][1] = KillerMoves[Ply][0]; 
  <DD>　KillerMoves[Ply][0] = CutMove; 
  <DD>} 
  <DT>　 
  <DT>　　而搜索结点时，先搜索最近保存的杀手着法<FONT 
  face="Times New Roman">(KillerMoves[Ply][0])</FONT>，再搜索比较旧的那个<FONT 
  face="Times New Roman">(KillerMoves[Ply][1])</FONT>。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.5 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>历史表启发</STRONG></FONT> 
  <DT>　 
  <DT>　　“历史表启发”<FONT face="Times New Roman">(History 
  Heuristic)</FONT>是杀手着法启发的扩展，历史表记录的是整个搜索树中着法的好坏。历史表的思想是：搜索树中某个结点上的一个好的着法，对于其他结点可能也是好的。没有什么非常可靠的理由来支持这个思想，但根据历史表来排序着法，总比不排序要好得多，而且实践证明这是一种效果非常好的启发算法，几乎每个程序都用到。 

  <DT>　　历史表的处理方法，在各个程序中都有所差异，主要反映在以下几个方面： 
  <DT>　　<FONT face="Times New Roman">(1) 
  </FONT>产生全部着法时，是否完全根据历史表来排序。很多程序先产生吃子的着法，用<FONT 
  face="Times New Roman">MVV/LVA</FONT>来排序，然后产生不吃子的着法，根据历史表来排序。目前<FONT 
  face="Times New Roman">ElephantEye</FONT>在生成不吃子的着法后就按照历史表来排序，被排序的着法包括吃子启发没有搜索到的吃子着法和不吃子的着法。 

  <DT>　　<FONT face="Times New Roman">(2) </FONT>找到好的着法时，在历史表中增加多少值。<FONT 
  face="Times New Roman">ElephantEye</FONT>采用通常的<FONT 
  face="Times New Roman"><EM>n</EM><SUP>2</SUP>(<EM>n</EM></FONT>为当前结点需要搜索的深度<FONT 
  face="Times New Roman">)</FONT>的策略，而也有的程序设计师偏爱传统的<FONT 
  face="Times New Roman">2<SUP><EM>n</EM></SUP></FONT>。如果不确定哪个更好，那么不妨试试斐波那契数列<FONT 
  face="Times New Roman">(</FONT>即<FONT face="Times New Roman">1</FONT>、<FONT 
  face="Times New Roman">2</FONT>、<FONT face="Times New Roman">3</FONT>、<FONT 
  face="Times New Roman">5</FONT>、<FONT face="Times New Roman">8</FONT>……<FONT 
  face="Times New Roman">)</FONT>。 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>什么样的着法算是好的着法。<FONT 
  face="Times New Roman">ElephantEye</FONT>认为产生<FONT 
  face="Times New Roman">Beta</FONT>截断的着法和<FONT 
  face="Times New Roman">PV</FONT>结点中最好的着法都是好的着法<FONT 
  face="Times New Roman">(</FONT>杀手着法也是这样认定的<FONT 
  face="Times New Roman">)</FONT>，而且这两类着法在历史表中增加同样多的值。也有的程序则为PV结点的最好着法增加更多的值。 
  <DT>　　<FONT face="Times New Roman">(4) </FONT>历史表应该用什么样的结构。<FONT 
  face="Times New Roman">ElephantEye</FONT>只设立一个<FONT 
  face="Times New Roman">[256][256]</FONT>的数组，红方和黑方的着法都记录在这个数组中，更多的程序则是红方着法和黑方着法分别记录的，例如国际象棋程序<FONT 
  face="Times New Roman">Fruit</FONT>用的历史表是<FONT 
  face="Times New Roman">[12][64]</FONT>的，前一个指标代表兵种，后一个指标代表目标格。 
  <DT>　 
  <DT>　　尽管历史表处理起来非常简单，笔者也不打算列出操作历史表的代码，但是历史表中出现的问题远不止以上这几点。 
  <DT>　　很重要的一点是：历史表受置换表和迭代加深的影响很大。根结点做浅一层搜索时，历史表中已经记录了丰富的信息，因此深一层的搜索就可以充分利用这些信息来做更好的启发。反过来，如果根结点不做迭代加深，直接开始深层次的搜索，那么历史表启发的效率就会大幅度下降，因此这就引发出清空历史表的问题。 

  <DT>　　思考完一个着法时是否清空置换表，各个程序有不同的做法。<FONT 
  face="Times New Roman">ElephantEye</FONT>是彻底清空置换表的，因此下一次搜索时根结点总是迭代加深的。而是否清空历史表，则是更复杂的问题，它与是否清空置换表有关，<FONT 
  face="Times New Roman">ElephantEye</FONT>在清空置换表的同时也清空历史表。 
  <DT>　　如果每次搜索时不清空置换表，那么根结点浅层分值在置换表中已经找到，程序就直接做深层次的搜索，如果历史表是空的，那么历史表的启发效率就非常低了，因此不清空置换表而去清空历史表是不明智的做法，这样会导致“历史表信息丢失”。那么就不对历史表作处理吗？历史表中的数据会日积月累，而大部分数据是早期搜索时留下的，有可能开局时的历史着法信息被保留到了残局，这样当然更会影响历史表启发，导致“历史表信息污染”。 

  <DT>　　笔者提出一个“历史表衰减”的方法，程序每次思考一个新的局面时，如果不清空置换表，那么就对历史表中的每项数据做一个衰减，可以尝试衰减为原来的一半或<FONT 
  face="Times New Roman">1/4</FONT>，在“历史表信息丢失”和“历史表信息污染”之间作一个权衡。 
  <DT>　 
  <DT><FONT face=Arial size=4><STRONG>4.6 </STRONG></FONT><FONT face=楷体_GB2312 
  size=4><STRONG>总体着法顺序</STRONG></FONT> 
  <DT>　 
  <DT>　　以上我们主要介绍了四种启发算法，即吃子启发、置换表启发、杀手着法启发和历史表启发。现在我们要考虑如何把这四种算法结合起来。<FONT 
  face="Times New Roman">ElephantEye</FONT>和大多数程序一样，采用了以下的顺序： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>置换表启发； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>吃子启发<FONT 
  face="Times New Roman">(</FONT>之前生成所有吃子着法<FONT 
  face="Times New Roman">)</FONT>； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>杀手着法启发； 
  <DT>　　<FONT face="Times New Roman">(4) </FONT>历史表启发<FONT 
  face="Times New Roman">(</FONT>之前生成所有不吃子着法<FONT 
  face="Times New Roman">)</FONT>； 
  <DT>　　这个顺序用一个<FONT face="Times New Roman">MoveSortStruct</FONT>的结构来维护<FONT 
  face="Times New Roman">(</FONT>参阅<FONT 
  face="Times New Roman">&lt;movesort.cpp&gt;)</FONT>，使得搜索例程变得格外简单： 
  <DD>　 
  <DD>Move = MoveSort.Next(); 
  <DD>while (Move != NullMove) { 
  <DD>　MakeMove(Move); 
  <DD>　…… 
  <DD>　Move = MoveSort.Next(); 
  <DD>} 
  <DT>　 
  <DT>　　我们感兴趣的是<FONT face="Times New Roman">Next()</FONT>这个例程，它要求按照以上<FONT 
  face="Times New Roman">4</FONT>个不同的启发阶段来给出着法，但当某个阶段没有着法时，不跳出例程而直接进入下一个阶段<FONT 
  face="Times New Roman">(</FONT>最后一个阶段则直接给出<FONT 
  face="Times New Roman">NullMove)</FONT>。<FONT 
  face="Times New Roman">ElephantEye</FONT>和<FONT 
  face="Times New Roman">Crafty</FONT>、<FONT 
  face="Times New Roman">Fruit</FONT>等程序一样，用了不带<FONT 
  face="Times New Roman">break</FONT>的<FONT 
  face="Times New Roman">switch...case</FONT>这样一个炫技。<FONT 
  face="Times New Roman">MoveSortStruct</FONT>中有一个称为<FONT 
  face="Times New Roman">Phase(</FONT>阶段<FONT 
  face="Times New Roman">)</FONT>的变量，记录了当前的启发阶段，除了以上<FONT 
  face="Times New Roman">4</FONT>个阶段外，还包括两个： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>在吃子启发前，是生成吃子着法的阶段； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>在历史表启发前，是生成不吃子着法的阶段。 
  <DD>　 
  <DD>MoveStruct MoveSortStruct::Next(void) { 
  <DD>　switch (Phase) { 
  <DD>　case HASH_MOVE: 
  <DD>　　Phase = GEN_CAP_MOVES; 
  <DD>　　if (HashMove != NullMove) { 
  <DD>　　　return HashMove; 
  <DD>　　} 
  <DD>　　// 直接进入下一个"case"，下同。 
  <DD>　case GEN_CAP_MOVES: 
  <DD>　　Phase = CAP_MOVES; 
  <DD>　　MoveNum = GenCapMoves(MoveList); 
  <DD>　case CAP_MOVES: 
  <DD>　　i ++; 
  <DD>　　if (i &lt; MoveNum) { 
  <DD>　　　return MoveList[i]; 
  <DD>　　} 
  <DD>　case KILLER_MOVE: 
  <DD>　　Phase = GEN_NONCAP_MOVES; 
  <DD>　　if (KillerMove != NullMove &amp;&amp; LegalMove(KillerMove)) { 
  <DD>　　　return KillerMove; 
  <DD>　　} 
  <DD>　　…… 
  <DD>　} 
  <DD>} </DD></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_search.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>三<FONT face="Times New Roman">)</FONT>：搜索和置换表</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/eleeye_horizon.htm">中国象棋程序设计探索<FONT 
face="Times New Roman">(</FONT>五<FONT 
face="Times New Roman">)</FONT>：克服水平线效应</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>