?? 基本搜索方法——簡介(三).htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/search_intro3.htm -->
<HTML><HEAD><TITLE>基本搜索方法——簡介(三)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——簡介(三)_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT size=3>《對弈程序基本技術》專題</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>散列技術和著法排序</FONT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">David Eppstein */</FONT>文
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">* </FONT>加州愛爾文大學<FONT
face="Times New Roman">(UC Irvine)</FONT>信息與計算機科學系 </CENTER></DT></DIV>
<DT>
<DT> 我還沒有講完<FONT
face="Times New Roman">Alpha-Beta</FONT>呢，因為我的偽代碼里包含神秘的“排序著法”還沒有解釋，暫時先扔在一邊，在講完散列技術后，我將繼續這部分內容。
<DT> 散列技術的思想非常簡單，很多棋類會出現“置換”的著法，即著法順序的不同會導致相同的局面。例如在國際象棋中，開局走“<FONT
face="Times New Roman">1. d4 Nf6 2. c4</FONT>”和“<FONT
face="Times New Roman">1. c4 Nf6 2. d4</FONT>”都會導致一樣的局面<FONT
face="Times New Roman">(</FONT>稱為印度防御<FONT
face="Times New Roman">)</FONT>，白方兩次進兵可以按不同的順序走。再看一個更加復雜置換：“<FONT
face="Times New Roman">1. e4 c6 2. d4 d5 3. ed Qxd5 4. Nc3 Qd6</FONT>”<FONT
face="Times New Roman">(</FONT>卡羅<FONT
face="Times New Roman">-</FONT>卡恩防御<FONT
face="Times New Roman">)</FONT>，“<FONT face="Times New Roman">1. e4 d5 2. ed
Qxd5 3. Nc3 Qd6 4. d4 c6</FONT>”<FONT
face="Times New Roman">(</FONT>斯堪的那維亞防御<FONT
face="Times New Roman">)</FONT>，以及“<FONT face="Times New Roman">1. e4 Nf6 2.
e5 Ng8 3. d4 d6 4. ed Qxd6 5.Nc3 c6</FONT>”<FONT
face="Times New Roman">(</FONT>阿廖欣防御<FONT
face="Times New Roman">)</FONT>都會在走不同的步數后到達相同的局面。
<DT> 因為換位，相同的局面能在<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索樹的很多位置上找到。如果有一種數據結構能夠保存以前找過的每一個位置，那么我們不必重新搜索，取而代之的是查找局面。但是有兩個困難擺在面前，一是我們沒有足夠的存儲器來存放所有搜索過的局面，二是查找速度要足夠快以至于超過搜索的時間。幸運的是，找不到已經搜索過的局面也沒關系，再搜索一遍就是了，因為畢竟這種情況不會經常發生。
<DT> 這種數據結構就是“散列表”<FONT face="Times New Roman">(Hash
Tables)</FONT>，一個很大的數組，大到不超出物理存儲器為止<FONT
face="Times New Roman">(</FONT>不要擴展到虛擬存儲器，否則會非常慢的<FONT
face="Times New Roman">)</FONT>。
<DT>
<DD>struct {
<DD> long checksum; // long long 可能會更好
<DD> int depth;
<DD> enum { exact, lower_bound, upper_bound } entry_type;
<DD> double eval;
<DD>} hashtable[HASH_TABLE_SIZE]; //<FONT
color=#0000ff>【譯注：完整的散列表還應記錄最佳著法。】</FONT>
<DT>
<DT> 對于每一個需要搜索的局面，先計算散列值<FONT
face="Times New Roman"><EM>x</EM></FONT>作為散列表的指標，另計算散列值<FONT
face="Times New Roman"><EM>y</EM></FONT>來檢查這個局面是否是所要找的局面。
<DT> 在搜索一個局面前，先去找 <FONT
face="Times New Roman">hashtable[<EM>x</EM>]</FONT>，如果 <FONT
face="Times New Roman">hashtable[<EM>x</EM>].checksum ==
<EM>y</EM></FONT>，<FONT
face="Times New Roman">hashtable[<EM>x</EM>].entry_type == exact</FONT>，并且
<FONT face="Times New Roman">hashtable[<EM>x</EM>].depth
</FONT>不比現在需要搜索的深度淺，那么就可以返回 <FONT
face="Times New Roman">hashtable[<EM>x</EM>].eval</FONT>。
<DT> 每搜索完一個局面，就把散列值<FONT
face="Times New Roman"><EM>y</EM></FONT>、當前搜索的深度和搜索的評分保存到 <FONT
face="Times New Roman">hashtable[<EM>x</EM>] </FONT>里。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>如何計算散列值？</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">Zobrist </FONT>散列技術<FONT
face="Times New Roman">(</FONT>已經在“重復檢測”這個話題中探討過了<FONT
face="Times New Roman">)</FONT>是指：在下棋以前<FONT
face="Times New Roman">(</FONT>但在程序里<FONT
face="Times New Roman">)</FONT>產生隨機數組<FONT face="Times New Roman">Z[square,
piecetype]</FONT>。棋盤的散列值就是棋盤上各個棋子的<FONT face="Times New Roman">Z[s,
p]</FONT>相加，再加上一些額外的信息如是否能王車易位等。通常求和被“異或”運算所代替，因為它操作方便且快速，但算術加法會更好些。走完一步棋后，不要把散列值整個都算一遍，只要減去原來位置的棋子和格子值，并加上新位置的棋子和格子值，就實現了散列值的更新。這個技術同時適用于散列值<FONT
face="Times New Roman"><EM>x</EM></FONT>和校驗值<FONT
face="Times New Roman"><EM>y</EM>(</FONT>但要使用不同的隨機數表<FONT
face="Times New Roman">)</FONT>。
<DT> 在散列技術中，另有一些十分有用的訣竅：
<DT> <FONT face="Times New Roman">(1)
</FONT>在走完一步后，不要把散列表清空，這樣不但浪費時間，而且原來的內容或許對后面的走法有用。<FONT
color=#0000ff>【這里指的是電腦完成整個局面的搜索，走完一步后不需要清空散列表，電腦進行下一回合時，上一回合留下的信息或許有用。當然，是否清空散列表不能一概而論，還要取決于散列表的覆蓋策略，以后的文章將談到這個問題。】</FONT>
<DT> <FONT face="Times New Roman">(2) </FONT>如果相同的局面出現在搜索樹的不同深度中<FONT
face="Times New Roman">(</FONT>例如上面講到置換時的第二個例子<FONT
face="Times New Roman">)</FONT>，那么你可能得到比預期更深的搜索結果，這樣會非常好。<FONT
color=#0000ff>【譯者把這個現象稱為“搜索樹的遷移式延伸”，當這種情況出現在殘局時反而不是好事，因為你有可能找到一步殺棋，而它卻不是最短路線，你就停止了搜索。后面的文章會說明一個問題，當你搜索到殺棋時，如果你的著法不是最短路線，那么在實戰中可能明知殺棋但怎么也殺不了。】</FONT>
<DT> <FONT face="Times New Roman">(3)
</FONT>不要在搜索樹靠近葉子的局面上用散列技術，因為這些局面太多了<FONT
face="Times New Roman">(</FONT>它們可能取代別的更重要的局面<FONT
face="Times New Roman">)</FONT>，并且不去搜索這些局面也不會省掉很多時間。<FONT
color=#0000ff>【如果把搜索分為完全搜索和靜態搜索兩個階段，那么靜態搜索的結果是肯定不寫入散列表的，因為靜態搜索的分枝因子非常小(只考慮吃子著法)，所以查找散列表的時間或許比搜索的時間還長。在完全搜索中，這條法則是就“始終覆蓋”這一策略而言的，若使用“深度優先”策略則無所謂。】</FONT>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>散列技術如何跟</STRONG></FONT><FONT
face=Arial size=5><STRONG>Alpha-Beta</STRONG></FONT><FONT face=楷體_GB2312
size=5><STRONG>聯系起來？</STRONG></FONT>
<DT>
<DT> 國際象棋程序中很多的錯誤都跟散列技術有關，原因是它們要跟<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索聯系起來，但你無法繞開這個話題，因為散列技術和<FONT
face="Times New Roman">Alpha-Beta</FONT>都是非常有效的搜索方法。現在重新來看<FONT
face="Times New Roman">Alpha-Beta</FONT>，當你在一個局面中調用 <FONT
face="Times New Roman">alphabeta(depth, alpha, beta) </FONT>時，可能有三種情況發生：<FONT
face="Times New Roman">(1) </FONT>高出邊界<FONT face="Times New Roman">(Fail
High)</FONT>，即返回評分至少是<FONT face="Times New Roman">Beta</FONT>，但到底多少卻不知道；<FONT
face="Times New Roman">(2) </FONT>低出邊界<FONT face="Times New Roman">(Fail
Low)</FONT>，即返回評分最多是<FONT face="Times New Roman">Alpha</FONT>，但到底多少也不知道；<FONT
face="Times New Roman">(3) </FONT>準確值，即返回評分在<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>之間。如果我們知道準確結果，那么散列表中只記錄準確評分，但是高出邊界和低出邊界的情況，仍然在以后的裁剪中有用。可以跟記錄準確評分一樣，散列表中也可以記錄這兩種情況的評分，“下界標志”<FONT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -