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

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