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