【文章內(nèi)容簡介】 成計算機的著法時認(rèn)為將帥碰面是非法的，而對用戶所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了） 。產(chǎn)生了著法后要將其存入著法隊列以供搜索之用，由于搜索會搜索多層（即考慮雙方你來我往好幾步，這樣才有利于對局面進行評估以盡可能避免“目光短淺” ） ，所以在把著法存入著法隊列的時候還要同時存儲該著法所屬的搜索層數(shù)。因此可以將著法隊列定義為二維數(shù)組 m_MoveList[8][80]，其中第一個數(shù)組下標(biāo)為層數(shù)，第二個數(shù)組下標(biāo)為每一層的全部著法數(shù)。關(guān)于搜索層數(shù)，設(shè)定為 8，實際使用的是 1 到 7（在界面中將其限定為 1—7） 。搜索層數(shù)的增加會顯著提高電腦的下棋水平（當(dāng)然計算機的棋力在很大程度上也依賴于局面評估） 。在配置為 ，512M 內(nèi)存的計算機上最多只能搜索4 層，再多將導(dǎo)致搜索時間達(dá)到令人無法容忍的地步（這里還需要特別說明的是，搜索的速度也和著法生成的效率以及局面評估的復(fù)雜度有關(guān)，因為每分析一個結(jié)點都要執(zhí)行這兩種操作） 。對于每一層的著法數(shù)，也就是當(dāng)前下棋方針對當(dāng)前局面的所有可選的合法著法，據(jù)有關(guān)數(shù)據(jù)統(tǒng)計在象棋實戰(zhàn)中一般最多情況下也就五六十種。定義第二個數(shù)組下標(biāo)為 80，應(yīng)當(dāng)可以保證十分的安全。著法生成為搜索部分提供了“原料” ，接下來的任務(wù)就交給搜索和局面評估了。 搜索算法搜索算法對于整個下棋引擎來說都是至關(guān)重要的。它如同程序的心臟，驅(qū)動著整個程序。搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計算機的下棋水平。因為，計算機必須在有限的時間內(nèi)完成思考，搜索速度快意味著在相同的時間內(nèi)程序可以“看”得更遠(yuǎn)， “想”的更多） 。關(guān)于棋類對弈程序中的搜索算法，已有成熟的 AlphaBeta 搜索算法以及其它一些輔助增強算法（還有眾多基于 AlphaBeta 算法的派生、變種算法）在程序中直接借鑒了 AlphaBeta 搜索算法并輔以了歷史啟發(fā)。本節(jié)先介紹 AlphaBeta 搜索算法：在中國象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。由此，可以用一棵“博弈樹” （圖 2）來表示下棋的過程——樹中每一個結(jié)點代表棋盤上的一個局面，對每一個局面（結(jié)點）根據(jù)不同的走法又產(chǎn)生不同的局面（生出新的結(jié)點） ，如此不斷直到再無可選擇的走法，即到達(dá)葉子結(jié)點（棋局結(jié)束） 。中國象棋的博弈樹的模型大概如下圖所示，可以把其中連接結(jié)點的線段看作是著法，不同的著法自然產(chǎn)生不同的局面。。表示黑方走棋表示紅方走棋圖 2 博弈樹該樹包含三種類型的結(jié)點： 奇數(shù)層的中間結(jié)點（以及根結(jié)點） ，表示輪到紅方走棋； 偶數(shù)層的中間結(jié)點，表示輪到黑方走棋； 葉子結(jié)點，表示棋局結(jié)束。現(xiàn)在讓計算機來下中國象棋，它應(yīng)當(dāng)選擇一步對它最有利的著法（最終導(dǎo)致它取勝的著法） 。獲得最佳著法的方法就是“試走”每一種可能的著法，比較它們所產(chǎn)生的不同后果，然后從中選出能夠產(chǎn)生對自己最有利的局面的著法。結(jié)合上面所講的博弈樹，若給每個結(jié)點都打一個分值來評價其對應(yīng)的局面（這一任務(wù)由后面所講的局面評估來完成） ，那么可以通過比較該分值的大小來判斷局面的優(yōu)劣。假定甲乙兩方下棋，甲勝的局面是一個極大值（一個很大的正數(shù)） ，那么乙勝的局面就是一個極小值（極大值的負(fù)值） ，和棋的局面則是零值（或是接近零的值） 。如此，當(dāng)輪到甲走棋時他會盡可能地讓局面上的分值大，相反輪到乙走棋時他會選盡可能地讓局面上的分值小。反映到博弈樹上，即如果假設(shè)奇數(shù)層表示輪到甲方走棋，偶數(shù)層表示輪到乙方走棋。那么由于甲方希望棋盤上的分值盡可能大，則在偶數(shù)層上會挑選分值最大的結(jié)點——偶數(shù)層的結(jié)點是甲走完一步棋之后的棋盤局面，反映了甲方對棋局形勢的要求。同樣道理，由于乙方希望棋盤上的分值盡可能小，那么在奇數(shù)層上會選擇分值最小的結(jié)點。這是“最小最大” （Minimax）的基本思想。這樣搜索函數(shù)在估值函數(shù)的協(xié)助下可以通過在奇數(shù)層選擇分值最大（最?。┑慕Y(jié)點，在偶數(shù)層選擇分值最?。ㄗ畲螅┑慕Y(jié)點的方式來搜索以當(dāng)前局面為根結(jié)點、限定搜索層數(shù)以內(nèi)的整棵樹來獲得一個最佳的著法。然而不幸的是，博弈樹相當(dāng)龐大（它會成指數(shù)增長） ，因而搜索（限定層數(shù)以內(nèi)的）整棵樹是一件相當(dāng)費時的工作——其時間復(fù)雜度為 O(bn)。其中 b 是分枝因子，即針對各種局面的合法著法的數(shù)目的平均值，n 是搜索的深度。對于中國象棋而言，在中盤時平均著法數(shù)目大約是 40 種左右，那么搜索 4 層需要檢查 250 萬條路線，搜索 5 層需要檢查 1 億條路線，搜索 6 層需要檢查 40 億條路線！AlphaBeta 搜索能在不影響搜索精度的前提下大幅減少工作量。因為，如果考慮到下棋是一個你來我往的交替進行并且相互“較勁”的過程。由于每一方都會盡可能將局面導(dǎo)向?qū)ψ约河欣鴮Ψ讲焕姆较颍俣ㄏ缕咫p方對棋局有著同樣的認(rèn)知，即你認(rèn)為對你很糟糕的局面，在你的對手看來則是對他很有利的局面） ，那么某些局面由于能夠產(chǎn)生出很糟糕的局面因而根本沒有再繼續(xù)考慮的價值。所以當(dāng)你看到某個局面有可能產(chǎn)生很糟糕的局面時（確切地說這里的“很糟糕”是與之前分析的情況相比較而言的） ，你應(yīng)當(dāng)立刻停止對其剩余子結(jié)點的分析——不要對它再抱任何幻想了，如果你選擇了它，那么你必將得到那個很糟糕的局面，甚至可能更糟……這樣一來便可以在很大程度上減少搜索的工作量，提高搜索效率，這稱為“樹的裁剪” 。下面用圖來進一步說明“樹的裁剪” 。為了簡便起見，將博弈樹進行了簡化——每個結(jié)點只有三個分支，實際情況中，剛才講過在盤中應(yīng)有大約 40 個分支。假定棋盤上的局面發(fā)展到了結(jié)點 A（圖 3） ，現(xiàn)在輪到你走棋了，你是“最大的一方”——即你希望棋局的分值盡可能的高。用搜索兩層來看一看“樹的裁剪”對提高搜索效率的幫助。圖中 表示該結(jié)點要取子結(jié)點中的最大值； 表示該結(jié)點要取子結(jié)點中的最小值。ＡＢ Ｃ Ｄ1 0 5 2 8？ ？ 。 。 。 。 。 。圖 3 樹的裁剪首先，考察結(jié)點 A 的子結(jié)點 B。結(jié)點 B 所屬的這一層是輪到你的對手——“最小者”來走棋了，目的是使得棋局的分值盡可能的小。依次考察結(jié)點 B 的各個子結(jié)點，查看它們的分值（因為事先約定好了搜索兩層，現(xiàn)在已達(dá)到搜索深度的要求了，所以就停下來調(diào)用局面評估函數(shù)來給它打分） 。結(jié)點 B 的第一個子結(jié)點（從左到右算起）返回 10，第二個子結(jié)點返回了5，第三個子結(jié)點返回了 2。由于結(jié)點 B 這層是你的對手來做選擇，假設(shè)他一定會做出明智的選擇（你不能寄希望于你的對手會走出一步“昏招” ） ，那么他會選擇返回值為5 的那個結(jié)點。5 最終也就成了從結(jié)點 B 傳遞回的值，即倘若你（現(xiàn)在位于結(jié)點A）選擇了產(chǎn)生結(jié)點 B 的走法，使得局面發(fā)展到了結(jié)點 B。那么下一步，你的對手的選擇就會使得棋局發(fā)展成為分值為5 的那個結(jié)點所表示的局面。再來分析結(jié)點 A 的第二個子結(jié)點 C，結(jié)點 C 與結(jié)點 B 同屬一層，它依然是輪到你的對手作選擇。依次查看結(jié)點 C 的各個子結(jié)點的分值，其第一個子結(jié)點返回了8……采用 “裁剪”方法。不必再繼續(xù)考察結(jié)點 C 的剩余子結(jié)點了，因為結(jié)點 C已經(jīng)夠糟糕的了，不管結(jié)點 C 的剩余子結(jié)點有怎樣的分值，它最多只能傳回8（有可能其剩余子結(jié)點中還有分值更小的結(jié)點，因而結(jié)點 C 還有可能傳回更小的值） 。而與前面已經(jīng)分析過的結(jié)點 B 所傳回5 相比較，作為“最大一方”的你顯然更不愿意看到8 的局面。所以，你當(dāng)然不會選擇相應(yīng)的著法使得局面發(fā)展成為結(jié)點 C。因為那樣的話，下一步你的對手就會帶給你一個分值不高于8的局面。由此，在不影響搜索質(zhì)量的前提下避免了搜索“無價值的”結(jié)點 C 的剩余子結(jié)點的大量工作，從而節(jié)省了寶貴時間，為在同樣機器配置下搜索更多的層數(shù)提供了可能?！白钚∽畲蟆钡乃枷朐偌由稀皩涞牟眉簟?，這就是 AlphaBeta 搜索算法的核心。最基本的 AlphaBeta 算法的代碼如下：int AlphaBeta(int depth, int alpha, int beta){if (depth == 0) //如果是葉子節(jié)點（到達(dá)搜索深度要求）return Evaluate()。 //則由局面評估函數(shù)返回估值GenerateLegalMoves()。 //產(chǎn)生所有合法著法while (MovesLeft()) //遍歷所有著法{MakeNextMove()。 //執(zhí)行著法int val = AlphaBeta(depth 1, beta, alpha)。 //遞歸調(diào)用UnmakeMove()。 //撤銷著法if (val = beta) //裁剪return beta。if (val alpha) //保留最大值alpha = val。}return alpha。} 歷史啟發(fā)及著法排序既然 Alpha