?? 解剖大象的眼睛——中國象棋程序設計探索(五)：克服水平線效應.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0055)http://www.elephantbase.net/computer/eleeye_horizon.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><FONT face=隸書 size=6>解剖大象的眼睛</FONT><FONT
size=6><STRONG>——</STRONG></FONT><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">*</FONT> <FONT
face="Times New Roman">2005</FONT>年<FONT
face="Times New Roman">6</FONT>月初稿，<FONT
face="Times New Roman">2005</FONT>年<FONT face="Times New Roman">11</FONT>月修訂
</CENTER></DT></DIV>
<DIV align=center>
<CENTER>
<DT><FONT face="Times New Roman">( * </FONT>聯系地址：復旦大學化學系表面化學實驗室，<FONT
face="Times New Roman">eMail</FONT>：<A
href="mailto:webmaster@elephantbase.net"><FONT
face="Times New Roman">webmaster@elephantbase.net</FONT></A><FONT
face="Times New Roman">)</FONT> </CENTER></DT></DIV>
<DT>
<DT><FONT face=Arial size=5><STRONG>(</STRONG></FONT><FONT face=楷體_GB2312
size=5><STRONG>五</STRONG></FONT><FONT face=Arial size=5><STRONG>)
</STRONG></FONT><FONT face=楷體_GB2312 size=5><STRONG>克服水平線效應</STRONG></FONT>
<DT>
<DT> 在閱讀本章前，建議讀者先閱讀《<A href="http://www.elephantbase.net/"
target=_blank>象棋百科全書</A>》網站中《<A
href="http://www.elephantbase.net/computer/outline.htm"
target=_blank>對弈程序基本技術</A>》專題的以下幾篇譯文：
<DT> <FONT face="Times New Roman">(1) </FONT><A
href="http://www.elephantbase.net/computer/advanced_intro1.htm"
target=_blank>高級搜索方法——簡介<FONT face="Times New Roman">(</FONT>一<FONT
face="Times New Roman">)</FONT></A><FONT face="Times New Roman">(David
Eppstein)</FONT>；
<DT> <FONT face="Times New Roman">(2) </FONT><A
href="http://www.elephantbase.net/computer/advanced_quiescent.htm"
target=_blank>高級搜索方法——靜態搜索</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(3) </FONT><A
href="http://www.elephantbase.net/computer/advanced_nullmove.htm"
target=_blank>高級搜索方法——空著裁剪</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(4) </FONT><A
href="http://www.elephantbase.net/computer/other_repetition.htm"
target=_blank>其他策略——重復檢測</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>；
<DT> <FONT face="Times New Roman">(5) </FONT><A
href="http://www.elephantbase.net/computer/other_contempt.htm"
target=_blank>其他策略——藐視因子</A><FONT face="Times New Roman">(Bruce
Moreland)</FONT>。
<DT>
<DT> 在象棋程序的搜索技術中，裁剪和延伸是最有挖掘潛力之處，在各個程序中的差異也比較大。<FONT
face="Times New Roman">ElephantEye</FONT>在這方面沒有花太多的筆墨，空著裁剪、靜態搜索和選擇性延伸跟其他程序大同小異，讀者可能會認為“歷史表裁剪”<FONT
face="Times New Roman">(History Pruning)</FONT>是<FONT
face="Times New Roman">ElephantEye</FONT>的亮點，但是筆者對該算法的原理并未完全把握，而且很多細節還有待摸索，所以這里就不作介紹，有興趣的讀者可參考<FONT
face="Times New Roman">ElephantEye</FONT>源程序中<FONT
face="Times New Roman"><search.cpp></FONT>的相關注釋。筆者將對幾個比較成熟可靠的算法作一些介紹。
<DT>
<DT><FONT face=Arial size=4><STRONG>5.1 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>無害裁剪</STRONG></FONT>
<DT>
<DT> 很多局面不需要搜索即可知道它的確切評價值，或者至少超出<FONT
face="Times New Roman">Alpha-Beta</FONT>窗口，此時就可以把該結點以下的搜索樹裁剪掉，而不影響搜索結果，這類裁剪稱為“無害裁剪”，<FONT
face="Times New Roman">ElephantEye</FONT>使用了以下幾種無害裁剪：
<DT> <FONT face="Times New Roman">(1) </FONT>殺棋步數<FONT
face="Times New Roman">(DTM)</FONT>裁剪。由于<FONT
face="Times New Roman">DTM</FONT>調整的緣故，在深度為<FONT
face="Times New Roman">Ply</FONT>的結點中，搜索結果不會落在窗口<FONT
face="Times New Roman">(Ply </FONT><FONT face=Symbol>-</FONT><FONT
face="Times New Roman"> MATE_VALUE, MATE_VALUE </FONT><FONT
face=Symbol>-</FONT><FONT face="Times New Roman"> Ply)</FONT>外，所以當<FONT
face="Times New Roman">(Alpha,
Beta)</FONT>窗口和該窗口沒有交疊時，立即可以作出裁剪。裁剪有兩種情況，要么<FONT
face="Times New Roman">MATE_VALUE </FONT><FONT face=Symbol>-</FONT><FONT
face="Times New Roman"> Ply <= Alpha</FONT>，要么<FONT
face="Times New Roman">Ply </FONT><FONT face=Symbol>-</FONT><FONT
face="Times New Roman"> MATE_VALUE >= Beta</FONT>，<FONT
face="Times New Roman">ElephantEye</FONT>只考慮了后者。
<DT> <FONT face="Times New Roman">(2)
</FONT>重復裁剪。如果出現重復局面，那么應當根據規則直接判和或判某方長打作負，所以應當返回相應的分值。盡管象棋規則規定局面重復三次或更多次才予以判定，但在搜索過程中只要遇到一次重復，繼續搜索下去就會有第二次、第三次，所以<FONT
face="Times New Roman">ElephantEye</FONT>只要遇到一次重復就不再搜索下去，但根結點要另外處理<FONT
face="Times New Roman">(</FONT>否則一個著法也沒搜索，就出不了子了<FONT
face="Times New Roman">)</FONT>。
<DT> <FONT face="Times New Roman">(3)
</FONT>和棋裁剪。如果雙方都沒有明顯可以殺死對方的子力，即可返回和棋分值<FONT
face="Times New Roman">(0</FONT>或藐視因子<FONT
face="Times New Roman">)</FONT>，而不必繼續往下搜索。<FONT
face="Times New Roman">ElephantEye</FONT>把雙方都只剩下仕<FONT
face="Times New Roman">(</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">(4)
</FONT>置換裁剪。置換表的一個作用就是利用置換現象裁剪掉某些分枝，前面已經作了詳細的介紹。這里要提的是，由于存在“搜索的不穩定性”的原因，置換裁剪并非絕對無害的，<FONT
face="Times New Roman">ElephantEye</FONT>就不記錄“利用長將判負策略搜索到的局面”，前面也有所介紹。
<DT>
<DT><FONT face=Arial size=4><STRONG>5.2 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>帶檢驗的空著裁剪</STRONG></FONT>
<DT>
<DT> “帶檢驗的空著裁剪”<FONT face="Times New Roman">(Verified Null-Move
Pruning)</FONT>指的是檢驗空著裁剪是否安全的算法，它首先由<FONT
face="Times New Roman">Tabibi</FONT>發表在<FONT
face="Times New Roman">2002</FONT>年的<FONT
face="Times New Roman">ICGA(</FONT>原<FONT
face="Times New Roman">ICCA)</FONT>雜志上<FONT
face="Times New Roman">(</FONT>參閱<FONT face="Times New Roman">Tabibi OD,
Netanyahu NS: <EM><STRONG>Verified Null-Move Pruning</STRONG></EM><EM>, ICGA
J.</EM> 25 (3): 153-161, <STRONG>2002</STRONG></FONT>，可以從互聯網上找到<FONT
face="Times New Roman">)</FONT>。其內容可以概括為：
<DT> <FONT face="Times New Roman">(1) </FONT>用<FONT
face="Times New Roman"><EM>R</EM> = 3</FONT>的空著裁剪進行搜索；
<DT> <FONT face="Times New Roman">(2) </FONT>如果高出邊界，那么做淺一層的搜索<FONT
face="Times New Roman">(</FONT>這就意味著一層的搜索是無法做帶驗證的空著裁剪的<FONT
face="Times New Roman">)</FONT>；
<DT> <FONT face="Times New Roman">(3) </FONT>做淺一層的搜索時，子結點用<FONT
face="Times New Roman"><EM>R</EM> = 3</FONT>的不帶驗證的空著裁剪；
<DT> <FONT face="Times New Roman">(4)
</FONT>如果淺一層的搜索高出邊界，那么帶驗證的空著裁剪是成功的，否則必須重新做完全的搜索。
<DT> 筆者認為這里存在很多問題：
<DT> <FONT face="Times New Roman">(1) </FONT>用<FONT
face="Times New Roman"><EM>R</EM> = 3</FONT>非常冒進，還是用<FONT
face="Times New Roman"><EM>R</EM> = 2</FONT>比較合適；
<DT> <FONT face="Times New Roman">(2)
</FONT>檢驗時做淺一層的搜索太浪費時間，裁剪的層數可以跟空著裁剪一樣的<FONT
face="Times New Roman"><EM>R</EM></FONT>值一樣，而且窗口也用以<FONT
face="Times New Roman">Beta</FONT>為界的零窗口；
<DT> <FONT face="Times New Roman">(3)
</FONT>做檢驗時，子結點仍舊應該做帶檢驗的空著裁剪，否則“連停著殺”就檢測不出來了。
<DT> <FONT face="Times New Roman">ElephantEye</FONT>是否啟用空著裁剪，分三種情況討論：
<DT> <FONT face="Times New Roman">(1) </FONT>我方進攻子力達到<FONT
face="Times New Roman">3</FONT>個，就使用不帶檢驗的空著裁剪；
<DT> <FONT face="Times New Roman">(2) </FONT>我方進攻子力小于<FONT
face="Times New Roman">3</FONT>個，則使用帶檢驗的空著裁剪；
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -