?? 高級搜索方法——主要變例搜索.htm

?? 象棋程序設(shè)計全資料集(介紹編寫象棋程序的方法思路）
?? 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>《對弈程序基本技術(shù)》專題 </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>的改進(jìn)</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>搜索中，任何結(jié)點都屬于以下三種類型： 
  <DT>　　<FONT face="Times New Roman">1. Alpha</FONT>結(jié)點。每個搜索都會得到一個小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值，這就意味著這里沒有一個著法是好的，可能是因為這個局面對于要走的一方太壞了。 
  <DT>　　<FONT face="Times New Roman">2. Beta</FONT>結(jié)點。至少一個著法會返回大于或等于<FONT 
  face="Times New Roman">Beta</FONT>的值。 
  <DT>　　<FONT face="Times New Roman">3. </FONT>主要變例<FONT 
  face="Times New Roman">(PV)</FONT>結(jié)點。有一個或多個著法會返回大于或等于<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>　　有些時候你可以很早地判斷出你要處理的是哪類結(jié)點。如果你搜索的第一個著法高出邊界<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>結(jié)點。如果低出邊界<FONT 
  face="Times New Roman">(</FONT>返回一個小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值<FONT 
  face="Times New Roman">)</FONT>，假設(shè)你的著法順序非常好，那么你有可能得到<FONT 
  face="Times New Roman">Alpha</FONT>結(jié)點。如果返回值在<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之間，你可能得到<FONT 
  face="Times New Roman">PV</FONT>結(jié)點。 
  <DT>　　當(dāng)然，有兩種情況你可能會判斷錯誤。當(dāng)你高出邊界時，你返回<FONT 
  face="Times New Roman">Beta</FONT>，因此你不會犯錯誤，但是如果第一個著法低出邊界或者是<FONT 
  face="Times New Roman">PV</FONT>著法時，仍然有可能在下一個著法得到更高的值。 
  <DT>　　主要變例搜索作了假設(shè)，如果你在搜索一個結(jié)點時找到一個<FONT 
  face="Times New Roman">PV</FONT>著法，那么你就得到<FONT 
  face="Times New Roman">PV</FONT>結(jié)點。也就是說假設(shè)你的著法排序已經(jīng)足夠好了，使得你不必在其余的著法中找更好的<FONT 
  face="Times New Roman">PV</FONT>著法或者高出邊界的著法<FONT 
  face="Times New Roman">(</FONT>這就會使結(jié)點變成<FONT 
  face="Times New Roman">Beta</FONT>結(jié)點<FONT face="Times New Roman">)</FONT>。 
  <DT>　　你找到一個著法其值在<FONT face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</FONT>之間，那么對其余的著法，搜索的目標(biāo)就是證明他們都是壞的。跟要搜索出更好的著法相比，這種搜索也許要快一些。 

  <DT>　　如果這個算法發(fā)現(xiàn)判斷是錯的，即其中一個后續(xù)著法比第一個<FONT 
  face="Times New Roman">PV</FONT>著法好，那么它會被再一次搜索，這次使用正常的<FONT 
  face="Times New Roman">Alpha-Beta</FONT>搜索方法。這種情況有時會發(fā)生，這樣就浪費時間了，但是這些時間通常不會超過面所說的“證明是壞著法”所節(jié)約下來的時間。 

  <DT>　　算法如下，是從<FONT 
  face="Times New Roman">Alpha-Beta</FONT>算法改過來的，改過的地方用醒目的字標(biāo)出： 
  <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>　　算法的核心部分就是函數(shù)中間醒目的“<FONT 
  face="Times New Roman">if</FONT>”塊中的內(nèi)容。如果沒有找到<FONT 
  face="Times New Roman">PV</FONT>結(jié)點，“<FONT 
  face="Times New Roman">AlphaBeta()</FONT>”函數(shù)就正常調(diào)用，如果找到了一個，那么情況就變了。不是用常規(guī)的窗口<FONT 
  face="Times New Roman">(Alpha, Beta)</FONT>，而是用<FONT 
  face="Times New Roman">(Alpha, Alpha + 1)</FONT>來搜索。這樣做的前提是，搜索必須返回小于或等于<FONT 
  face="Times New Roman">Alpha</FONT>的值，如果確實這樣，那么把窗口的上面部分去掉就會導(dǎo)致更多的截斷。當(dāng)然，如果前提是錯的，返回值是<FONT 
  face="Times New Roman">Alpha + 1</FONT>或更高，那么搜索必須用寬的窗口重做。 
  <DT>　　據(jù)報道<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>搜索不穩(wěn)定性的問題</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>，你就必須重新搜索。你認(rèn)為重新搜索的值必定在<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>搜索的不穩(wěn)定性</A>”引起的，我會在別的章節(jié)中討論這個問題。 
  <DT>　　上面寫的那個程序?qū)@個情況作了防御，并對這種情況的發(fā)生作了正確的處理。如果你要使用這個程序并且作一些改動，就要特別當(dāng)心你的搜索是否總是穩(wěn)定的。如果你得到不期望得到的返回值，就必須采取措施避免讓程序陷入故障。 

  <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">高級搜索方法——搜索的不穩(wěn)定性</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>
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關(guān)標(biāo)簽

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

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

?? 高級搜索方法——主要變例搜索.htm

?? 快捷鍵說明
