【正文】 類智能行為的核心；那些能夠存在于下棋活 動(dòng)中的重大原則，或許就存在于其它任何需要人類智能的活動(dòng)中。 而當(dāng)今對(duì)中國(guó)象棋的研究也 正如專家們所期望的那樣 在蓬勃地發(fā)展著。通過(guò)本課題的研究 ,掌握智能知識(shí)的表示與計(jì)算、搜索，不僅是對(duì)所學(xué)知識(shí)的鍛煉，更是在人工智能領(lǐng)域的有意義的探索 發(fā)展動(dòng)態(tài)及研究現(xiàn)狀 和國(guó)際象棋博弈系統(tǒng)相比，中國(guó)象棋博弈系統(tǒng)的研究起步比較晚，是八十年代開(kāi)始的。于是有專家學(xué)者想如何將國(guó)際象棋電腦技術(shù)移植到中國(guó)象棋上來(lái)，以帶動(dòng)中國(guó)象棋電腦較快的發(fā)展；同時(shí)中國(guó)象棋從技術(shù)研究進(jìn)入理論研究，有關(guān)開(kāi)局、中局、殘局理論以及象棋對(duì)策相繼建立起來(lái)，為中國(guó)象棋計(jì)算機(jī)博弈提供了理論基礎(chǔ)。但該文主要 以殘局 做實(shí)驗(yàn)，缺乏完整對(duì)局的考慮。 1983 年黃少龍、周玉龍合作制成《象棋排局系列軟盤》專家系統(tǒng)與人對(duì)弈。 比較著名的軟件有臺(tái)灣的吳身潤(rùn)的《中國(guó)象棋》、光譜公司出品的《將族Ⅲ》、 晟 業(yè)編制的《象棋水滸戰(zhàn)》、《象棋武林帖》。近幾年，在內(nèi)地也涌現(xiàn)出一批對(duì)中國(guó)象棋人機(jī)博弈問(wèn)題感興趣的高校、單位及個(gè)人，而且進(jìn)入 21 世紀(jì)以后，中國(guó)象棋計(jì)算機(jī)博弈的研究受到越來(lái)越多的學(xué) 者的關(guān)注，比較著名的博弈軟件如表 1 所示。 這些都體現(xiàn)了中國(guó)象棋的人機(jī)博弈的研究的受關(guān)注程度 。 系統(tǒng)概述 棋盤 表示 (Board Representations) 棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋盤及棋盤上的棋子，以方便計(jì)算機(jī)處理。 最直觀也是最典型的方式是使用 10x9 的二維棋盤數(shù)組表示，也有使用棋子數(shù)組，擴(kuò)展棋盤 — 棋子數(shù)組等，棋盤的數(shù)據(jù)表示直接影響到程序的時(shí)間及空間復(fù)雜度。它與棋盤表示的數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，一般需要大量繁瑣的判斷，伴隨著搜索進(jìn)行，并 且調(diào)用頻繁，是相當(dāng)復(fù)雜而且耗費(fèi)運(yùn)算時(shí)間。當(dāng)前為了提高著法生 成的效率 通常采用以空間換時(shí)間的方法 :與先求出棋子的在某位置的所有走法。目前象棋程序的靜態(tài)評(píng)價(jià)函數(shù)主要有子力價(jià)值，子力靈活性，子力對(duì)棋盤的控制，和一些對(duì)棋局影響比較大的重要特征計(jì)算幾部分組成。 搜索技術(shù) (Search Techniques) 搜索技術(shù)與算法是象棋博弈系統(tǒng)程序的核心，是決定搜索效率的關(guān)鍵所在。如何在成指數(shù)遞增的狀態(tài)空間中尋求最優(yōu)解，是象棋博弈系統(tǒng)的一個(gè)重要的方向。如何有選擇地搜索，既瞄準(zhǔn)最有希望的方向局部加深，又不遺漏其它存在最優(yōu)解的可 能。 開(kāi)局庫(kù) (Opening Book) 把開(kāi)局幾步的走法建成數(shù)據(jù)庫(kù)供程序直接取用。直接從開(kāi)局庫(kù)中取就可以大大加快開(kāi)局時(shí)的運(yùn)行速度和提高開(kāi)局的質(zhì)量。 機(jī)器自學(xué)習(xí) (Machine Learning) 機(jī)器自學(xué)習(xí)之一是針對(duì)評(píng)估函數(shù)。 本文的主要工作 本 文 的主要工作是將博弈策略應(yīng)用到中國(guó)象棋程序的設(shè)計(jì)與實(shí)現(xiàn)上，建 立一個(gè)完整的中國(guó)象棋計(jì)算機(jī)博弈系統(tǒng)，研究工作主要集中在以下幾個(gè)方面 ： 棋盤表示與走法生成 從操作速度 (性能 )以及使用方便與否考慮，本象棋博弈系統(tǒng)從帶位行位列信息的擴(kuò)展棋盤 —— 棋子聯(lián)系數(shù)組著手進(jìn)行研究。在產(chǎn)生走法時(shí)直接從中取出數(shù)據(jù)，進(jìn)行少量判斷以得到該棋子的合法走步。本系統(tǒng)采用通用的靜態(tài)估值方式，同時(shí)在估值時(shí)結(jié)合走法預(yù)生成數(shù)組，使估值的速 度有很大提升。本文討論了 αβ 剪枝搜索算法及其各種增強(qiáng)手段：包括窗口原則、置換表 (內(nèi)存增強(qiáng) )；歷史啟發(fā)表 (節(jié)點(diǎn)順序調(diào)整 )；迭代深化 (時(shí)間控制 )等。 論文結(jié)構(gòu) 第一章闡述了選題背景，課題的國(guó)內(nèi)外研究現(xiàn)狀及課題的主要工作和文章的章節(jié)安排。 第二部分研究本系統(tǒng)的著法生成，包括預(yù)置表法和模板匹配法，進(jìn)一步提高了搜索效率。 包括子力分?jǐn)?shù)、子力靈活度評(píng)價(jià)、棋盤 控制等并與走法預(yù)生成數(shù)組結(jié)合以提高估值速度。第五部分闡述了開(kāi)局庫(kù)的設(shè)計(jì)原理。 第 四章 是全文的總結(jié)及展望 。 棋盤的基本表示法 （ Board Representions） 棋盤表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋盤上的信息，以便程序知道博弈的狀態(tài)。為了追求更高效率，研究人員針對(duì)中國(guó)象棋提出了多種不同的表示方法。又在棋盤上最多 32 個(gè)棋子，故可以用一個(gè)32 個(gè)字節(jié)的一維數(shù)組表示所有 32 個(gè)棋子的位置，其中每個(gè)字節(jié)的高 4 位表示該棋子的橫坐標(biāo)，低 4 位表示棋子的縱坐標(biāo)。這樣棋盤信息就被裝入這 32 個(gè)字節(jié)中。 兩種棋盤表示方法：一是做一個(gè)棋盤數(shù)組；二是做一個(gè)棋子數(shù)組。如果一個(gè)程序同時(shí)使用這兩個(gè)數(shù)組，那么獲得棋子的類型和棋子的位置都可以在常數(shù)時(shí)間內(nèi)完成。棋子聯(lián)系數(shù)組”，它的技術(shù)要點(diǎn)是 : (l) 同時(shí)用棋盤數(shù)組和棋子數(shù)組表示一個(gè)局面，棋盤數(shù)組和棋子數(shù)組之間可以互相轉(zhuǎn)換。在棋盤上刪除一個(gè)棋子，需要做兩個(gè)操作 (分別修改棋盤數(shù)組和棋 子數(shù)組 )。 “棋盤同時(shí)“棋盤 —— 棋子聯(lián)系數(shù)組”是很多改進(jìn)的棋盤的基礎(chǔ)。 改進(jìn)型棋盤結(jié)構(gòu) 在計(jì)算機(jī)上面，位運(yùn)算比一般的加減乘除及取余運(yùn)算快得多。所以，人們把“棋盤 —— 棋子聯(lián)系數(shù)組“進(jìn)行擴(kuò)展：把棋盤做成 16 16 的大小，這樣得到行號(hào)可以用 16 除，得到列號(hào)可以對(duì) 16 取余（和 15 進(jìn)行運(yùn)算），這比除以 10 和對(duì) 9 取余操作要快得多。由 bool 型棋盤數(shù)組（屬于棋盤的位置為 true，否則為 false），判斷棋子是否走出棋盤邊界只要返回該數(shù)組對(duì)應(yīng)的值即可，速度快。 (3) 判斷是否過(guò)河的方法非常簡(jiǎn)單：只要設(shè)定特定的表達(dá)式，當(dāng)表達(dá)式為假表示已過(guò)河，否則沒(méi)過(guò)河。 著法生成 （ Move Generation） 著法生成就是要產(chǎn)生所有有效的著法，讓電腦棋手在這些著法中選擇最好的著法，并判斷人類棋手是否符合走棋規(guī)則。 中國(guó)象棋大約每一步可以有 45 個(gè)著法。 模板匹配法 當(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)容的確定。顯然，這比掃描整個(gè)棋盤，通過(guò)計(jì)算得到合法落址要快速的多。 預(yù)置表法 它是把所有可能的著法預(yù)先存儲(chǔ)起來(lái)，在生成著法時(shí)，用查表取代計(jì)算。預(yù)置表看起來(lái)似乎很大，但是只需在程 序開(kāi)始運(yùn)行時(shí)初始化一次就可以了，這些耗費(fèi)對(duì)整個(gè)程序的影響不大，但是對(duì)著法生成的作用卻是非常明顯的。圖中顯示，該車位于某行第 4 列，棋子分布的布爾向量形式為 [010100100]，可以看出，此時(shí)車可能的吃子著法落址為 [010000100]，非吃子著法的落址為 [f0010110001]。 如圖 所示： 圖 車的著法預(yù)置表范例 局面評(píng)估 局面估值就是通過(guò)既有的棋類知識(shí)來(lái)評(píng)估一個(gè)局面優(yōu)劣的過(guò)程。這一過(guò)程對(duì)具體的棋類知識(shí)依賴程度很深，但是仍有一般性的規(guī)律可循。同時(shí)由于隨著搜索層數(shù)的加深，葉子節(jié)點(diǎn)的數(shù)目迅速上升，估值函數(shù)被數(shù)以百萬(wàn)次的調(diào)用，花費(fèi)大量的運(yùn)算時(shí)間，如何提高估值函數(shù)的速度 ，也成了博弈性能改進(jìn)的重要話題。 估值函數(shù) （ Evaluation Function） 本系統(tǒng)的估值函數(shù)包括：棋子固定價(jià)值，棋子位置附加值，棋子靈活性，棋子對(duì)棋盤的控制，棋子間的關(guān)系幾部分。在棋盤上，棋子多者占優(yōu)，棋子少者為劣。在中國(guó)象棋的對(duì)弈中，由于一般以將死對(duì)方的將 (帥 )作為結(jié)束，因 此，通常賦值的規(guī)則是為將 (帥 )賦予一個(gè)遠(yuǎn)大于其他棋子的子力之和的值。如果紅色的棋子價(jià)值總和大于黑色的棋子價(jià)值總和，通常這意味著紅方的局勢(shì)優(yōu)于黑方。 同樣的棋子在不同位置上起的作用是不同的，最明顯的是兵 (卒 )過(guò)河之前與之后它的作用和攻 擊力以及對(duì)對(duì)方的威脅顯然是不一樣的，而當(dāng)兵卒一旦到了底線附近，它對(duì)將 (帥 )的威脅度將大大下降。棋子的威力能否充分發(fā)揮，與靈活性直接相關(guān)。例如車在縱橫線上遇到障礙物、馬被周圍棋子絆腳等，都降低了靈活性，也降低了威力的發(fā)揮，靈活性的計(jì)算是把棋子在棋盤上所能夠移動(dòng)到達(dá)的位置數(shù)作為靈活性計(jì)算，給予評(píng)分。 Mobility 就是所有棋子的靈活性分?jǐn)?shù)。在象棋中，如果一位置落在某方棋子的合法走步上，就可以認(rèn)為被該方控制。能控制更多位置的一方應(yīng)在這項(xiàng)評(píng)分上占優(yōu)。如棋 子 1 下一步將被吃掉，則應(yīng)該給一個(gè)負(fù)的附加值。棋子關(guān)系的評(píng)估應(yīng)考慮到該誰(shuí)走棋的問(wèn)題。而如果此時(shí)輪到黑方走棋，就應(yīng)認(rèn)為紅馬受到的威脅很大，應(yīng)減去一個(gè)相對(duì)較大的值了。但是，博弈系統(tǒng)的性能，速度，棋類知識(shí)一般滿足下面的 關(guān)系 ： Performance(性能 )=Speed(速度 ) Kowledge(知識(shí) ) 且向估值函數(shù)加入越多的棋類知識(shí)，估值函數(shù)的速度也就越慢，因?yàn)樗M(jìn)行的計(jì)算也相應(yīng)增加。在同等的知識(shí)含量下，速度越快，性能越高。在速度和知識(shí)量二者的相互作用下，開(kāi)發(fā)者要尋找的是一種平衡，是能夠使性能最大化的速度和知識(shí)量。 這樣的方法思路清晰，容易設(shè)計(jì)，而且模塊間獨(dú)立性高，同搜索算法的 耦合 度很低。 估值函數(shù)的優(yōu)化 目前最長(zhǎng)使用的是優(yōu)化估值參數(shù)的方法是利用大量的測(cè)試局面進(jìn)行手工調(diào)整， 也是本文在優(yōu)化評(píng)估函數(shù)時(shí)主要使用的手段。馬和炮的地位相當(dāng)，給予它們相當(dāng)?shù)臄?shù)值 ，以避免盲目換子 ；如果對(duì)弈中使用了一些優(yōu)秀的戰(zhàn)術(shù)配合，那么就給予一定數(shù)值的獎(jiǎng)勵(lì)，等等。 (1)規(guī)格化 (Normalize) 如果只 是關(guān)心評(píng)價(jià)的順序，而不怎么關(guān)心評(píng)價(jià)值，那么可以把每一項(xiàng)都乘以同樣 的常數(shù)。這個(gè)做法可以減少一個(gè)需要設(shè)定的參數(shù)。例如在對(duì)弈中即使賺到一個(gè)兵，用車換象或馬還是壞的，但如果能賺到兩個(gè)兵那還是好的，因?yàn)樵诳紤]子力價(jià)值是要防止換單兵，鼓勵(lì)換雙兵。在開(kāi)始設(shè)定權(quán)重值的時(shí)候，這個(gè)方法通?？梢缘玫胶线m的值，但是在后面仍然需要做一些調(diào)整。這個(gè)方法可以很快得到合理的結(jié)果，但是需要對(duì)棋類知識(shí)有足夠的了解，便于根據(jù)程序的對(duì)局來(lái)做分 析，從而知道程序的問(wèn)題在哪里。通過(guò)不斷的試驗(yàn)、修改參數(shù)值，可以得到不錯(cuò)的結(jié)果。 還有一種主要的優(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ù)很多次。 (2)模擬退火 (Simulated Annealing) 模擬退火是一種基于蒙特卡羅 (Monte Carlo)算法的啟發(fā)式隨機(jī)搜索算法，它沒(méi)有蒙特卡羅算法多次尋優(yōu)的過(guò)程，也不像爬山法那樣依賴初值。這個(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ù)開(kāi)始，而不是一組參數(shù)，具有很好的全局搜索能力，搜索速度也很快，而且此算法能將搜索重點(diǎn)集中于性能高的部分，能較快地求出最佳參數(shù)，魯棒性也明顯優(yōu)于前兩種算法，所以在計(jì)算機(jī)博弈中最有可能取得成功。 根據(jù)搜索策略，目前應(yīng)用于計(jì)算機(jī)博弈的搜索算法一般可分為三類 ： (l)窮盡搜索 (Exhaustive Search)，這種搜索是沒(méi)有拋棄任何可能成為最佳路徑的搜索，不存在 風(fēng)險(xiǎn)，得到的最佳走法肯定是在現(xiàn)有評(píng)估函數(shù)下應(yīng)該得到的，例如極大極 小值 搜索、α β 剪枝搜索及其變種等。中國(guó)象棋中最常用 裁剪算法是空著裁剪 (Null Move)等。中國(guó)象棋中的啟發(fā)算法有歷史啟發(fā)、殺手啟發(fā)、置換表等。香農(nóng)教授早在1950 年首先提出了“極 大極小算法” ，奠定了計(jì)算機(jī)博弈理論的基礎(chǔ) 。在象棋博弈中，極大極小值算法體現(xiàn)在始終站在博弈一方的立場(chǎng)上給棋局估值，有利于這一方的棋局給予一個(gè)較高的價(jià)值分?jǐn)?shù)，不利于這一方(有利于另一方 )的給予一個(gè)較低的價(jià)值分?jǐn)?shù)，雙方優(yōu)劣不明顯的局面給予一個(gè)中間值分 數(shù)。例如，如果紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點(diǎn)中找到評(píng)估值最大的一個(gè)，實(shí)行“ Max 搜索”，稱為 MAX 方，而其敵對(duì)方即黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點(diǎn)中要找到評(píng)估值最小的一個(gè)，實(shí)行“ Min 搜索”，稱為 MIN 方。 圖 極大極小值算法示意圖 由于完整的博弈樹(shù)過(guò)于龐大，程序不能也沒(méi)有必要搜索整棵博弈樹(shù)的所有節(jié)點(diǎn)，而需要像人類 棋 手一樣有選擇性地進(jìn)行搜索，對(duì)于一些已經(jīng)確定不佳的走步可以將以它 根節(jié)點(diǎn)的子樹(shù)剪掉 (cutoff/pruning)，以提高單位時(shí)間內(nèi)搜索的節(jié)點(diǎn)數(shù)。但假如將葉節(jié)點(diǎn)的評(píng)估計(jì)算與樹(shù)的 展 開(kāi) 同 時(shí) 進(jìn) 行，然后對(duì)博弈樹(shù)進(jìn)行必要的裁 剪，就可能大量減少所需搜索的 節(jié)點(diǎn)數(shù)目，并且保持搜索效果不 變。 它 是一種基于 αβ搜索的深度優(yōu)先 搜索，是所有剪枝算法的基礎(chǔ)， 它是根據(jù)極大極小搜索規(guī)則進(jìn)行的 。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最小值，即取 M 州 (8， 3，“ □ ” )，而無(wú)論“ □ ”中為何值，都不會(huì)比 5 大 (最大為 3)，故可以將“ □ ”表示的節(jié)點(diǎn)及其后繼節(jié)點(diǎn)剪掉，不再考慮此節(jié)點(diǎn)的延伸。此類剪枝稱為 α剪枝。 圖 所示的極大極小樹(shù)片段中，由左路分枝的葉節(jié)點(diǎn)倒推得到第一層 MIN 節(jié)點(diǎn)的值為 n，可表示此時(shí)對(duì)方著法的鉗制值，記為 β。在搜索中路分枝時(shí)，因?yàn)榈诙又ǖ倪x擇是取第三層節(jié)點(diǎn)的最大值，即取 MAX(5， 12，“○” )，