【正文】 ...............................39 附錄 A： A INTRODUCTION ABOUT CHINESE CHESSA ..................................39 附錄 B：關(guān)于中國(guó)象棋的一些簡(jiǎn)要介紹 .................................................................42 1 緒論 選題的背景和意義 在人類(lèi)文明發(fā)展的初期，人們便開(kāi)始進(jìn)行棋類(lèi)博弈的游戲了。近幾十年來(lái)，隨著計(jì)算機(jī)硬件和軟件技術(shù)的不斷發(fā)展，人們開(kāi)始對(duì)計(jì)算機(jī)能否戰(zhàn)勝人腦這個(gè)話題 產(chǎn)生了濃厚的興趣。從 1980 開(kāi)始，電腦博弈便開(kāi)始逐漸大規(guī)模地向人類(lèi)智能發(fā)起了挑戰(zhàn)，到了 1997年， IBM 超級(jí)電腦 Deeper Blue 擊敗了當(dāng)時(shí)的國(guó)際象棋冠軍卡斯帕羅夫，成為了人工智能挑戰(zhàn)人類(lèi)智能發(fā)展的一個(gè)重要里程碑。 許多學(xué)者認(rèn)為，對(duì)于人工智能研究而言，象棋的重要作用不亞于遺傳學(xué)研究中的果蠅。人類(lèi)對(duì)機(jī)器博弈的研究衍生了大量的研究成果，這些成果對(duì)更廣泛的領(lǐng)域產(chǎn)生了重要影響。人工智能的先驅(qū)們?cè)J(rèn)真的表明：如果能掌握下棋的本質(zhì)，也許就掌握了人類(lèi)智能行為的核心；那些能夠存在于下棋活動(dòng)中的重大原則，或許就存在于其 它任何需要人類(lèi)智能的活動(dòng)中。因此對(duì)于中國(guó)象棋人機(jī)博弈問(wèn)題的研究意義重大。 而當(dāng)今對(duì)中國(guó)象棋的研究也 正如專家們所期望的那樣 在蓬勃地發(fā)展著。中國(guó)象棋不僅是中國(guó)傳統(tǒng)智慧的體現(xiàn)，同時(shí)也具有著比國(guó)際象棋更高的復(fù)雜度，如何讓機(jī)器具有智能 ,與人進(jìn)行對(duì)弈成了本課題研究的一個(gè)重要問(wèn)題。通過(guò)本課題的研究 ,掌握智能知識(shí)的表示與計(jì)算、搜索，不僅是對(duì)所學(xué)知識(shí)的鍛煉，更是在人工智能領(lǐng)域的有意義的探索 發(fā)展動(dòng)態(tài)及研究現(xiàn)狀 和國(guó)際象棋博弈系統(tǒng)相比，中國(guó)象棋博弈系統(tǒng)的研究起步比較晚，是八十年代開(kāi)始的。在這個(gè)時(shí)候計(jì)算機(jī)國(guó)際象棋取得重大突 破， 1983 年美國(guó)貝爾公司的電腦參加美國(guó)人類(lèi)比賽，取得了不錯(cuò)的成績(jī)，被授予大師稱號(hào)。于是有專家學(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ǔ)。 1981 年張耀騰發(fā)表的《人造智慧在電腦象棋上的應(yīng)用》，他提出審局函數(shù)為 靜態(tài)子力值，棋子位置值，棋子靈活度值，威脅與保護(hù)等四項(xiàng)之和。但該文主要 以殘局 做實(shí)驗(yàn)，缺乏完整對(duì)局的考慮。 1982 年廖嘉成發(fā)表的《利用計(jì)算機(jī)象棋的 實(shí) 驗(yàn)》 就進(jìn)了一步，包括開(kāi)局、中局、殘局。 1983 年黃少龍、周玉龍合作制成《象棋排局系列軟盤(pán)》專家系統(tǒng)與人對(duì)弈。 到了 90 年代，中國(guó)象棋計(jì)算機(jī)博弈的應(yīng)用開(kāi)始發(fā)展起來(lái)，人們研究出了各種博弈軟件。 比較著名的軟件有臺(tái)灣的吳身潤(rùn)的《中國(guó)象棋》、光譜公司出品的《將族Ⅲ》、 晟 業(yè)編制的《象棋水滸戰(zhàn)》、《象棋武林帖》。而且涉足這個(gè)領(lǐng)域比較早的是臺(tái)灣的一些專家學(xué)者。近幾年，在內(nèi)地也涌現(xiàn)出一批對(duì)中國(guó)象棋人機(jī)博弈問(wèn)題感興趣的高校、單位及個(gè)人，而且進(jìn)入 21 世紀(jì)以后，中國(guó)象棋計(jì)算機(jī)博弈的研究受到越來(lái)越多的學(xué)者的關(guān)注，比較著名的博弈軟件如 表 1 所示。 表 11 著名中國(guó)象棋計(jì)算機(jī)博弈程序 程序 作者 地區(qū) 縱馬奔流 涂志堅(jiān) 廣州中山大學(xué) 謝謝象棋大師 法國(guó)電腦公司 法國(guó) ELP 鄭武堯、陳志呂 臺(tái)灣 SHIGA（象棋世家） 鄭明政、顏士?jī)? 臺(tái)灣 SHCC（神乎棋技） SAI team 美國(guó) Cyclone（象棋旋風(fēng)） 陳朝陽(yáng) 北京 CONTEMPLATION 千慮 陳志昌、許舜欽 臺(tái)灣 棋天大圣 王驕 東北大學(xué) 象棋奇兵 趙明陽(yáng) 中國(guó) 每年也會(huì)有中國(guó)象棋計(jì)算機(jī)博弈的國(guó)際奧林匹克大賽，這其中有 2020 年的世界冠軍“縱馬奔流”， 2020 年的世界冠軍“謝謝象棋大師”， 2020 年的世界冠軍“象棋奇兵”，20 2020 年的世界冠軍“棋天大圣” ， 2020 年的世界冠軍“倚天”。 這些都體現(xiàn)了中國(guó)象棋的人機(jī)博弈的研究的受關(guān)注程度 。雖然如此，但中國(guó)象棋的人機(jī)博弈的研究比國(guó)際象棋還是晚了幾十年，并且在搜索算法等方面的研究還與國(guó)際象棋相距甚遠(yuǎn)。 系統(tǒng)概述 棋盤(pán)表示 (Board Representations) 棋盤(pán)表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋盤(pán)及棋盤(pán)上的棋子，以方便計(jì)算機(jī)處理。中國(guó)象棋的棋盤(pán)表示還沒(méi)有形成統(tǒng)一的或者公認(rèn)的哪種為最佳的數(shù)據(jù)格式。 最直觀也是最典型的方式是使用 10x9 的二維棋盤(pán)數(shù)組表示，也有使用棋子數(shù)組，擴(kuò)展棋盤(pán) — 棋子數(shù)組等，棋盤(pán)的數(shù)據(jù)表示直接影響到程序的時(shí)間及空間復(fù)雜度。 著法生成 (Move Generation) 著法生成就是找到某個(gè)局面所有合法的走法。它與棋盤(pán)表示的數(shù)據(jù)結(jié)構(gòu)密切相關(guān)，一般需要大量繁瑣的判斷，伴隨著搜索進(jìn)行，并且調(diào)用頻繁，是相當(dāng)復(fù)雜而且耗費(fèi) 運(yùn)算時(shí)間。在一定程度上形成了程序的性能瓶頸。當(dāng)前為了提高著法生 成的效率 通常采用以空間換時(shí)間的方法 :與先求出棋子的在某位置的所有走法。 評(píng)估函數(shù) (Evaluation Function) 評(píng)估函數(shù)就是對(duì)博弈過(guò)程中實(shí)際局面的好壞做出判斷或打分，它影響著博弈 局 發(fā)展的趨勢(shì)。目前象棋程序的靜態(tài)評(píng)價(jià)函數(shù)主要有子力價(jià)值，子力靈活性，子力對(duì)棋盤(pán)的控制，和一些對(duì)棋局影響比較大的重要特征計(jì)算幾部分組成。它與著法生成一樣十分耗費(fèi)運(yùn)算時(shí)間，如何加速評(píng)估函數(shù)的速度十分關(guān)鍵。 搜索技術(shù) (Search Techniques) 搜索技術(shù)與算法是象棋博弈系統(tǒng)程序的核心，是決定搜索效率的關(guān)鍵所在。再好的硬件也無(wú)法實(shí)現(xiàn)“象棋不敗算法”。如何在成指數(shù)遞增的狀態(tài)空間中尋求最優(yōu)解，是象棋博弈系統(tǒng)的一個(gè)重要的方向。“蠻力搜索”肯定是不可取的。如何有選擇地搜索，既瞄準(zhǔn)最有希望的方向局部加深，又不遺漏其它存在最優(yōu)解的可 能。目前主要是使用α β 剪枝算法加上迭代深化、置換表、歷史啟發(fā)等策略的 綜合應(yīng)用。 開(kāi)局庫(kù) (Opening Book) 把開(kāi)局幾步的走法建成數(shù)據(jù)庫(kù)供程序直接取用。實(shí)踐表明無(wú)論搜索引擎如何出色，在開(kāi)局搜索過(guò)若干層后，得到的可能只 是一些 很笨拙 的開(kāi)局。直接從開(kāi)局庫(kù)中取就可以大大加快開(kāi)局時(shí)的運(yùn)行速度和提高開(kāi)局的質(zhì)量。開(kāi)局庫(kù)一般是采用 zobrist 哈希技術(shù)加以實(shí)現(xiàn)。 機(jī)器自學(xué)習(xí) (Machine Learning) 機(jī)器自學(xué)習(xí)之一是針對(duì)評(píng)估函數(shù)。對(duì)弈過(guò)程機(jī)器自動(dòng)調(diào)整評(píng)估函數(shù)參數(shù)的權(quán) 值 進(jìn)行優(yōu)化，發(fā)現(xiàn)一些棋子之間潛在的聯(lián)系 :之二是采用模式識(shí)別，學(xué)習(xí)的過(guò)程是通過(guò)對(duì)博弈過(guò)程的識(shí)別統(tǒng)計(jì)，自行豐富模式庫(kù)中的內(nèi)容，以提高程序的博弈性能。 本文的主要工作 本 文 的主要工作是將博弈策略應(yīng)用到中國(guó)象棋程序的設(shè)計(jì)與實(shí)現(xiàn)上，建立一個(gè)完整的中國(guó)象棋計(jì)算機(jī)博弈 系統(tǒng)，研究工作主要集中在以下幾個(gè)方面 ： 棋盤(pán)表示與走法生成 從操作速度 (性能 )以及使用方便與否考慮，本象棋博弈系統(tǒng)從帶位行位列信息的擴(kuò)展棋盤(pán) —— 棋子聯(lián)系數(shù)組著手進(jìn)行研究。然后根據(jù)棋盤(pán)表示獲得所有棋子的走法預(yù)生成數(shù)組。在產(chǎn)生走法時(shí)直接從中取出數(shù)據(jù)，進(jìn)行少量判斷以得到該棋子的合法走步。 估值函數(shù) 如何快速有效的對(duì)一個(gè)局面進(jìn)行評(píng)估需要從速度和知識(shí)的兩個(gè)角度進(jìn)行考慮 :一般知識(shí)越多估值越準(zhǔn)確，但速度也慢下來(lái)。本系統(tǒng)采用通用的靜態(tài)估值方式，同時(shí)在估值時(shí)結(jié)合走法預(yù)生成數(shù)組，使估值的速度有很大提升。 搜索技術(shù) 博弈樹(shù)搜索技術(shù)它很大程度上獨(dú)立于具體的計(jì)算機(jī)博弈程序。本文討論了 αβ剪枝搜索算法及其各種增強(qiáng)手段：包括窗口原則、置換表 (內(nèi)存增強(qiáng) )；歷史啟發(fā)表 (節(jié)點(diǎn)順序調(diào)整 )；迭代深化 (時(shí)間控制 )等。如何把各種增強(qiáng)手段有機(jī)組合起來(lái)達(dá)到最優(yōu)，文章對(duì)基于迭代加深、置換表、歷史啟發(fā)的 Negascout 算法進(jìn)行改進(jìn)。 論文結(jié)構(gòu) 第一章闡述了選題背景，課題的國(guó)內(nèi)外研究現(xiàn)狀及課題的主要工作和文章的章節(jié)安排。 第二章 第一部分 首先介紹中國(guó)象棋 程序的一些基本數(shù)據(jù)結(jié)構(gòu)，著重研究了 擴(kuò)展 的棋盤(pán) —— 棋子聯(lián)系數(shù)組棋盤(pán) ； 在此基礎(chǔ)上實(shí)現(xiàn)所有棋子的 走法預(yù)生成數(shù)組，以提高搜索過(guò)程中走法產(chǎn)生的效率。 第二部分研究本系統(tǒng)的著法生成，包括預(yù)置表法和模板匹配法，進(jìn)一步提高了搜索效率。第三部分 描述本系統(tǒng)的評(píng)價(jià)函數(shù)架構(gòu)， 著重描述了靜態(tài)估值方法，分析了其不足，并提出了解決之道。 包括子力分?jǐn)?shù)、子力靈活度評(píng)價(jià)、棋盤(pán) 控制等并與走法預(yù)生成數(shù)組結(jié)合以提高估值速度。第四 部分實(shí)現(xiàn) 了博弈樹(shù)的 αβ剪枝算法并簡(jiǎn)要介紹各種搜索 策略 。第五部分闡述了開(kāi)局庫(kù)的設(shè)計(jì)原理。 第三章 給出實(shí)驗(yàn)環(huán)境和 程序?qū)崿F(xiàn) 。 第 四章 是全文的總結(jié)及展望 。 2 系統(tǒng) 的分析和設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu) （ Data structure） 數(shù)據(jù)結(jié)構(gòu)是一個(gè)程序的骨架，選擇一種好的數(shù)據(jù)結(jié)構(gòu)可以使程序的運(yùn)行效率大大提 高。 棋盤(pán)的基本表示法 （ Board Representions） 棋盤(pán)表示就是使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋盤(pán)上的信息，以便程序知道博弈的狀態(tài)。棋盤(pán)的數(shù)據(jù)表示直接影響到程序的時(shí)間及空間復(fù)雜度。為了追求更高效率，研究人員針對(duì)中國(guó)象棋提出了多種不同的表示方法。 中國(guó)象棋的棋盤(pán)表示中最典型的是用一個(gè) 10 9 的二維字節(jié) (byte)數(shù)組，數(shù)組中每個(gè)元素代表棋盤(pán)上的一個(gè)交點(diǎn)，其值表明這個(gè)交點(diǎn)上放置的是一個(gè)什么棋子或是沒(méi)有棋子 從棋子的角 度考慮，如果把棋盤(pán)看成是一個(gè)平面坐標(biāo)系，可以知道每一個(gè)棋子的位置信息 :小于 10 的橫坐標(biāo)和小于 11 的縱坐標(biāo) 。又在棋盤(pán)上最多 32 個(gè)棋子，故可以用一個(gè)32 個(gè)字節(jié)的一維數(shù)組表示所有 32 個(gè)棋子的位置，其中每個(gè)字節(jié)的高 4 位表示該棋子的橫坐標(biāo)，低 4 位表示棋子的縱坐標(biāo)。而己被吃掉的棋子用坐標(biāo)范圍以外的數(shù)表示。這樣棋盤(pán)信息就被裝入這 32 個(gè)字節(jié)中。當(dāng)然也可以把棋盤(pán)看作一維的，每個(gè)元素保存直接的位置信息。 兩種棋盤(pán)表示方法：一是做一個(gè)棋盤(pán)數(shù)組；二是做一個(gè)棋子數(shù)組。棋盤(pán)數(shù)組中由棋子的位置獲得棋子的類(lèi)型可以在常數(shù)時(shí)間內(nèi)完成，但由棋 子的類(lèi)型獲得棋子的位置需要遍歷；在棋子數(shù)組中由棋子的類(lèi)型獲得棋子的位置可以在常數(shù)時(shí)間內(nèi)完成，但由棋子的位置獲得棋子的類(lèi)型操作繁瑣。如果一個(gè)程序同時(shí)使用這兩個(gè)數(shù)組，那么獲得棋子的類(lèi)型和棋子的位置都可以在常數(shù)時(shí)間內(nèi)完成。這就是“棋盤(pán)棋子聯(lián)系數(shù)組”，它的技術(shù)要點(diǎn)是 : (l) 同時(shí)用棋盤(pán)數(shù)組和棋子數(shù)組表示一個(gè)局面，棋盤(pán)數(shù)組和棋子數(shù)組之間可以互相轉(zhuǎn)換。 (2) 隨時(shí)保持這兩個(gè)數(shù)組之間的聯(lián)系，棋子移動(dòng)時(shí)必須同時(shí)更新這兩個(gè)數(shù)組。在棋盤(pán)上刪除一個(gè)棋子，需要做兩個(gè)操作 (分別修改棋盤(pán)數(shù)組和棋子數(shù)組 )。同樣，添加一個(gè)棋子時(shí) 也需要兩個(gè)操作。 “棋盤(pán)棋子聯(lián)系數(shù)組“最大的優(yōu)勢(shì)是：對(duì)于著法產(chǎn)生過(guò)程，可以逐一查找棋子數(shù)組，如果該子沒(méi)有被吃掉，就產(chǎn)生該子的所有合理著法，由于需要查找的棋子數(shù)組的數(shù)量 (每方只有 16 個(gè)棋子能走 )比棋盤(pán)格子的數(shù)量 (90 個(gè)格子 )少得多，因此聯(lián)系數(shù)組的速度要比單純的棋盤(pán)數(shù)組快很多。同時(shí)“棋盤(pán) —— 棋子聯(lián)系數(shù)組”是很多改進(jìn)的棋盤(pán)的基礎(chǔ)。 改進(jìn)型棋盤(pán)結(jié)構(gòu) 在計(jì)算機(jī)上面，位運(yùn)算比一般的加減乘除及取余運(yùn)算快得多。如果能在尋找棋子 和定位棋子上使用位運(yùn)算代替加減乘除和取余，這將很大程度上提高運(yùn)算速度。所以 ，人們把“棋盤(pán) —— 棋子聯(lián)系數(shù)組“進(jìn)行擴(kuò)展：把棋盤(pán)做成 16 16 的大小，這樣得到行號(hào)可以用 16 除，得到列號(hào)可以對(duì) 16 取余（和 15 進(jìn)行運(yùn)算），這比除以 10 和對(duì) 9 取余操作要快得多。如圖 （紅色格子都被標(biāo)上“出界”的標(biāo)志，目標(biāo)格在這些格子上就說(shuō)明著法無(wú)效）： 圖 擴(kuò)展的棋盤(pán) 這種棋盤(pán)的更大的好處是： (1) 它可以防止棋子走出棋盤(pán)邊界。由 bool 型棋盤(pán)數(shù)組（屬于棋盤(pán)的位置為 true，否則為 false），判斷棋子是否走出棋盤(pán)邊界只要返回該數(shù)組對(duì)應(yīng)的值即可，速度快。 (2) 對(duì)于是否在城池內(nèi)可以用 bool 型城池?cái)?shù)組判斷，因?yàn)槭欠裨诔浅貎?nèi)的判斷會(huì)非常頻繁，直接用該數(shù)組會(huì)很高效。 (3) 判斷是否過(guò)河的方法非常簡(jiǎn)單：只要設(shè)定特定的表達(dá)式，當(dāng)表達(dá)式為假表示已過(guò)河，否則沒(méi)過(guò)河。 (4) 還可以非常方便的判斷棋子是否在己方。 著法生成 （ Move Generation） 著法生成就是要產(chǎn)生所有有效的著法，讓電腦棋手在這些著法中選擇最好的著法，并判斷人類(lèi)棋手是否符合走棋規(guī)則。著法生成 是博弈程序中一個(gè)相當(dāng)復(fù)雜而且耗費(fèi)運(yùn)算