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

📄 高级搜索方法——期望窗口.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0060)http://www.elephantbase.net/computer/advanced_aspiration.htm -->
<HTML><HEAD><TITLE>高级搜索方法——期望窗口</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<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">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>　　期望窗口是对迭代加深的改进。迭代加深的最简单的实现方法是这样的： 
  <DD>　 
  <DD>for (depth = 1; ; depth ++) { 
  <DD>　val = AlphaBeta(depth, -INFINITY, INFINITY); 
  <DD>　if (TimedOut()) { 
  <DD>　　break; 
  <DD>　} 
  <DD>} 
  <DD>　 
  <DT>　　这里调用了一个“窗口”为正负无穷大的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索，以假定返回值可能是很大的正数或负数。 
  <DT>　　假设下一次迭代时，搜索的值不会比上一次有太多的变动，那么就可以对以上的程序作改进，代码如下： 
  <DD>　 
  <DD>#define valWINDOW 50 // <FONT 
  color=#0000ff>【译注：valWINDOW是窗口的半宽，在国际象棋中通常是半个兵的价值。】</FONT> 
  <DD>alpha = -INFINITY; 
  <DD>beta = INFINITY; 
  <DD>for (depth = 1; ; ) { 
  <DD>　val = AlphaBeta(depth, alpha, beta); 
  <DD>　if (TimedOut()) { 
  <DD>　　break; 
  <DD>　} 
  <DD>　if ((val &lt;= alpha) || (val &gt;= beta)) { 
  <DD>　　alpha = -INFINITY; 
  <DD>　　beta = INFINITY; 
  <DD>　　continue; 
  <DD>　} 
  <DD>　alpha = val - valWINDOW; 
  <DD>　beta = val + valWINDOW; 
  <DD>　depth ++; 
  <DD>} 
  <DT>　 
  <DT>　　这个代码有点烂，如果可能的话你可以把“<FONT 
  face="Times New Roman">continue</FONT>”前面的部分改一下试试。这个思想是用前一次<FONT 
  face="Times New Roman">Alpha-Beta</FONT>迭代的值来作用到这次的迭代中。大多数情况下你得到的返回值会在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间。如果没有，那么你可以尝试一个宽一些的窗口。 
  <DT>　　我的重新搜索并不那么有效，但是我相信你可以做得更好。一个很明显的思想是，如果返回值大于或等于<FONT 
  face="Times New Roman">Beta</FONT>，你就扩展<FONT 
  face="Times New Roman">Beta</FONT>，如果返回值小于等于<FONT 
  face="Times New Roman">Alpha</FONT>，你就扩展<FONT 
  face="Times New Roman">Alpha</FONT>，而不是我所做的<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>都扩展。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>搜索不稳定性的问题</STRONG></FONT> 
  <DT>　 
  <DT>　　这是你要小心搜索不稳定性的另一个地方。当我首次在我的国际象棋程序中加入期望窗口时，我设想如果返回值大于或等于<FONT 
  face="Times New Roman">Beta</FONT>，那么重新搜索的结果就应该得到更大的值。完全错了，我的程序陷入了非常严重的故障！下面是它的代码： 

  <DT>　 
  <DD>alpha = -INFINITY; 
  <DD>beta = INFINITY; 
  <DD>for (depth = 1; ; ) { 
  <DD>　val = AlphaBeta(depth, alpha, beta); 
  <DD>　if (TimedOut()) { 
  <DD>　　break; 
  <DD>　} 
  <DD>　if (val &lt;= alpha) { // 错！ 
  <DD>　　alpha = -INFINITY; 
  <DD>　　beta = val + 1; 　// <FONT color=#0000ff>【这行没有就对了，但效率会低很多。】</FONT> 
  <DD>　　continue; 
  <DD>　} 
  <DD>　if (val &gt;= beta) {　// 错！ 
  <DD>　　beta = INFINITY; 
  <DD>　　alpha = val - 1; 
  <DD>　　continue; 
  <DD>　} 
  <DD>　alpha = val - valWINDOW; 
  <DD>　beta = val + valWINDOW; 
  <DD>　depth++; 
  <DD>} 
  <DT>　 
  <DT>　　如果你能确认重新搜索会有结果，那么上面的代码会非常有效的。但是在我这里情况却是： 
  <DT>　　<FONT face="Times New Roman">1. </FONT>搜索<FONT 
  face="Times New Roman">(Alpha, Beta)</FONT>时高出边界； 
  <DT>　　<FONT face="Times New Roman">2. </FONT>重新搜索<FONT 
  face="Times New Roman">(Beta - 1, INFINITY)</FONT>时低出边界； 
  <DT>　　<FONT face="Times New Roman">3. </FONT>重新搜索<FONT 
  face="Times New Roman">(-INFINITY, Alpha + 1)</FONT>时高出边界； 
  <DT>　　<FONT face="Times New Roman">4. </FONT>等等，等等…… 
  <DT>　　无论如何你必须避免发生这种情况。 
  <DT>　 
  <DT><FONT 
  color=#0000ff>　　【译者研究认为，在用了后面要谈到的“主要变例搜索”以后，期望窗口就几乎没有作用了，因此很多程序都没有使用这个技术，尽管它的思想非常明显，看上去似乎可以起到好的效果。】</FONT> 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/aspiration.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/aspiration.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/advanced_nullmove.htm">高级搜索方法——空着裁剪</A> 

<LI>下一篇　<A 
href="http://www.elephantbase.net/computer/advanced_pvs.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 + -