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