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

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

📁 象棋程序设计全资料集(介绍编写象棋程序的方法思路）
💻 HTM
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0070)http://homepage.fudan.edu.cn/~auntyellow/computer/search_alphabeta.htm -->
<HTML><HEAD><TITLE>基本搜索方法——Alpha-Beta搜索</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=基本搜索方法——Alpha-Beta搜索_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=Arial size=6><STRONG>Alpha-Beta</STRONG></FONT><FONT face=隶书 
  size=6>搜索</FONT> </CENTER></DT></DIV>
  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <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>
  <DIV></DIV>
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>最小</STRONG></FONT><FONT face=Arial 
  size=5><STRONG>-</STRONG></FONT><FONT face=楷体_GB2312 
  size=5><STRONG>最大的问题</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT face="Times New Roman">Alpha-Beta </FONT>同“<A 
  href="http://homepage.fudan.edu.cn/~auntyellow/computer/search_minimax.htm" 
  target=_blank>最小<FONT 
  face="Times New Roman">-</FONT>最大</A>”非常相似，事实上只多了一条额外的语句。最小最大运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。 

  <DT>　　通常一个国际象棋局面都有<FONT face="Times New Roman">35</FONT>个左右的合理着法，所以用最小<FONT 
  face="Times New Roman">-</FONT>最大搜索来搜索一层深度，就有<FONT 
  face="Times New Roman">35</FONT>个局面要检查，如果用这个函数来搜索两层，就有<FONT 
  face="Times New Roman">35<SUP>2</SUP></FONT>个局面要搜索。这就已经上千了，看上去还不怎样，但是数字增长得非常迅速，例如六层的搜索就接近是二十亿，而十层的搜索就超过两千万亿了。 

  <DT>　　要想通过检查搜索树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜索是很重要的。最小<FONT 
  face="Times New Roman">-</FONT>最大搜索无法做到很深的搜索，因为有效的分枝因子实在太大了。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>口袋的例子</STRONG></FONT> 
  <DT>　 
  <DT>　　幸运的是我们有办法来减小分枝因子，这个办法非常可靠，实际上这样做绝对没有坏处，纯粹是个有益的办法。这个方法是建立在一个思想上的，如果你已经有一个不太坏的选择了，那么当你要作别的选择并知道它不会更好时，你没有必要确切地知道它有多坏。有了最好的选择，任何不比它更好的选择就是足够坏的，因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。 

  <DT>　　你可能仍旧不明白，那么我就举个例子。比如你的死敌面前有很多口袋，他和你打赌赌输了，因此他必须从中给你一样东西，而挑选规则却非常奇怪： 
  <DT>　　每个口袋里有几件物品，你能取其中的一件，你来挑这件物品所在的口袋，而他来挑这个口袋里的物品。你要赶紧挑出口袋并离开，因为你不愿意一直做在那里翻口袋而让你的死敌盯着你。 

  <DT>　　假设你一次只能找一只口袋，在找口袋时一次只能从里面摸出一样东西。 
  <DT>　　很显然，当你挑出口袋时，你的死敌会把口袋里最糟糕的物品给你，因此你的目标是挑出“诸多最糟的物品当中是最好的”那个口袋。 
  <DT>　　你很容易把最小<FONT 
  face="Times New Roman">-</FONT>最大原理运用到这个问题上。你是最大一方棋手，你将挑出最好的口袋。而你的死敌是最小一方棋手，他将挑出最好的口袋里尽可能差的物品。运用最小<FONT 
  face="Times New Roman">-</FONT>最大原理，你需要做的就是挑一个有“最好的最差的”物品的口袋。 
  <DT>　　假设你可以估计口袋里每个物品的准确价值的话，最小<FONT 
  face="Times New Roman">-</FONT>最大原理可以让你作出正确的选择。我们讨论的话题中，准确评价并不重要，因为它同最小<FONT 
  face="Times New Roman">-</FONT>最大或<FONT 
  face="Times New Roman">Alpha-Beta</FONT>的工作原理没有关系。现在我们假设你可以正确地评价物品。 
  <DT>　　最小<FONT 
  face="Times New Roman">-</FONT>最大原理刚才讨论过，它的问题是效率太低。你必须看每个口袋里的每件物品，这就需要花很多时间。 
  <DT>　　那么怎样才能做得比最小<FONT face="Times New Roman">-</FONT>最大更高效呢？ 
  <DT>　　我们从第一个口袋开始，看每一件物品，并对口袋作出评价。比方说口袋里有一只花生黄油三明治和一辆新汽车的钥匙。你知道三明治更糟，因此如果你挑了这只口袋就会得到三明治。事实上只要我们假设对手也会跟我们一样正确评价物品，那么口袋里的汽车钥匙就是无关紧要的了。 

  <DT>　　现在你开始翻第二个口袋，这次你采取的方案就和最小<FONT 
  face="Times New Roman">-</FONT>最大方案不同了。你每次看一件物品，并跟你能得到的最好的那件物品<FONT 
  face="Times New Roman">(</FONT>三明治<FONT 
  face="Times New Roman">)</FONT>去比较。只要物品比三明治更好，那么你就按照最小<FONT 
  face="Times New Roman">-</FONT>最大方案来办——去找最糟的，或许最糟的要比三明治更好，那么你就可以挑这个口袋，它比装有三明治的那个口袋好。 

  <DT>　　比方这个口袋里的第一件物品是一张<FONT 
  face="Times New Roman">20</FONT>美元的钞票，它比三明治好。如果包里其他东西都没比这个更糟了，那么如果你选了这个口袋，它就是对手必须给你的物品，这个口袋就成了你的选择。 

  <DT>　　这个口袋里的下一件物品是六合装的流行唱片。你认为它比三明治好，但比<FONT 
  face="Times New Roman">20</FONT>美元差，那么这个口袋仍旧可以选择。再下一件物品是一条烂鱼，这回比三明治差了。于是你就说“不谢了”，把口袋放回去，不再考虑它了。 

  <DT>　　无论口袋里还有什么东西，或许还有另一辆汽车的钥匙，也没有用了，因为你会得到那条烂鱼。或许还有比烂鱼更糟的东西<FONT 
  face="Times New Roman">(</FONT>那么你看着办吧<FONT 
  face="Times New Roman">)</FONT>。无论如何烂鱼已经够糟的了，而你知道挑那个有三明治的口袋肯定会更好。 
  <DT>　 
  <DT><FONT face=楷体_GB2312 size=5><STRONG>算法</STRONG></FONT> 
  <DT>　 
  <DT>　　<FONT 
  face="Times New Roman">Alpha-Beta</FONT>就是这么工作的，并且只能用递归来实现。稍后我们再来谈最小一方的策略，我希望这样可以更明白些。 

  <DT>　　这个思想是在搜索中传递两个值，第一个值是<FONT 
  face="Times New Roman">Alpha</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">Beta</FONT>更坏的。如果搜索过程中返回<FONT 
  face="Times New Roman">Beta</FONT>或比<FONT 
  face="Times New Roman">Beta</FONT>更好的值，那就够好的了，走棋的一方就没有机会使用这种策略了。 
  <DT>　　在搜索着法时，每个搜索过的着法都返回跟<FONT face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。 
  <DT>　　如果某个着法的结果小于或等于<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">Beta</FONT>，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -