【文章內(nèi)容簡介】 生成著法時，用查表取代計算。中國象棋每種棋子的行棋規(guī)則不同，生成每種棋子的著法和整個棋盤棋子的分布密切相關(guān)，如果建立每種棋子最大可能著法的小型數(shù)據(jù)庫，用查詢?nèi)〈鷱?fù)雜的判斷，那么也可以在很大程度上加快著法生成的速度。預(yù)置表看起來似乎很大，但是只需在程序開始運(yùn)行時初始化一次就可以了，這些耗費(fèi)對整個程序的影響不大，但是對著法生成的作用卻是非常明顯的。圖 即是以路向行向比特向量為索引的一個車的預(yù)置著法表的生成范例。圖中顯示，該車位于某行第 4 列，棋子分布的布爾向量形式為 [010100100]，可以看出，此時車可能的吃子著法落址為[010000100]，非吃子著法的落址為[f0010110001]。把車的列號和該行棋子的布爾分布作為輸入，把吃子落址和非吃子落址作為輸出，將輸入和輸出的關(guān)系寫入一個預(yù)置表中，在使用時通過查表，就可以快速構(gòu)成可行著法，而且可以區(qū)分開吃子著法和非吃子著法。如圖 所示：圖 車的著法預(yù)置表范例 局面評估局面估值就是通過既有的棋類知識來評估一個局面優(yōu)劣的過程。從象棋的棋力上考慮，在搜索之外，局面估值是最重要的部分，因?yàn)閷?shí)際局面的評價的好壞，影響著今后局勢發(fā)展的趨勢。這一過程對具體的棋類知識依賴程度很深，但是仍有一般性的規(guī)律可循。目前在計算機(jī)象棋博弈中常用的估值方法主要采用靜態(tài)估值方法。同時由于隨著搜索層數(shù)的加深，葉子節(jié)點(diǎn)的數(shù)目迅速上升，估值函數(shù)被數(shù)以百萬次的調(diào)用，花費(fèi)大量的運(yùn)算時間，如何提高估值函數(shù)的速度，也成了博弈性能改進(jìn)的重要話題。下面分別從這兩個方面及其關(guān)系介紹局面評估。 估值函數(shù)（Evaluation Function）本系統(tǒng)的估值函數(shù)包括：棋子固定價值，棋子位置附加值，棋子靈活性，棋子對棋盤的控制，棋子間的關(guān)系幾部分。棋子固定價值指的是對棋盤中的每一個棋子，根據(jù)它的重要性和走法的豐富程度賦予其一個特定的值。在棋盤上，棋子多者占優(yōu)，棋子少者為劣。根據(jù)經(jīng)驗(yàn)，可以讓一個車價值為 500，一個馬價值為 300，一個兵價值為 100 等等。在中國象棋的對弈中，由于一般以將死對方的將(帥)作為結(jié)束，因此，通常賦值的規(guī)則是為將(帥)賦予一個遠(yuǎn)大于其他棋子的子力之和的值?？梢杂孟旅娴谋磉_(dá)式求某一方的棋子固定值 SideValue=sum(PieceNum*PieceValue)；其中 PieceNum 是某種棋子的數(shù)量，PieceValue 是該種棋子的價值， sum 是對各種棋子的總價值求和。如果紅色的棋子價值總和大于黑色的棋子價值總和，通常這意味著紅方的局勢優(yōu)于黑方。而紅黑雙方的 SideValue 之差越大，紅方的優(yōu)勢也就越大。同樣的棋子在不同位置上起的作用是不同的，最明顯的是兵(卒)過河之前與之后它的作用和攻擊力以及對對方的威脅顯然是不一樣的，而當(dāng)兵卒一旦到了底線附近，它對將(帥 )的威脅度將大大下降。棋子靈活性描述的是棋子的活動范圍，即棋子向各處調(diào)動的可能性大小。棋子的威力能否充分發(fā)揮，與靈活性直接相關(guān)。本方棋子可以走的點(diǎn)越多，說明本方棋子的靈活性越大。例如車在縱橫線上遇到障礙物、馬被周圍棋子絆腳等，都降低了靈活性，也降低了威力的發(fā)揮，靈活性的計算是把棋子在棋盤上所能夠移動到達(dá)的位置數(shù)作為靈活性計算，給予評分。可以用下面的表達(dá)式求某一方棋子靈活性:Mobility=Sum(MoveNum*MoveValue)；其中，MoveNum 是某種棋子的合法走法數(shù)量，MoveValue 是該種棋子每一走法的價值，sum 是對所有棋子的靈活性價值求和。Mobility 就是所有棋子的靈活性分?jǐn)?shù)。一方對棋盤控制的棋盤區(qū)域越多，那么他就越具有主動性。在象棋中，如果一位置落在某方棋子的合法走步上，就可以認(rèn)為被該方控制。如果某一位置同時落在雙方的合法走步上，可以根據(jù)雙方控制該位置的棋子數(shù)量及棋子價值來決定孰優(yōu)孰劣。能控制更多位置的一方應(yīng)在這項評分上占優(yōu)。在中國象棋博弈中，每個棋子都不是孤立存在的，他們之間構(gòu)成了各種相互關(guān)系。如棋子 1 下一步將被吃掉，則應(yīng)該給一個負(fù)的附加值。而如果周圍有己方棋子對其進(jìn)行了保護(hù)，也就是說，對方在理智的情況下不會去吃棋子 1，那么棋子 l 沒有受到威脅，價值不變。棋子關(guān)系的評估應(yīng)考慮到該誰走棋的問題。如果某個紅馬落在黑炮的合法走步之內(nèi)，但此時輪到紅方走棋，應(yīng)認(rèn)為紅馬受到的威脅較輕。而如果此時輪到黑方走棋，就應(yīng)認(rèn)為紅馬受到的威脅很大，應(yīng)減去一個相對較大的值了。 估值的速度與博弈性能開發(fā)人員可以向估值函數(shù)加入大量的棋類知識，使之對于局面的評估更為精確。但是，博弈系統(tǒng)的性能，速度，棋類知識一般滿足下面的關(guān)系：Performance(性能)=Speed(速度)Kowledge(知識)且向估值函數(shù)加入越多的棋類知識，估值函數(shù)的速度也就越慢，因?yàn)樗M(jìn)行的計算也相應(yīng)增加。因此過于簡單的估值函數(shù)和過于復(fù)雜的估值函數(shù)同樣性能不佳。在同等的知識含量下，速度越快，性能越高。在同等速度之下，知識量越大性能越高。在速度和知識量二者的相互作用下，開發(fā)者要尋找的是一種平衡，是能夠使性能最大化的速度和知識量。使用終點(diǎn)估值(end—point envaluation)，意思是當(dāng)葉子節(jié)點(diǎn)到達(dá)時，使用估值函數(shù)對一個局面進(jìn)行評估。這樣的方法思路清晰，容易設(shè)計，而且模塊間獨(dú)立性高，同搜索算法的耦合度很低?？梢暂p易的更換估值函數(shù)，只改動極少的代碼；你也可以隨意使用任何估值方法來評估整個棋盤，最終給出估值，但這種方法的速度較慢。 估值函數(shù)的優(yōu)化目前最長使用的是優(yōu)化估值參數(shù)的方法是利用大量的測試局面進(jìn)行手工調(diào)整，也是本文在優(yōu)化評估函數(shù)時主要使用的手段。這種方法是利用人類的象棋經(jīng)驗(yàn)知識來調(diào)整參數(shù)值，比如，從經(jīng)驗(yàn)上可以知道，一個車的價值要比一個兵大，給車賦予比兵大的數(shù)值，馬炮則賦予位于其間的值。馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值，以避免盲目換子；如果對弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎勵，等等。將這些經(jīng)驗(yàn)放進(jìn)評估函數(shù)中反復(fù)對弈，然后不斷修正參數(shù)，找出一組性能較高的參數(shù)。(1)規(guī)格化(Normalize)如果只是關(guān)心評價的順序，而不怎么關(guān)心評價值，那么可以把每一項都乘以同樣的常數(shù)。這就意味著，對某個特定的模塊，例如兵的價值，可以硬性設(shè)一個值，其他值就可以表示成它們相當(dāng)于多少個兵。這個做法可以減少一個需要設(shè)定的參數(shù)。(2)約束法 (Deduce Constraints)通過考慮希望電腦作出怎樣的判斷，就可以確定一些參數(shù)。例如在對弈中即使賺到一個兵，用車換象或馬還是壞的，但如果能賺到兩個兵那還是好的，因?yàn)樵诳紤]子力價值是要防止換單兵，鼓勵換雙兵。這樣的條件越多，合適的權(quán)重組合就越少。在開始設(shè)定權(quán)重值的時候，這個方法通?？梢缘玫胶线m的值，但是在后面仍然需要做一些調(diào)整。(3)交手法 (Hand Tweaking)這是調(diào)整評估函數(shù)時非常常用的方法，通過讓程序?qū)?，來找到它的?yōu)勢和弱點(diǎn)，猜測哪些參數(shù)會讓程序更好，然后挑選新的參數(shù)。這個方法可以很快得到合理的結(jié)果，但是需要對棋類知識有足夠的了解，便于根據(jù)程序的對局來做分析，從而知道程序的問題在哪里。手工調(diào)整是象棋引擎調(diào)整估值參數(shù)的主要手段之一，把人類的知識和經(jīng)驗(yàn)盡量準(zhǔn)確客觀地“教授”給計算機(jī)，是提高棋力的普遍做法，雖然比較費(fèi)時，但是很有效。通過不斷的試驗(yàn)、修改參數(shù)值，可以得到不錯的結(jié)果。但是人類的知識畢竟具有一定的局限性，評估函數(shù)也不能包含所有情況，參數(shù)之間往往又互相聯(lián)系，調(diào)整某個參數(shù)可能解決了某類問題，但又可能給其它問題的解決帶來麻煩，在這種情況下很難實(shí)現(xiàn)全局下的最優(yōu)組合。還有一種主要的優(yōu)化方法是機(jī)器自學(xué)習(xí)：(1)爬山法(HillClimbing)爬山法通過對參數(shù)進(jìn)行小范圍的試探來尋找最優(yōu)解，一次只能對參數(shù)作一點(diǎn)小改變，然后測試博弈程序的性能是否提高了，僅當(dāng)性能提高時才采納這個改變，需要重復(fù)很多次。這種方法很慢，并且受初始采樣值的限制，很容易陷入局部最優(yōu)，即評價可能很差，但是任何很小的改變都會使評價更差。(2)模擬退火 (Simulated Annealing)模擬退火是一種基于蒙特卡羅 (Monte Carlo)算法的啟發(fā)式隨機(jī)搜索算法，它沒有蒙特卡羅算法多次尋優(yōu)的過程，也不像爬山法那樣依賴初值。在優(yōu)化參數(shù)時，類似于爬山法，模擬退火法也是對權(quán)重做改變來提高成績，如果所做的改變沒有提高成績，也會根據(jù)一個隨機(jī)的幾率采納這個改變，試圖跳出局部最優(yōu)。這個方法需要給定一些幾率，從幾率高、梯度大的條件開始，然后逐漸減小。模擬退火法比爬山法更慢，是最終可能得到比較好的值。(3)遺傳算法 (Geic Algorithm，GA)遺傳算法是建立在自然選擇和自然遺傳學(xué)機(jī)理基礎(chǔ)上的迭代自適應(yīng)概率性全局優(yōu)化算法，因其模仿生物的遺傳機(jī)制而得名，最早由美國密執(zhí)安大學(xué) 于 1975年提出，它通過染色體的復(fù)制，交叉，變異等操作，實(shí)現(xiàn)個體適應(yīng)性的提高。遺傳算法可以同時維護(hù)多組較好的參數(shù)，通過向其中添加一組新參數(shù)，通常是將從幾組老參數(shù)中選出的值組合在一起作微小的變化，然后同幾組老的參數(shù)比較孰優(yōu)孰劣，將最壞的一組去除。遺傳算法是從幾組參數(shù)開始，而不是一組參數(shù)，具有很好的全局搜索能力，搜索速度也很快，而且此算法能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳參數(shù)，魯棒性也明顯優(yōu)于前兩種算法，所以在計算機(jī)博弈中最有可能取得成功。 博弈樹搜索技術(shù)中國象棋博弈樹非常龐大，完全建立博弈樹是不可能的，唯一的解決方法就是讓博弈樹擴(kuò)展到計算機(jī)運(yùn)算可以接受的深度，然后對沒有分出勝負(fù)的葉子節(jié)點(diǎn)給出一個盡量準(zhǔn)確的打分，表示此局面下取得勝利的可能性，這個打分是由評估函數(shù)計算給出的，將搜索樹展開是著法生成的功能，而搜索引擎則是盡可能縮小樹的規(guī)模，避免一切冗余的計算，這也是計算機(jī)博弈中搜索引擎研究的重點(diǎn)。根據(jù)搜索策略，目前應(yīng)用于計算機(jī)博弈的搜索算法一般可分為三類：(l)窮盡搜索 (Exhaustive Search)，這種搜索是沒有拋棄任何可能成為最佳路徑的搜索，不存在風(fēng)險，得到的最佳走法肯定是在現(xiàn)有評估函數(shù)下應(yīng)該得到的，例如極大極小值搜索、α β 剪枝搜索及其變種等。(2)選擇性搜索 (Selective Search)，即裁剪搜索，這種搜索略去對一些著法的搜索，冒著有可能漏掉最佳走法的風(fēng)險，而換來局部更深的搜索深度。中國象棋中最常用裁剪算法是空著裁剪(Null Move)等。(3)啟發(fā)式搜索 (Heuristic search)利用象棋領(lǐng)域的知識(啟發(fā)信息)設(shè)計搜索算法，著重對走法排序，以簡化和加快搜索過程。中國象棋中的啟發(fā)算法有歷史啟發(fā)、殺手啟發(fā)、置換表等。 基本搜索算法極大極小值方法(Minimax Algorithm)是解決博弈樹問題的基本方法。香農(nóng)教授早在 1950 年首先提出了“極大極小算法” ，奠定了計算機(jī)博弈理論的基礎(chǔ)。極大極小值算法的原則是:博弈雙方所要達(dá)到的目的相反，一方要尋找的利益是另一方失去的利益，博弈的一方總是希望下一步是子節(jié)點(diǎn)中取值最大者，而另一方希望下一步是子節(jié)點(diǎn)中取值最小者。在象棋博弈中，極大極小值算法體現(xiàn)在始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分?jǐn)?shù)，不利于這一方(有利于另一方)的給予一個較低的價值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面給予一個中間值分?jǐn)?shù)。在這一方走棋的時候，選擇價值最大的子節(jié)點(diǎn)走法，即實(shí)行“Max 搜索” ，另一方走棋則選擇價值最小的子節(jié)點(diǎn)走法，即實(shí)行“Min 搜索” ，這就是象棋博弈中的一個極大極小過程。例如，如果紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點(diǎn)中找到評估值最大的一個，實(shí)行“Max 搜索” ，稱為 MAX 方，而其敵對方即黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點(diǎn)中要找到評估值最小的一個，實(shí)行“Min搜索” ，稱為 MIN 方。圖 表示了一個極大極小搜索過程，粗箭頭為最佳路徑片段。圖 極大極小值算法示意圖由于完整的博弈樹過于龐大，程序不能也沒有必要搜索整棵博弈樹的所有節(jié)點(diǎn)，而需要像人類棋手一樣有選擇性地進(jìn)行搜索，對于一些已經(jīng)確定不佳的走步可以將以它根節(jié)點(diǎn)的子樹剪掉(cutoff/pruning)，以提高單位時間內(nèi)搜索的節(jié)點(diǎn)數(shù)。上述極大極小值搜索過程中，遍歷了整個的博弈樹，這樣的搜索算法效率低，搜索量非常大，如果要減少搜索量，又可能影響搜索效果。但假如將葉節(jié)點(diǎn)的評估計算與樹的展開同時進(jìn)行，然后對博弈樹進(jìn)行必要的裁剪，就可能大量減少所需搜索的節(jié)點(diǎn)數(shù)目，并且保 持搜索效果不變。這個技術(shù)叫 αβ 剪枝搜索。它是一種基于 αβ 搜索的深度優(yōu)先搜索，是所有剪枝算法的基礎(chǔ)，它是根據(jù)極大極小搜索規(guī)則進(jìn)行的。圖 和圖 給出兩個剪枝示意圖：MAXMINMAX圖 α 剪枝示意圖 MIN MAXMIN圖 β 剪枝示意圖在圖 所示的極大極小樹片段中，按照極大極小值搜索規(guī)則，從左路分枝的葉節(jié)點(diǎn)倒推得到第一層 MAX 節(jié)點(diǎn)的值為 5，可表示此時的著法最佳值，記為 α，顯然此 α值可作為 MAX 方著法指標(biāo)的下界。在搜索中路分枝時，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最小值，即取 M 州(8，3， “□”)，而無論“□”中為何值，都不會比 5大(最大為 3)，故可以將“□”表示的節(jié)點(diǎn)及其后繼節(jié)點(diǎn)剪掉，不再考慮此節(jié)點(diǎn)的延伸。同理搜索右路分枝，也可以進(jìn)行剪枝操作。此類剪枝稱為 α剪枝。圖 中通過剪枝，最后得到如粗箭頭所示的最佳路徑片斷。圖 所示的極大極小樹片段中，由左路分枝的葉節(jié)點(diǎn)倒推得到第一層 MIN 節(jié)點(diǎn)的值為 n，可表示此時對方著法的鉗制值，記為 β。顯然此 β 值可作為 MIN 方可能實(shí)現(xiàn)著法指標(biāo)的上界。在搜索中路分枝時，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最大值，即取 MAX(5，12， “○”