?? 高級搜索方法——空著裁剪.htm

?? 象棋程序設計全資料集(介紹編寫象棋程序的方法思路）
?? HTM
?? 第 1 頁 / 共 2 頁
字號:
12 下一頁
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0058)http://www.elephantbase.net/computer/advanced_nullmove.htm -->
<HTML><HEAD><TITLE>高級搜索方法——空著裁剪</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.536" name=GENERATOR></HEAD>
<BODY background=高級搜索方法——空著裁剪_files/background.gif>
<DL dir=ltr>
  <DIV align=center>
  <CENTER>
  <DT><FONT size=3>《對弈程序基本技術》專題</FONT> </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> 
  <DT>　 
  <DT>　　空著向前裁剪<FONT face="Times New Roman">(Null-Move Forward 
  Pruning)</FONT>，運用可能忽視重要路線的冒險策略，使得國際象棋的分枝因子銳減，它導致搜索深度的顯著提高，因為大多數情況下它明顯降低了搜索的數量。它的工作原理是裁剪大量無用著法而只保留好的。 

  <DT>　　這個技術在很多刊物上報道過，但是使得大家都來關注空著的，則是由<FONT face="Times New Roman">Chrilly 
  Donniger</FONT>發表在<FONT face="Times New Roman">1993</FONT>年<FONT 
  face="Times New Roman">9</FONT>月的<FONT 
  face="Times New Roman">ICCA</FONT>雜志上的一篇文章。 
  <DT>　　試想國際象棋搜索樹中的某個局面，你的程序將以<FONT 
  face="Times New Roman"><EM>D</EM></FONT>層搜索這個局面的每個著法。如果其中任何一個著法的分數超過<FONT 
  face="Times New Roman">Beta</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">Alpha</FONT>，你就要返回<FONT 
  face="Times New Roman">Alpha</FONT>。 
  <DT>　　空著向前裁剪是你搜索任何著法之前要做的事。你要問一個問題：“如果我在這里什么都不做，對手能做什么？” 
  <DT>　　記得在剛才，你沒有問這個問題。你只是去找最佳的著法去打擊對手。問對手是否會打擊你，這個問題卻有所不同。 
  <DT>　　但是事實證明很多情況下對手無法打擊你。比如說你送了一個車，而其他棋子都沒有作用，在這種情況下，對手隨便走哪步你都吃虧，因為你丟了一個車。空著向前裁剪的要點，就是簡單地去掉那些沒用的著法，而不要在這上面多花時間。 

  <DT>　　這就好比像打架時，根據自己的能力給對手一個出擊的機會，來增加自己的信心。如果任憑對手攻擊也無法擊倒你，那么你攻擊他的時候他會輸掉。 
  <DT>　　我們不討論這個策略了，現在來談它是如何運用在電腦國際象棋中的。在你搜索著法以前<FONT 
  face="Times New Roman">(</FONT>事實上在你生成著法以前<FONT 
  face="Times New Roman">)</FONT>，你做一個減少深度的搜索，讓對手先走，如果這個搜索的結果大于或等于<FONT 
  face="Times New Roman">Beta</FONT>，那么你簡單地返回<FONT 
  face="Times New Roman">Beta</FONT>而不需要搜索任何著法。 
  <DT>　　這個思想就給了對手出擊的機會，如果你的局面仍然好到超過<FONT 
  face="Times New Roman">Beta</FONT>的程度，你就假設如果你搜索了所有的著法也會超過<FONT 
  face="Times New Roman">Beta</FONT>。 
  <DT>　　這個方法能節省時間的原因是，開始時用了減少深度的搜索。深度減少因子稱為<FONT 
  face="Times New Roman"><EM>R</EM></FONT>，因此跟你用深度<FONT 
  face="Times New Roman"><EM>D</EM></FONT>搜索所有的著法相比，現在你是先以<FONT 
  face="Times New Roman"><EM>D</EM> </FONT><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> <EM>R</EM></FONT>搜索對手的著法。一個比較好<FONT 
  face="Times New Roman"><EM>R</EM></FONT>是<FONT 
  face="Times New Roman">2</FONT>，如果你要對所有的著法搜索<FONT 
  face="Times New Roman">6</FONT>層，你最終只對對手所有的著法搜索了<FONT 
  face="Times New Roman">4</FONT>層。<FONT 
  color=#0000ff>【譯注：因為放棄著法后層數應該減1，所以實際在對手上面搜索的層數是</FONT><FONT 
  face="Times New Roman" color=#0000ff><EM>D</EM> </FONT><FONT face=Symbol 
  color=#0000ff>-</FONT><FONT face="Times New Roman" color=#0000ff> 1 
  </FONT><FONT face=Symbol color=#0000ff>-</FONT><FONT face="Times New Roman" 
  color=#0000ff> <EM>R</EM></FONT><FONT color=#0000ff>。】</FONT> 
  <DT>　　這就使得很多時間節約下來了，實踐證明可以使搜索增加一到兩層。效果真的非常可觀！ 
  <DT>　　代碼如下，醒目的文字是在<FONT face="Times New Roman">Alpha-Beta</FONT>搜索的基礎上增加的部分： 
  <DD>　 
  <DD><FONT face=宋體 color=#ff0000>#define R 2</FONT> 
  <DD><FONT face=宋體>int AlphaBeta(int depth, int alpha, int beta) {</FONT> 
  <DD><FONT face=宋體>　if (depth == 0) {</FONT> 
  <DD><FONT face=宋體>　　return Evaluate();</FONT> 
  <DD>　} 
  <DD><FONT face=宋體 color=#ff0000>　MakeNullMove();</FONT> 
  <DD><FONT face=宋體 color=#ff0000>　val = -AlphaBeta(depth - 1 - R, -beta, -beta 
  + 1);</FONT> 
  <DD><FONT face=宋體 color=#ff0000>　UnmakeNullMove();</FONT> 
  <DD><FONT face=宋體 color=#ff0000>　if (val &gt;= beta) {</FONT> 
  <DD><FONT face=宋體 color=#ff0000>　　return beta;</FONT> 
  <DD><FONT color=#ff0000>　}</FONT> 
  <DD><FONT face=宋體>　GenerateLegalMoves();</FONT> 
  <DD><FONT face=宋體>　while (MovesLeft()) {</FONT> 
  <DD><FONT face=宋體>　　MakeNextMove();</FONT> 
  <DD><FONT face=宋體>　　val = -AlphaBeta(depth - 1, -beta, -alpha);</FONT> 
  <DD><FONT face=宋體>　　UnmakeMove();</FONT> 
  <DD><FONT face=宋體>　　if (val &gt;= beta) { // 
  </FONT>把這部分去掉，就用純粹的最小-最大代替了Alpha-Beta。 
  <DD><FONT face=宋體>　　　return beta;</FONT> 
  <DD><FONT face=宋體>　　</FONT>} 
  <DD><FONT face=宋體>　　if (val &gt; alpha) {</FONT> 
  <DD><FONT face=宋體>　　　alpha = val;</FONT> 
  <DD><FONT face=宋體>　　}</FONT> 
  <DD><FONT face=宋體>　</FONT>} 
  <DD><FONT face=宋體>　return alpha;</FONT> 
  <DD><FONT face=宋體>}</FONT> 
  <DT>　 
  <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><FONT face=Symbol>-</FONT><FONT 
  face="Times New Roman"> 1, Beta)</FONT>調用了搜索，但是由于遞歸時必須把<FONT 
  face="Times New Roman">Alpha</FONT>和<FONT 
  face="Times New Roman">Beta</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">(Zugzwang)</FONT>。無等著局面指的是，如果你不走棋，局勢會好些，但是你被強迫走子，這使得你的局勢會崩潰。下面是個典型的例子： 

  <DT>　 
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="高級搜索方法——空著裁剪_files/advanced_nullmove1.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　在這個局面里，如果白方被迫走子，他走 <FONT face="Times New Roman">Kb2</FONT>，而黑走 <FONT 
  face="Times New Roman">Kd2 </FONT>助兵變后。如果白方不走棋，那么黑的走 <FONT 
  face="Times New Roman">Kc3</FONT>，局面就是和棋。<FONT 
  face="Times New Roman">(</FONT>事實上這是一個互相的無等著局面，因為雙方都被先走棋所困擾，這個問題不在我們的討論范圍內。<FONT 
  face="Times New Roman">)</FONT> 
  <DT>　　如果到達這個局面，而且試圖用空著向前裁剪，那么可能會認為黑方沒有威脅白方，因為現在黑方確實沒威脅白方。而現在黑方在等待白方毀掉局勢，這就完全不同了。 

  <DT>　　由于這個原因，空著向前裁剪不能在殘局中使用，或者至少不能直接地使用。如果你試圖在殘局中用，則會出現很糟糕的事情。 
  <DT>　　有一個更困擾人的例子，是這樣的： 
  <DIV align=left></DIV>
  <DT>　 
  <DIV></DIV>
  <DIV align=center>
  <CENTER></DIV>
  <DT><IMG height=256 src="高級搜索方法——空著裁剪_files/advanced_nullmove2.gif" width=256> 
  </CENTER>
  <DIV></DIV>
  <DT>　 
  <DT>　　這個局面選自<FONT face="Times New Roman">Goetsch</FONT>和<FONT
12 下一頁
?? 文件大小 859 K
?? 上傳用戶 Emouse
?? 所屬分類文件格式
??? 相關標簽

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

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

?? 高級搜索方法——空著裁剪.htm

?? 快捷鍵說明
