?? 基本搜索方法——迭代加深.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.elephantbase.net/computer/search_iterative.htm -->
<HTML><HEAD><TITLE>基本搜索方法——迭代加深</TITLE>
<META http-equiv=Content-Language content=en-us>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content=FrontPage.Editor.Document name=ProgId>
<META content="zero-plus-one 110, default" name="Microsoft Theme">
<META content="tlb, default" name="Microsoft Border">
<META content="MSHTML 6.00.3790.536" name=GENERATOR><LINK href="../styles.css"
type=text/css rel=stylesheet></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"><EM>D</EM></FONT>層搜索所需要的時間取決于很多不確定的因素。在復雜的中局局面里，你可能不會搜索得很深，而在殘局中你可能會搜索得非常深，在某些王兵殘局里你可能會搜索<FONT
face="Times New Roman">100</FONT>多層<FONT color=#0000ff>【譯注：這也太夸張了點吧】</FONT>。
<DT> 有一個思想，就是一開始只搜索一層，如果搜索的時間比分配的時間少，那么搜索兩層，然后再搜索三層，等等，直到你用完時間為止。
<DT> 這足以保證很好地運用時間了。如果你可以很快搜索到一個深度，那么你在接下來的時間可以搜索得更深，或許你可以完成。如果局面比你想象的復雜，那么你不必搜索得太深，但是至少有合理的著法可以走了，因為你不太可能連1層搜索也完不成。
<DT> 這個思想稱為“迭代加深”<FONT face="Times New Roman">(Iterative
Deepening)</FONT>，因為你在迭代搜索，每次都比一次前一次加深<FONT
face="Times New Roman">1</FONT>層<FONT face="Times New Roman">(</FONT>多<FONT
face="Times New Roman">1</FONT>層沒有什么奧妙的，當然你可以試試多兩層，但是<FONT
face="Times New Roman">1</FONT>層比較好<FONT face="Times New Roman">)</FONT>。
<DT> 代碼如下：
<DT>
<DD>for (depth = 1; ; depth ++) {
<DD> val = AlphaBeta(depth, -INFINITY, INFINITY);
<DD> if (TimedOut()) {
<DD> break;
<DD> }
<DD>}
<DT>
<DT> 這是一個非常有效的搜索方法，你可能會感到吃驚。如果你能增強<FONT
face="Times New Roman">Alpha-Beta</FONT>使得它返回一條“<A
href="http://www.elephantbase.net/computer/other_pvcollect.htm"
target=_blank>主要變例</A>”，你可以用主要變例中的著法來做下一次迭代搜索。
<DT> 例如，一層的搜索顯示“<FONT face="Times New Roman">1.
e4</FONT>”是最好的著法，那么在做兩層的搜索時你先搜索“<FONT face="Times New Roman">1.
e4</FONT>”。如果返回“<FONT face="Times New Roman">1. e4
e5</FONT>”，那么你在做三層的搜索時仍舊先搜索這條路線。
<DT> 這樣做之所以有好的效果，是因為第一次搜索的線路通常是好的，而<FONT
face="Times New Roman">Alpha-Beta</FONT>對著法的順序特別敏感。如果著法順序很壞，那么在國際象棋中你的“<A
href="http://www.elephantbase.net/computer/search_alphabeta.htm#branching factor"
target=_blank>分枝因子</A>”將接近<FONT
face="Times New Roman">35</FONT>。如果你的著法很好，那么分枝因子將接近于<FONT
face="Times New Roman">6</FONT>。前一次迭代的搜索函數得到的主要變例通常是非常好的著法。
<DT> 迭代加深的思想給了你一個簡單的方法，它可以在時間用完時中斷搜索，并且會提高你的搜索效率。
<DT><FONT color=#0000ff> 【有可能的話，你可以把檢測超時的程序做到“</FONT><FONT
face="Times New Roman" color=#0000ff>AlphaBeta</FONT><FONT
color=#0000ff>”函數里去，而“</FONT><FONT face="Times New Roman"
color=#0000ff>TimeOut</FONT><FONT color=#0000ff>”只是由“</FONT><FONT
face="Times New Roman" color=#0000ff>AlphaBeta</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>
<DT> 原文：<A href="http://www.seanet.com/~brucemo/topics/iterative.htm"
target=_blank><FONT
face="Times New Roman">http://www.seanet.com/~brucemo/topics/iterative.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_alphabeta.htm">基本搜索方法——<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索</A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/search_hashing.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 + -