?? 解剖大象的眼睛——中國象棋程序設(shè)計探索(四)：啟發(fā)算法.htm
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.elephantbase.net/computer/eleeye_heuristic.htm -->
<HTML><HEAD><TITLE>解剖大象的眼睛——中國象棋程序設(shè)計探索(四)：啟發(fā)算法</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=解剖大象的眼睛——中國象棋程序設(shè)計探索(四)：啟發(fā)算法_files/background.gif>
<DL>
<DIV align=center>
<CENTER>
<DT><FONT face=隸書 size=6>解剖大象的眼睛</FONT><FONT
size=6><STRONG>——</STRONG></FONT><FONT face=隸書 size=6>中國象棋程序設(shè)計探索</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>聯(lián)系地址：復(fù)旦大學(xué)化學(xué)系表面化學(xué)實(shí)驗室，<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>啟發(fā)算法</STRONG></FONT>
<DT>
<DT><FONT face=Arial size=4><STRONG>4.1 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>啟發(fā)算法概述</STRONG></FONT>
<DT>
<DT> <FONT face="Times New Roman">Laram</FONT>é<FONT
face="Times New Roman">e</FONT>的《<A
href="http://www.elephantbase.net/computer/basic_search.htm"
target=_blank>國際象棋程序設(shè)計<FONT face="Times New Roman">(</FONT>四<FONT
face="Times New Roman">)</FONT>：基本搜索方法</A>》連載中曾經(jīng)提到，<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索的結(jié)點(diǎn)數(shù)，數(shù)量相當(dāng)于最笨的“最小<FONT
face="Times New Roman">-</FONT>最大”搜索的平方根。嚴(yán)格來說，如果搜索樹在每個結(jié)點(diǎn)的分枝因子都是<FONT
face="Times New Roman"><EM>b</EM></FONT>，那么<FONT
face="Times New Roman"><EM>d</EM></FONT>層<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索在最好情況下搜索的結(jié)點(diǎn)數(shù)是：<FONT
face="Times New Roman"><EM>b</EM><SUP>[<EM>d</EM> / 2]</SUP> +
<EM>b</EM><SUP>[(<EM>d </EM>+ 1) / 2] </SUP></FONT><FONT
face=Symbol>-</FONT><FONT face="Times New Roman"> 1(</FONT>都是指葉子結(jié)點(diǎn)，其中<FONT
face="Times New Roman"><EM>b</EM><SUP>[<EM>d</EM> / 2] </SUP></FONT><FONT
face=Symbol>-</FONT><FONT face="Times New Roman"> 1</FONT>個是<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)，<FONT
face="Times New Roman"><EM>b</EM><SUP>[(<EM>d</EM> + 1) / 2]
</SUP></FONT><FONT face=Symbol>-</FONT><FONT face="Times New Roman">
1</FONT>個是<FONT face="Times New Roman">Beta</FONT>結(jié)點(diǎn)，<FONT
face="Times New Roman">1</FONT>個是<FONT face="Times New Roman">PV</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">)</FONT>，這樣的搜索樹稱為“最小樹”。因此，讓<FONT
face="Times New Roman">Alpha-Beta</FONT>的搜索樹盡可能地接近最小樹是非常重要的，相關(guān)的措施在廣義上都稱為“啟發(fā)”<FONT
face="Times New Roman">(Heuristic)</FONT>。
<DT> 由于<FONT
face="Times New Roman">Alpha-Beta</FONT>搜索對著法順序非常敏感，因此對著法進(jìn)行排序，是體現(xiàn)<FONT
face="Times New Roman">Alpha-Beta</FONT>算法效率的關(guān)鍵所在，這就是我們狹義上所說的啟發(fā)，即通過排序盡量首先搜索最好的著法。著法啟發(fā)通常有置換表啟發(fā)、吃子啟發(fā)、殺手著法啟發(fā)和歷史表啟發(fā)這四種最為常用的算法。廣義上的啟發(fā)還可以通過改變窗口寬度來實(shí)現(xiàn)，因為改變窗口寬度也可以提高<FONT
face="Times New Roman">Alpha-Beta</FONT>的截斷效率，因此很多<FONT
face="Times New Roman">Alpha-Beta</FONT>的變種算法實(shí)際上都屬于啟發(fā)這個范疇，例如期望窗口、<FONT
face="Times New Roman">PVS</FONT>和<FONT
face="Times New Roman">MTD(<EM>f</EM>)</FONT>。
<DT> 本章我們只討論著法啟發(fā)。
<DT>
<DT><FONT face=Arial size=4><STRONG>4.2 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>靜態(tài)著法啟發(fā)</STRONG></FONT>
<DT>
<DT> 靜態(tài)著法啟發(fā)是指不依賴于搜索結(jié)果的著法排序方式，即程序分析了某個局面后，不經(jīng)過搜索，就大致應(yīng)該知道哪些著法應(yīng)該首先嘗試。在上面提到的<FONT
face="Times New Roman">4</FONT>種著法啟發(fā)中，吃子啟發(fā)是靜態(tài)著法啟發(fā)，因為吃子著法數(shù)量不多，而且往往很多情況能立刻得到實(shí)惠，所以需要首先考慮。而置換表啟發(fā)、殺手著法啟發(fā)和歷史表啟發(fā)，都依賴于以前搜索的結(jié)果，因此屬于動態(tài)著法啟發(fā)的范疇。
<DT> 在<FONT
face="Times New Roman">ElephantEye</FONT>中，吃子著法是有選擇的，即“表面上立刻能得到實(shí)惠”的著法。為此<FONT
face="Times New Roman">ElephantEye</FONT>用了一個稱為<FONT
face="Times New Roman">MVV(LVA)</FONT>的策略，在被吃子有保護(hù)的情況下，考慮<FONT
face="Times New Roman">MVV(</FONT>被吃子價值<FONT
face="Times New Roman">)-LVA(</FONT>攻擊子價值<FONT
face="Times New Roman">)</FONT>的值，而在被吃子沒保護(hù)的情況下，只考慮<FONT
face="Times New Roman">MVV</FONT>的值，然后對這種策略產(chǎn)生的<FONT
face="Times New Roman">MVV(LVA)</FONT>值作排序，并選擇<FONT
face="Times New Roman">MVV(LVA)</FONT>大于零的著法首先搜索。為此，<FONT
face="Times New Roman"><genmoves.cpp></FONT>提供了一個稱為“<FONT
face="Times New Roman">Protected()</FONT>”的函數(shù)，對某個棋子是否有保護(hù)作快速判斷。
<DT> 吃子啟發(fā)僅僅是靜態(tài)著法啟發(fā)的最明顯的表現(xiàn)，事實(shí)上這類啟發(fā)還體現(xiàn)在其他地方。當(dāng)搜索進(jìn)行初期，置換表、殺手著法、歷史表等動態(tài)著法啟發(fā)還沒起作用，此時著法生成的順序就起了主要作用。因此，在著法生成時，考慮首先生成車的著法，最后生成帥<FONT
face="Times New Roman">(</FONT>將<FONT
face="Times New Roman">)</FONT>的著法，往往是很有效的；而在生成車的著法時，首先生成車向前走的著法，然后生成車向后走的著法，也能起到一定的啟發(fā)作用。因此，這種靜態(tài)著法啟發(fā)也是很多程序所考慮的。
<DT>
<DT><FONT face=Arial size=4><STRONG>4.3</STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG> 置換表啟發(fā)和低出</STRONG></FONT><FONT face=Arial
size=4><STRONG>(</STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>高出</STRONG></FONT><FONT face=Arial
size=4><STRONG>)</STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>邊界的修正</STRONG></FONT>
<DT>
<DT> 在置換表中保存一個著法，一方面可以利用置換表來獲得主要變例，但最主要的作用是置換表啟發(fā)。在探測置換表時，盡管局面命中但深度沒達(dá)到要求時，至少可以得到一個著法，這個著法應(yīng)該首先搜索，幾乎所有的象棋程序都是這么做的。哪些著法應(yīng)該被保存到置換表中呢？實(shí)踐證明，<FONT
face="Times New Roman">PV</FONT>結(jié)點(diǎn)中的最佳著法，以及<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)中產(chǎn)生截斷的著法，都應(yīng)該被保存到置換表中，而<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)盡管也要保存，但不要保存著法<FONT
face="Times New Roman">(</FONT>置換表著法是空的<FONT
face="Times New Roman">)</FONT>，因為<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)的每個著法都返回<FONT
face="Times New Roman">Alpha</FONT>值，我們不知道哪個著法是最好的。
<DT> 顯然，當(dāng)探測置換表時找到<FONT face="Times New Roman">PV</FONT>結(jié)點(diǎn)或<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">(</FONT>但深度不夠<FONT
face="Times New Roman">)</FONT>，就會有需要首先搜索的置換表著法。那么，找到<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)時，是否還會有置換表著法呢？中國象棋程序“縱馬奔流”采取了一個稱為“低出<FONT
face="Times New Roman">(</FONT>高出<FONT
face="Times New Roman">)</FONT>邊界的修正”策略，使得某些<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)也存在置換表著法。
<DT> “低出邊界的修正”指的是，當(dāng)某個<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)覆蓋某個相同局面的置換表項時，保留該表項的最佳著法。相應(yīng)地，當(dāng)某個<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)沒能覆蓋某個相同局面的置換表項<FONT
face="Times New Roman">(</FONT>該表項記錄了一個沒有著法的<FONT
face="Times New Roman">Alpha</FONT>結(jié)點(diǎn)<FONT
face="Times New Roman">)</FONT>時，只把這個<FONT
face="Times New Roman">Beta</FONT>結(jié)點(diǎn)的截斷著法寫入該置換表項，稱為“高出邊界的修正”。在前一章介紹的雙層置換表的覆蓋策略中，第一層<FONT
face="Times New Roman">(</FONT>深度優(yōu)先<FONT
face="Times New Roman">)</FONT>需要考慮“低出邊界的修正”和“高出邊界的修正”，而第二層<FONT
face="Times New Roman">(</FONT>始終覆蓋<FONT
face="Times New Roman">)</FONT>則只需要考慮“低出邊界的修正”。
<DT>
<DT><FONT face=Arial size=4><STRONG>4.4 </STRONG></FONT><FONT face=楷體_GB2312
size=4><STRONG>殺手著法啟發(fā)</STRONG></FONT>
<DT>
<DT> 殺手著法啟發(fā)<FONT face="Times New Roman">(Killer
Heuristic)</FONT>是基于這樣一個思想，搜索某個結(jié)點(diǎn)時首先嘗試著法<FONT
face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>，由<FONT
face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>的后續(xù)著法<FONT
face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>產(chǎn)生截斷，回到原來的結(jié)點(diǎn)時再搜索<FONT
face="Times New Roman"><EM>a</EM><SUB>1</SUB></FONT>的兄弟結(jié)點(diǎn)<FONT
face="Times New Roman"><EM>a</EM><SUB>2</SUB></FONT>時，如果<FONT
face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>仍舊是<FONT
face="Times New Roman"><EM>a</EM><SUB>2</SUB></FONT>的后續(xù)著法，那么<FONT
face="Times New Roman"><EM>b</EM><SUB>1</SUB></FONT>很有可能也會產(chǎn)生截斷。
<DT> 采用殺手著法啟發(fā)時，需要構(gòu)造一個稱為<FONT
face="Times New Roman">KillerMoves[MaxPly]</FONT>的全局?jǐn)?shù)組。搜索到深度為<FONT
face="Times New Roman">Ply</FONT>的結(jié)點(diǎn)時，首先嘗試<FONT
face="Times New Roman">KillerMoves[Ply]</FONT>的著法<FONT
face="Times New Roman">(</FONT>前提是該著法在當(dāng)前局面下是合理的<FONT
face="Times New Roman">)</FONT>，搜索完這個結(jié)點(diǎn)時，把產(chǎn)生截斷的著法<FONT
face="Times New Roman">(</FONT>如果有的話<FONT
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -