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

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