基本搜索方法——alpha-beta搜索.htm

象棋程序设计全资料集(介绍编写象棋程序的方法思路）

  <DT>　　如果某个着法的结果大于<FONT face="Times New Roman">Alpha</FONT>但小于<FONT 
  face="Times New Roman">Beta</FONT>，那么这个着法就是走棋一方可以考虑走的，除非以后有所变化。因此<FONT 
  face="Times New Roman">Alpha</FONT>会不断增加以反映新的情况。有时候可能一个合理着法也不超过<FONT 
  face="Times New Roman">Alpha</FONT>，这在实战中是经常发生的，此时这种局面是不予考虑的，因此为了避免这样的局面，我们必须在博弈树的上一个层局面选择另外一个着法。 

  <DT>　　在第二个口袋里找到烂鱼就相当于超过了<FONT 
  face="Times New Roman">Beta</FONT>，如果口袋里没有烂鱼，那么考虑六盒装流行唱片的口袋会比三明治的口袋好，这就相当于超过了<FONT 
  face="Times New Roman">Alpha(</FONT>在上一层<FONT 
  face="Times New Roman">)</FONT>。算法如下，醒目的部分是在最小<FONT 
  face="Times New Roman">-</FONT>最大算法上改过的： 
  <DD>　 
  <DD>int <FONT color=#ff0000>AlphaBeta</FONT>(int depth<FONT color=#ff0000>, 
  int alpha, int beta</FONT>) { 
  <DD>　if (depth == 0) { 
  <DD>　　return Evaluate(); 
  <DD>　} 
  <DD>　GenerateLegalMoves(); 
  <DD>　while (MovesLeft()) { 
  <DD>　　MakeNextMove(); 
  <DD>　　val = -<FONT color=#ff0000>AlphaBeta</FONT>(depth - 1<FONT 
  color=#ff0000>, -beta, -alpha</FONT>); 
  <DD>　　UnmakeMove(); 
  <DD><FONT color=#ff0000>　　if (val &gt;= beta) {</FONT> 
  <DD><FONT color=#ff0000>　　　return beta;</FONT> 
  <DD><FONT color=#ff0000>　　}</FONT> 
  <DD>　　if (val &gt; alpha) { 
  <DD>　　　alpha = val; 
  <DD>　　} 
  <DD>　} 
  <DD>　return alpha; 
  <DD>} 
  <DT>　 
  <DT>　　把醒目的部分去掉，剩下的就是最小-最大函数。可以看出现在的算法没有太多的改变。 
  <DT>　　这个函数需要传递的参数有：需要搜索的深度，负无穷大即<FONT 
  face="Times New Roman">Alpha</FONT>，以及正无穷大即<FONT 
  face="Times New Roman">Beta</FONT>： 
  <DD>　 
  <DD>val = AlphaBeta(5, -INFINITY, INFINITY); 
  <DT>　 
  <DT>　　这样就完成了<FONT face="Times New Roman">5</FONT>层的搜索。我在写最小<FONT 
  face="Times New Roman">-</FONT>最大函数时，用了一个诀窍来避免用了“<FONT 
  face="Times New Roman">Min</FONT>”还用“<FONT 
  face="Times New Roman">Max</FONT>”函数。在那个算法中，我从递归中返回时简单地对返回值取了负数。这样就使函数值在每一次递归中改变评价的角度，以反映双方棋手的交替着子，并且它们的目标是对立的。 

  <DT>　　在<FONT 
  face="Times New Roman">Alpha-Beta</FONT>函数中我们做了同样的处理。唯一使算法感到复杂的是，<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>是不断互换的。当函数递归时，<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>不但取负数而且位置交换了，这就使得情况比口袋的例子复杂，但是可以证明它只是比最小<FONT 
  face="Times New Roman">-</FONT>最大算法更好而已。 
  <DT>　　最终出现的情况是，在搜索树的很多地方，<FONT 
  face="Times New Roman">Beta</FONT>是很容易超过的，因此很多工作都免去了。 
  <DT>　 
  <DT><A name="branching factor"></A><FONT face=楷体_GB2312 
  size=5><STRONG>可能的弱点</STRONG></FONT> 
  <DT>　 
  <DT>　　这个算法严重依赖于着法的寻找顺序。如果你总是先去搜索最坏的着法，那么<FONT 
  face="Times New Roman">Beta</FONT>截断就不会发生，因此该算法就如同最小<FONT 
  face="Times New Roman">-</FONT>最大一样，效率非常低。该算法最终会找遍整个博弈树，就像最小<FONT 
  face="Times New Roman">-</FONT>最大算法一样。 
  <DT>　　如果程序总是能挑最好的着法来首先搜索，那么数学上有效分枝因子就接近于实际分枝因子的平方根。这是<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法可能达到的最好的情况。 
  <DT>　　由于国际象棋的分枝因子在<FONT face="Times New Roman">35</FONT>左右，这就意味着<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法能使国际象棋搜索树的分枝因子变成<FONT 
  face="Times New Roman">6</FONT>。 
  <DT>　　这是很大的改进，在搜索结点数一样的情况下，可以使你的搜索深度达到原来的两倍。这就是为什么使用<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索时，着法顺序至关重要的原因。 
  <DT>　 
  <DT>　　原文：<A href="http://www.seanet.com/~brucemo/topics/alphabeta.htm" 
  target=_blank><FONT 
  face="Times New Roman">http://www.seanet.com/~brucemo/topics/alphabeta.htm</FONT></A> 

  <DT>　　译者：黄晨 <FONT face="Times New Roman">(</FONT><A 
  href="mailto:[e-mail]"><FONT 
  face="Times New Roman">[e-mail]</FONT></A><FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　类型：全译 </DT></DL>
<DIR>
<LI>上一篇　<A 
href="http://homepage.fudan.edu.cn/~auntyellow/computer/search_minimax.htm">基本搜索方法——最小<FONT 
face="Times New Roman">-</FONT>最大搜索</A> 
<LI>下一篇　<A 
href="http://homepage.fudan.edu.cn/~auntyellow/computer/search_iterative.htm">基本搜索方法——迭代加深</A> 

<LI>返　回　<A 
href="http://homepage.fudan.edu.cn/~auntyellow/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="基本搜索方法——Alpha-Beta搜索_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>