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