?? 基本搜索方法——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 下一頁
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關標簽

#程序設計 #程序 #編寫
?? 快捷鍵說明

復制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

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

?? 快捷鍵說明
