?? 高級搜索方法——靜態(tài)搜索.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0059)http://www.elephantbase.net/computer/advanced_quiescent.htm -->
<HTML><HEAD><TITLE>高級搜索方法——靜態(tài)搜索</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=高級搜索方法——靜態(tài)搜索_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>靜態(tài)搜索</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>
<DT>
<DT> 國際象棋中會有很多強(qiáng)制的應(yīng)對。如果有人用馬吃掉你的象，那么你最好吃還他的馬。
<DT> <FONT
face="Times New Roman">Alpha-Beta</FONT>搜索不是特別針對這種情況的。你把深度參數(shù)傳遞給函數(shù)，當(dāng)深度到達(dá)零就做完了，即使一方的后被捉。
<DT> 一個應(yīng)對的方法稱為“靜態(tài)搜索”<FONT face="Times New Roman">(Quiescent
Search)</FONT>。當(dāng)<FONT
face="Times New Roman">Alpha-Beta</FONT>用盡深度后，通過調(diào)用靜態(tài)搜索來代替調(diào)用“<FONT
face="Times New Roman">Evaluate()</FONT>”。這個函數(shù)也對局面作評價，只是避免了在明顯有對策的情況下看錯局勢。
<DT> 簡而言之，靜態(tài)搜索就是應(yīng)對可能的動態(tài)局面的搜索。
<DT> 典型的靜態(tài)搜索只搜索吃子著法。這會引發(fā)一個問題，因?yàn)樵趪H象棋中吃子通常不是強(qiáng)制的。如果局勢很平靜，而且你面對的吃子只有<FONT
face="Times New Roman">QxP(</FONT>后吃兵，導(dǎo)致丟后<FONT
face="Times New Roman">)</FONT>，你不會強(qiáng)迫后去吃兵的，所以靜態(tài)搜索不應(yīng)該強(qiáng)迫吃子。
<DT> 因此，走子一方可以選擇是吃子還是不吃子。這就好比打撲克牌時可以只用手中的牌而不去抓牌<FONT
color=#0000ff>【譯注：術(shù)語“</FONT><FONT face="Times New Roman"
color=#0000ff>Standing Pat</FONT><FONT color=#0000ff>”】</FONT>。
<DT> 代碼如下：
<DD>
<DD>int Quies(int alpha, int beta) {
<DD> val = Evaluate();
<DD> if (val >= beta) {
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD> }
<DD> GenerateGoodCaptures();
<DD> while (CapturesLeft()) {
<DD> MakeNextCapture();
<DD> val = -Quies(-beta, -alpha);
<DD> UnmakeMove();
<DD> if (val >= beta) {
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD> }
<DD> }
<DD> return alpha;
<DD>}
<DD>
<DT><FONT size=3> 這看上去和“</FONT><A
href="http://www.elephantbase.net/computer/search_alphabeta.htm"
target=_blank><FONT face="Times New Roman" size=3>Alpha-Beta</FONT></A><FONT
size=3>”非常相似，但是區(qū)別是很明顯的。這個函數(shù)調(diào)用靜態(tài)評價，如果評價好得足以截?cái)喽恍枰噲D吃子時，就馬上截?cái)?lt;/FONT><FONT
face="Times New Roman" size=3>(</FONT><FONT size=3>返回</FONT><FONT
face="Times New Roman" size=3>Beta)</FONT><FONT
size=3>。如果評價不足以產(chǎn)生截?cái)啵潜?lt;/FONT><FONT face="Times New Roman"
size=3>Alpha</FONT><FONT size=3>好，那么就更新</FONT><FONT face="Times New Roman"
size=3>Alpha</FONT><FONT size=3>來反映靜態(tài)評價。</FONT>
<DT> 然后嘗試吃子著法，如果其中任何一個產(chǎn)生截?cái)啵阉骶椭兄埂？赡芩鼈儧]有一個是好的，這也沒問題。
<DT> 這個函數(shù)有幾個可能的結(jié)果：可能評價函數(shù)會返回足夠高的數(shù)值，使得函數(shù)通過<FONT
face="Times New Roman">Beta</FONT>截?cái)囫R上返回；也可能某個吃子產(chǎn)生<FONT
face="Times New Roman">Beta</FONT>截?cái)啵豢赡莒o態(tài)評價比較壞，而任何吃子著法也不會更好；或者可能任何吃子都不好，但是靜態(tài)評價只比<FONT
face="Times New Roman">Alpha</FONT>高一點(diǎn)點(diǎn)。
<DT> 注意這里靜態(tài)搜索中沒有傳遞“深度”這個參數(shù)。正因?yàn)槿绱耍绻业胶玫某宰樱蛘哂幸幌盗羞B續(xù)的強(qiáng)制性吃子的著法，那么搜索可能會非常深。
<DT> 我的示范程序不檢測將軍，因此它不能找到殺棋。先詢問要走的一方是否被將軍，這是可以嘗試的做法。如果被將軍了，就不能用“<FONT
face="Times New Roman">Evaluate()</FONT>”來嘗試截?cái)啵鴳?yīng)該以一層的深度調(diào)用<FONT
face="Times New Roman">Alpha-Beta</FONT>。例如：
<DD>
<DD>int Quies(int alpha, int beta) {
<DD> if (InCheck()) {
<DD> return AlphaBeta(1, alpha, beta);
<DD> }
<DD> val = Evaluate();
<DD> if (val >= beta) {
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD> }
<DD> GenerateGoodCaptures();
<DD> while (CapturesLeft()) {
<DD> MakeNextCapture();
<DD> val = -Quies(-beta, -alpha);
<DD> UnmakeMove();
<DD> if (val >= beta) {
<DD> return beta;
<DD> }
<DD> if (val > alpha) {
<DD> alpha = val;
<DD> }
<DD> }
<DD> return alpha;
<DD>}
<DT>
<DT> 這個版本會找到帶有連續(xù)吃子的殺棋。至于用哪個版本，取決于個人喜好和測試結(jié)果。
<DT> “好的”吃子的界定也是仁者見仁智者見智的。如果你允許任何吃子，并且以任何原始的順序來搜索，那么你會降低搜索效率，并且導(dǎo)致靜態(tài)搜索的膨脹，從而大幅度降低搜索深度，并使程序崩潰。
<DT> 有一些簡單的做法可以避免靜態(tài)搜索的膨脹。
<DT>
<DT><A name=MVVLVA></A><FONT face=Arial size=5><STRONG>MVV/LVA</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">MVV/LVA </FONT>意思是“最有價值的受害者<FONT
face="Times New Roman">/</FONT>最沒價值的攻擊者”<FONT face="Times New Roman">(Most
Valuable Victim/Least Valuable
Attacker)</FONT>。這是一個應(yīng)用上非常簡單的著法排序技巧，從而最先搜索最好的吃子著法。這個技術(shù)假設(shè)最好的吃子是吃到最大的子。如果不止一個棋子能吃到最大的子，那么假設(shè)用最小的子去吃是最好的。
<DT> 這就意味者<FONT face="Times New Roman">PxQ(</FONT>兵吃后<FONT
face="Times New Roman">)</FONT>首先考慮<FONT
face="Times New Roman">(</FONT>假設(shè)王的將軍另外處理<FONT
face="Times New Roman">)</FONT>。接下來是<FONT
face="Times New Roman">NxQ</FONT>或<FONT
face="Times New Roman">BxQ</FONT>，然后是<FONT
face="Times New Roman">RxQ</FONT>、<FONT
face="Times New Roman">QxQ</FONT>、<FONT
face="Times New Roman">KxQ</FONT>。接下來是<FONT
face="Times New Roman">PxR</FONT>、<FONT
face="Times New Roman">B/NxR</FONT>、<FONT
face="Times New Roman">RxR</FONT>、<FONT
face="Times New Roman">QxR</FONT>、<FONT face="Times New Roman">KxR</FONT>，等等。
<DT> 這個工作總比不做要好，但是很明顯有很嚴(yán)重的問題。即使車被保護(hù)著，<FONT
face="Times New Roman">RxR</FONT>仍舊排在<FONT
face="Times New Roman">PxB</FONT>的前面。
<DT> <FONT face="Times New Roman">MVV/LVA
</FONT>可以解決靜態(tài)搜索膨脹的問題，但是它仍然留給你比較龐大的靜態(tài)搜索樹。
<DT> <FONT face="Times New Roman">MVV/LVA
</FONT>的優(yōu)勢在于它實(shí)現(xiàn)起來非常方便，而且可以達(dá)到很高的<FONT face="Times New Roman">NPS</FONT>值<FONT
face="Times New Roman">(</FONT>每秒搜索的結(jié)點(diǎn)數(shù)<FONT
face="Times New Roman">)</FONT>。它的缺點(diǎn)是搜索效率低——你花大量的時間來評估吃虧的吃子，所以你的搜索不會很深。
<DT>
<DT><A name=SEE></A><FONT face=Arial size=5><STRONG>SEE</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">SEE </FONT>意思是“靜態(tài)交換評價”<FONT
face="Times New Roman">(Static Exchange Evaluation)</FONT>。它比 <FONT
face="Times New Roman">MVV/LVA </FONT>更復(fù)雜，但是著法排序更準(zhǔn)確，從而很多吃子都不必考慮。
<DT> 在 <FONT face="Times New Roman">MVV/LVA </FONT>中你無法去掉<FONT
face="Times New Roman">QxP</FONT>的著法，因?yàn)楹芸赡鼙菦]保護(hù)的，這就意味著<FONT
face="Times New Roman">QxP</FONT>是好的著法。當(dāng)然，如果兵是保護(hù)的，我不相信你還能在搜索這步時有什么好的發(fā)現(xiàn)。用了
<FONT face="Times New Roman">SEE </FONT>后，如果<FONT
face="Times New Roman">QxP</FONT>是吃虧的著法，你就可以把它挑出來，然后在吃子的順序里把它排在最后，或簡單地把它裁剪掉。
<DT> 現(xiàn)在我還沒有 <FONT face="Times New Roman">SEE
</FONT>的示范代碼，你可以設(shè)計(jì)一個處理吃子的過程，然后根據(jù)它看上去能得到的價值進(jìn)行排序。<FONT
color=#0000ff>【當(dāng)考慮吃子著法時，需要考慮能吃到的該子的所有攻擊子，也要保護(hù)該子的所有防守子，因此處理吃子的過程是相當(dāng)復(fù)雜的。】</FONT>
<DT> <FONT face="Times New Roman">SEE
</FONT>能讓你非常有效地裁剪掉壞的著法，很多重要的吃子不會被錯誤地裁剪，并且能改進(jìn)著法的順序。你能做的另一件事是，如果著法看起來還不算充分好，那么你可以裁剪掉這些好的著法。如果你領(lǐng)先一個車，那么得一個兵的吃子或許不值得在靜態(tài)搜索中嘗試。
<DT> 我很懷疑用 <FONT face="Times New Roman">SEE </FONT>的程序能比相同的但用了 <FONT
face="Times New Roman">MVV/LVA </FONT>的程序強(qiáng)。問題在于代碼的編寫上，需要很好地設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)，才能讓 <FONT
face="Times New Roman">SEE </FONT>變得有效。
<DT>
<DT><FONT face=楷體_GB2312 size=5><STRONG>靜態(tài)搜索不是完美的</STRONG></FONT>
<DT>
<DT> 靜態(tài)搜索極有可能會犯錯誤。這是一個不幸的現(xiàn)實(shí)，但是它更多地在搜索看上去非常愚蠢<FONT
face="Times New Roman">(</FONT>例如一層的搜索，它根本不會是非常好的<FONT
face="Times New Roman">)</FONT>的情況下會犯錯誤，因此這不是一個嚴(yán)重的問題。
<DT> 如果可能用更準(zhǔn)確的靜態(tài)搜索而不降低速度，那么我肯定這個程序會比以前更強(qiáng)。但是我們必須明白的是，你在耗費(fèi)時間的前提下試圖讓靜態(tài)搜索更準(zhǔn)確，需要找到平衡點(diǎn)。如果為了讓靜態(tài)搜索更聰明，你花費(fèi)了幾層完全搜索的時間，那么這就不值得讓它更聰明了。
<DT>
<DT> 原文：<A href="http://www.seanet.com/~brucemo/topics/quiescent.htm"
target=_blank><FONT
face="Times New Roman">http://www.seanet.com/~brucemo/topics/quiescent.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_intro2.htm">高級搜索方法——簡介<FONT
face="Times New Roman">(</FONT>二<FONT face="Times New Roman">)</FONT></A>
<LI>下一篇 <A
href="http://www.elephantbase.net/computer/advanced_nullmove.htm">高級搜索方法——空著裁剪</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="高級搜索方法——靜態(tài)搜索_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>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -