⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 基本搜索方法——迭代加深.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 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 + -