?? 國際象棋程序設計(五)：高級搜索方法.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/basic_advanced.htm -->
<HTML><HEAD><TITLE>國際象棋程序設計(五)：高級搜索方法</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb_2312-80">
<META content="MSHTML 6.00.3790.2759" name=GENERATOR></HEAD>
<BODY link=#0000ff background=國際象棋程序設計(五)：高級搜索方法_files/background.gif>
<DL>
<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">Fran</FONT>ç<FONT face="Times New Roman">ois
Dominic Laram</FONT>é<FONT face="Times New Roman">e/</FONT>文
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT> </CENTER></DT></DIV>
<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>可以運用到任何<FONT
face="Times New Roman">2</FONT>人游戲中，然而讓它們用到一些具體問題上，對很多讀者來說還需要加工。
<DT>
<DT><FONT face=楷體_GB2312 size=5><B>干嗎要那么麻煩？</B></FONT>
<DT>
<DT> 到此為止，我們知道的所有搜索算法，都把局面推演到固定的深度。但是這未必是件好事。例如，假設你的程序最多可以用迭代加深的<FONT
face="Times New Roman">Alpha-Beta</FONT>算法搜索到<FONT
face="Times New Roman">5</FONT>層，那么來看下這幾個例子：
<DT>
<DT> <FONT face="Times New Roman">1. </FONT>沿著某條路線，你發現在第<FONT
face="Times New Roman">3</FONT>層有將死或逼和的局面。顯然你不想再搜索下去了，因為游戲的最終目的達到了。搜索<FONT
face="Times New Roman">5</FONT>層不僅是浪費時間，而且可能會讓電腦自己把自己引入不合理的狀態。
<DT> <FONT face="Times New Roman">2. </FONT>現在假設在<FONT
face="Times New Roman">5</FONT>層你吃到了兵。程序可能會認為這個局面稍稍有利，并且會這么走下去。然而，如果你看得更深遠些，可能會發現吃了兵以后你的后就處于被攻擊的狀態，完了！
<DT> <FONT face="Times New Roman">3. </FONT>最后，假設你的后被捉了，不管你怎么走，她會在第<FONT
face="Times New Roman">4</FONT>層被對手吃掉，但是有一條路線可以讓她堅持到第<FONT
face="Times New Roman">6</FONT>層。如果你的搜索深度是<FONT
face="Times New Roman">5</FONT>，那么后在第<FONT
face="Times New Roman">4</FONT>層被吃掉的路線會被檢測出來，這些情況會評估成災難局面，但是唯一能使后在第<FONT
face="Times New Roman">6</FONT>層<FONT
face="Times New Roman">(</FONT>超出了搜索樹<FONT
face="Times New Roman">)</FONT>捉到的那條路線，對于電腦來說被吃是不能被發現的，因此它會認為后很安全，從而打一個較高的分數。現在，為了讓后被吃的情況排除在搜索樹以外，唯一的辦法就是調虎離山，這樣做是很冒險的——犧牲一些局面，還是有可能讓對手犯下錯誤讓你的后溜掉的。那么如果你要通過犧牲一個車來延緩后的被吃呢？對電腦來說，在第<FONT
face="Times New Roman">4</FONT>層丟車要比丟后損失小，所以在這個搜索水平上，它情愿丟一個那么大的子，來推遲那個可憐的后的被吃了。<FONT
face="Times New Roman">(</FONT>當然在隨后一回合里，電腦會發現無論怎么走，它的后會在第<FONT
face="Times New Roman">4</FONT>層被吃掉，并且車丟得莫名其妙。<FONT
face="Times New Roman">)</FONT>很早以前<FONT face="Times New Roman">Hans
Berliner</FONT>就把這個情況稱為“水平線效應”，這在很大程度上可以通過后面即將介紹的“靜態搜索”來改善。
<DT>
<DT> 最后要說一句：象棋中的很多局面<FONT face="Times New Roman">(</FONT>其他游戲也一樣<FONT
face="Times New Roman">)</FONT>太不可預測了，實在很難恰當地評估。評價函數只能在“安靜”的局面下起作用，即這些局面在不久的將來不可能發生很大的變化。這將是我們介紹下一個內容。
<DT>
<DT><FONT face=楷體_GB2312 size=5><B>請安靜！</B></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>。動態評估需要深入的搜索。我們剛剛提到，局面在不久的將來不可能發生很大的變化的情況下，靜態評估才是可行的。這些相對穩定的局面稱為“安靜”<FONT
face="Times New Roman">(Quiet)</FONT>或“寂靜”<FONT
face="Times New Roman">(Quiescent)</FONT>的局面，它們需要通過“靜態搜索”<FONT
face="Times New Roman">(Quiescence Search)</FONT>來達到。
<DT> 靜態搜索的最基本的概念是指：當程序搜索到固定深度時<FONT face="Times New Roman">(</FONT>比如<FONT
face="Times New Roman">6</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">(</FONT>僅僅是能導致將死的將軍<FONT
face="Times New Roman">)</FONT>。<FONT
color=#0000ff>【譯注：我認為任何將軍都應該考慮進去，因為它會導致抽吃、長將等決定性局面的產生】</FONT>。在西洋棋里，吃子和升變<FONT
color=#0000ff>【西洋棋的棋子分兵棋</FONT><FONT face="Times New Roman"
color=#0000ff>(Man)</FONT><FONT color=#0000ff>和王棋</FONT><FONT
face="Times New Roman" color=#0000ff>(King)</FONT><FONT
color=#0000ff>，兵棋沖到底線就變成王棋，因此我斷定它是國際象棋的前身】</FONT>都是選擇。在黑白棋中，每一步都必須吃子，并且“子力平衡”<FONT
color=#0000ff>【僅僅指目前棋子的多少，它和最終棋子的多少沒多大聯系】</FONT>在短時間內翻覆無常，所以可以說它根本不存在“靜態局面”！
<DT> 我自己的程序用了簡單的靜態搜索，它只考慮所有帶吃子著法的線路<FONT
face="Times New Roman">(</FONT>在<FONT
face="Times New Roman"><I>x</I></FONT>層完全搜索以后<FONT
face="Times New Roman">)</FONT>。由于通常局面下沒有太多合理的吃子著法，所以靜態搜索的分枝因子非常小<FONT
face="Times New Roman">(</FONT>平均在<FONT
face="Times New Roman">4-6</FONT>，雙方在吃子后會迅速下降到<FONT
face="Times New Roman">0)</FONT>。但是，靜態搜索算法要分析大量的局面，它可能會占用整個處理器一半以上的時間。當你的程序使用這個方案以前，你要確定你是否需要用它。
<DT> 當沒有吃子發生時，我的程序才開始評價局面。其結果就是將層數固定的搜索樹作選擇性的延伸，它能克服大多數由“水平線效應”產生的后果。
<DT>
<DT><FONT face=楷體_GB2312 size=5><B>重要的空著</B></FONT>
<DT>
<DT> 有個加快象棋程序速度的有效方法，就是引入空著的概念。
<DT> 簡而言之，空著就是自己不走而讓對手連走兩次。大多數局面中，什么事都不做顯然不是辦法，你總是必須做點事情來改善局面。<FONT
face="Times New Roman">(</FONT>老實說，有一些“走也不是，不走也不是”的局面，空著確實是你的最佳選擇，但不能走，這種
“被迫移動”<FONT face="Times New Roman">(Zugzwang)</FONT>局面是沒有指望的，所以不必對電腦感到失望。<FONT
face="Times New Roman">)</FONT>
<DT> 在搜索中讓電腦走空著，可以提高速度和準確性。例如：
<DT>
<DT> <FONT face="Times New Roman">1.
</FONT>假設局面對你來說是壓倒性優勢，即便你什么都不走，對手也無法挽回。<FONT
face="Times New Roman">(</FONT>用程序的術語來說，你不走棋也可以產生<FONT
face="Times New Roman">Beta</FONT>截斷。<FONT
face="Times New Roman">)</FONT>假設這個局面本來準備搜索<FONT
face="Times New Roman"><I>N</I></FONT>層，而空著取代了整個搜索樹<FONT
face="Times New Roman">(</FONT>你的所有合理著法用空著取代了<FONT
face="Times New Roman">)</FONT>，并且你的分枝因子是<FONT
face="Times New Roman"><I>B</I></FONT>，那么搜索空著就相當于只搜索了一個<FONT
face="Times New Roman"><I>N</I>-1</FONT>層的分枝，而不是<FONT
face="Times New Roman"><I>B</I></FONT>個這樣的分枝。在中局階段通常<FONT
face="Times New Roman"><I>B</I>=35</FONT>，所以空著搜索只消耗了完整搜索所需的<FONT
face="Times New Roman">3%</FONT>的資源。如果空著搜索表明你已經強大到沒有必要再走棋<FONT
face="Times New Roman">(</FONT>即會產生截斷<FONT
face="Times New Roman">)</FONT>的地步，那么你少花了<FONT
face="Times New Roman">97%</FONT>的力氣。如果沒有，你就必須檢查合理的著法，這只是多花了<FONT
face="Times New Roman">3%</FONT>的力氣。平均來說，收益是巨大的。<FONT
color=#0000ff>【當然，空著搜索對于處理“被迫移動”局面還是有負面作用的，特別是在殘局中，這個作用相當明顯。可以參考《對弈程序基本技術》專題之《</FONT><A
href="http://www.elephantbase.net/computer/advanced_nullmove.htm"
target=_blank><FONT color=#0000ff>高級搜索方法——空著裁剪</FONT></A><FONT
color=#0000ff>》一文。】</FONT>
<DT> <FONT face="Times New Roman">2.
</FONT>假設在靜態搜索中，你面對一個只有車吃兵一種吃子著法的局面，然而接下來對手就會走馬吃車。你最好不去吃子而走其他不吃子的著法對嗎？你可以在靜態搜索中插入空著來模擬這種情況，如果在某個局面下空著比其他吃子著法有利，那么你繼續吃子就是壞的選擇。并且由于最佳著法是靜態著法，所以這個局面就是評估函數可以作用的局面。
<DT>
<DT> 總的來說，空著啟發會減少<FONT face="Times New Roman">20%</FONT>到<FONT
face="Times New Roman">75%</FONT>的搜索時間。這當然值得，特別是當你把這個方法用在靜態搜索算法上的時候，就像改變“走子的一方”這種代碼一樣簡單，用不了十行就行了。
<DT><FONT color=#0000ff> 【很多書上把“空著”這一技術稱為“空著啟發”</FONT><FONT
face="Times New Roman" color=#0000ff>(Null-Move Heuristic)</FONT><FONT
color=#0000ff>，本文就是這個意思，事實上在歷史表、迭代加深等啟發的作用下，空著啟發已經意義不大了。現在絕大多數程序都使用了稱為“空著的向前裁剪”</FONT><FONT
face="Times New Roman" color=#0000ff>(Null-Move Forward Pruning)</FONT><FONT
color=#0000ff>的搜索</FONT><FONT face="Times New Roman"
color=#0000ff>(</FONT><FONT color=#0000ff>它跟空著啟發是有區別的</FONT><FONT
face="Times New Roman" color=#0000ff>)</FONT><FONT
color=#0000ff>，盡管是一種不完全搜索，但它卻是諸多向前裁剪的搜索中最有效的一個。】</FONT>
<DT>
<DT><FONT face=楷體_GB2312 size=5><B>期望搜索和</B></FONT><FONT face=Arial
size=5><B>MTD(</B><EM><B>f</B></EM><B>)</B></FONT>
<DT>
<DT> 普通的老式<FONT face="Times New Roman">Alpha-Beta</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">0</FONT>，因為非常均衡。現在來假設對一個內部結點作先前的評價，它的值在<FONT
face="Times New Roman">+20,000</FONT><FONT color=#0000ff>【這里的單位應該是“千分兵值”，
即</FONT><FONT face="Times New Roman" color=#0000ff>1000</FONT><FONT
color=#0000ff>相當于一個兵的價值，那么馬和象等于</FONT><FONT face="Times New Roman"
color=#0000ff>3000</FONT><FONT color=#0000ff>，車</FONT><FONT
face="Times New Roman" color=#0000ff>5000</FONT><FONT
color=#0000ff>，后</FONT><FONT face="Times New Roman"
color=#0000ff>9000</FONT><FONT color=#0000ff>，其他因素也折算成這個值，而</FONT><FONT
face="Times New Roman" color=#0000ff>UCI</FONT><FONT
color=#0000ff>協議中則用“百分兵值”，因為沒有必要過于精確】</FONT>，那么你可以有充分信心對它截斷。
<DT> 這就是“期望搜索”<FONT face="Times New Roman">(Aspiration
Search)</FONT>背后的思想，一個<FONT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -