vc中國象棋軟件.doc

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