target=_blank><FONT 
  face="Times New Roman">Zobrist</FONT>鍵值</A>”一文中提到。如果你要實現“<A 
  href="http://www.elephantbase.net/computer/search_hashing.htm" 
  target=_blank>置換散列表</A>”，那么你應該先實現<FONT 
  face="Times New Roman">Zobrist</FONT>鍵值，這才能讓置換表得以實現。你需要對<FONT 
  face="Times New Roman">Zobrist</FONT>鍵值作處理，從搜索樹的當前局面往回找，看有沒有和當前局面相等的鍵值。 
  <DT>　　一個實現方法就是根據當前路線建立一個先進后出的堆棧，把鍵值加到歷史局面中。為了檢測重復，就要一層層地讀取堆棧，比較其中的鍵值，以確認當前鍵值是否已經存在于堆棧中。 

  <DT>　　沒有必要找遍整個列表，只要往回找，直到遇到進兵或吃子的著法，因為這些著法在棋局中是不可逆的。你不可能在最后一次吃子或進兵的前面找到重復局面。 
  <DT>　　這樣做看上去有點花時間，恐怕是吧，但是我相信有些程序就是這么做的。 
  <DT>　　在我寫國際象棋程序的早期，我在<FONT 
  face="Times New Roman">Usenet</FONT>上問了個關于散列技術的問題，得到<FONT 
  face="Times New Roman">Belle(</FONT>尤物<FONT 
  face="Times New Roman">)</FONT>作者<FONT face="Times New Roman">Ken 
  Thompson</FONT>的回答。<FONT color=#0000ff>【貝爾實驗室的</FONT><FONT 
  face="Times New Roman" color=#0000ff>Ken Thompson</FONT><FONT 
  color=#0000ff>，可能是影響力僅次于</FONT><FONT face="Times New Roman" color=#0000ff>John 
  Von Nouma(</FONT><FONT color=#0000ff>馮</FONT><FONT face="Times New Roman" 
  color=#0000ff>-</FONT><FONT color=#0000ff>諾依曼</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>的計算機科學家了，他是</FONT><FONT face="Times New Roman" 
  color=#0000ff>C</FONT><FONT color=#0000ff>語言的前身</FONT><FONT 
  face="Times New Roman" color=#0000ff>B</FONT><FONT 
  color=#0000ff>語言的發明者，</FONT><FONT face="Times New Roman" 
  color=#0000ff>Unix</FONT><FONT 
  color=#0000ff>系統的創立者之一，有關他在電腦國際象棋上作出的貢獻，可參閱譯文《</FONT><A 
  href="http://www.elephantbase.net/computer/history.htm" target=_blank><FONT 
  color=#0000ff>電腦國際象棋簡史</FONT></A><FONT 
  color=#0000ff>》。】</FONT>他告訴我他用置換表來檢測重復局面，他是這樣做的： 
  <DT>　　當探測置換表時，在表項中設置“打開”標志。這個標志一直被設置著，直到不再搜索這個局面為止，即從局面返回時才關閉。任何時刻打開的結點不是歷史局面就是在搜索樹的當前路線上，因此如果探索散列表時遇到一個打開的結點，就一定是前面發生過的局面。 

  <DT>　　這種方法具有數據結構上的優勢，因為這樣的數據結構在典型的國際象棋中都用到，但是這個思想有一些問題。當進入一個結點時，必須寫入散列項，因此需要使用“<A 
  href="http://www.elephantbase.net/computer/search_hashing.htm#replacement" 
  target=_blank>始終替換</A>” 的策略。對于<FONT 
  face="Times New Roman">Thompson</FONT>來說這不是問題，因為他的策略包含了“始終替換”的散列表，但是其他替換策略就無法使用這種方法。另一個問題出現在散列表項沖突的情況下，這個問題必須得到處理。當兩個局面具有相同的<FONT 
  face="Times New Roman">64</FONT>位鍵值時，我不討論散列鍵值的沖突問題。現在我討論過兩個局面共用一個散列項時，應該保留哪一個。如果兩個打開的結點要占用同一個散列項，除了要檢測第二個局面是否重復以外，要做什么并不清楚。可能這個問題要通過重新散列的策略來解決，但是這個方法跟散列表的主要用途沒有關系，所以要加這個功能比較麻煩<FONT 
  color=#0000ff>【重新散列</FONT><FONT face="Times New Roman" 
  color=#0000ff>(Re-Hashing)</FONT><FONT 
  color=#0000ff>是一個解決散列沖突的常用方法，但是在國際象棋程序中并不常用】</FONT>。最后一個問題就是如何適應多處理器搜索，因為很多線程可能會讀取一個散列表。遇到打開的結點時，可能根本就不是重復局面，因為它可能屬于另一個處理器的搜索路線。這個問題解決起來看上去很復雜。<FONT 
  color=#0000ff>【譯者認為，可以在散列項中記錄一個被打開的處理器號，每個處理器只對自己打開的結點作重復檢測。】</FONT> 
  <DT>　　另一個簡單的策略就是用一個很小的散列表<FONT color=#0000ff>【如果考慮</FONT><FONT 
  face="Times New Roman" color=#0000ff>50</FONT><FONT 
  color=#0000ff>回合限著</FONT><FONT face="Times New Roman" 
  color=#0000ff>(</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>)</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>200</FONT><FONT 
  color=#0000ff>個散列項就足夠了】</FONT>。進入結點時探測散列表，如果當前局面的<FONT 
  face="Times New Roman">Zobrist</FONT>鍵值已經在散列表里，就返回平局分值。否則就加入這個鍵值。當結點退出時，鍵值就刪除。這看上去很直觀，并且散列項的沖突處理起來很容易，因為散列表不是滿的，散列項以先進后出的順序存取，也不存在替換策略的問題。 

  <DT>　　我不愿說這個方法比其他方法好，因為畢竟有<FONT face="Times New Roman">Ken 
  Thompson</FONT>的方法。我的這個方法有一些問題，因為它需要靠額外的數據結構和額外的函數的支持。 
  <DT>　　當程序改成多處理器搜索時，這種方法有點令人擔憂，但是比起<FONT 
  face="Times New Roman">Thompson</FONT>的策略在這方面遇到的問題，我的這個問題看上去不那么嚴重。 
  <DT>　　如果你們想看這個第二散列表的策略，就去檢查<FONT 
  face="Times New Roman">Gerbil</FONT>的源程序。這里我不準備列出源代碼的示例，這只是實現上的問題罷了。 
  <DT><FONT 
  color=#0000ff>　　【中國象棋程序也可以通過探測散列表進行重復檢測，但是不能立即返回平局分值。當檢測出重復局面時，必須逐個分析兩次重復局面之間的著法，根據著法的性質來判定勝負，這一點比國際象棋麻煩得多。】</FONT> 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/repetition.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/repetition.htm</FONT></A> 

  <DT>　　譯者：黃晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:webmaster@elephantbase.net"><FONT 
  face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　類型：全譯加譯注 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://www.elephantbase.net/computer/other_pvcollect.htm">其他策略——主要變例的獲取</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/other_contempt.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>