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