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

📄 高级搜索方法——主要变例搜索.htm

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0053)http://www.elephantbase.net/computer/advanced_pvs.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>
  <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>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DT><FONT face=楷体_GB2312 size=5><STRONG>对</STRONG></FONT><FONT face=Arial 
  size=5><STRONG>Alpha-Beta</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>的改进</STRONG></FONT> 
  <DT>　 
  <DT>　　主要变例搜索<FONT face="Times New Roman">(PVS, Principal Variation 
  Search)</FONT>是提高“<A 
  href="http://www.elephantbase.net/computer/search_alphabeta.htm" 
  target=_blank><FONT face="Times New Roman">Alpha-Beta</FONT></A>”算法效率的一种方法。 
  <DT>　　在<FONT face="Times New Roman">Alpha-Beta</FONT>搜索中，任何结点都属于以下三种类型： 
  <DT>　　<FONT face="Times New Roman">1. Alpha</FONT>结点。每个搜索都会得到一个小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值，这就意味着这里没有一个着法是好的，可能是因为这个局面对于要走的一方太坏了。 
  <DT>　　<FONT face="Times New Roman">2. Beta</FONT>结点。至少一个着法会返回大于或等于<FONT 
  face="Times New Roman">Beta</FONT>的值。 
  <DT>　　<FONT face="Times New Roman">3. </FONT>主要变例<FONT 
  face="Times New Roman">(PV)</FONT>结点。有一个或多个着法会返回大于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值<FONT 
  face="Times New Roman">(</FONT>即<FONT face="Times New Roman">PV</FONT>着法<FONT 
  face="Times New Roman">)</FONT>，但是没有着法会返回大于或等于<FONT 
  face="Times New Roman">Beta</FONT>的值。 
  <DT>　　有些时候你可以很早地判断出你要处理的是哪类结点。如果你搜索的第一个着法高出边界<FONT 
  face="Times New Roman">(</FONT>返回一个大于或等于<FONT 
  face="Times New Roman">Beta</FONT>的值<FONT 
  face="Times New Roman">)</FONT>，那么很明显你得到<FONT 
  face="Times New Roman">Beta</FONT>结点。如果低出边界<FONT 
  face="Times New Roman">(</FONT>返回一个小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值<FONT 
  face="Times New Roman">)</FONT>，假设你的着法顺序非常好，那么你有可能得到<FONT 
  face="Times New Roman">Alpha</FONT>结点。如果返回值在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间，你可能得到<FONT 
  face="Times New Roman">PV</FONT>结点。 
  <DT>　　当然，有两种情况你可能会判断错误。当你高出边界时，你返回<FONT 
  face="Times New Roman">Beta</FONT>，因此你不会犯错误，但是如果第一个着法低出边界或者是<FONT 
  face="Times New Roman">PV</FONT>着法时，仍然有可能在下一个着法得到更高的值。 
  <DT>　　主要变例搜索作了假设，如果你在搜索一个结点时找到一个<FONT 
  face="Times New Roman">PV</FONT>着法，那么你就得到<FONT 
  face="Times New Roman">PV</FONT>结点。也就是说假设你的着法排序已经足够好了，使得你不必在其余的着法中找更好的<FONT 
  face="Times New Roman">PV</FONT>着法或者高出边界的着法<FONT 
  face="Times New Roman">(</FONT>这就会使结点变成<FONT 
  face="Times New Roman">Beta</FONT>结点<FONT face="Times New Roman">)</FONT>。 
  <DT>　　你找到一个着法其值在<FONT face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间，那么对其余的着法，搜索的目标就是证明他们都是坏的。跟要搜索出更好的着法相比，这种搜索也许要快一些。 

  <DT>　　如果这个算法发现判断是错的，即其中一个后续着法比第一个<FONT 
  face="Times New Roman">PV</FONT>着法好，那么它会被再一次搜索，这次使用正常的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索方法。这种情况有时会发生，这样就浪费时间了，但是这些时间通常不会超过面所说的“证明是坏着法”所节约下来的时间。 

  <DT>　　算法如下，是从<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法改过来的，改过的地方用醒目的字标出： 
  <DD>　 
  <DD>int AlphaBeta(int depth, int alpha, int beta) { 
  <DD><FONT color=#ff0000>　BOOL fFoundPv = FALSE;</FONT> 
  <DD>　if (depth == 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD><FONT color=#ff0000>　　if (fFoundPv) {</FONT> 
  <DD><FONT color=#ff0000>　　　val = -AlphaBeta(depth - 1, -alpha - 1, 
  -alpha);</FONT> 
  <DD><FONT color=#ff0000>　　　if ((val &gt; alpha) &amp;&amp; (val &lt; beta)) { 
  // 检查失败</FONT> 
  <DD><FONT color=#ff0000>　　　　val = -AlphaBeta(depth - 1, -beta, -alpha);</FONT> 

  <DD><FONT color=#ff0000>　　　}</FONT> 
  <DD><FONT color=#ff0000>　　} else</FONT> 
  <DD>　　　val = -AlphaBeta(depth - 1, -beta, -alpha); 
  <DD>　　} 
  <DD>　　UnmakeMove(); 
  <DD>　　if (val &gt;= beta) { 
  <DD>　　　return beta; 
  <DD>　　} 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD><FONT color=#ff0000>　　　fFoundPv = TRUE;</FONT> 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　算法的核心部分就是函数中间醒目的“<FONT 
  face="Times New Roman">if</FONT>”块中的内容。如果没有找到<FONT 
  face="Times New Roman">PV</FONT>结点，“<FONT 
  face="Times New Roman">AlphaBeta()</FONT>”函数就正常调用，如果找到了一个，那么情况就变了。不是用常规的窗口<FONT 
  face="Times New Roman">(Alpha, Beta)</FONT>，而是用<FONT 
  face="Times New Roman">(Alpha, Alpha + 1)</FONT>来搜索。这样做的前提是，搜索必须返回小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值，如果确实这样，那么把窗口的上面部分去掉就会导致更多的截断。当然，如果前提是错的，返回值是<FONT 
  face="Times New Roman">Alpha + 1</FONT>或更高，那么搜索必须用宽的窗口重做。 
  <DT>　　据报道<FONT face="Times New Roman">PVS</FONT>可以提高<FONT 
  face="Times New Roman">10%</FONT>的效率。我没有试图检测<FONT 
  face="Times New Roman">PVS</FONT>用在我的程序里到底提高了多少，但是确实提高了，所以我用了这个算法。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>搜索不稳定性的问题</STRONG></FONT> 
  <DT>　 
  <DT>　　如果你用<FONT face="Times New Roman">(Alpha, Alpha + 
  1)</FONT>这个窗口去做搜索，返回值超过了窗口<FONT face="Times New Roman">(</FONT>但是没有超过<FONT 
  face="Times New Roman">Beta)</FONT>，你就必须重新搜索。你认为重新搜索的值必定在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之间，但是恐怕不一定是。这很有可能是由“<A 
  href="http://www.elephantbase.net/computer/advanced_instability.htm" 
  target=_blank>搜索的不稳定性</A>”引起的，我会在别的章节中讨论这个问题。 
  <DT>　　上面写的那个程序对这个情况作了防御，并对这种情况的发生作了正确的处理。如果你要使用这个程序并且作一些改动，就要特别当心你的搜索是否总是稳定的。如果你得到不期望得到的返回值，就必须采取措施避免让程序陷入故障。 

  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/pvs.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/pvs.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_aspiration.htm">高级搜索方法——期望窗口</A> 

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