?? 基本搜索方法——簡(jiǎn)介(一).htm

?? 象棋程序設(shè)計(jì)全資料集(介紹編寫象棋程序的方法思路）
?? HTM
?? 第 1 頁(yè) / 共 2 頁(yè)
字號(hào):
12 下一頁(yè)
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0054)http://www.elephantbase.net/computer/search_intro1.htm -->
<HTML><HEAD><TITLE>基本搜索方法——簡(jiǎn)介(一)</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="" name=Owner>
<META content="" name=Reply-To>
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY background=基本搜索方法——簡(jiǎn)介(一)_files/background.gif>
<DL>
  <DIV align=center>
  <CENTER>
  <DT><FONT size=3>《對(duì)弈程序基本技術(shù)》專題</FONT> </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face=隸書 size=6>最小</FONT><FONT face=Arial size=6>-</FONT><FONT 
  face=隸書 size=6>最大和負(fù)值最大搜索</FONT> </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT>　 </CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">David Eppstein */</FONT>文 
</CENTER></DT></DIV>
  <DIV align=center>
  <CENTER>
  <DT><FONT face="Times New Roman">* </FONT>加州愛(ài)爾文大學(xué)<FONT 
  face="Times New Roman">(UC Irvine)</FONT>信息與計(jì)算機(jī)科學(xué)系 </CENTER></DT></DIV>
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>搜索樹(shù)</STRONG></FONT> 
  <DT>　 
  <DT>　　任何棋類游戲都要定義一棵有根的樹(shù)<FONT face="Times New Roman">(</FONT>即“博弈樹(shù)”<FONT 
  face="Times New Roman">)</FONT>，一個(gè)結(jié)點(diǎn)就代表棋類的一個(gè)局面，子結(jié)點(diǎn)就是這個(gè)局面走一步可以到達(dá)的一個(gè)局面。例如下圖是井子棋<FONT 
  face="Times New Roman">(Tic-tac-toe)</FONT>的搜索樹(shù)： 
  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT>　 </CENTER>
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=287 src="基本搜索方法——簡(jiǎn)介(一)_files/search_intro1.gif" width=393> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　<FONT face="Times New Roman">(</FONT>實(shí)際上，這個(gè)搜索樹(shù)的根結(jié)點(diǎn)應(yīng)該有<FONT 
  face="Times New Roman">9</FONT>個(gè)子結(jié)點(diǎn)，但是我去掉了一些對(duì)稱的情況。如果同樣的棋盤是由兩個(gè)不同的著法順序形成的，那么我們就建立兩個(gè)結(jié)點(diǎn)，所以這的確是樹(shù)的結(jié)構(gòu)。稍后我們會(huì)在討論散列技術(shù)的時(shí)候談到如何利用重復(fù)的結(jié)點(diǎn)來(lái)提高搜索速度——我們只要搜索第一個(gè)，另一個(gè)就用第一個(gè)搜索結(jié)果來(lái)代替。另外我們假設(shè)棋手是輪流下棋的，沒(méi)有人一次走多步或跳過(guò)不走的，那些復(fù)雜的情況可以把它走的一系列著法看作一個(gè)著法來(lái)處理。<FONT 
  color=#0000ff>【譯注：復(fù)雜的情況是指一些一次能走很多步的棋類游戲，例如跳棋、西洋跳棋、黑白棋等，按照原作者的方案，可以把一方連續(xù)走的幾步棋看成一步棋。而譯者更愿意把一方連續(xù)的幾步棋拆成幾個(gè)回合，只是另一方都別無(wú)選擇地走了空著。】</FONT>最后，我們假設(shè)搜索樹(shù)是有限的，這樣我們就不會(huì)遇到永無(wú)止境的棋局或者一步有無(wú)限多種著法的棋局。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　搜索樹(shù)中有三種類型的結(jié)點(diǎn)： 
  <DT>　　<FONT face="Times New Roman">(1) </FONT>偶數(shù)層的中間結(jié)點(diǎn)，代表棋手甲要走的局面； 
  <DT>　　<FONT face="Times New Roman">(2) </FONT>奇數(shù)層的中間結(jié)點(diǎn)，代表棋手乙要走的局面； 
  <DT>　　<FONT face="Times New Roman">(3) </FONT>葉子結(jié)點(diǎn)，代表棋局結(jié)束的局面，即棋手甲或棋手乙獲勝，或者是和局。 

  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>博弈樹(shù)的評(píng)價(jià)</STRONG></FONT> 
  <DT>　 
  <DT>　　假設(shè)某個(gè)中間結(jié)點(diǎn)的所有子結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，那么棋局會(huì)在一回合內(nèi)結(jié)束。現(xiàn)在我們假設(shè)棋手會(huì)挑選最好的著法，如果有一個(gè)著法能使他贏下棋局，那么他一定會(huì)走這步。如果沒(méi)有可以贏的著法，但是有取得和局的著法，那么他會(huì)走這步取得和局的著法。但是，如果所有的著法都使得對(duì)手獲勝，那么無(wú)論如何他都會(huì)輸。 

  <DT>　　因此在葉子結(jié)點(diǎn)的上一層結(jié)點(diǎn)，我們就能知道棋局的結(jié)果。現(xiàn)在我們知道了這個(gè)結(jié)點(diǎn)的結(jié)果，那么我們可以用同樣的方法作推演，知道葉子結(jié)點(diǎn)的上兩層結(jié)點(diǎn)的結(jié)果，然后是上三層結(jié)點(diǎn)，等等，直到我們達(dá)到搜索樹(shù)的根結(jié)點(diǎn)。在每個(gè)結(jié)點(diǎn)上，棋手只要找到一個(gè)子結(jié)點(diǎn)能讓他獲勝，那么他就可以贏下棋局；他只要找到一個(gè)形成和局的子結(jié)點(diǎn)，棋局就和了；如果獲勝與和局的子結(jié)點(diǎn)都沒(méi)有，那么肯定是輸?shù)摹Ｈ绻覀冇凶銐蚨嗟臅r(shí)間來(lái)計(jì)算，那么這就給了我們一個(gè)可以下棋的完美算法。但是對(duì)于任何常規(guī)的棋類游戲，我們都不可能有足夠的計(jì)算時(shí)間，因?yàn)樗阉鳂?shù)實(shí)在太大了。 

  <DT>　　另外，“正確”的評(píng)價(jià)函數(shù)只有三個(gè)值，贏、輸或者和局。在實(shí)際的棋類程序中，我們通常使用一個(gè)更寬泛的實(shí)數(shù)來(lái)作評(píng)價(jià)值，就是因?yàn)橼A、輸或者和局是不確定的。如果棋手甲獲勝的值用<FONT 
  face="Times New Roman">+1</FONT>表示，和局的值用<FONT 
  face="Times New Roman">0</FONT>表示，棋手乙獲勝的值用<FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman">1</FONT>表示，那么博弈樹(shù)的每個(gè)中間結(jié)點(diǎn)的值就是子結(jié)點(diǎn)的最大值或最小值，這取決于棋手甲還是棋手乙著棋。 
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>部分的博弈樹(shù)</STRONG></FONT> 
  <DT>　 
  <DT>　　在實(shí)戰(zhàn)中，我們的搜索算法只能對(duì)博弈樹(shù)展開(kāi)一部分。我們用一些“中止規(guī)則”來(lái)決定搜索樹(shù)展開(kāi)到哪個(gè)結(jié)點(diǎn)就停下來(lái)，例如我們?cè)?lt;FONT 
  face="Times New Roman">8</FONT>步變化以后聽(tīng)下來(lái)。由于棋局沒(méi)有在葉子結(jié)點(diǎn)結(jié)束，我們只能用評(píng)價(jià)函數(shù)來(lái)猜哪一方獲勝。現(xiàn)在我們來(lái)假設(shè)在我們展開(kāi)的結(jié)點(diǎn)中，棋手甲總是希望棋局到達(dá)評(píng)價(jià)函數(shù)大的局面，而棋手乙總是希望棋局到達(dá)評(píng)價(jià)函數(shù)小的局面。 

  <DT>　　如果雙方都用這種方法來(lái)下棋，那么我們可以使用同樣的最小<FONT 
  face="Times New Roman">-</FONT>最大過(guò)程，來(lái)確定到達(dá)的葉子結(jié)點(diǎn)的評(píng)價(jià)值，這個(gè)過(guò)程如下：對(duì)每個(gè)中間結(jié)點(diǎn)，計(jì)算子結(jié)點(diǎn)的最大值或最小值，這取決于是棋手甲還是棋手乙走棋。到達(dá)葉子結(jié)點(diǎn)的線路稱為“主要變例”<FONT 
  face="Times New Roman">(Principal Variation)</FONT>。最小<FONT 
  face="Times New Roman">-</FONT>最大博弈樹(shù)的基本原理，就是對(duì)博弈樹(shù)作部分展開(kāi)，去找主要變例，并走出變例中的第一步。 
  <DT>　 
  <DT><FONT face=楷體_GB2312 size=5><STRONG>廣度優(yōu)先和深度優(yōu)先搜索，負(fù)值最大代碼</STRONG></FONT> 
  <DT>　 
  <DT>　　正如上面所講的，計(jì)算博弈樹(shù)的值是一個(gè)廣度優(yōu)先的過(guò)程<FONT 
  face="Times New Roman">(</FONT>我們要自下而上地，一次一層地計(jì)算<FONT 
  face="Times New Roman">)</FONT>。然而實(shí)戰(zhàn)中，我們使用深度優(yōu)先<FONT 
  face="Times New Roman">(</FONT>即后序遍歷<FONT 
  face="Times New Roman">)</FONT>的遞歸過(guò)程來(lái)遍歷搜索樹(shù)，即要得到一個(gè)結(jié)點(diǎn)的值，就對(duì)子結(jié)點(diǎn)做遞歸，然后根據(jù)它們的返回值來(lái)決定自身的返回值。這樣要節(jié)省很多空間，因?yàn)椴恍枰獊?lái)存儲(chǔ)整個(gè)博弈樹(shù)，而只是存儲(chǔ)一條線路<FONT 
  face="Times New Roman">(</FONT>相對(duì)來(lái)說(shuō)非常短，例如上面提到的<FONT 
  face="Times New Roman">8</FONT>步中止的規(guī)則<FONT 
  face="Times New Roman">)</FONT>。下次我們討論<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索時(shí)，會(huì)發(fā)現(xiàn)深度優(yōu)先的遍歷會(huì)有很大的優(yōu)勢(shì)，你可以用目前得到的信息來(lái)決定某些結(jié)點(diǎn)是不需要訪問(wèn)的，這樣就節(jié)省下很多的時(shí)間。 

  <DT>　　只要對(duì)搜索樹(shù)的值作一個(gè)很小的改動(dòng)，就可以用一個(gè)求最大值的操作來(lái)代替最小值和最大值交替的過(guò)程。在搜索樹(shù)的奇數(shù)層<FONT 
  face="Times New Roman">(</FONT>即輪到棋手乙下棋的結(jié)點(diǎn)<FONT 
  face="Times New Roman">)</FONT>，就對(duì)上面提到的評(píng)價(jià)值取負(fù)數(shù)。因此在每個(gè)結(jié)點(diǎn)上，這些值都可以由子結(jié)點(diǎn)的負(fù)值求得。我把博弈樹(shù)搜索的源代碼寫出來(lái)，恐怕就會(huì)清楚很多了。 

  <DT>　 
  <DD>// 將博弈樹(shù)搜索到一定的深度，返回根結(jié)點(diǎn)的評(píng)價(jià)值 
  <DD>double negamax(int depth) { 
  <DD>　if (depth &lt;= 0 || 棋局結(jié)束) 
  <DD>　　return eval(pos); 
  <DD>　else { 
  <DD>　　double e = -infty; 
  <DD>　　for (當(dāng)前局面所有可能的著法 m) { 
  <DD>　　　執(zhí)行著法 m; 
  <DD>　　　e = max(e, -negamax(depth - 1)); 
  <DD>　　　撤消著法 m; 
  <DD>　　} 
  <DD>　　return e; 
  <DD>　} 
  <DD>} 
  <DT>　 
  <DT>　　注意，這個(gè)過(guò)程只能找到評(píng)價(jià)值，但是無(wú)法得知著法。我們只要在搜索樹(shù)的根結(jié)點(diǎn)找到著法<FONT 
  face="Times New Roman">(</FONT>盡管很多程序都返回整個(gè)主要變例<FONT 
  face="Times New Roman">)</FONT>就可以了，要做到這一點(diǎn)，可以對(duì)根結(jié)點(diǎn)的搜索稍作改動(dòng)： 
  <DD>　 
  <DD>// 將博弈樹(shù)搜索到一定的深度，返回根結(jié)點(diǎn)的著法 
  <DD>move rootsearch(int depth) { 
  <DD>　double e = -infty; 
  <DD>　move mm; 
  <DD>　for (當(dāng)前局面所有可能的著法 m) { 
  <DD>　　執(zhí)行著法 m; 
  <DD>　　double em = -negamax(depth - 1); 
  <DD>　　if (e &lt; em) {
12 下一頁(yè)
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關(guān)標(biāo)簽

#程序設(shè)計(jì) #程序 #編寫
?? 快捷鍵說(shuō)明

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

?? 基本搜索方法——簡(jiǎn)介(一).htm

?? 快捷鍵說(shuō)明
