面向計(jì)算機(jī)博弈的高級(jí)搜索技術(shù)徐長明、徐心和、王翠榮2011.06.13大綱再談alpha與beta迭代搜索渴望搜索主要變異（極小窗口）搜索NULLMOVE搜索著法順序相關(guān)的啟發(fā)式其它零再談alpha與beta最原始的alpha和beta涵義再談alpha與betaalpha和beta是搜索過程中的重要約束，違反該約束的分支對(duì)最終的搜索結(jié)果不起作用，因而應(yīng)將其剪枝（alpha剪枝或beta剪枝）。因此，搜索算法能產(chǎn)生的剪枝越多越好；對(duì)于一個(gè)特定的結(jié)點(diǎn)，剪枝產(chǎn)生的越早越好。

采用最樸素的alpha-beta搜索計(jì)算的結(jié)果與MiniMax搜索來計(jì)算的結(jié)果是完全一樣的。174298MAXMINMIN77(1)下圖是何種剪枝？再談alpha與betaMAXMAXMIN45682434(2)下圖是何種剪枝？再談alpha與beta最原始的alpha和beta再談alpha與beta1）Max手握alpha，使alpha有不斷增大的趨勢；Min手握beta，使beta有不斷減小的趨勢。Max的alpha值對(duì)應(yīng)一個(gè)葉節(jié)點(diǎn)的值；Min的beta值也對(duì)應(yīng)一個(gè)葉節(jié)點(diǎn)的值。2）產(chǎn)生剪枝的唯一根據(jù)是“alpha≥beta”。雙方均能接受的值應(yīng)當(dāng)落在(alpha，beta)區(qū)間上，該約束一般被稱為窗口。（試想：為什么“alpha≥beta”就一定剪枝？）最原始的alpha和beta再談alpha與beta3）alpha剪枝是因?yàn)閎eta突然被兒子結(jié)點(diǎn)的返回值減小，減小后的beta滿足了2），或者說，違背了約束alpha；類似地，beta剪枝是因?yàn)閍lpha突然被兒子結(jié)點(diǎn)的返回值增大，增大后的alpha滿足了2），或者說，違背了約束beta。4）基于NegaMax的alpha-beta搜索中，僅有beta剪枝。窗口的初始化再談alpha與beta1）在最樸素的alpha-beta搜索中，初始窗口取為(-INFINITY,+INFINITY)。這代表，在開始搜索之前，Max和Min都做最壞的假定，它保證了最佳解（特定條件下的博弈樹中的某個(gè)葉子）一定包含在搜索的狀態(tài)空間之中。2）思考問題：若初始窗口比(-INFINITY,+INFINITY)小，能保證搜索一定找到最優(yōu)解么？

答：不能保證。Why？…搜索算法中的窗口再談alpha與beta1）在搜索算法的執(zhí)行中，窗口充當(dāng)了約束（相當(dāng)于多主體的分支界限法）。a）屬于Max（在偶數(shù)層）的祖先結(jié)點(diǎn)向?qū)?yīng)子樹中的偶數(shù)層子孫結(jié)點(diǎn)施加了alpha約束；b）屬于Min（在奇數(shù)層）的祖先結(jié)點(diǎn)向?qū)?yīng)子樹中的奇數(shù)層子孫結(jié)點(diǎn)施加了alpha約束。搜索算法中的窗口再談alpha與beta2）在搜索函數(shù)的遞歸調(diào)用中，從父節(jié)點(diǎn)向子節(jié)點(diǎn)傳遞了一個(gè)窗口，但從兒子結(jié)點(diǎn)僅返回一個(gè)返回值，不返回窗口。3）窗口是以“值傳遞”的形式向下傳播給子孫結(jié)點(diǎn)的。4）從兒子返回的（估值，或搜索函數(shù)返回值）值：Max結(jié)點(diǎn)返回alpha，其值可能修改祖先的beta；Min結(jié)點(diǎn)返回beta，其值可能修改祖先的alpha。MAXMAXMIN45682434黑板上演示窗口變化！再談alpha與beta返回值與窗口再談alpha與betaA1A2A3An…（alpha，beta）Value=-Search()If(Value<=alpha)A1A2A3An…Value=-Search()返回值對(duì)(alpha,beta)窗口的影響（情形1）（alpha，beta）MINMAXA1A2A3An…（alphaValue，beta）Value=-Search()If(Value>alpha&&

Value<beta)A1A2A3An…Value=-Search()返回值對(duì)(alpha,beta)窗口的影響（情形2）（alpha，beta）MINMAX返回值與窗口再談alpha與beta返回值對(duì)(alpha,beta)窗口的影響（情形3）A1A2A3An…If(Value>=beta)A1A2A3An…Value=-Search()（alpha，beta）發(fā)生了剪枝（Pruning/cutting-off）MINMAX返回值與窗口再談alpha與beta嘗試小的初始窗口在樸素alpha-beta搜索中，初始窗口為（-INFINITY,+INFINITY）。考慮不采用（-INFINITY,+INFINITY）。若給定博弈樹和估值函數(shù)，則其解也隨之確定，若解的真實(shí)估值為v。a）當(dāng)分別采用包含了v的兩個(gè)初始窗口分別搜索時(shí)，每個(gè)搜索算法都能找到解，且小窗口的剪枝效率更高！b）當(dāng)所采納的初始窗口并沒有包含v，則搜索算法將錯(cuò)失解。這時(shí)，需要關(guān)注兩種樸素alpha-beta搜索算法。再談alpha與betaFail-hardalpha-beta再談alpha與betaFail-softalpha-beta再談alpha與betaFail-softvs.Fail-hard再談alpha與beta1）只有在采用了非全窗口的初始窗口時(shí)，討論Fail-soft和Fail-hard才有意義。a）在根結(jié)點(diǎn)處采用非(-INFINITY,+INFINITY)。b）中間結(jié)點(diǎn)的全窗口是（alpha，beta），但在對(duì)應(yīng)的子樹采用（a0，b0）搜索。alpha<a0,beta<b0。Fail-softvs.Fail-hard再談alpha與beta2）Fail-soft在尋找解失敗的時(shí)候，可以指示真值在哪個(gè)范圍；Fail-hard無法區(qū)分開“找解失敗”與“真值為alpha”兩種情況，F(xiàn)ail-hard也不能在找解失敗后指出解的范圍。3）在沒有用全窗口搜索時(shí)，F(xiàn)ail-soft的返回值v<alpha,這是稱為Fail-low（與此情形區(qū)分）；v≥beta,稱為Fail-high（與此情形區(qū)分）。3）※Fail-soft是幾乎所有alpha-beta改進(jìn)算法的基礎(chǔ)。Fail-low/high與cutting-off再談alpha與beta

Fial-low/high是指返回值落在搜索前預(yù)設(shè)（猜測）的窗口(a,b)之外。Fail-high或Fail-low說明預(yù)先猜測的窗口范圍有失準(zhǔn)確，憑借該窗口尋找根節(jié)點(diǎn)的最佳著法的努力失敗了。剪枝是指某些著法或分枝對(duì)最終的搜索結(jié)果沒有影響，因而可以不搜索。1）改進(jìn)的前提：改進(jìn)后仍然能找到解。

2）改進(jìn)的途徑：a）在博弈樹中，更多地產(chǎn)生剪枝：找到某個(gè)比（-INFINITY，+INFINITY）小，但包含解v的小窗口。b）對(duì)于單個(gè)結(jié)點(diǎn)，更早地產(chǎn)生剪枝：著法排序，盡可能早地訪問最好的兒子。改進(jìn)alpha-beta的途徑再談alpha與beta壹迭代搜索寬度優(yōu)先：完備性、最優(yōu)性、空間瓶頸。深度優(yōu)先：非完備性、非最優(yōu)性、線性空間需求。雙向?qū)挾葍?yōu)先搜索：完備性、最優(yōu)性、空間瓶頸下降。幾種搜索策略迭代加深搜索當(dāng)采用深度優(yōu)先搜索方式時(shí)，因無法知道解的深度，最大搜索深度的設(shè)置便成了個(gè)難題。a）無法準(zhǔn)確地預(yù)測解的深度；b）因?yàn)楦傎悤r(shí)間有限制，程序可用的時(shí)間資源受限。無法精確控制時(shí)間（深度大可能超時(shí)，否則過早結(jié)束搜索）；最大深度的設(shè)定迭代加深搜索DFID(DepthFirstIterativeDeepening)的執(zhí)行過程如圖所示：

DFID迭代加深搜索DFID執(zhí)行過程的示意圖直至?xí)r間耗盡1）以深度優(yōu)先的方式模擬深度優(yōu)先，因而可找到路徑最短的解。2）迭代加深為優(yōu)化時(shí)間控制提供支持。3）淺層迭代對(duì)深層迭代有重要的啟發(fā)作用。4）迭代加深的額外代價(jià)并不高（見下頁的證明和解釋）。DFID的特點(diǎn)迭代加深搜索當(dāng)分枝因子為R，當(dāng)前迭代的最大深度為d時(shí)，DFID總的代價(jià)為：Time(R,d)=(

Rd

+2Rd-1+…+dR+(d+1)R0)=Rd(1+2R-1+…+dR1-d+(d+1)R-d)<Rd(1-1/R)-2R=2:Time(R,d)=4RdR=3:Time(R,d)=9/4RdR=4:Time(R,d)=16/9RdR=5:Time(R,d)=25/16Rd……可見，分支因子越大，迭代加深越有優(yōu)勢。DFID的特點(diǎn)迭代加深搜索還有一種稱為“迭代加寬”的迭代搜索技術(shù)?？傊趶?fù)雜棋類中，迭代以相對(duì)較小的代價(jià)獲取了有彈性的搜索控制策略，并提供了采用啟發(fā)式方法的重要途徑。總結(jié)迭代加深搜索二渴望搜索當(dāng)分枝因子為R，當(dāng)前迭代的最大深度為d時(shí)，DFID總的是一種猜測初始窗口的搜索?；谑虑安聹y的返回值val，預(yù)設(shè)初始窗口為（val－，val＋）。

基于fail-softalpha-beta搜索。執(zhí)行該搜索可有三種情況：

a）返回值v落在窗口(val－，val＋),v即為所求的值b）返回值v<val－時(shí)，用窗口(-,val－)重搜c）返回值v>=val+時(shí)，用窗口(val+,+)重搜若能正確猜測真值所在的窗口，搜索效率便有所提高。算法簡介渴望搜索偽代碼描述渴望搜索<

Val和對(duì)搜索效率的影響。

提升算法效率的最大障礙在于重搜的風(fēng)險(xiǎn)。涉及：a）Val如何取值？

b）如何取值？

效率分析渴望搜索三主要變異（極小窗口）搜索極小窗口（或空窗口）：a）設(shè)估值均為整數(shù)，稱(v,v+1)為極小窗口；b）搜索的結(jié)果(設(shè)返回值為val)要么Fail-low(val<=v)，要么Fail-high(val>v,即val>=v+1)c）既然窗口越小發(fā)生剪枝的概率就越高，那么，極小窗口可使得剪枝效率發(fā)揮到極致。極小窗口（或空窗口）極小窗口搜索極小窗口的用法：a）某節(jié)點(diǎn)A的窗口為(alpha,beta)，想驗(yàn)證“A的所有兄弟節(jié)點(diǎn)都不比A強(qiáng)”，只需構(gòu)造極小窗口(alpha,alpha+1)來搜索A的兄弟們；b）某節(jié)點(diǎn)B的窗口為(alpha,beta)，想驗(yàn)證其某個(gè)兒子是否“可以引發(fā)剪枝”，只需構(gòu)造極小窗口(beta-1,beta)來搜索該兒子。極小窗口的用法極小窗口搜索主要變異搜索(PVS，PrincipalVariationSearch)/極小窗口搜索（MinimalWindowSearch）的基本思想：對(duì)于任何一個(gè)節(jié)點(diǎn)，PVS總是假設(shè)其第一個(gè)兒子s0是最好的，直到證明某個(gè)兒子sn比s0還好。然后，再假設(shè)sn比其它兒子都好……注意：在博弈程序中，由于采用迭代加深、啟發(fā)式算法等優(yōu)化方法，著法生成、選擇和排序機(jī)制能夠讓第一個(gè)兒子以很大的概率可成為最佳著法。算法思想極小窗口搜索具體地，總是以全窗口（alpha,Beta）搜索第一個(gè)兒子s0，設(shè)得到的值為v，以窗口（v,v+1）去搜索其余的兒子。對(duì)于任意一個(gè)兒子si，若結(jié)果為Fail-low，則證明它不如s好，接著以窗口（v,v+1）去搜si+1；否則，必定是Fail-high，這說明si好于s0，這時(shí)，需要以構(gòu)造新的全窗口（v,Beta），并用該窗口重搜si，設(shè)得到的值為v′，再用（v′,v′+1）去搜后面的兒子…直到所有的兒子都得到搜索，算法結(jié)束。算法的自然語言描述極小窗口搜索舉例極小窗口搜索總結(jié)極小窗口搜索1）極小窗口搜索是非常優(yōu)秀的alpha-beta搜索算法，是復(fù)雜棋類中應(yīng)當(dāng)優(yōu)先考慮的算法。2）極小窗口、渴望窗口、迭代加深搜索經(jīng)常組合到一起使用。3）有一個(gè)類似的算法，稱為NegaScout。4）另外，MTD(f)也是一個(gè)優(yōu)秀的應(yīng)用極小窗口搜索的算法。它的主要思想屬于典型的分治，類似于折半查找。該算法應(yīng)用的時(shí)候有一定的限制；其優(yōu)點(diǎn)是易于并行計(jì)算。四NullMove搜索剪枝NullMove搜索1）驗(yàn)前剪枝(ForwardPruning)。

如：NullMove剪枝2）驗(yàn)后剪枝（BackwardPruning）

如：alpha-beta剪枝思想NullMove搜索1）一般而言，走棋總比不走棋要好，不走棋就是一步nullmove。2）將nullmove視為當(dāng)前局面的一個(gè)著法（即使不走棋是非法的），且若該著法所導(dǎo)致的子樹的值為v，應(yīng)該有v。3）若v，則說明，故應(yīng)立刻剪枝。Nullmove的使用NullMove搜索1）Null-move的條件

被將軍時(shí)不能用nullmove；不能連續(xù)nullmove；距離horizon太近（如3ply）不宜用nullmove；本方處于絕對(duì)劣勢時(shí)，不宜用nullmove；Zugzwang局面。2）為了用更小的代價(jià)剪枝，常常與極小窗口配合。3）用于檢測威脅。例如，若我走了nullmove，搜索的結(jié)果說在第N步會(huì)輸棋，則說明該局面潛伏著對(duì)我的嚴(yán)重威脅。所以，在搜索nullmove的兄弟節(jié)點(diǎn)時(shí)，要進(jìn)行適當(dāng)?shù)臍⑵逖由臁？偨Y(jié)NullMove搜索1）NullMove是Forwardpruning中極為有效的一種啟發(fā)方法。2）NullMove搜索的前提條件極為重要，應(yīng)用時(shí)需結(jié)合特定的上下文精心設(shè)計(jì)。五著法順序相關(guān)的啟發(fā)式著法順序著法順序相關(guān)的啟發(fā)1）著法順序不影響搜索的結(jié)果，但影響效率。2）如何改善著法排序的效率，是博弈程序優(yōu)化的一個(gè)重要方面。3）著法排序的目標(biāo)是使得最佳著法有更大的機(jī)會(huì)被優(yōu)先嘗試。4）著法排序的關(guān)鍵：a）著法排序的依據(jù)是什么？——先驗(yàn)經(jīng)驗(yàn)vs.后驗(yàn)經(jīng)驗(yàn)。b）排序的代價(jià)可接受么？——性能增益vs.排序代價(jià)。啟發(fā)式著法順序相關(guān)的啟發(fā)1）經(jīng)典人工智能的成就。如單一智能主體的A*搜索。2）啟發(fā)函數(shù)（啟發(fā)標(biāo)準(zhǔn)）的設(shè)計(jì)方法。a）第一步：形式化描述。b）第二步：松弛。3）博弈程序中常見的基于著法的啟發(fā)式方法：a）殺手啟發(fā)。b）歷史啟發(fā)。c）同形表啟發(fā)。d）預(yù)置表著法啟發(fā)。殺手啟發(fā)著法順序相關(guān)的啟發(fā)思想：更多更早地剪枝，則搜索效率必然更高；剛剛引發(fā)剪枝的著法，在不遠(yuǎn)的將來也很可能引發(fā)剪枝；總是優(yōu)先嘗試殺手著法，從而希望更快地剪枝。定義：引發(fā)剪枝的著法，稱為殺手(KillerMove)。實(shí)現(xiàn)：同層啟發(fā)，即在每一層都維護(hù)引發(fā)剪枝的k個(gè)殺手；殺手表采用先進(jìn)先出的隊(duì)列結(jié)構(gòu)，新殺手替代最老的殺手，并且維持好殺手之間的新舊順序。歷史啟發(fā)著法順序相關(guān)的啟發(fā)歷史啟發(fā)是一個(gè)調(diào)整節(jié)點(diǎn)排列順序的方法。國際象棋程序的經(jīng)驗(yàn)證明，歷史表是很好的走法排序依據(jù)。歷史啟發(fā)著法順序相關(guān)的啟發(fā)歷史啟發(fā)是一個(gè)調(diào)整節(jié)點(diǎn)排列順序的方法。國際象棋程序的經(jīng)驗(yàn)證明，歷史表是很好的走法排序依據(jù)。車8平6車8平6車8平6歷史啟發(fā)著法順序相關(guān)的啟發(fā)著法映射HistoryValueHistoryTable[90][90];

第一維坐標(biāo)表示著法的起始位置，第二維坐標(biāo)表示著法的終止位置。歷史啟發(fā)著法順序相關(guān)的啟發(fā)歷史得分權(quán)值。如果一個(gè)著法引發(fā)剪枝或者證明是最佳的，那么，應(yīng)該給這個(gè)著法多大的獎(jiǎng)勵(lì)值呢？a）JonathanSchaeffer給出的獎(jiǎng)勵(lì)值是2depth。

b）也有引擎給出depth*depth。c）但不管哪種獎(jiǎng)勵(lì)方法，要遵循一個(gè)原則，即在搜索樹中,越靠近根結(jié)點(diǎn)，獎(jiǎng)勵(lì)值也應(yīng)該越大。預(yù)置表啟發(fā)著法順序相關(guān)的啟發(fā)問題轉(zhuǎn)化（以“紅車”為例）預(yù)置表啟發(fā)著法順序相關(guān)的啟發(fā)車的水平預(yù)置表車的垂直預(yù)置表List*Rook_hor[90][1024]List*Rook_ver[90][1024][63][292][63][138]總結(jié)著法順序相關(guān)的啟發(fā)1）基于著法順序的相關(guān)啟發(fā)比較好的方法是：先將著法分類，再將最好的一類著法排序，直到所有此類著法都嘗試過，再對(duì)次好一類的著法進(jìn)行排序。2）一般而言，對(duì)全部著法一次性排序的代價(jià)比較大。六其它樹與圖其它1）博弈問題的實(shí)際狀態(tài)空間往往是圖；而博弈程序所采用搜索算法卻將狀態(tài)空間當(dāng)作樹來遍歷。2）重復(fù)出現(xiàn)在樹中的狀態(tài)可能致使計(jì)算冗余。1）忘記歷史必然導(dǎo)致重復(fù)歷史。應(yīng)當(dāng)記住已經(jīng)訪問過的大量狀態(tài)?！獱顟B(tài)數(shù)量大。2）尋找和設(shè)計(jì)一種數(shù)據(jù)結(jié)構(gòu)——同形表：a）可快速存儲(chǔ)、快速檢索的數(shù)據(jù)結(jié)構(gòu)?！猦ash表符合。b）hash表的設(shè)