?? 基本搜索方法——置換表.htm

?? 象棋程序設(shè)計全資料集(介紹編寫象棋程序的方法思路）
?? HTM
?? 第 1 頁 / 共 2 頁
字號:
上一頁 12
  <DD>　phashe-&gt;best = BestMove(); 
  <DD>　phashe-&gt;val = val; 
  <DD>　phashe-&gt;hashf = hashf; 
  <DD>　phashe-&gt;depth = depth; 
  <DD>} 
  <DD>　 
  <DT>　　你所看到的代碼，并不像航天科學(xué)一樣準(zhǔn)確，而是很可能有錯誤的，而且細(xì)節(jié)上的問題我還沒有討論。如果你的程序中有錯誤，或許就是很嚴(yán)重的錯誤。 
  <DT><FONT color=#0000ff>　　【以上代碼有個速度上的瓶頸，即“</FONT><FONT face="Times New Roman" 
  color=#0000ff>ZobristKey() % TableSize()</FONT><FONT 
  color=#0000ff>”這個表達(dá)式。由于“電腦一做除法就成了傻瓜”，所以“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSize</FONT><FONT color=#0000ff>”最好是一個</FONT><FONT 
  face="Times New Roman" color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>的常量，只有當(dāng)除數(shù)是</FONT><FONT face="Times New Roman" 
  color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>時除法才可以由右移指令取代。最好的方法是設(shè)一個“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSizeMask</FONT><FONT color=#0000ff>”的變量：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>int TableSizeMask = TableSize() - 1;</FONT> 
  <DD><FONT color=#0000ff>HASHE *phashe = &amp;hash_table[ZobristKey() &amp; 
  TableSizeMask];</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　而這里“</FONT><FONT face="Times New Roman" 
  color=#0000ff>TableSize()</FONT><FONT color=#0000ff>”也必須是</FONT><FONT 
  face="Times New Roman" color=#0000ff>2<SUP><EM>n</EM></SUP></FONT><FONT 
  color=#0000ff>。正是這個道理，在很多可以設(shè)定置換表大小的國際象棋程序中，允許的設(shè)定值總是呈倍數(shù)增長的，要么是</FONT><FONT 
  face="Times New Roman" color=#0000ff>3M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>6M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>12M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>24M</FONT><FONT color=#0000ff>等等</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>如果每個散列項(xiàng)有</FONT><FONT face="Times New Roman" 
  color=#0000ff>12</FONT><FONT color=#0000ff>字節(jié)</FONT><FONT 
  face="Times New Roman" color=#0000ff>)</FONT><FONT 
  color=#0000ff>，要么是</FONT><FONT face="Times New Roman" 
  color=#0000ff>4M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>8M</FONT><FONT 
  color=#0000ff>、</FONT><FONT face="Times New Roman" 
  color=#0000ff>16M</FONT><FONT color=#0000ff>、</FONT><FONT 
  face="Times New Roman" color=#0000ff>32M</FONT><FONT 
  color=#0000ff>等等</FONT><FONT face="Times New Roman" 
  color=#0000ff>(</FONT><FONT color=#0000ff>如果每個散列項(xiàng)有</FONT><FONT 
  face="Times New Roman" color=#0000ff>16</FONT><FONT 
  color=#0000ff>字節(jié)</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　 
  <DT><A name=replacement></A><FONT face=楷體_GB2312 
  size=5><STRONG>替換策略</STRONG></FONT> 
  <DT>　 
  <DT>　　最主要的細(xì)節(jié)就包括，什么時候該覆蓋散列項(xiàng)。在上面的例子中，我用了“始終替換”的策略，即簡單地覆蓋已經(jīng)存在的值。這或許不是最好的策略，事實(shí)上已經(jīng)有大量的工作試圖找出哪個策略是最好的。 

  <DT>　　另一個策略是“同樣深度或更深時替換”。除非新局面的深度大于或等于散列表中已經(jīng)有的值，否則已經(jīng)存在的結(jié)點(diǎn)將被保留。 
  <DT>　　還有很多試驗(yàn)的余地。<FONT face="Times New Roman">1994</FONT>年我在<FONT 
  face="Times New Roman">Usenet(</FONT>新聞組網(wǎng)絡(luò)系統(tǒng)<FONT 
  face="Times New Roman">)</FONT>的新聞組<FONT 
  face="Times New Roman">rec.games.chess(</FONT>如今是<FONT 
  face="Times New Roman">rec.games.chess.computer)</FONT>上問了這個問題，得到了<FONT 
  face="Times New Roman">Ken Thompson</FONT>的答復(fù)。 
  <DT>　　他的回答是使用兩個散列表。一個使用“始終替換”策略，另一個使用“同樣深度或更深時替換”。當(dāng)你做試探時，兩個散列表都去試探，如果其中一個可以產(chǎn)生截斷，那就可以了。如果兩者都不能產(chǎn)生截斷，那么你可能至少得到一個最佳著法，實(shí)際上更多的可能是得到兩個不同的著法，兩者都應(yīng)該首先<FONT 
  face="Times New Roman">(</FONT>或第二個<FONT face="Times New Roman">)</FONT>嘗試。 
  <DT>　　記錄的時候，你只要簡單地根據(jù)替換策略來執(zhí)行。 
  <DT>　　如果你使用“同樣深度或更深時替換”的策略，那么你的散列表可能最終會被過期的但很深的結(jié)點(diǎn)所占滿。解決方案就是每次你走棋時都清除散列表，或者在散列項(xiàng)中加入“順序”這個域，從而使這個策略變成變成“同樣深度，或更深，或原來是舊的搜索，才替換”。 

  <DT>　　我在我的程序<FONT face="Times New Roman">Ferret</FONT>中使用了<FONT 
  face="Times New Roman">Thompson</FONT>的策略，并且運(yùn)行得很好。另一個程序<FONT 
  face="Times New Roman">Gerbil</FONT>也使用這個策略，你可以去看它的源代碼。 
  <DT><FONT color=#0000ff>　　【根據(jù)譯者研究的結(jié)果，只用“深度優(yōu)先覆蓋”策略</FONT><FONT 
  face="Times New Roman" color=#0000ff>(</FONT><FONT 
  color=#0000ff>即“同樣深度或更深時替換”</FONT><FONT face="Times New Roman" 
  color=#0000ff>)</FONT><FONT 
  color=#0000ff>，效果會比“始終替換”好得多，而代碼則并不復(fù)雜，只有醒目的部分是新增的：</FONT> 
  <DD>　 
  <DD><FONT color=#0000ff>void RecordHash(int depth, int val, int hashf) 
  {</FONT> 
  <DD><FONT color=#0000ff>　HASHE *phashe = &amp;hash_table[ZobristKey() &amp; 
  (TableSize() - 1)];</FONT> 
  <DD><FONT color=#ff0000>　if (phashe-&gt;hashf != hashfEMPTY &amp;&amp; 
  phashe-&gt;depth &gt; depth) {</FONT> 
  <DD><FONT color=#ff0000>　　return;</FONT> 
  <DD><FONT color=#ff0000>　}</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;key = ZobristKey();</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;best = BestMove();</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;val = val;</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;hashf = hashf;</FONT> 
  <DD><FONT color=#0000ff>　phashe-&gt;depth = depth;</FONT> 
  <DD><FONT color=#0000ff>}</FONT> 
  <DT>　 
  <DT><FONT color=#0000ff>　　如果使用這個代碼，那么每走一步以前都必須把散列表中所有的標(biāo)志項(xiàng)置為“</FONT><FONT 
  face="Times New Roman" color=#0000ff>hashfEMPTY</FONT><FONT 
  color=#0000ff>”。】</FONT> 
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>不穩(wěn)定性的問題</STRONG></FONT> 
  <DT>　 
  <DT>　　當(dāng)你用置換表時，如果你允許搜索過程根據(jù)散列項(xiàng)來截斷，那就會產(chǎn)生另一個問題，你的搜索會受“<A 
  href="http://www.elephantbase.net/computer/advanced_instability.htm" 
  target=_blank>不穩(wěn)定性</A>”的捆擾。 
  <DT>　　不穩(wěn)定性至少是由以下因素引起的： 
  <DT>　　<FONT face="Times New Roman">1. </FONT>你可能在做<FONT 
  face="Times New Roman">6</FONT>層的搜索，但是如果你在散列項(xiàng)中得到<FONT 
  face="Times New Roman">10</FONT>層搜索的結(jié)果，就可能根據(jù)這個值來截斷。在后來的搜索中，這個散列項(xiàng)被覆蓋了，因此你在這個結(jié)點(diǎn)上得到了兩個不同的值。 

  <DT>　　<FONT face="Times New Roman">2. 
  Zobrist</FONT>鍵值無法記錄到達(dá)結(jié)點(diǎn)的線路，這個結(jié)點(diǎn)上不是每條線路都有相同結(jié)果的。如果某條線路遇到重復(fù)局面，那么散列項(xiàng)的值就會跟路線有關(guān)。因?yàn)橹貜?fù)局面會導(dǎo)致和局的分值，或者至少不一樣的分值。 

  <DT>　　就我所知，還沒有什么辦法能處理這些問題。 
  <DT><FONT color=#0000ff>　　【另外，如果搜索過程中找到殺棋，那么評價值會接近“</FONT><FONT 
  face="Times New Roman" color=#0000ff>INFINITY</FONT><FONT 
  color=#0000ff>”或“</FONT><FONT face=Symbol color=#0000ff>-</FONT><FONT 
  face="Times New Roman" color=#0000ff>INFINITY</FONT><FONT 
  color=#0000ff>”，此時記錄散列表時不能簡單地記錄這些評價值，在后面介紹的“</FONT><A 
  href="http://www.elephantbase.net/computer/other_winning.htm" 
  target=_blank><FONT color=#0000ff>勝利局面</FONT></A><FONT 
  color=#0000ff>”的處理中，會談到這個問題。】</FONT> 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/hashing.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/hashing.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/search_iterative.htm">基本搜索方法——迭代加深</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_intro1.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>
上一頁 12
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關(guān)標(biāo)簽

#程序設(shè)計 #程序 #編寫
?? 快捷鍵說明

復(fù)制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? 基本搜索方法——置換表.htm

?? 快捷鍵說明
