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>