中國(guó)象棋軟件設(shè)計(jì)與實(shí)現(xiàn)論文.doc

1中國(guó)象棋對(duì)弈程序?qū)I(yè)：計(jì)算機(jī)科學(xué)與技術(shù)小組成員：孫忱、周俊、施聰聰、周理想指導(dǎo)老師：陳宇、蔣德茂（蘇州大學(xué)計(jì)算機(jī)學(xué)院）作品類別：學(xué)術(shù)論文+計(jì)算機(jī)程序【摘要】：人機(jī)博弈是人工智能研究的經(jīng)典課題之一。憑借設(shè)計(jì)優(yōu)良的算法和計(jì)算機(jī)的快速運(yùn)算能力，計(jì)算機(jī)可以在人機(jī)對(duì)弈中表現(xiàn)出相當(dāng)高的“智能”。通常，一款象棋程序的實(shí)現(xiàn)可以被分為下棋引擎（人工智能）和外殼（界面及程序輔助）兩大部分。本文將介紹如何實(shí)現(xiàn)一款中國(guó)象棋對(duì)弈程序?！娟P(guān)鍵詞】：中國(guó)象棋；人工智能；博弈樹；Alpha-Beta搜索；歷史啟發(fā)；界面；多線程；計(jì)時(shí)器；列表框；MFC。Abstract:Man-machineGameisaclassictopicinArtificialIntelligence.Relyingonfine-designedalgorithmsandthefastoperationability,computerscandisplayhighintelligenceinplayingchess.Usually,therealizationofachessprogramcanbedecomposedintotwomajorparts:theChessEngine(ArtificialIntelligence)andtheShell(UserInterface&ProgramAssist).ThispaperwillintroducehowtorealizeaChineseChessprogram.Keywords:ChineseChess；ArtificialIntelligence(AI)；GameTree；Alpha-BetaSearch；HistoryHeuristic；UserInterface；Multithreaded；Timer；ListBox；MFC.一、前言我們的目標(biāo)是實(shí)現(xiàn)一款有著一定下棋水平且交互友好的中國(guó)象棋人機(jī)對(duì)弈程序。該程序功能包括：*人機(jī)對(duì)弈；*盲棋模式；（注：此功能為創(chuàng)新功能）*搜索深度設(shè)定；（電腦棋力選擇）*棋子、棋盤樣式選擇；*悔棋、還原；*著法名稱顯示；*下棋雙方計(jì)時(shí)；整個(gè)程序的實(shí)現(xiàn)可分為兩大部分：一、人工智能部分（計(jì)算機(jī)下棋引擎）該部分實(shí)現(xiàn)了如何讓計(jì)算機(jī)下中國(guó)象棋，其中涉及人機(jī)博弈的基本理論及思想，是該程序的核心部分，同時(shí)也是本項(xiàng)目研究的重點(diǎn)所在。二、界面及程序輔助部分2光有下棋引擎尚不能滿足人機(jī)交互的基本要求，因此我們還需要一個(gè)框架（界面）來(lái)作為引擎的載體，同時(shí)提供一些諸如悔棋，計(jì)時(shí)之類的附屬功能（程序輔助）來(lái)為程序增色添彩。下面分別介紹各部分實(shí)現(xiàn)。由于界面及程序輔助部分涉及內(nèi)容寬泛而又繁瑣，因而本文只介紹其中重點(diǎn)部分以及我們?cè)陂_發(fā)過(guò)程中曾經(jīng)遇到過(guò)困難的地方。二、人工智能部分（計(jì)算機(jī)下棋引擎）1、概述程序的基本框架：從程序的結(jié)構(gòu)上講，大體上可以將引擎部分劃分為四大塊：棋局表示；著法生成；搜索算法；局面評(píng)估。程序的大概的思想是：首先使用一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)描述棋局信息，對(duì)某一特定的棋局信息由著法生成器生成當(dāng)前下棋方所有合法的著法并依次存入著法隊(duì)列。然后通過(guò)搜索算法來(lái)逐一讀取著法并調(diào)用局面評(píng)估函數(shù)對(duì)該著法所產(chǎn)生的后繼局面進(jìn)行評(píng)估打分，從中選出一個(gè)最有可能導(dǎo)致走棋方取勝的著法。在搜索的過(guò)程中還可以采用一些輔助手段來(lái)提高搜索的效率。其過(guò)程如下圖所示：下面將分別介紹各個(gè)部分。32、棋局表示計(jì)算機(jī)下棋的前提是要讓計(jì)算機(jī)讀懂象棋。所謂讀懂，即計(jì)算機(jī)應(yīng)該能夠清楚地了解到棋盤上的局面（棋盤上棋子的分布情況）以及下棋方所走的每一種著法。因而首先我們需要有一套數(shù)據(jù)結(jié)構(gòu)來(lái)表示棋盤上的局面以及著法。對(duì)于棋盤局面的表示我們采用了最傳統(tǒng)的同時(shí)也是最為簡(jiǎn)單的“棋盤數(shù)組”。即用一個(gè)9*10的數(shù)組來(lái)存儲(chǔ)棋盤上的信息，數(shù)組的每個(gè)元素存儲(chǔ)棋盤上相應(yīng)位置是何種棋子。這種表示方法簡(jiǎn)單易行（缺點(diǎn)是效率不是很高）。按此方法棋盤的初始情形如下所示：BYTECChessBoard910=R,0,0,P,0,0,p,0,0,r,H,0,C,0,0,0,0,c,0,h,E,0,0,P,0,0,p,0,0,e,A,0,0,0,0,0,0,0,0,a,K,0,0,P,0,0,p,0,0,k,A,0,0,0,0,0,0,0,0,a,E,0,0,P,0,0,p,0,0,e,H,0,C,0,0,0,0,c,0,h,R,0,0,P,0,0,p,0,0,r；其中“0”表示無(wú)棋子，大寫字母表示紅方棋子，小寫字母表示黑方棋子（所有這些大小寫字母都是用宏定義的整數(shù)）。具體如下：“R”表示紅車；“H”表示紅馬；“E”表示紅相；“A”表示紅仕；“K”表示紅帥；“C”表示紅炮；“P”表示紅兵?！皉”表示黑車；“h”表示黑馬；“e”表示黑象；“a”表示黑士；“k”表示黑將；“c”表示黑炮；“p”表示黑卒。此外這個(gè)數(shù)組也表明了我們對(duì)棋盤進(jìn)行了如右圖所示的編號(hào)，并約定紅方棋子總處于棋盤的下方。對(duì)于著法的表示，我們直接借用棋盤數(shù)組的下標(biāo)來(lái)記錄著法的起點(diǎn)和目標(biāo)點(diǎn)。至于是什么棋子在走，以及是否吃子、吃的是什么子，我們?cè)谥ńY(jié)構(gòu)中并不記錄。這些信息由外部讀取棋盤上起點(diǎn)、終點(diǎn)的數(shù)據(jù)獲得。著法結(jié)構(gòu)定義如下，其中還包含了對(duì)著法的歷史得分的記錄項(xiàng)，以供后面要講到的“歷史啟發(fā)”所用。typedefstruct_cchessmovePOINTptFrom；/起點(diǎn)POINTptTo；/目標(biāo)點(diǎn)intnScore；/該走法的歷史得分CCHESSMOVE；/走法結(jié)構(gòu)有了對(duì)棋盤局面和著法的表示之后，程序才能夠完成以下操作：1、生成所有合法著法；2、執(zhí)行著法、撤銷著法；3、針對(duì)某一局面進(jìn)行評(píng)估。因而，棋局表示好比是整個(gè)程序（計(jì)算機(jī)下棋引擎部分）的地基，之后所有的操作都將建4立在其基礎(chǔ)上。3、著法生成我們的程序需要讓計(jì)算機(jī)在輪到它走子的時(shí)候能夠執(zhí)行一步它認(rèn)為對(duì)它最有利的著法，那前提就是它要有諸多（也可能是唯一）可供選擇的著法，提供所有候選著法的“清單”就是我們的著法生成器所要完成的。之后用搜索函數(shù)來(lái)搜索“清單”，并用局面評(píng)估函數(shù)來(lái)逐一打分，最后就可以選擇出“最佳著法”并執(zhí)行了。在著法生成器中，我們采用的基本思想就是遍歷整個(gè)棋盤（一個(gè)接一個(gè)地查看棋盤上的每個(gè)位置點(diǎn)），當(dāng)發(fā)現(xiàn)有當(dāng)前下棋方的棋子時(shí)先判斷它是何種類型的棋子，然后根據(jù)其棋子類型而相應(yīng)地找出其所有合法著法并存入著法隊(duì)列。這里談到的“合法著法”包括以下幾點(diǎn)：1、各棋子按其行子規(guī)則行子。諸如馬跳“日”字、象走“田”字、士在九宮內(nèi)斜行等等（這里需要特別注意的是卒（兵）的行子規(guī)則會(huì)隨其所在位置的不同而發(fā)生變化過(guò)河后可以左右平移）。2、行子不能越出棋盤的界限。當(dāng)然所有子都不能走到棋盤的外面，同時(shí)某些特定的子還有自己的行棋界限，如將、士不能出九宮，象不能過(guò)河。3、行子的半路上不能有子阻攔（除了炮需要隔一個(gè)子才能打子之外）以及行子的目的點(diǎn)不能有本方棋子（當(dāng)然不能自己吃自己了）。4、將帥不能碰面（本程序中只在生成計(jì)算機(jī)的著法時(shí)認(rèn)為將帥碰面是非法的，而對(duì)用戶所走的導(dǎo)致將帥碰面的著法并不認(rèn)為其非法，而只是產(chǎn)生敗局罷了）。產(chǎn)生了著法后要將其存入著法隊(duì)列以供搜索之用，由于搜索會(huì)搜索多層（即考慮雙方你來(lái)我往好幾步，這樣才有利于對(duì)局面進(jìn)行評(píng)估以盡可能避免“目光短淺”），所以在把著法存入著法隊(duì)列的時(shí)候還要同時(shí)存儲(chǔ)該著法所屬的搜索層數(shù)。因此我們將著法隊(duì)列定義為二維數(shù)組MoveList1280，其中第一個(gè)數(shù)組下標(biāo)為層數(shù)，第二個(gè)數(shù)組下標(biāo)為每一層的全部著法數(shù)。關(guān)于搜索層數(shù)，我將數(shù)組下標(biāo)設(shè)定為12，實(shí)際使用的是1到11（在界面中我又將其限定為110）。搜索層數(shù)的增加會(huì)顯著提高電腦的下棋水平（當(dāng)然計(jì)算機(jī)的棋力在很大程度上也依賴于局面評(píng)估）。在我的迅馳1.5，736M內(nèi)存的筆記本上最多只能搜索5層，再多將導(dǎo)致搜索時(shí)間達(dá)到令人無(wú)法容忍的地步（這里還需要特別說(shuō)明的是，搜索的速度也和著法生成的效率以及局面評(píng)估的復(fù)雜度有關(guān)，因?yàn)槊糠治鲆粋€(gè)結(jié)點(diǎn)都要執(zhí)行這兩種操作）。對(duì)于每一層的著法數(shù)，也就是當(dāng)前下棋方針對(duì)當(dāng)前局面的所有可選的合法著法，據(jù)有關(guān)數(shù)據(jù)統(tǒng)計(jì)在象棋實(shí)戰(zhàn)中一般最多情況下也就五六十種。定義第二個(gè)數(shù)組下標(biāo)為80，應(yīng)當(dāng)可以保證十分的安全。著法生成為搜索部分提供了“原料”，接下來(lái)的任務(wù)就交給搜索和局面評(píng)估了。4、搜索算法搜索算法對(duì)于整個(gè)下棋引擎來(lái)說(shuō)都是至關(guān)重要的。它如同程序的心臟，驅(qū)動(dòng)著整個(gè)程序。搜索算法的好壞直接影響著程序執(zhí)行的效率（從某種角度上，它影響著計(jì)算機(jī)的下棋水平。因?yàn)?，?jì)算機(jī)必須在有限的時(shí)間內(nèi)完成思考，搜索速度快意味著在相同的時(shí)間內(nèi)程序可以“看”得更遠(yuǎn)，“想”