畢業(yè)答辯-基于QT的中國象棋游戲界面設(shè)計(jì)與實(shí)現(xiàn).ppt

中國象棋游戲的設(shè)計(jì)與實(shí)現(xiàn),研究背景,中國象棋發(fā)展至今已有數(shù)千年的歷史了，它是中華民族智慧的結(jié)晶。在我國，中國象棋的普及程度是其它棋類無法比擬的，大至國際、國內(nèi)比賽，小至社區(qū)街道。如今，僅中國就有2億人會(huì)下中國象棋，且中國象棋的發(fā)展趨勢(shì)日益國際化。本文首先研究了中國象棋在計(jì)算機(jī)中的表示問題，討論如何產(chǎn)生著法等一系列相關(guān)內(nèi)容，其次研究了博弈樹的搜索技術(shù)及在此基礎(chǔ)上發(fā)展起來的相關(guān)剪枝算法。系統(tǒng)使用MFC文檔視圖體系結(jié)構(gòu)和QT開發(fā)工具，實(shí)現(xiàn)了一個(gè)具有一定棋力的中國象棋人機(jī)對(duì)弈程序。此博弈程序?qū)崿F(xiàn)了人機(jī)博弈，悔棋，電腦難度設(shè)置，著法名稱生成等功能。,目錄,1緒論11.1中國象棋游戲設(shè)計(jì)背景和研究意義41.2國內(nèi)外象棋軟件發(fā)展概況41.3中國象棋游戲設(shè)計(jì)研究方法41.4本文的主要工作42棋局表示和著法生成62.1棋盤和棋子的表示62.2著法生成93走棋和博弈程序的實(shí)現(xiàn)103.1博弈程序的實(shí)現(xiàn)103.1.1搜索算法103.1.2著法排序143.1.3局面評(píng)估183.2悔棋和還原功能的實(shí)現(xiàn)213.3著法名稱顯示功能的實(shí)現(xiàn)253.4勝敗判定344系統(tǒng)實(shí)現(xiàn)37,中國象棋研究背景,國內(nèi)外象棋軟件發(fā)展概況最早的象棋軟件是一副可以外出攜帶的電子棋盤，后來升級(jí)到電視游戲機(jī)。開始出現(xiàn)的一些容量很小的象棋軟件如：DOS界面將族、WIN31程序的中國象棋等等，與其說人類下不過電腦，倒不如說是沒有耐性等待電腦程序慢吞吞的搜索算法，有時(shí)甚至懷疑軟件是否在搜索中死掉了。后來，網(wǎng)絡(luò)上先后出現(xiàn)了真正的WINDOWS窗口界面的象棋專業(yè)高級(jí)軟件棋隱、象棋世家、象棋參謀、象棋奇兵等?？偠灾黝愊笃遘浖扔凶陨淼膬?yōu)點(diǎn)，也存在共通性的缺陷，如：中局審勢(shì)不夠智能化，走不出棄子取勢(shì)的人性化佳構(gòu)，殘局時(shí)智力明顯低于人腦，難以走出殘局例勝的必然著法等。放眼未來，象棋軟件已經(jīng)走完了一波持續(xù)上漲的行情，有可能出現(xiàn)逐步降溫的滑坡趨勢(shì)。,主要功能,該象棋人機(jī)博弈系統(tǒng)實(shí)現(xiàn)的功能主要包括：1、選手選擇（人或電腦）；2、人機(jī)對(duì)弈（人與電腦競(jìng)技）；3、悔棋、還原；4、著法名稱顯示（象棋走棋規(guī)范名稱）,主要工作,1.1本程序的主要工作第一部分主要介紹了中國象棋游戲開發(fā)的背景及意義、國內(nèi)外象棋軟件的發(fā)展概況和象棋游戲的設(shè)計(jì)研究方法；第二部分介紹了棋局表示方法和著法生成；第三部分介紹了走棋和博弈程序的實(shí)現(xiàn)；第四部分介紹了系統(tǒng)的實(shí)現(xiàn)。,算法設(shè)計(jì),采用shortboard256表征棋盤,非棋盤位置0.棋盤上無棋子的位置也為0.采用256長度的數(shù)組,可以方便的像使用二位數(shù)組那樣使用一維數(shù)組,如想要表征第三行第四列,只需使用board0 x34即可.,算法設(shè)計(jì),1.1悔棋和還原功能的實(shí)現(xiàn)悔棋和還原是棋類軟件中較為基本的功能。要實(shí)現(xiàn)悔棋和還原功能，首先要明確哪些信息應(yīng)當(dāng)被保存以供悔棋和還原所使用。在程序中保存了如下信息：棋局表示中所定義的棋盤數(shù)組；各棋子的貼圖位置；這里需要特別說明的是通常象棋程序處于程序效率的考慮并不保存所有棋子的信息，而只是保存之前一步的走棋信息。此后當(dāng)悔棋的時(shí)候，需要撤銷著法；還原的時(shí)候，需要執(zhí)行著法。然而，在編寫自己的程序時(shí)一來考慮到程序的可讀性和不易出錯(cuò)性，二來考慮到對(duì)當(dāng)今的計(jì)算機(jī)的配置來說這點(diǎn)開銷基本上不會(huì)對(duì)程序的效率產(chǎn)生什么影響。因此保存了全部棋子的信息。,算法設(shè)計(jì),在悔棋中主要完成了以下任務(wù)：1、下棋回合數(shù)減一；2、將當(dāng)前局面信息保存至走法隊(duì)列，以供還原所用；3、從走法隊(duì)列中取出上一回合的棋局信息，恢復(fù)到當(dāng)前局面，然后將其從隊(duì)列中剔除掉；4、將顯示著法名稱的列表框中的本回合的著法名稱保存到一個(gè)著法名稱隊(duì)列，以供還原所用。然后從列表框中刪除它。,算法設(shè)計(jì),(三)將軍檢測(cè)將軍檢測(cè)功能的相關(guān)函數(shù)在check文件夾中.checkmate.cpp調(diào)用check文件夾中的其他函數(shù),檢測(cè)當(dāng)前方(檢查side)/當(dāng)前局面(檢查地方的攻擊性棋子)是否本方被將軍.若是返回true,否則返回false.可以造成將軍的棋子有對(duì)方的車/對(duì)方的馬/對(duì)方的兵/對(duì)方的炮,另外,有不能對(duì)將的規(guī)定.因而對(duì)general/chariot/cannon/horse/soldier這五類棋子各寫了一個(gè)檢測(cè)函數(shù),它們都被checkmate.cpp中的boolcheckmate()調(diào)用.,算法設(shè)計(jì),AI部分采用bottom-up的方法設(shè)計(jì),包括局面表示/走法生成/局面評(píng)估/將軍檢測(cè)/搜索算法.AI部分代碼在kernel文件夾中.kernel文件夾中代碼的組織與AI的結(jié)構(gòu)同構(gòu).表征局面的數(shù)據(jù)結(jié)構(gòu)以及其他一些全局變量在global.h中聲明,在define_global.cpp中定義.move文件夾中為走法生成的函數(shù).check文件夾中為將軍檢測(cè)函數(shù).eval文件夾中為局面評(píng)估函數(shù).search文件夾中為搜索函數(shù).每個(gè)文件夾中都有test.cpp及makefile,為相應(yīng)函數(shù)的測(cè)試代碼.用戶可到相應(yīng)文件夾中運(yùn)行make,然后執(zhí)行可執(zhí)行文件查看測(cè)試結(jié)果(makefile在linux環(huán)境下寫成),算法設(shè)計(jì),局面評(píng)估。為某一特定局面進(jìn)行評(píng)分。當(dāng)實(shí)現(xiàn)了引擎部分的各要素時(shí)，可先建立一個(gè)Win32控制臺(tái)項(xiàng)目，之后只要再添加一個(gè).cpp文件負(fù)責(zé)接受用戶的輸入、調(diào)用搜索函數(shù)、顯示搜索結(jié)果，便可簡單的測(cè)試引擎了（采用輸入著法的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)的方式來傳送用戶走棋的信息。同樣，程序顯示計(jì)算機(jī)走棋的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)來做出回應(yīng)）。對(duì)局時(shí)，由執(zhí)紅棋的一方先走，雙方輪流各走一著，直至分出勝、負(fù)、和，對(duì)局即終了。輪到走棋的一方，將某個(gè)棋子從一個(gè)交叉點(diǎn)走到另一個(gè)交叉點(diǎn)，或者吃掉對(duì)方的棋子而占領(lǐng)其交叉點(diǎn)，都算走一著。雙方各走一著，稱為一個(gè)回合。如果有一方的主帥被對(duì)方吃了，就算那一方輸。各種棋子的走法：帥（將）：帥和將是棋中的首腦，是雙方竭力爭奪的目標(biāo)。它只能在“九宮”之內(nèi)活動(dòng)，可上可下，可左可右，每次走動(dòng)只能按豎線或橫線走動(dòng)一格。帥與將不能在同一直線上直接對(duì)面，否則走方判負(fù)。仕（士）：仕（士）是帥（將）的貼身保鏢，它也只能在九宮內(nèi)走動(dòng)。它的行棋路徑只能是九宮內(nèi)的斜線。相（象）：相（象）的主要作用是防守，保護(hù)自己的帥（將）。它的走法是每次循對(duì)角線走兩格，俗稱“象走田”。相（象）的活動(dòng)范圍限于“河界”以內(nèi)的本方陣地，不能過河，且如果它走的“田”字中央有一個(gè)棋子，就不能走，俗稱“塞象眼”。車：車在象棋中威力最大，無論橫線、豎線均可行走，只要無子阻攔，步數(shù)不受限制。因此，一車可以控制十七個(gè)點(diǎn)，故有“一車十子寒”之稱。炮：炮在不吃子的時(shí)候，走動(dòng)與車完全相同。馬：馬走動(dòng)的方法是一直一斜，即先橫著或直著走一格，然后再斜著走一個(gè)對(duì)角線，俗稱“馬走日”。馬一次可走的選擇點(diǎn)可以達(dá)到四周的八個(gè)點(diǎn)，故有“八面威風(fēng)”之說。如果在要去的方向有別的棋子擋住，馬就無法走過去，俗稱“蹩馬腿”。兵（卒）：兵（卒）在未過河前，只能向前一步步走，過河以后，除不能后退外，允許左右移動(dòng)，但也只能一次一步。在懂的以上規(guī)則之后并可進(jìn)行游戲，執(zhí)行該軟件后，并可進(jìn)入游戲界面,總結(jié),2014年2月，我開始了我的畢業(yè)論文工作，時(shí)至今日，論文基本完成。從最初的茫然，到慢慢的進(jìn)入狀態(tài)，再到對(duì)思路逐漸的清晰，整個(gè)寫作過程難以用語言來表達(dá)。歷經(jīng)了幾個(gè)月的奮戰(zhàn)，緊張而又充實(shí)的畢業(yè)設(shè)計(jì)終于落下了帷幕?；叵脒@段日子的經(jīng)歷和感受，我感慨萬千，在這次畢業(yè)設(shè)計(jì)的過程中，我擁有了無數(shù)難忘的回憶和收獲。腳踏實(shí)地，認(rèn)真嚴(yán)謹(jǐn)，實(shí)事求是的學(xué)習(xí)態(tài)度，不怕困難、堅(jiān)持不懈、吃苦耐勞的精神是我在這次設(shè)計(jì)中最大的收益。我想這是一次意志的磨練，是對(duì)我實(shí)際能力的一次提升，也會(huì)對(duì)我未來的學(xué)習(xí)和工作有很大的幫助。在這次畢業(yè)設(shè)計(jì)中也使我們的同學(xué)關(guān)系更進(jìn)一步了，同學(xué)之間互相幫助，有什么不懂的大家在一起商量，聽聽不同的看法對(duì)我們更好的理解知識(shí)，所以在這里非常感謝幫助我的同學(xué)。在此更要感謝我的導(dǎo)師和專業(yè)老師，是你們的細(xì)心指導(dǎo)和關(guān)懷，使我能夠順利的完成畢業(yè)論文。在我的學(xué)業(yè)和論文的研究工作中無不傾注著老師們辛勤的汗水和心血。老師的嚴(yán)謹(jǐn)治學(xué)態(tài)度、淵博的知識(shí)、無私的奉獻(xiàn)精神使我深受啟迪。從尊敬的導(dǎo)師身上，我不僅學(xué)到了扎實(shí)、寬廣的專業(yè)知識(shí)，也學(xué)到了做人的道理。在此我要向我的導(dǎo)師致以最衷心的感謝和深深的敬意。,不足之處,本程序?qū)τ?jì)算機(jī)博弈技術(shù)進(jìn)行了研究，在深入研究了機(jī)器下中國象棋方法理論基礎(chǔ)上，實(shí)現(xiàn)了一個(gè)具有一定棋力的人機(jī)對(duì)弈中國象棋程序。然而，由于時(shí)間關(guān)系，程序也存在著幾點(diǎn)不足：第一：沒對(duì)計(jì)算機(jī)下棋引擎部分作更深一步的挖掘和研究。對(duì)于諸如位棋盤（BitBoard）、迭代加深（IterativeDeepening）、機(jī)器學(xué)習(xí)（MachineLearning）等當(dāng)今棋類對(duì)弈程序中所采用的先進(jìn)技術(shù)和思想，在程序中并未涉及。這在一定程度上影響了程序中下棋引擎的工作效率。第二：由于對(duì)人工智能算法的不熟悉，在Alpha-Beta搜索算法上花了大量的時(shí)間和精力來了解，導(dǎo)致程序進(jìn)度的緩慢。盡管，這些問題最終都得以解決，但卻影響了程序開發(fā)的進(jìn)程。第三、程序仍在局面檢測(cè)和貼圖刷新上存在著隨機(jī)性的出錯(cuò)可能（出錯(cuò)幾率很?。?。,參考文獻(xiàn),主要參考文獻(xiàn)（資料）1錢壽宇,葛敏芳.中國象棋對(duì)弈的計(jì)算機(jī)輔助分析J.微電子學(xué)與計(jì)算機(jī).1987(05)2岳金朋,馮速.博弈樹搜索算法在中國象棋中的應(yīng)用J.計(jì)算機(jī)系統(tǒng)應(yīng)用.2009(09)3徐心和,王驕.中國象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析J.小型微型計(jì)算機(jī)系統(tǒng).2006(06)4高強(qiáng),郭琛.哈希技術(shù)在中國象棋機(jī)器博弈系統(tǒng)中的應(yīng)用研究J.科學(xué)技術(shù)與工程.2008(17)5謝國.中國象棋機(jī)器博弈數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與搜索算法研究D.西安理工大學(xué)20086董紅安.計(jì)算機(jī)五子棋博奕系統(tǒng)的研究與實(shí)現(xiàn)D.山東師范大學(xué)20057萬翼.計(jì)算機(jī)國際象棋博弈系統(tǒng)的研究與實(shí)現(xiàn)D.西南交通大學(xué)2006,參考文獻(xiàn),8。YenWuR,BealDF.Fast,memory-efficientretrogradealgorithms.ICGAJournal.20019.S.J.,