?? 基本搜索方法——置換表.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/search_hashing.htm -->
<HTML><HEAD><TITLE>基本搜索方法——置換表</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2817" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——置換表_files/background.gif>
<DL dir=ltr>
<DIV align=center>
<CENTER>
<DT>《對弈程序基本技術》專題 </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">Bruce Moreland (</FONT><A
href="mailto:brucemo@seanet.com"><FONT
face="Times New Roman">brucemo@seanet.com</FONT></A><FONT
face="Times New Roman">) / </FONT>文 </CENTER></DT></DIV>
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>一個多功能的數據結構</STRONG></FONT>
<DT>
<DT> 國際象棋的搜索樹可以用圖來表示，而置換結點可以引向以前搜索過的子樹上。置換表可以用來檢測這種情況，從而避免重復勞動。如果“<FONT
face="Times New Roman">1. e4 d6 2. d4</FONT>”以后的局面已經搜索過了，那就沒有必要再搜索“<FONT
face="Times New Roman">1. d4 d6 2. e4</FONT>”以后的局面了。
<DT> 這個原因可能鼓舞著早期的電腦國際象棋程序的設計師們，而現在事實上這還是置換表的次要用途。在某些局面，例如在沒有通路兵的王兵殘局中，檢查到的置換的數量是驚人的，以至于搜索可以在短達時間內達到很深的深度。
<DT> 省去重復的工作，這是置換表的一大特色，但是在一般的中局局面里，置換表的另一個作用更為重要。每個散列項里都有局面中最好的著法，我在“<A
href="http://www.elephantbase.net/computer/search_iterative.htm"
target=_blank>迭代加深</A>”這一章里解釋過，首先搜索好的著法可以大幅度提高搜索效率。因此如果你在散列項里找到最好的著法，那么你首先搜索這個著法，這樣會改進你的著法順序，減少分枝因子，從而在短的時間內搜索得更深。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>實現</STRONG></FONT>
<DT>
<DT> 主置換表是一個散列數組，每個散列項看上去像這樣：
<DD>
<DD>#define hashfEXACT 0
<DD>#define hashfALPHA 1
<DD>#define hashfBETA 2
<DD>typedef struct tagHASHE {
<DD> U64 key;
<DD> int depth;
<DD> int flags;
<DD> int value;
<DD> MOVE best;
<DD>} HASHE;
<DD>
<DT> 這個散列數組是以“<A
href="http://www.elephantbase.net/computer/struct_zobrist.htm"
target=_blank><FONT
face="Times New Roman">Zobrist</FONT>鍵值</A>”為指標的。你求得局面的鍵值，除以散列表的項數得到余數，這個散列項就代表該局面。由于很多局面都有可能跟散列表中同一項作用，因此散列項需要包含一個校驗值，它可以用來確認該項就是你要找的。通常校驗值是一個<FONT
face="Times New Roman">64</FONT>位的數，也就是上面那個例子的第一個域。
<DT> 你從搜索中得到結果后，要保存到散列表中。如果你打算用散列表來避免重復工作，那么重要的是記住搜索有多深。如果你在一個結點上搜索了<FONT
face="Times New Roman">3</FONT>層，后來又打算做<FONT
face="Times New Roman">10</FONT>層搜索，你就不能認為散列項里的信息是準確的。因此子樹的搜索深度也要記錄。
<DT> 在<FONT face="Times New Roman">Alpha-Beta</FONT>搜索中，你很少能得到搜索結點的準確值。<FONT
face="Times New Roman">Alpha</FONT>和<FONT
face="Times New Roman">Beta</FONT>的存在有助你裁剪掉沒有用的子樹，但是用<FONT
face="Times New Roman">Alpha-Beta</FONT>有個小的缺點，你通常不會知道一個結點到底有多壞或者有多好，你只是知道它足夠壞或足夠好，從而不需要浪費更多的時間。
<DT> 當然，這就引發了一個問題，散列項里到底要保存什么值，并且當你要獲取它時怎樣來做。答案是儲存一個值，另加一個標志來說明這個值是什么含義。在我上面的例子中，比方說你在評價域中保存了<FONT
face="Times New Roman">16</FONT>，并且在標志域保存了“<FONT
face="Times New Roman">hashfEXACT</FONT>”，這就意味著該結點的評價是準確值<FONT
face="Times New Roman">16</FONT>；如果你在標志域中保存了“<FONT
face="Times New Roman">hashfALPHA</FONT>”，那么結點的值最多是<FONT
face="Times New Roman">16</FONT>；如果保存了“<FONT
face="Times New Roman">hashfBETA</FONT>”，這個值就至少是<FONT
face="Times New Roman">16</FONT>。
<DT> 當你在搜索中遇到特定情況時，很容易決定評價和標志應該保存哪些內容。然而避免錯誤是非常重要的，散列表是非常容易犯錯誤的，而且一旦犯下錯誤就很難捕捉出來。
<DT> 我的散列項的最后一個域，保存著上次搜索到這個局面時的最佳著法。有時我沒有得到最佳著法，比如任何低出邊界的情況<FONT
face="Times New Roman">(</FONT>返回一個小于或等于<FONT
face="Times New Roman">Alpha</FONT>的值<FONT
face="Times New Roman">)</FONT>，而其他情況必定有最佳著法，比如高出邊界的情況<FONT
face="Times New Roman">(</FONT>返回一個大于或等于<FONT
face="Times New Roman">Beta</FONT>的值<FONT
face="Times New Roman">)</FONT>。<FONT
color=#0000ff>【譯注：只有葉子結點才沒有最佳著法，即便是</FONT><FONT face="Times New Roman"
color=#0000ff>Alpha</FONT><FONT
color=#0000ff>結點，所有的著法都是差的，也應該從中找一個最好的著法，它對更深一層的搜索會帶來很大的好處。】</FONT>
<DT> 如果找到最佳著法，那么它應該首先被搜索。
<DT> 下面是示范程序，是根據<FONT
face="Times New Roman">Alpha-Beta</FONT>函數修改的，改動的地方用醒目的字標出：
<DT>
<DD>int AlphaBeta(int depth, int alpha, int beta) {
<DD><FONT color=#ff0000> int hashf = hashfALPHA;</FONT>
<DD><FONT color=#ff0000> if ((val = ProbeHash(depth, alpha, beta)) !=
valUNKNOWN) {</FONT>
<DD><FONT color=#ff0000> // </FONT><FONT
color=#0000ff>【valUNKNOWN必須小于-INFINITY或大于INFINITY，否則會跟評價值混淆。】</FONT>
<DD> return val;
<DD> }
<DD> if (depth == 0) {
<DD> val = Evaluate();
<DD><FONT color=#ff0000> RecordHash(depth, val, hashfEXACT);</FONT>
<DD> return val;
<DD> }
<DD> GenerateLegalMoves();
<DD> while (MovesLeft()) {
<DD> MakeNextMove();
<DD> val = -AlphaBeta(depth - 1, -beta, -alpha);
<DD> UnmakeMove();
<DD> if (val >= beta) {
<DD><FONT color=#ff0000> RecordHash(depth, beta, hashfBETA);</FONT>
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD><FONT color=#ff0000> hashf = hashfEXACT;</FONT>
<DD> alpha = val;
<DD> }
<DD> }
<DD><FONT color=#ff0000> RecordHash(depth, alpha, hashf);</FONT>
<DD> return alpha;
<DD>}
<DT>
<DT> 以下就是兩個新的函數的代碼：
<DD>
<DD>int ProbeHash(int depth, int alpha, int beta) {
<DD> HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
<DD> if (phashe->key == ZobristKey()) {
<DD> if (phashe->depth >= depth) {
<DD> if (phashe->flags == hashfEXACT) {
<DD> return phashe->val;
<DD> }
<DD> if ((phashe->flags == hashfALPHA) && (phashe->val <=
alpha)) {
<DD> return alpha;
<DD> }
<DD> if ((phashe->flags == hashfBETA) && (phashe->val >=
beta)) {
<DD> return beta;
<DD> }
<DD> }
<DD> RememberBestMove();
<DD> }
<DD> return valUNKNOWN;
<DD>}
<DD>
<DD>void RecordHash(int depth, int val, int hashf) {
<DD> HASHE *phashe = &hash_table[ZobristKey() % TableSize()];
<DD> phashe->key = ZobristKey();
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -