【文章內容簡介】 每個結點都打一個分值來評價其對應的局面（這一任務由后面所講的局面評估來完成），那么可以通過比較該分值的大小來判斷局面的優(yōu)劣。假定甲乙兩方下棋，甲勝的局面是一個極大值（一個很大的正數），那么乙勝的局面就是一個極小值（極大值的負值），和棋的局面則是零值（或是接近零的值）。如此，當輪到甲走棋時他會盡可能地讓局面上的分值大，相反輪到乙走棋時他會選盡可能地讓局面上的分值小。反映到博弈樹上，即如果假設奇數層表示輪到甲方走棋，偶數層表示輪到乙方走棋。那么由于甲方希望棋盤上的分值盡可能大，則在偶數層上會挑選分值最大的結點——偶數層的結點是甲走完一步棋之后的棋盤局面，反映了甲方對棋局形勢的要求。同樣道理，由于乙方希望棋盤上的分值盡可能小，那么在奇數層上會選擇分值最小的結點。這是“最小最大”（Minimax）的基本思想。這樣搜索函數在估值函數的協(xié)助下可以通過在奇數層選擇分值最大（最?。┑慕Y點，在偶數層選擇分值最?。ㄗ畲螅┑慕Y點的方式來搜索以當前局面為根結點、限定搜索層數以內的整棵樹來獲得一個最佳的著法。然而不幸的是，博弈樹相當龐大（它會成指數增長），因而搜索（限定層數以內的）整棵樹是一件相當費時的工作——其時間復雜度為O(bn)。其中b是分枝因子，即針對各種局面的合法著法的數目的平均值，n是搜索的深度。對于中國象棋而言，在中盤時平均著法數目大約是40種左右，那么搜索4層需要檢查250萬條路線，搜索5層需要檢查1億條路線，搜索6層需要檢查40億條路線！AlphaBeta搜索能在不影響搜索精度的前提下大幅減少工作量。因為，如果考慮到下棋是一個你來我往的交替進行并且相互“較勁”的過程。由于每一方都會盡可能將局面導向對自己有利而對對方不利的方向（假定下棋雙方對棋局有著同樣的認知，即你認為對你很糟糕的局面，在你的對手看來則是對他很有利的局面），那么某些局面由于能夠產生出很糟糕的局面因而根本沒有再繼續(xù)考慮的價值。所以當你看到某個局面有可能產生很糟糕的局面時（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的），你應當立刻停止對其剩余子結點的分析——不要對它再抱任何幻想了，如果你選擇了它，那么你必將得到那個很糟糕的局面，甚至可能更糟……這樣一來便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪”。下面用圖來進一步說明“樹的裁剪”。為了簡便起見，將博弈樹進行了簡化——每個結點只有三個分支，實際情況中，剛才講過在盤中應有大約40個分支。假定棋盤上的局面發(fā)展到了結點A（圖3），現(xiàn)在輪到你走棋了，你是“最大的一方”——即你希望棋局的分值盡可能的高。用搜索兩層來看一看“樹的裁剪”對提高搜索效率的幫助。圖中表示該結點要取子結點中的最大值；表示該結點要取子結點中的最小值。圖3 樹的裁剪首先，考察結點A的子結點B。結點B所屬的這一層是輪到你的對手——“最小者”來走棋了，目的是使得棋局的分值盡可能的小。依次考察結點B的各個子結點，查看它們的分值（因為事先約定好了搜索兩層，現(xiàn)在已達到搜索深度的要求了，所以就停下來調用局面評估函數來給它打分）。結點B的第一個子結點（從左到右算起）返回10，第二個子結點返回了5，第三個子結點返回了2。由于結點B這層是你的對手來做選擇，假設他一定會做出明智的選擇（你不能寄希望于你的對手會走出一步“昏招”），那么他會選擇返回值為5的那個結點。5最終也就成了從結點B傳遞回的值，即倘若你（現(xiàn)在位于結點A）選擇了產生結點B的走法，使得局面發(fā)展到了結點B。那么下一步，你的對手的選擇就會使得棋局發(fā)展成為分值為5的那個結點所表示的局面。再來分析結點A的第二個子結點C，結點C與結點B同屬一層，它依然是輪到你的對手作選擇。依次查看結點C的各個子結點的分值，其第一個子結點返回了8……采用 “裁剪”方法。不必再繼續(xù)考察結點C的剩余子結點了，因為結點C已經夠糟糕的了，不管結點C的剩余子結點有怎樣的分值，它最多只能傳回8（有可能其剩余子結點中還有分值更小的結點，因而結點C還有可能傳回更小的值）。而與前面已經分析過的結點B所傳回5相比較，作為“最大一方”的你顯然更不愿意看到8的局面。所以，你當然不會選擇相應的著法使得局面發(fā)展成為結點C。因為那樣的話，下一步你的對手就會帶給你一個分值不高于8的局面。由此，在不影響搜索質量的前提下避免了搜索“無價值的”結點C的剩余子結點的大量工作，從而節(jié)省了寶貴時間，為在同樣機器配置下搜索更多的層數提供了可能?！白钚∽畲蟆钡乃枷朐偌由稀皩涞牟眉簟?，這就是AlphaBeta搜索算法的核心。最基本的AlphaBeta算法的代碼如下：int AlphaBeta(int depth, int alpha, int beta){ if (depth == 0) //如果是葉子節(jié)點（到達搜索深度要求） return Evaluate()。 //則由局面評估函數返回估值 GenerateLegalMoves()。 //產生所有合法著法 while (MovesLeft()) //遍歷所有著法 { MakeNextMove()。 //執(zhí)行著法 int val = AlphaBeta(depth 1, beta, alpha)。 //遞歸調用 UnmakeMove()。 //撤銷著法 if (val = beta) //裁剪 return beta。 if (val alpha) //保留最大值 alpha = val。 } return alpha。} 歷史啟發(fā)及著法排序既然AlphaBeta搜索算法是在“最小最大”的基礎上引入“樹的裁剪”的思想以期提高效率，那么它的效率將在很大程度上取決于樹的結構——如果搜索了沒多久就發(fā)現(xiàn)可以進行“裁剪”了，那么需要分析的工作量將大大減少，效率自然也就大大提高；而如果直至分析了所有的可能性之后才能做出“裁剪”操作，那此時“裁剪”也已經失去了它原有的價值（因為你已經分析了所有情況，這時的AlphaBeta搜索已和“最小最大”搜索別無二致了）。因而，要想保證AlphaBeta搜索算法的效率就需要調整樹的結構，即調整待搜索的結點的順序，使得“裁剪”可以盡可能早地發(fā)生?？梢愿鶕糠忠呀浰阉鬟^的結果來調整將要搜索的結點的順序。因為，通常當一個局面經過搜索被認為較好時，其子結點中往往有一些與它相似的局面（如個別無關緊要的棋子位置有所不同）也是較好的?！皻v史啟發(fā)”（History Heuristic）就是建立在這樣一種觀點之上的。在搜索的過程中，每當發(fā)現(xiàn)一個好的走法，就給該走法累加一個增量以記錄其“歷史得分”，一個多次被搜索并認為是好的走法的“歷史得分”就會較高。對于即將搜索的結點，按照“歷史得分”的高低對它們進行排序，保證較好的走法（“歷史得分”高的走法）排在前面，這樣AlphaBeta搜索就可以盡可能早地進行“裁剪”，從而保證了搜索的效率。對于著法的排序可以使用各種排序算法，在程序中采用了歸并排序。歸并排序的空間復雜度為O(n)，時間復雜度為O(nlog2n)，具有較高的效率。 局面評估前文已經講過了棋局表示、著法生成、搜索算法（包括搜索輔助）， 在象棋程序中如果說搜索算法是心臟，那么局面評估就是大腦。搜索算法負責驅動整個程序，而局面評估則負責對搜索的內容進行判斷和評價。因而搜索與局面評估是整個下棋引擎的核心。首先，先介紹一下在局面評估中需要考慮的因素。就不同的棋類可能要考慮的因素略有差異。在中國象棋中所要考慮的最基本的幾個因素包括如下四點：子力總和子力是指某一棋子本身所具有的價值。通俗地講就是一個棋子它值個什么價。例如，車值500的話，那可能馬值300，卒值80等等。所以在評估局面時，首先要考慮雙方的子力總和的對比。比如紅方擁有士象全加車馬炮，而黑