?? 高級搜索方法——簡介(二).htm
字號:
face="Times New Roman">WIN </FONT>和 <FONT face="Times New Roman">-WIN</FONT>
的差的對數<FONT face="Times New Roman">)</FONT>。而<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>的思想則是用超出邊界的<FONT
face="Times New Roman">Alpha-Beta</FONT>對搜索進行控制：每次調用超出邊界的<FONT
face="Times New Roman">Alpha-Beta</FONT>就會返回一個值更接近于最終值，如果用這個搜索值作為下次測試的開始，我們最終會達到收斂。
<DD>
<DD>// MTD(f)
<DD>int test = 0;
<DD>for ( ; ; ) {
<DD> score = alphabeta(depth, test, test + 1);
<DD> if (test == score) {
<DD> break;
<DD> }
<DD> test = score;
<DD>}
<DT>
<DT><FONT
size=3> 不幸的是，它和散列表之間的復雜作用會導致這個過程陷入無限循環，所以必須加上額外的代碼，如果迭代次數太多而沒有收斂，就必須中止搜索。</FONT>
<DT><FONT size=3> </FONT><FONT face="Times New Roman"
size=3>MTD(<EM>f</EM>)</FONT><FONT size=3>的一個大的優勢在于我們可以簡化</FONT><FONT
face="Times New Roman" size=3>Alpha-Beta</FONT><FONT
size=3>搜索，因為它只需要兩個參數</FONT><FONT face="Times New Roman" size=3>(</FONT><FONT
size=3>深度和</FONT><FONT face="Times New Roman" size=3>Alpha)</FONT><FONT
size=3>而不是三個。</FONT><FONT
color=#0000ff>【據說這樣做可以提高并行計算的效率，遺憾的是譯者對并行計算一竅不通。】</FONT>
<DT><FONT color=#0000ff> 【為了對</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT
color=#0000ff>有更詳細的了解，譯者查閱了該算法的發明者</FONT><FONT face="Times New Roman"
color=#0000ff>Plaat</FONT><FONT color=#0000ff>的網站，他提供的</FONT><FONT
face="Times New Roman" color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT
color=#0000ff>代碼中用了兩個邊界，可以防止迭代過程中出現振蕩而不收斂的情況，代碼如下</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>原來是</FONT><FONT face="Times New Roman"
color=#0000ff>Pascal</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>)</FONT><FONT color=#0000ff>：</FONT>
<DD>
<DD><FONT color=#0000ff>int MTDF(int test, int depth) {</FONT>
<DD><FONT color=#0000ff> int score, beta, upperbound, lowerbound;</FONT>
<DD><FONT color=#0000ff> score = test;</FONT>
<DD><FONT color=#0000ff> upperbound = +INFINITY;</FONT>
<DD><FONT color=#0000ff> lowerbound = -INFINITY;</FONT>
<DD><FONT color=#0000ff> do {</FONT>
<DD><FONT color=#0000ff> beta = (score == lowerbound ? score + 1 :
score);</FONT>
<DD><FONT color=#0000ff> score = alphabeta(depth, beta - 1, beta);</FONT>
<DD><FONT color=#0000ff> (score < beta ? upperbound : lowerbound) =
score;</FONT>
<DD><FONT color=#0000ff> } while (lowerbound < upperbound);</FONT>
<DD><FONT color=#0000ff> return score;</FONT>
<DD><FONT color=#0000ff>}</FONT>
<DT>
<DT><FONT color=#0000ff> 而關于</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>的使用另有以下幾點技巧：</FONT>
<DT><FONT color=#0000ff> </FONT><FONT face="Times New Roman"
color=#0000ff>(1) </FONT><FONT
color=#0000ff>通常試探值并不一定設成零，而是用迭代加深的形式由淺一層的</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>搜索給出；</FONT>
<DT><FONT color=#0000ff> </FONT><FONT face="Times New Roman"
color=#0000ff>(2) </FONT><FONT color=#0000ff>局面評價得越粗糙，</FONT><FONT
face="Times New Roman" color=#0000ff>MTD(<EM>f</EM>)</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>10</FONT><FONT
color=#0000ff>，其他子力也相應比例降低，以提高</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>f</EM>)</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>
<DT><FONT color=#0000ff> </FONT><FONT face="Times New Roman"
color=#0000ff>(3) </FONT><FONT
color=#0000ff>零寬度窗口的搜索需要置換表的有力支持，因此稱為“用存儲器增強的試探驅動器”</FONT><FONT
face="Times New Roman" color=#0000ff>(Memory-enhanced Test Driver</FONT><FONT
color=#0000ff>，即</FONT><FONT face="Times New Roman"
color=#0000ff>MTD)</FONT><FONT color=#0000ff>，它只需要傳遞兩個參數</FONT><FONT
face="Times New Roman" color=#0000ff>(</FONT><FONT
color=#0000ff>深度</FONT><FONT face="Times New Roman"
color=#0000ff><EM>n</EM></FONT><FONT color=#0000ff>和試探值</FONT><FONT
face="Times New Roman" color=#0000ff><EM>f</EM>)</FONT><FONT
color=#0000ff>，故得名為</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>n</EM>,<EM>f</EM>)</FONT><FONT
color=#0000ff>，縮寫為</FONT><FONT face="Times New Roman"
color=#0000ff>MTD(<EM>f</EM>)</FONT><FONT color=#0000ff>。】</FONT>
<DT>
<DT><FONT face=Arial size=5><STRONG>PVS</STRONG></FONT>
<DT>
<DT> 或許最好的<FONT face="Times New Roman">Alpha-Beta</FONT>變體，要算是這些名稱了：負值偵察<FONT
face="Times New Roman">(NegaScout)</FONT>和主要變例搜索<FONT
face="Times New Roman">(Principal Variation Search</FONT>，簡稱<FONT
face="Times New Roman">PVS)</FONT>。這個思想就是當第一次迭代搜索時找到最好的值，那么<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索的效率最高。對著法列表進行排序，或者把最好的著法保存到散列表中，這些技術可能讓第一個著法成為最佳著法。如果真是如此，我們就可以假設其他著法不可能是好的著法，從而對它們快速地搜索過去。
<DT> 因此<FONT
face="Times New Roman">PVS</FONT>對第一個搜索使用正常的窗口，而后續搜索使用零寬度的窗口，來對每個后續著法和第一個著法作比較。只有當零窗口搜索失敗后才去做正常的搜索。
<DD>
<DD>// 主要變例搜索(超出邊界的版本)
<DD>int alphabeta(int depth, int alpha, int beta) {
<DD> move bestmove, current;
<DD> if (棋局結束 || depth <= 0) {
<DD> return eval();
<DD> }
<DD> move m = 第一個著法;
<DD> 執行著法 m;
<DD> current = -alphabeta(depth - 1, -beta, -alpha);
<DD> 撤消著法 m;
<DD> for (其余的每個著法 m) {
<DD> 執行著法 m;
<DD> score = -alphabeta(depth - 1, -alpha - 1, -alpha);
<DD> if (score > alpha && score < beta) {
<DD> score = -alphabeta(depth - 1, -beta, -alpha);
<DD> }
<DD> 撤消著法 m;
<DD> if (score >= current) {
<DD> current = score;
<DD> bestmove = m;
<DD> if (score >= alpha) {
<DD> alpha = score;
<DD> }
<DD> if (score >= beta) {
<DD> break;
<DD> }
<DD> }
<DD> }
<DD> return current;
<DD>}
<DT>
<DT> 這個算法跟<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>有個同樣的優勢，即搜索樹的大多數結點都以零寬度的窗口搜索，可以用雙參數的<FONT
face="Times New Roman">Alpha-Beta</FONT>。由于“<FONT face="Times New Roman">Beta
> Alpha + 1</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>
<DT>
<DT> 我自己的程序結合了期望搜索<FONT face="Times New Roman">(</FONT>用在整個搜索過程以外<FONT
face="Times New Roman">)</FONT>和<FONT
face="Times New Roman">PVS(</FONT>用在搜索過程內部<FONT
face="Times New Roman">)</FONT>。但是不同的棋類游戲不一樣，由于這些搜索不難實現，所以要在這些方法中進行選擇或調節參數，就必須對它們逐一實現并做一些試驗。它們都必須返回同樣的搜索值<FONT
face="Times New Roman">(</FONT>如果受散列表影響，那么至少是相近的值<FONT
color=#0000ff>【例如常規的</FONT><FONT face="Times New Roman"
color=#0000ff>Alpha-Beta</FONT><FONT color=#0000ff>搜索和超出邊界的</FONT><FONT
face="Times New Roman" color=#0000ff>Alpha-Beta</FONT><FONT
color=#0000ff>搜索，在使用散列表時可能會返回不同的值】</FONT><FONT
face="Times New Roman">)</FONT>，但搜索的結點數會不同。在你的棋類的典型局面中，能使搜索樹最小的方法則被采納。
<DT>
<DT> 原文：<A href="http://www.ics.uci.edu/~eppstein/180a/990202b.html"
target=_blank><FONT
face="Times New Roman">http://www.ics.uci.edu/~eppstein/180a/990202b.html</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/advanced_intro1.htm">高級搜索方法——簡介<FONT
face="Times New Roman">(</FONT>一<FONT face="Times New Roman">)</FONT></A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/advanced_quiescent.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>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -