（計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)論文）中國象棋博弈·局面評(píng)估研究.pdf

摘要 摘要 計(jì)算機(jī)博弈是博弈領(lǐng)域長期的奮斗目標(biāo)，也是人工智能學(xué)科極具挑戰(zhàn)性 的研究課題之一。憑借計(jì)算機(jī)的高速運(yùn)算能力和設(shè)計(jì)嚴(yán)謹(jǐn)?shù)乃惴?，?jì)算機(jī)可 以在人機(jī)對(duì)弈中表現(xiàn)出相當(dāng)高的“智能”。 國際象棋已經(jīng)有了“深藍(lán)”這樣震驚世界的成果，更加復(fù)雜的中國象棋 計(jì)算機(jī)博弈水平卻遠(yuǎn)遠(yuǎn)落后。 一款象棋博弈程序的實(shí)現(xiàn)主要被分為兩大部分：界面( 程序輔助) + 引擎 ( 人工智能) 。本文將介紹如何實(shí)現(xiàn)一款中國象棋博弈程序。其中包括：搜索 算法、局面評(píng)估、哈希表、歷史啟發(fā)、局面庫以及中盤研究；打譜；復(fù)盤等 功能的實(shí)現(xiàn)。 關(guān)鍵詞：中國象棋；人工智z f j 匕v - , ；博弈樹；p v s 搜索算法；局面評(píng)估； i i a b s t r a c t a b s t r a c t c o m p u t e rg a m ei st h ea i mo fg a m ef i e l d sf o rl o n g ，a n di st h eo n eo ft h e c h a l l e n g i n gt o p i c s i na r t i f i c i a l i n t e l l i g e n c e r e s e a r c h w i t ht l l e c o m p u t e r s l l i g h - s p e e dc o m p u t i n gp o w e ra n dw 色l l - s t r u c t u r e da l g o r i t h m s ，t h ep e r f o r m a n c eo f c o m p u t e rc a nb ev e r y “s m a r t i nm a n m a c h i n ec h e s s t h o u g hw eh a v ec h e s sl i k e “d e e pb l u e ”w h i c hs h o c k e dt h ew o r l d ，t h em o r e c o m p l i c a t e dc h i n e s ec h e s sl e v e l sa r ef a rb e h i n d t h ei m p l e m e n t a t i o no fc h e s sg a m ep r o g r a ms h a l lb ed i v i d e di n t ot w op a r t s ： i n t e r f a c e ( p r o g r a ma s s i s o + e n g i n e ( a r t i f i c i a li n t e l l i g e n c e ) 7 n l i sa r t i c l ew i l l i n t r o d u c eh o wt o i m p l e m e n tac h i n e s ec h e s sg a m ep r o g r a m a b o u t ：s e a r c h a l g o r i t h m 、r e s e a r c ho fs i t u a t i o na s s e s s m e n t 、h a s h t a b l e 、h i s t o r i c a li n s p i r a t i o n 、 s i t u a t i o nl i b r a r ya n dm i d c a pr e s e a r c h 、m a k es i t u a t i o n 、r e c o v e r yd i s ka st h e r e a l i z a t i o no ff u n c t i o n ss u c h k e yw o r d s ：c h i n e s ec h e s s ；a r t i f i c i a li n t e l l i g e n c e ；g a m et r e e ；p v ss e a r c h a l g o r i t h m ；r e s e a r c ho fs i t u a t i o na s s e s s m e n t ； i i i 學(xué)位論文獨(dú)創(chuàng)性聲明 學(xué)位論文獨(dú)創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文是本人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作及取得的 研究成果。據(jù)我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文中不包含其 他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得直昌盍堂或其他教育機(jī)構(gòu) 的學(xué)位或證書而使用過的材料。與我一同工作的同志對(duì)本研究所做的任何貢獻(xiàn)均 已在論文中作了明確的說明并表示謝意。 學(xué)位論文作者簽名( 手寫) ：眵撙 簽字日期： 硼羅年l 乞月衫日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解直邑太堂有關(guān)保留、使用學(xué)位論文的規(guī)定，有權(quán)保 留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和磁盤，允許論文被查閱和借閱。 本人授權(quán)直量太堂可以將學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索， 可以采用影印、縮印或掃描等復(fù)制手段保存、匯編本學(xué)位論文。同時(shí)授權(quán)中國科 學(xué)技術(shù)信息研究所將本學(xué)位論文收錄到中國學(xué)位論文全文數(shù)據(jù)庫，并通過網(wǎng) 絡(luò)向社會(huì)公眾提供信息服務(wù)。 ( 保密的學(xué)位論文在解密后適用本授權(quán)書) 學(xué)位論文作者簽名( 手寫) ： 哆撙 簽字日期：叫年l z 月勺” 導(dǎo)師簽名( 手寫) ：白c 妒 簽字日期：訓(xùn)7 年f2 ，月弓e l 第1 章引言 第1 章引言 1 1 計(jì)算機(jī)博弈概述 計(jì)算機(jī)博弈是人工智能學(xué)科和計(jì)算機(jī)學(xué)科的交叉研究方向之一。自從計(jì)算機(jī) 誕生以來，許多著名學(xué)者都曾經(jīng)涉足于這一領(lǐng)域的研究工作。計(jì)算機(jī)之父馮諾 依曼( w b n n e u n a n n ) 就提出了用于博弈的極大極小定理【1 1 ，信息論的創(chuàng)始人香濃 ( c l a u d ee s h a n n o n ) 教授，又給出了極大極小算法 2 1 ，著名的計(jì)算機(jī)學(xué)家阿蘭圖 靈( a t u r i n g ) 也曾做過機(jī)器博弈的研究【3 1 。伴隨著計(jì)算機(jī)硬件的飛速發(fā)展， a l p h a b e t a 剪枝算法的提出”1 、極小樹的證明【5 t 、負(fù)極大值算法的給出1 5 1 、迭代深 化思想的實(shí)現(xiàn)f 6 1 ，都使得機(jī)器博弈有了長足進(jìn)展。以i b m “深藍(lán)為代表的劃時(shí) 代成果，表明計(jì)算機(jī)的弈棋能力已經(jīng)可以和人類精英較量。如今，機(jī)器博弈已經(jīng) 成為一個(gè)獨(dú)立而重要、頗有發(fā)展前途的學(xué)術(shù)研究領(lǐng)域，但是它在中國的發(fā)展還很 落后。計(jì)算機(jī)博弈通常只被看作是一種科技活動(dòng)，而常常被學(xué)術(shù)界所忽視，也正 是由于缺少學(xué)術(shù)研究的有力支持，才使得這一方向的發(fā)展比較緩慢，尤其是在中 國內(nèi)陸。機(jī)器博弈作為計(jì)算機(jī)學(xué)科的一個(gè)分支，在吸收其他學(xué)科的成果方面明顯 不夠，如對(duì)策論、系統(tǒng)論、控制論等。作為人工智能學(xué)科的“果蠅 ，機(jī)器博 弈由于缺少計(jì)算機(jī)學(xué)科的有力支持，其研究成果也只能作為初級(jí)的游戲產(chǎn)品。 1 2 計(jì)算機(jī)棋類博弈分析 盡管目前有的棋類的計(jì)算機(jī)水平已經(jīng)高出了人類大師，如國際象棋，但是計(jì) 算機(jī)間的較量仍然持續(xù)不斷，各種人機(jī)大戰(zhàn)也接二連三。因?yàn)橛?jì)算機(jī)的智能也需 要不斷地提高。而那些水平還不高的計(jì)算機(jī)博弈項(xiàng)目，如中國象棋、日本將棋和 圍棋，更是倍受人們的青睞。 計(jì)算機(jī)棋類博弈基本屬于完全信息的動(dòng)態(tài)博弈。也就是對(duì)弈雙方不僅清楚當(dāng) 前的局面，了解對(duì)手以往的著數(shù)，而且了解對(duì)手接下來可能采取的著數(shù)。盡管雙 方可能采取的著法數(shù)以十計(jì)、百計(jì)，但畢竟還是有限的。計(jì)算機(jī)可以通過展開一 顆根在上、葉在下的龐大的博弈樹描述這一過程。再利用自身在時(shí)間、空間上的 強(qiáng)大能力進(jìn)行巧妙的搜索，從而找到可行解及近優(yōu)解，即給出當(dāng)前的著法。 摩爾根與果蠅 p p t o l ，t o m a sh u n tm o r g a na n dd r o s o p h i l a h t t p ：b a s i c s h s m u e d u c n j p k c m a r x _ p h i l o s o p h y y x y z x 2 5 6 ，1 ，t h o m a sh u n tm o r g 柚 l 第1 章引言 顯然，計(jì)算機(jī)的搜索能力是計(jì)算機(jī)智力水平的重要體現(xiàn)。其實(shí)，人類在求解 各種問題的時(shí)候，解析求解還是次要的。人們大量采用的方法，人類智能的體現(xiàn)， 主要也是在頭腦里搜索。腦袋轉(zhuǎn)的快、主意多，智商就高。 棋類博弈軟件的設(shè)計(jì)，首先遇到的難題便是數(shù)據(jù)結(jié)構(gòu)的選擇。其中包括棋盤、 棋子、棋局和著法的編碼與存儲(chǔ)。良好的數(shù)據(jù)結(jié)構(gòu)可以節(jié)省大量的存儲(chǔ)空間，可 以提高存取的效率。為了適應(yīng)博弈樹的展開與搜索，常常還要同時(shí)給出棋局的多 種數(shù)據(jù)格式。如棋局狀態(tài)、棋子位置、比特棋局和比特向量，還要用到哈希變換 和哈希表等。 棋局的靜態(tài)評(píng)估是機(jī)器博弈的另一個(gè)難點(diǎn)，它不僅需要棋類對(duì)弈的基本知 識(shí)，而且用到直接量化、模式量化、隨機(jī)評(píng)估、模糊評(píng)估等一系列手段。對(duì)于象 棋可以給每個(gè)棋子和棋位打分，而對(duì)于圍棋則要進(jìn)行定式的抽取和模式的匹配。 棋類博弈的高手主要應(yīng)在這方面提供更多的專業(yè)知識(shí)。 搜索算法是機(jī)器“思維 的核心。包括著法生成，博弈樹展開，各種剪枝搜 索和各種啟發(fā)式搜索?，F(xiàn)有的成果非常豐富，也是今后研究工作的重點(diǎn)。 編程語言，程序設(shè)計(jì)方法、軟件工程、并行計(jì)算等都是算法實(shí)現(xiàn)的重要技術(shù)， 需要和博弈原理有機(jī)結(jié)合，才能編寫出高水平的博弈軟件。 2 第2 帝中國象棋在計(jì)算機(jī)中的表示 第2 章中國象棋在計(jì)算機(jī)中的表示 2 1 基本功能模塊 中國象棋要在計(jì)算機(jī)上實(shí)現(xiàn)，首先要解決的就足界面和操作問題。程序應(yīng)該 挺供給用戶個(gè)基本的游戲界面并且能夠?qū)崿F(xiàn)下棋，悔棋等千h 關(guān)的操作。 圈2 】程序界面 由此，我們給程序規(guī)劃了以下幾個(gè)基本功能模塊 一、初始化部分 p r i v a t ev o i di n i t g a m e 0 rj ! g j - ! “ ! ! j 二j 叫乜簽 ) l n i t g a m e 0 負(fù)責(zé)的是游戲的韌始化。我們把有關(guān)中國象棋的棋局初始化過程放 在了這里f i i 。初始化的內(nèi)容包括：l 、引擎部分用到的相關(guān)變量初始化( 包括棋 予位趕( 拱盤數(shù)組) ，當(dāng)前下棋方標(biāo)志、選中棋子標(biāo)志、游成模式、棋局過程數(shù) 組等) ：2 、程序輔助部分用到的帽關(guān)控件的初貽化( 包括對(duì)上一步、下一步按鈕 的狀態(tài)顯示，棋局過程列表框顯示等) 。 撾瑟l_蓋髫上甲11笛國甲氬_i一|門溶籮忿警嘞一塞漿擎卜y|i卜l澎 第2 章中國象棋在計(jì)算機(jī)中的表示 二、繪圖部分 v o i dd r a w q p ( ) v o i dd r a w k u a n g o v o i dd r a w v a l u e 0 ；： ) d r a w q p 0 函數(shù)和d r a w k u a n g ( ) 匪1 數(shù)負(fù)責(zé)的是程序界面的繪圖。在這里要完成 棋盤、棋子的顯示，下棋起始位置和目標(biāo)位置的提示框的顯示。 由于程序中的棋盤、棋子等都是以位圖的形式給出的。所以在d r a w q p ( ) i 呈j 數(shù) 里所做的工作主要都是在貼位圖。 需要注意的是由于位圖文件不能像g i f 文件那樣有透明的背景并且棋子是圓 形的而位圖文件只能是矩形的，所以如果直接貼圖的話會(huì)在棋盤上留下一塊白色 的邊框棋子的背景。因此，要想讓棋子文件的背景“隱藏”需要通過一些“與” 和“異或”操作來屏蔽掉棋子的背景。在這里使用到了一些a p i 函數(shù)：如 c r e a t e c o m p a t i b l e d c ( ) 、t r a n s p a r e n t b l t ( ) 、s e l e c t o b je c t ( ) 等。另外為了對(duì)顏 色更好控制，還需要編寫一個(gè)顏色轉(zhuǎn)換函數(shù)，能夠?qū)㈩伾? c o l o r 對(duì)象) 轉(zhuǎn)換 成r g b 值。 d r a w v a l u e ( ) i 函數(shù)負(fù)責(zé)的是游戲過程中局面分?jǐn)?shù)的顯示，它能夠把當(dāng)前局面每 一個(gè)棋子的得分畫在棋子的下方并且顯示局面分差。這樣方便我們觀察棋局過程 棋子分?jǐn)?shù)的變化，來理解計(jì)算機(jī)選擇下法的依據(jù)，從而判斷局面評(píng)估函數(shù)參數(shù)是 否設(shè)置得合理。這也是程序中重要的一個(gè)輔助部分。 三、行棋部分( 鼠標(biāo)事件響應(yīng)) 程序中下棋的操作是通過鼠標(biāo)在棋盤( p a n e l _ q i p a n 控件) 上的點(diǎn)擊實(shí)現(xiàn)的， 我們?yōu)樵摽丶砑邮髽?biāo)事件的消息，可得到如下函數(shù)： p f i v a t ev o i dp a n e l _ q i p a n _ m o u s e c l i c k ( o b j e c ts e n d e r , m o u s e e v e n t a r g se ) ： ) 當(dāng)用戶在窗體棋盤面板按下鼠標(biāo)左鍵時(shí)，程序就會(huì)調(diào)用該函數(shù)來進(jìn)行處理。其 中第二個(gè)參數(shù)e 是我們?cè)诔绦蛑兴玫降模o出了當(dāng)鼠標(biāo)被按下時(shí)鼠標(biāo)指針 相對(duì)于棋盤的位置坐標(biāo)。通過對(duì)這一信息進(jìn)行轉(zhuǎn)換我們可以得知用戶的走法，并 且調(diào)用相關(guān)的規(guī)則函數(shù)判斷該走法是否合法。 4 第2 章中國象棋在計(jì)算機(jī)中的表示 在m o u s e c l i c k 函數(shù)里我們處理以下幾種游戲模式： 1 、人機(jī)對(duì)戰(zhàn) 2 、打譜練習(xí) 3 、復(fù)盤模式 4 、局面評(píng)估 5 、中盤研究 6 、空模式 在大多數(shù)模式中，主要的操作為： 1 、如果用戶點(diǎn)擊鼠標(biāo)的位置落在己方的棋子上，表示用戶選中了該棋子， 下一步將移動(dòng)該子進(jìn)行走棋( 也可能用戶下一步將會(huì)選擇己方另外的棋子，總之 這一操作會(huì)記錄下用戶所選的將要走的棋子) 。 2 、如果之前用戶已經(jīng)選過了棋子，那么這一次的點(diǎn)擊( 如果不是另選本方 的其它棋子的話) 表達(dá)了用戶的一次走棋過程。在收到用戶傳達(dá)的走棋信息后， 我們先判斷該著法是否合法( 是否符合中國象棋的游戲規(guī)則) ；如果合法，則執(zhí) 行該下法。如此，在m o u s e c l i c k 函數(shù)里，我們實(shí)現(xiàn)了游戲的操作部分( 當(dāng)然每走 一步棋，還還需要調(diào)用繪圖函數(shù)來顯示棋盤局面的更新) 。 以上三部分并非程序所實(shí)現(xiàn)的全部，而僅僅是與我們的程序密切相關(guān)的部 分。此外還有其它部分對(duì)程序同樣必不可少，比如游戲規(guī)則函數(shù)、棋局過程顯示 等，但在此不多做介紹。 2 2 棋局表示 計(jì)算機(jī)下棋的前提是要讓計(jì)算機(jī)讀懂象棋。所謂讀懂，即計(jì)算機(jī)應(yīng)該能夠清 楚地了解到棋盤上的局面( 棋盤上棋子的分布情況) 以及下棋方所走的每一種著 法。因而首先我們需要有一套數(shù)據(jù)結(jié)構(gòu)來表示棋盤上的局面以及著法。 當(dāng)前主要有兩種棋盤表示法：一種是棋盤數(shù)組，另一種是位棋盤。位棋盤最 初是國際象棋( 8 木8 ，剛好6 4 b i t s ) 里引入的，其最大的優(yōu)點(diǎn)就是超高的運(yùn)算效率與 空間節(jié)省。所以大多數(shù)博弈軟件都是用位棋盤作為基本的數(shù)據(jù)結(jié)構(gòu)。但中國象棋 是1 0 9 的棋盤，不易用位棋盤表示。這里采用了最傳統(tǒng)的同時(shí)也是最為簡(jiǎn)單的 棋盤數(shù)組。即用一個(gè)1 0 9 的數(shù)組來存儲(chǔ)棋盤上的信息，數(shù)組的每個(gè)元素存儲(chǔ)棋 盤上相應(yīng)位置是何種棋子。這種表示方法簡(jiǎn)單易行( 缺點(diǎn)是效率不是很高) 。按 此方法棋盤的初始情形如下所示： 第2 章中國象棋在計(jì)算機(jī)中的表示 p u b l i cb y t e ， c h e s s b o a r d 2 n e w b y t e 10 ，9 】 1 1 ，1 0 ，1 2 ，1 3 ，1 4 ，1 3 ，1 2 ，1 0 ，1 1 0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 0 ，9 ，0 ，0 ，0 ，0 ，0 ，9 ，0 8 ，0 ，。8 ，0 ，8 ，0 ，8 ，0 ，8 0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 ，0 1 ，0 ，1 ，0 ，1 ，0 ，1 ，0 ，1 a l p h a )a l p h a = s c o r e ；保留最大值 i f ( s c o r e = b e t a )b r e a k ；剪枝 r e t u r na l p h a ；返回極大值 ) 1 4 第3 章算法設(shè)計(jì)與實(shí)現(xiàn) p v s ( 也稱極小窗口m i n i m a lw i n d o w ss e a r c h ) 搜索算法是a l p h a - b e t a 的 種變體。此算法基于如下假設(shè)：假定第一步是最佳的下法，搜索其后繼者，直到 更好的另一節(jié)點(diǎn)。在每一個(gè)中間節(jié)點(diǎn)中，第一個(gè)分枝都以完整窗口( a ，b ) 進(jìn)行搜 索并產(chǎn)生一個(gè)值v ，后繼的分枝則以一個(gè)極小的窗口( v ，v + 1 ) 進(jìn)行搜索。如果猜 測(cè)被證明不準(zhǔn)確( f a i l h i g h ) ，隨后就需要以( v + l ，b ) 為窗口進(jìn)行搜索；如果猜測(cè) 是( f a i l l o w ) 則剪枝；否則表示猜測(cè)命中。以此達(dá)到高效搜索的目的。p v s 算法 的基本代碼如下 i n tn e g a s c o u t ( i n td e p t h ，i n ta l p h a ，h a tb e t a ) i f ( d e p t h 一0 ) r e t u r ne v e l u a t e 0 ； c r e a t e a l l m o v e 0 ；m a k e m o v e o ； b e s t = n e g a s c o u t ( d e p t h 一1 一b e t a , - a l p h a ) ；調(diào)用全窗口搜索第一個(gè)結(jié)點(diǎn) u n m a k e m o v e o ； f o r ( e a c hm o v em 、 。i f ( b e s t a l p h a ) a l p h a 2 b e s t ； m a k e m o v e 0 ； s c o r e = - n e g a s c o u t ( d e p t h l ，一a l p h a - 1 ，一a l p h a ) ；極窄窗口搜索 i f ( s c o r e a l p h a & & s c o r e b e s t ) b e s t = s c o r e ；窄窗搜索命中 u n m a k e m o v e o ； ) r e t u r nb e s t ； ) 第4 章算法的優(yōu)化 第4 章算法的優(yōu)化 通過設(shè)計(jì)好的搜索算法和局而評(píng)估，我們已經(jīng)可以讓計(jì)算帆產(chǎn)生搏弈的過 程。但如果能加i 二一蝗附加的手段進(jìn)行優(yōu)化，計(jì)算機(jī)所體現(xiàn)出來的智商會(huì)大大的 提高。 4 1 哈希表應(yīng)用 計(jì)算機(jī)在搜索過程中時(shí)有可能會(huì)出現(xiàn)以下局面，如幽4 辮辮饕 囂淄囂 黼 嘲 目喜喜 事毒s 茜 蘸 田 曰 凈t 爭(zhēng) 潦母s 每掣 一 謄始嗡舞； | f。x 1 ：萼蚓 一 。；7 遣：= ：= i 圖4l 相同節(jié)點(diǎn) 喜占：；0 圭 田 從圈中我們可以看出：從a 節(jié)點(diǎn)開始，有兩個(gè)分枝( b 節(jié)點(diǎn)和c 節(jié)點(diǎn)) 。b 1 6 第4 章算法的優(yōu)化 節(jié)點(diǎn)又有子節(jié)點(diǎn)d ，c 節(jié)點(diǎn)有子節(jié)點(diǎn)e 。在再往下d 節(jié)點(diǎn)又存在子節(jié)點(diǎn)f ，e 節(jié) 點(diǎn)存在子節(jié)點(diǎn)g 。節(jié)點(diǎn)f 和g 在同一層，卻又是兩個(gè)完全相同的局面。這時(shí)我們 在搜索g 節(jié)點(diǎn)的時(shí)候完全可以利用已經(jīng)搜索過的f 節(jié)點(diǎn)的結(jié)果，而沒有必要浪費(fèi) 時(shí)間重新搜索一次g 。 將已經(jīng)搜索過的節(jié)點(diǎn)結(jié)果保存起來，在以后的搜索過程中先在表中進(jìn)行查 找，如果找到了則直接使用該值，找不到則正常搜索。可以提高搜索的效率。 考慮到存放數(shù)據(jù)和查找數(shù)據(jù)速度要盡可能的快( 否則將得不償失) ，哈希表 是一種很好的選擇。其基本算法如下： i n ta l p h a b e t a ( i n td e p t h ，i n ta l p h a ，i n tb e t a ) s c o r e = s e a r c h h a s h t a b l e 0 ；至l j 哈希表中查找該局面是否出現(xiàn)過 i f ( 搜索命中) r e t u r ns c o r e ； i f ( d e p t h o ) a d d h a s h i t e m ( s c o r e ) ；添加結(jié)果到哈希表節(jié)點(diǎn) r e t u r ne v a l u a t e ( ) ；由局面評(píng)估函數(shù)返回估值 ： 為了能更快速的進(jìn)行局面的存放和查找，每一個(gè)保存的節(jié)點(diǎn)應(yīng)該是敖列存放 的。c 拌中有一個(gè)現(xiàn)成的h a s h t a b l e 類可以使用，我們要解決的問題是：如何迅速 確定該節(jié)點(diǎn)在哈希表中的位置。為此我定義了一個(gè)3 2 位的1 0 9 二維數(shù)組和一個(gè) 6 4 位的1 0 9 二維數(shù)組，它們的值都由隨機(jī)函數(shù)產(chǎn)生。通過對(duì)3 2 位二維數(shù)組的計(jì) 算得到該節(jié)點(diǎn)在哈希表中的下標(biāo)，再通過對(duì)6 4 位二維數(shù)組的計(jì)算生成一個(gè)驗(yàn)證 碼，確定節(jié)點(diǎn)與局面是否相同。在搜索的過程中，每一個(gè)搜索過的節(jié)點(diǎn)都把得分 保存到哈希表中去，而在搜索節(jié)點(diǎn)之前則先在表中查找一下該節(jié)點(diǎn)是否存在：如 果存在，直接取出結(jié)果；否則正常搜索。 4 2 歷史啟發(fā) 在各類搜索算法中，改進(jìn)搜索算法的目的在于將不必搜索的分枝從搜索過程 中排除( 剪枝) 。而剪枝的效率幾乎完全取決于節(jié)點(diǎn)排列的順序。在節(jié)點(diǎn)排列順 1 7 第4 章算法的優(yōu)化 序處于理想狀態(tài)下，a l p h a b e t a 搜索算法需要遍歷的節(jié)點(diǎn)數(shù)僅為完全遍歷節(jié)點(diǎn)數(shù) 平方根的兩倍左右。也就是說如果一般情況搜索5 層局面需要遍歷l 億個(gè)節(jié)點(diǎn)， 那么理想狀態(tài)下的a l p h a b e t a 搜索只需要遍歷約2 萬個(gè)節(jié)點(diǎn)( 狹義理解速度提高 了5 0 0 0 倍) 。如何調(diào)整節(jié)點(diǎn)的順序是提高搜索效率的關(guān)鍵。 我們可以將一些具體的棋類知識(shí)加入其中，例如：優(yōu)先展開車馬炮所產(chǎn)生的 節(jié)點(diǎn)，優(yōu)先展開攻防關(guān)鍵棋子所產(chǎn)生的節(jié)點(diǎn)等等。但這一方法需要通過一系列復(fù) 雜的判斷。 我們還可以使用歷史啟發(fā)【7 1 ( h i s t o r yh e u r i s t i c ) 進(jìn)行增強(qiáng)排序。該方法脫離 了對(duì)具體棋類知識(shí)的依賴：在搜索過程中，每找到一個(gè)好的走法，就將該走法對(duì) 應(yīng)的歷史得分增加。這樣一個(gè)被多次搜索且被確認(rèn)好的走法，其歷史得分會(huì)較高。 當(dāng)搜索中間節(jié)點(diǎn)時(shí)，將產(chǎn)生的節(jié)點(diǎn)集合( 步驟數(shù)組) 按歷史得分預(yù)先做一個(gè)排序， 從而在搜索時(shí)引發(fā)更多的剪值以實(shí)現(xiàn)高效。好的走法可以定義如下： 1 、由其產(chǎn)生的節(jié)點(diǎn)引發(fā)了剪枝。 2 、是同層節(jié)點(diǎn)中最好的走法 這一方法的實(shí)現(xiàn)需要我們解決兩個(gè)問題： 首先，如何將一個(gè)走法映射到歷史得分的數(shù)組中? 考慮到整個(gè)象棋棋盤是1 0 行9 列的顯示，我們可以使用起始和目標(biāo)坐標(biāo)作為存取這個(gè)數(shù)組的兩個(gè)下標(biāo)。汶 樣就只需要9 0 * 9 0 的一個(gè)二維數(shù)組即可。 另一個(gè)問題是如何確定歷史得分的權(quán)重? 也就是說當(dāng)一個(gè)好的走法被發(fā)現(xiàn) 時(shí)，應(yīng)該給它加多少分合適呢? 一般而言，當(dāng)該節(jié)點(diǎn)越靠近根節(jié)點(diǎn)的時(shí)候，所對(duì) 應(yīng)的局面相似程度就越高，搜索得到的值也就越可靠。所盼在程序中設(shè)定每發(fā)現(xiàn) d e p t h 一個(gè)好走法就給其歷史得分加上2 ( d e p t h 是當(dāng)前層數(shù)) 。 4 3 開局庫與殘局庫 中國象棋經(jīng)過千百年的演繹和發(fā)展，涌現(xiàn)出許多干錘百煉的經(jīng)典招數(shù)。無論 我們的搏弈程序如何優(yōu)秀，由于其受到諸多因素的影響，搜索出來的大部分著法 都很難與之相媲美。特別是開局和殘局。如果我們能將這些開局方法和殘局手段 加以引入，可以大大的提高博弈的質(zhì)量。 大多數(shù)棋譜類書籍中都能找到幾十種常用的開局方式。將這些經(jīng)典開局搜集 起來集中保存，我們可以建立一個(gè)5 1 0 步的開局?jǐn)?shù)據(jù)庫。這樣博弈時(shí)就可以先 在開局庫中找出類似的局面，直接獲得其著法，加快開局的速度和質(zhì)量。 l r 第4 章算法的優(yōu)化 開局庫的數(shù)據(jù)庫不必很大，我們也可以在其中使用哈希方法，只存放某一局 面的哈希值以及對(duì)應(yīng)的走法。有時(shí)候某一局面有著多種不錯(cuò)的走法，這時(shí)我們可 以把一系列開局走法歸為一組，前面的走法隨機(jī)選擇一種，后繼的走法則在該組 中優(yōu)先選擇。這樣可以保持一個(gè)一致的策略。此外還可以增加一個(gè)勝率統(tǒng)計(jì)的字 段，通過統(tǒng)計(jì)不同開局的勝率來自動(dòng)選擇成功率較高的開局。 殘局與開局不同，殘局的局面極少相同。我們建立的殘局庫可以使用回朔分 析( r e t r o g r a d ea n a l y s i s ) 的方法生成一個(gè)數(shù)據(jù)庫。將所有6 子( 6 子以下) 殘局 的結(jié)果保存在數(shù)據(jù)庫中。在棋局的過程中一但出現(xiàn)了棋子數(shù)量少于或等于5 個(gè)的 局面，就可以直接在庫中取出其最終的結(jié)果。這樣搜索的精度就大大的提高，同 時(shí)也可以提早發(fā)現(xiàn)一些必勝必?cái)〉慕Y(jié)局。但7 子( 7 予以上) 殘局庫受存儲(chǔ)空間 和數(shù)據(jù)庫查詢速度等因素的影響j 較難實(shí)現(xiàn)。 殘局庫的具體實(shí)現(xiàn)上依然可以使用哈希技術(shù)。唯一不同的是哈希表所使用的 隨機(jī)數(shù)組應(yīng)該做為常量保存在殘局庫中，在程序啟動(dòng)時(shí)不再生成該數(shù)組，而是從 庫中取出使用。這樣在搜索過程中生成的哈希值才能和殘局庫中保存的局面相契 合。 1 9 第5 章算法分析與比較 第5 章算法分析與比較 在程序完成后測(cè)試中發(fā)現(xiàn)，編寫此類的w i n d o w s 應(yīng)用程序還是應(yīng)該選擇更貼 近底層的c c + + 語言。c 群開發(fā)環(huán)境在運(yùn)行速度上比v c + + 開發(fā)環(huán)境要慢許多。據(jù) 本人測(cè)試( p e n t i u m ( r ) 4c p u2 8 0 g h z + 5 1 2 m 內(nèi)存) ，在c + + 環(huán)境下搜索7 萬個(gè)節(jié) 點(diǎn)只需要2 3 秒，但c 拌n e t 環(huán)境下卻要花費(fèi)3 0 4 0 秒。這使得我的程序無法快速 的搜索到更高層。表5 1 是幾種搜索引擎在開局時(shí)搜索不同深度的平均節(jié)點(diǎn)數(shù)。 表5 1 算法分析比較 12345 a l p h a - b e t a 搜索 4 55 2 31 0 6 8 97 2 9 5 4 p v s 搜索 4 55 5 25 3 0 24 6 3 6 1 綜合搜索 4 51 6 41 5 6 7 6 8 9 55 5 6 2 3 。與我所搜集到其他同類程序相比，相同搜索深度下，搜索的節(jié)點(diǎn)數(shù)大約減少 了1 7 左右。而且由于在程序中添加了多種輔助手段用來測(cè)試評(píng)估函數(shù)，所以局 面評(píng)估更為精細(xì)。特別是開局時(shí)脫離開局庫也能準(zhǔn)確的模仿名家開局。 但由于我對(duì)在c 撐使用w i n d o w s a p i 函數(shù)的不熟悉，導(dǎo)致我在界面及輔助功能 部分花費(fèi)了大量的時(shí)問和精力。因而沒能夠?qū)τ?jì)算機(jī)引擎部分作更深一步的挖掘 和研究。對(duì)于諸如機(jī)器學(xué)習(xí)( m a c h i n el e a r n i n g ) 、位棋盤( b i t b o a r d ) 、迭代加深 ( i t e r a t i v ed e e p e n i n g ) 、水平效應(yīng)( h o r i z o ne f f e c t ) 、并行搜索等當(dāng)今棋類對(duì)弈程 序中所采用的先進(jìn)技術(shù)和思想，在我的程序中并未涉及。這在一定程度上影響了 程序中引擎的工作效率。 而在局面評(píng)估模塊中又缺乏對(duì)面向?qū)ο笏枷氲呢瀼睾褪褂?。由于本人最初?編寫局面評(píng)估部分時(shí)一心只想盡快看到成果，因而從一開始就按照自己先前的程 序習(xí)慣( 面向過程) 來編寫代碼。到了開發(fā)后期，又缺少時(shí)間和精力來用面向?qū)?象思想重新改寫程序，最終導(dǎo)致局面評(píng)估部分與類“無緣。這也是我的一大遺 憾。 2 0 第6 章結(jié)論與展望 6 1 結(jié)論 第6 章結(jié)論與展望 首先在導(dǎo)師的熱心幫助下，最終順利實(shí)現(xiàn)了程序。整個(gè)程序近5 0 0 0 行代碼， 內(nèi)容涉及人工智能的基本理論以及開發(fā)c 拌應(yīng)用程序的一些基礎(chǔ)知識(shí)。無論是在程 序難度上還是規(guī)模上都是之前所未遇到過的。該程序的i l i o n 完成為我積累了相當(dāng) 可觀的運(yùn)用理論知識(shí)解決實(shí)際問題的經(jīng)驗(yàn)。特別是當(dāng)程序運(yùn)行過程中發(fā)現(xiàn)錯(cuò)誤的 時(shí)候，找出問題所在并解決問題更是一個(gè)提高實(shí)際編程能力的過程。得益于此次 編寫中國象棋對(duì)弈程序，我對(duì)人工智能有了一個(gè)較全面的認(rèn)識(shí)這為我以后進(jìn) 一步學(xué)習(xí)或研究的方向也提供了一定的參考。此外，我還實(shí)踐了用c 拌編寫基本的 w i n d o w s 應(yīng)用程序，為今后從事類似應(yīng)用程序開發(fā)也起到了一定的幫助作用。 6 2 進(jìn)一步工作的方向 本文的研究雖然取得了初步的成果，但依然任重道遠(yuǎn)，尚有許多需要進(jìn)一步 深入進(jìn)行的研究工作，研究?jī)?nèi)容主要包括以下三個(gè)方面： 1 、局面庫的存儲(chǔ)及管理方式；2 、搜索樹的并行處理方式的研究；3 、使用 面向?qū)ο蟮乃枷雽?duì)局面評(píng)估部分做更深入的細(xì)化，優(yōu)化各項(xiàng)參數(shù)。 在程序內(nèi)借鑒了國際象棋中采用各種方法和取得的成果，包括開局庫、殘局 庫等。這些庫的運(yùn)用給程序節(jié)省了很多時(shí)間，但也吃掉了很多存儲(chǔ)資源。6 子殘 局庫需要大于1 0 g 的硬盤空間。我擬定的一項(xiàng)研究?jī)?nèi)容是對(duì)局面庫的存儲(chǔ)方式進(jìn) 行研究，以確定是否存在更好的方案來有效地降低局面庫的存儲(chǔ)空間。 另外，可以提高處理器利用率的樹結(jié)構(gòu)深度并行搜索方法也非常值得研究； 也是我們所面臨的一個(gè)關(guān)鍵問題。一般的小型機(jī)服務(wù)器大都配有多個(gè)處理器，從 成本角度來看，可以使用多臺(tái)微機(jī)來進(jìn)行局面處理，這樣就很容易搭建多處理器 環(huán)境，給并行搜索的研究帶來方便。 此外，使用v c + + 開發(fā)環(huán)境重新改寫程序。從面向?qū)ο蟪霭l(fā)，首先定義一個(gè) 棋子類，然后派生出具體的車馬炮等子類，以此來做個(gè)體整體的評(píng)估。從而實(shí)現(xiàn) 在類的對(duì)象中對(duì)局面做出準(zhǔn)確的描述。 2 l 致謝 致謝 工作六年后再進(jìn)校園學(xué)習(xí)已是一件十分值得慶幸的事，更為慶幸的是，我遇 到了一位好導(dǎo)師。我對(duì)計(jì)算機(jī)博弈的興趣始于平時(shí)生活中的一些愛好，我的學(xué)位 論文也是源于導(dǎo)師的指引。 在論文完成之際，首先，要特別感謝的是我的導(dǎo)師白似雪教授：最終我能夠 順利完成論文，離不開導(dǎo)師對(duì)我的指導(dǎo)與幫助。謝謝您的支持! 其次，要感謝對(duì)我再教育的各位任課老師。在讀研究生的期間，你們也給了 我很多的教育和啟發(fā)，讓我能夠進(jìn)一步完善計(jì)算機(jī)學(xué)科的知識(shí)體系。 此外還要感謝學(xué)院領(lǐng)導(dǎo)李勇院長，黃海哨書記，蔡澤光院長對(duì)我的關(guān)心和愛 護(hù)。讓我盡可能的減少了一些學(xué)院工作安排，我才有更多的時(shí)間和精力去完成本 次論文。 讀研三年期間，班主任陳小紅老師也給予了我很多的幫助。讓我能更順利的 安排好各項(xiàng)學(xué)習(xí)時(shí)間，獲得最新的通知。在這里也對(duì)您說一聲謝謝，您辛苦了! 最后感謝胡彩明老師、肖雄斌老師等各位同事。謝謝你們?cè)诎倜χ谐榭諑?助我測(cè)試程序，我才能更快的修正程序中的各種b u g 。感謝w w w c s d n n e t 論壇 上各位大蝦們，每次當(dāng)我遇到問題的時(shí)候總能在第一時(shí)間得到你們的幫助。 羅濤 2 0 0 9 年1 0 月 參考文獻(xiàn) 參考文獻(xiàn) 1 j y o nn e u m a n na n d0 m o r g e n s t e r n t h e o r yo fg a m e sa n de c o n o m i cb e h a v i o r m p r i n c e t o n ：p r i n c e t o nu n i v e r s i t yp r e s s ，1 9 4 4 2 s h a n n o n ，c l a u d ee p r o g r a m m i n gac o m p u t e rf o rp l a y i n gc h e s s j p h il o s o p h i c a l m a g a zi n e ，1 9 5 0 ，4 1 ：2 5 6 2 7 5 3 a t u r i n g d i g i t a lc o m p u t e r sa p p l i e dt og a m e s f a t h e rt h a nt h o u g h t c ( b b o w d e n ， e d i t o r ) ，p i t m a n ，1 9 5 3 ，2 8 6 2 9 5 4 s n f u l l e r ，j g g a s c h i n ga n dj j g i l l o g l y ，a na n a l y s i so ft h ea l p h a b e t a p r u n i n ga l g o r i t h m d d e p a r t m e n to fc o m p u t e rs c i e n c er e p o r t ，c a r e g i e - m e l l o n u n i v e r s i t y ，p i t t s b u r g ，1 9 7 3 5 d ek n u t ha n dr nm o o r e ，a na n a l y z eo f a l p h a - b e t ap r u n i n g j a r t i f i c i a li n t e l l i g e n c e ，1 9 7 5 ，6 ： 2 9 3 3 2 6 6 r k o r f i t e r a t i v ed e e p e n i n g ：a no p t i m a la d m i s s i b l et r e es e a r c h j a r t i f i c i a li n t e l l i g e n c e ，19 8 5 ， 2 7 ( 1 、：9 7 1 0 9 【7 】j o n a t h a ns c h a e f f e r , t h eh i s t o r yh e u r i s t i ca n da l p h a - b e t as e a r c he n h a n c e m e n t si np r a c t i c e i e e e t r a n s a c t i o n so np a t t o na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ，n o v e m b e r19 8 9 ，p a m i - i1 ( 1 ) ： 1 2 0 3 - 1 2 1 2 8 b r e a k t h r o u g ho ft h ey e a r ，s ，c i e n c e j ，2 0 0 7 ，v 0 1 318 ，18 4 2 18 4 9 9 t a m a r s l a n d ，c o m p u t e rc h e s sa n ds e a r c h d 】，c o m p u t i n gs c i e n c ed e p a r t m e n t , u n i v e r s i t yo f a l b e r t a 1 0 b e r l i n e rhj a ne x a m i n a t i o no fb r u t ef o r c ei n t e l l i g e n c e c i n t e m a t i o n a lj o i n tc o n f e r e n c e o na r t i f i c i a li n t e l l i g e n c e ，1 9 8 1 ：5 8 1 - 5 8 7 11 e h e i n z , ”h o wd a r k t h o u g h tp l a y sc h e s s ，”j o u r n a lo ft h ei n t e r n a t i o n a lc o m p u t e rc h e s s a s s o c i a t i o n ，v 0 1 2 0 ，n o 3 ，p p 1 6 6 ，1 7 6 ( 1 9 9 7 ) 1 2 c r a c r a f l ，s m ( 1 9 8 4 ) b i t m a pm o v eg e n e r a t i o ni nc h e s s i c c aj o u r n a l ，v 0 1 7 ，n o 3 ，p p 1 9 8 4 ：1 4 6 一1 5 3 13 a n d r e a sj u n g h a r m s ，j s c h a e f f e 5s e a r c hv e s u sk n o w l e d g ei ng a m e - p l a y i n gp r o g r a m r e v i s i t e d t e c h n i c a lr e p o r t ，d e p t o fc o m p u t e rs c i e n c e ，u n i v e r s i t yo fa l b a m a , 19 9 8 1 4 h s u ，s c a n dt s a o ，k m ( 1 9 9 1 ) d e s i g na n di m p l e m e n t a t i o no f a no p e n i n gg a m e k n o w l e d g e b a s es y s t e mf o rc o m p u t e rc he n d g a m ed a t a b a s eb yr e t r o g r a d ea n a l y s i s 1 5 a z o b r i s t an e wh a s h i n gm e t h o dw i t ha p p l i c a t i o nf o rg a m ep l a y i n g t e c h n i c a lr e p o r t 8 8 ，c o m p u t e rs c i e n c ed e p a r t m e n t ，u n i v e r s i t yo fw i s c o n s i n ，m a d i s o n 1 9 7 0 1 6 h a w r e nf a n g ，t s a n s h e n gh s u ，a n ds h u n c h i nh s u ，c o n s t r u c t i o no fc h i n e s ec h e s s 1 7 r e nw u d o n a l df b e a l ，am e m o r ye f f i c i e n tr e t r o g r a d el g o r i t h ma n di t sa p p l i c a t i o nt o c h i n e s ec h e s se n d g a m e s ，m o r eg a m e so f n oc h a n c em s r ip u b l i c a t i o n sv o l u m e4 2 ，2 0 0 2 1 8 h o l l a n djh a d a p t a t i o ni nn a t u r ea n da r t i f i c i a ls y s t e m m a n na r b o r ：t h eu n i v e r s i t yo f m i c h i g a np r e s s 1 9 7 5 i n e s ec h e s s j b u l l e t i no f t h ec o l l e g eo f e n g i n e e r i n g ，n t u ，n o 5 3 ，p p 參考文獻(xiàn) 7 5 - 8 6 1 9 王小春：p c 游戲編程( 人機(jī)博弈) m ，2 0 0 2 年，第版，重慶大學(xué)出版社 2 0 網(wǎng)冠科技： v i s u a lc + + n e t 小游戲開發(fā)時(shí)尚編程百例 m ，2 0 0 4 年，第一版，機(jī)械 工業(yè)出版社 2 1 陳建春： v i s u a lc + + 高級(jí)編程技術(shù)開發(fā)實(shí)例剖析 m ，1 9 9 9 年，第一版，電 子工業(yè)出版社 2 2 涂光平，黃敏，鐘堅(jiān)成等： v i s u a lc + + n e t 基礎(chǔ)教程與上機(jī)指導(dǎo) m ，2 0 0 5 年，第 一版，清華大學(xué)出版社 2 3 伍紅兵：v is u a lc + + 編程深入引導(dǎo) m ，2 0 0 2 年，第一版，中國水利水電出版社 2 4 何斌，馬天予，王運(yùn)堅(jiān)等編著： v i s u a lc + + 數(shù)字圖像處理 m ，2 0 0 2 年( 第二版) ， 人民郵電出版社 2 5 范如國，韓民春：博弈論 m ，武漢大學(xué)出版社，2 0 0 6 1 2 6 李光久：博弈論基礎(chǔ)教程 m ，化學(xué)工業(yè)出版社，2 0 0 5 2 7 徐心和，徐長明，鄧志立：積極開展民間棋類的計(jì)算機(jī)博弈活動(dòng)【g 】，2 0 0 7 中國自動(dòng) 化教育年會(huì)論文集，機(jī)械工業(yè)出版社 2 8 徐心和，王驕：中國象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析 j ，小型微型計(jì)算機(jī)系統(tǒng)，2 0 0 6 年第6 期 2 9 徐心和，王浩，孔凡禹：事件對(duì)策理論及在棋類游戲中的應(yīng)用【g 】，2 0 0 7 年中國智能 自動(dòng)化會(huì)議論文集 3 0 徐陽東，劉弘：遺傳算法在機(jī)器博弈中的創(chuàng)新應(yīng)用 j 】，電腦知識(shí)與技術(shù)，2 0 0 8 年第 1 卷第7 期 3 1 何大華，陳傳波：弈棋程序的設(shè)計(jì)思路【g 】，( 2 0 0 4 年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)計(jì) 算機(jī)科學(xué) 3 2 韓逢慶：基于選手風(fēng)格的中國象棋博弈樹搜索【g 】， 2 0 0 6 中國機(jī)器博弈學(xué)術(shù)研討會(huì) 3 3 王曉鵬，王驕，徐心和等：中國象棋與國際象棋比較分析【g 】，2 0 0 6 中國機(jī)器博弈學(xué) 術(shù)研討會(huì) 3 4 徐心和，鄭新穎： 棋牌游戲與事件對(duì)策 g 】， 2 0 0 6 中國機(jī)器博弈學(xué)術(shù)研