西洋跳棋智能程序設(shè)計(jì)

西洋跳棋智能程序設(shè)計(jì)學(xué)院計(jì)算機(jī)學(xué)院專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級學(xué)號姓名指導(dǎo)教師負(fù)責(zé)教師2016年6月摘要隨著社會發(fā)展，科技進(jìn)步，電腦得以普及。電腦游戲伴隨著網(wǎng)絡(luò)和電腦的普及深深的吸引了很多玩家，特別是快節(jié)奏的生活，傳統(tǒng)的兩個(gè)人一張桌子的下棋方式逐漸被取締，人機(jī)對弈棋牌類電腦游戲被越來越多的人認(rèn)可。西洋跳棋作為一款益智類棋牌游戲，不僅可以休閑娛樂，達(dá)到游戲自身放松的目的，同時(shí)，可以鍛煉玩家的思維能力。計(jì)算機(jī)博弈是非常實(shí)際的計(jì)算機(jī)科學(xué)與技術(shù)研究課題，也是非常富有挑戰(zhàn)性的人工智能領(lǐng)域的研究方向。西洋跳棋是一種平均分支因子較少的棋種，博弈樹算法可以得到很好地應(yīng)用。本游戲是利用Qt開發(fā)工具與C++開發(fā)語言，利用搜索算法設(shè)計(jì)最優(yōu)落子的一款西洋跳棋人機(jī)博弈游戲。Qt是一個(gè)多平臺的C++圖形用戶界面應(yīng)用程序框架，一種完全面向?qū)ο蟮牡某绦蜷_發(fā)軟件，具有很好地封裝機(jī)制、較高的模塊化程度和良好的應(yīng)用性。C++是一種應(yīng)用非常廣泛的面向?qū)ο蟮挠?jì)算機(jī)程序設(shè)計(jì)語言，利用C++語言在游戲中的編程，使得西洋跳棋游戲具有美觀的界面，人機(jī)對弈方面電腦具有較高的智商。本文主要是對西洋跳棋設(shè)計(jì)的詳細(xì)闡述，分別從軟件設(shè)計(jì)背景，需求分析，總體設(shè)計(jì)和詳細(xì)設(shè)計(jì)深入的介紹了軟件的開發(fā)，并通過對軟件的調(diào)試分析詳細(xì)介紹了軟件的使用方法，同時(shí)，本文深入比較了多種搜素按算法在本設(shè)計(jì)中的應(yīng)用。關(guān)鍵詞：西洋跳棋；人工智能；Qt；C++AbstractWiththedevelopmentofsocietyandtheprogressofscienceandtechnology,computerhasbeenpopularized.Computergameswiththepopularityofcomputernetworksanddeeplyattractedalotofplayers,especiallythefastpaceoflife,traditionaltwotablechesshasgraduallybeenbanned,man-machinechesschesscomputergameismoreandmorepeoplerecognized.Asapuzzlegameofchess,checkerscannotonlyentertainment,toachievethegoaloftheirgametorelax,atthesametime,youcanexerciseplayer'sthinkingability.Computergameisaverypracticalcomputerscienceandtechnologyresearch,isveryrichchallengeinthefieldofartificialintelligenceresearchdirection.Checkersisanaveragebranchingfactorlesschess,thegametreealgorithmcanbeappliedwell.ThegameisusingQtdevelopmenttoolsandC++programminglanguage,usingsearchalgorithmsforthedesignofoptimalLaziacheckershuman-computergame.QtisamultiplatformC++graphicaluserinterfaceapplicationprogramframework,afullyobject-orientedprogrammingsoftware,hasagoodencapsulationmechanismandhighdegreeofmodularizationandgoodapplicationofC++isakindofwidelyusedobjectorientedcomputerprogramminglanguage,usingC++languageingameprogramming,makescheckersgamewithbeautifulinterface,man-machinechesselectricbrainhasahigherIQ.Themainpurposeofthispaperistocheckersdesignareelaboratedindetail,respectively,fromthebackgroundofsoftwaredesign,demandanalysis,generaldesignanddetaileddesigndeeplyintroducedsoftwaredevelopment,andthroughthesoftwaredebuggingandanalysisoftheusageofthesoftwareareintroducedindetail.Atthesametime,thispaperwithvarioussearchelementaccordingtothealgorithminthedesignoftheapplication.Keywords:checkers;artificialintelligence;Qt;C++目錄TOC\t"標(biāo)題_謝辭及參考文獻(xiàn),1,標(biāo)題_附錄,1,第2級標(biāo)題,2,第3級標(biāo)題,3,第1級標(biāo)題,1"1前言 11.1研究背景 11.2國內(nèi)外研究狀況 11.3研究內(nèi)容 21.4課題意義 22需求分析及相關(guān)技術(shù)介紹 32.1軟件設(shè)計(jì)總體目標(biāo) 32.2系統(tǒng)基本功能 32.3西洋跳棋游戲規(guī)則說明 42.4相關(guān)技術(shù)介紹 42.4.1Qt軟件簡介 42.4.2C++編程語言介紹 52.5系統(tǒng)技術(shù)需求 53系統(tǒng)分析及設(shè)計(jì) 63.1系統(tǒng)總體設(shè)計(jì) 63.1.1模塊化設(shè)計(jì)流程 63.1.2系統(tǒng)總體構(gòu)成流程 63.2系統(tǒng)算法設(shè)計(jì)概述 73.3系統(tǒng)特點(diǎn)及功能結(jié)構(gòu) 73.3.1系統(tǒng)特點(diǎn) 73.3.2功能結(jié)構(gòu) 74詳細(xì)設(shè)計(jì) 94.1游戲界面模塊詳細(xì)設(shè)計(jì) 94.2棋盤設(shè)計(jì)模塊詳細(xì)設(shè)計(jì) 104.3人機(jī)博弈模塊設(shè)計(jì)詳細(xì)設(shè)計(jì) 124.3.1博弈樹算法設(shè)計(jì) 124.3.2局面評估設(shè)計(jì) 124.3.3走法生成 124.4游戲規(guī)則模塊詳細(xì)設(shè)計(jì) 144.5勝負(fù)判斷模塊詳細(xì)設(shè)計(jì) 155運(yùn)行及調(diào)試 175.1開始界面調(diào)試情況 175.2棋盤初始化調(diào)試情況 175.3走棋調(diào)試 185.4勝負(fù)判斷調(diào)試 196總結(jié) 21參考文獻(xiàn) 22致謝 23前言研究背景西洋跳棋的起源無法追溯，根據(jù)大多數(shù)棋藝史家的考證，現(xiàn)在認(rèn)為西洋跳棋起源于法國的南部地區(qū)。當(dāng)今，例如國際象棋等游戲規(guī)則在西方已經(jīng)統(tǒng)一標(biāo)準(zhǔn)，擁有一套統(tǒng)一化的走棋規(guī)則，但西洋跳棋至根據(jù)地域不同今卻流傳著幾十種不同的游戲規(guī)則，例如波蘭跳棋、英國跳棋、中東跳棋等。西洋跳棋下棋過程特別注重玩家對整體棋局的掌控性。西洋跳棋玩法種類繁多，本次設(shè)計(jì)采用最通用的西洋跳棋規(guī)則。雙方輪流走子，玩家執(zhí)紅旗先行，人機(jī)輪流落子。規(guī)則規(guī)定：未成王的棋子只能沿斜線向?qū)Ψ阶笊匣蛘哂疑锨靶幸桓?該格空出沒有落子)，且未成王的棋子只能前行不可后退。吃子時(shí)，對方的棋子在己方棋子斜對角格子的左上或者右上，且對方棋子左上或者右上格子沒有其他棋子。加冕成王，游戲在雙方底界設(shè)計(jì)了加冕線，當(dāng)己方棋子到達(dá)對方底邊界時(shí)，加冕成王，王棋與未成網(wǎng)的棋子區(qū)別在于王棋可以后退。勝負(fù)判斷為兩種情況，當(dāng)一方棋子數(shù)量為零時(shí)，判斷為對方游戲勝利；當(dāng)雙方棋子都無法移動后，由局面評估給出勝利一方。國內(nèi)外研究狀況當(dāng)今，西洋跳棋在流行5000年的歷史之后已經(jīng)被計(jì)算機(jī)完全攻破。多年來，西洋跳棋一直被眾多數(shù)學(xué)家、電腦學(xué)家和英國跳棋專家研究，取得了非常顯著的成功。早在1989年，喬納森·謝弗（JonathanSchaeffer）開始了西洋跳棋項(xiàng)目的研究，在1994年，謝弗的計(jì)算機(jī)程序已經(jīng)可以擊敗當(dāng)時(shí)人類最頂尖的西洋跳棋大師。在之后的研究中，喬納森·謝弗聯(lián)手艾伯特大學(xué)的學(xué)者共同研究出西洋跳棋程序“奇努克”，被譽(yù)為當(dāng)今世界無法被戰(zhàn)勝的跳棋程序。自1950年，香儂首次提出國際象棋解決方案揭開機(jī)器博弈發(fā)展序幕之后，諸多計(jì)算機(jī)愛好者和科學(xué)家在此領(lǐng)域不斷研究，在九十年代初期，計(jì)算機(jī)連續(xù)戰(zhàn)勝很多棋道大師，特別是1997年“深藍(lán)”戰(zhàn)勝世界棋王，人工智能在計(jì)算機(jī)博弈方面取得輝煌的成就。之后的研究中，相繼攻克中國象棋等眾多棋類。2016年3月谷歌AlphaGo與韓國與韓國棋手李世石進(jìn)行的圍棋比賽中計(jì)算機(jī)以4：1戰(zhàn)勝對手獲得勝利，人工智能在下棋程序又一次重大進(jìn)步。研究內(nèi)容西洋跳棋是一款規(guī)則簡單，易于上手的游戲，由于游戲的特性，可以提高玩家對全局的把握能力，并且可以提高玩家邏輯思維能力。本次設(shè)計(jì)研究內(nèi)容主要包括以下介個(gè)方面：游戲界面設(shè)計(jì)：游戲界面的設(shè)計(jì)風(fēng)格直接影響到玩家對游戲的興趣，所以游戲界面設(shè)計(jì)在游戲設(shè)計(jì)中起到非常重要的作用，游戲界面設(shè)計(jì)主要為游戲開始界面。游戲棋盤設(shè)計(jì)：本游戲棋盤設(shè)計(jì)為標(biāo)準(zhǔn)西洋跳棋10*10的棋盤設(shè)計(jì)，棋盤中100個(gè)格子黑白分明落子明確，玩家可以很容易掌握棋盤。落子設(shè)計(jì)：落子設(shè)計(jì)分為玩家落子和電腦落子。玩家落子只需遵從游戲規(guī)則即可，電腦落子采用博弈樹搜索算法，尋找最優(yōu)落子方案。局面評估設(shè)計(jì)：局面評估采用分類加權(quán)計(jì)算雙方優(yōu)勢，最終判斷局面勝負(fù)情況。課題意義目前，市面上棋牌類游戲種類繁多，例如中國象棋、跳棋等棋類游戲版本眾多，但西洋跳棋游戲卻在棋牌類游戲中特別少見，特別是網(wǎng)絡(luò)上玩家可選擇的西洋跳棋游戲制作簡單，畫面粗糙，加上許多讓玩家不喜的廣告，很難滿足西洋跳棋愛好者的興趣。因此需要一款設(shè)計(jì)畫面精美，走棋風(fēng)格合理的西洋跳棋程序來滿足西洋跳棋愛好者的興趣。本設(shè)計(jì)在過程中注重界面設(shè)計(jì)，Qt軟件獨(dú)特的界面設(shè)計(jì)功能在設(shè)計(jì)中可以為玩家設(shè)計(jì)出精美的界面，精美的開始界面有利于提高玩家的游戲樂趣。在游戲設(shè)計(jì)中，略高的電腦走法，使玩家不會感到枯燥，玩家在下棋過程中提高自身棋藝的同時(shí)，不僅可以起到放松的作用，還可以鍛煉玩家的邏輯思維能力和智力。需求分析及相關(guān)技術(shù)介紹軟件設(shè)計(jì)總體目標(biāo)西洋跳棋是一款益智類人機(jī)對弈棋類游戲。本款軟件主要針對的用戶為西洋跳棋愛好者和初學(xué)者玩家，玩家在使用軟件過程中達(dá)到休閑娛樂，提高棋藝的目的。設(shè)計(jì)目標(biāo)：第一，界面設(shè)計(jì)獨(dú)特新穎，輕松自然，可以吸引玩家，使玩家達(dá)到放松的目的；第二，游戲難度適中，電腦走棋算法合理，適合初級玩家使用，使玩家在使用過程中可以達(dá)到提高棋藝的目的，但游戲難度不會過大，不可以讓玩家使用過程中因游戲難度過高感到枯燥。系統(tǒng)基本功能本軟件使用對象為游戲玩家，以界面新穎，風(fēng)格獨(dú)特，走棋合理的特點(diǎn)為主，軟件應(yīng)包括游戲開始界面，棋盤，棋子，人機(jī)博弈，局面評估，勝負(fù)判斷等內(nèi)容，設(shè)計(jì)分為五個(gè)模塊：開設(shè)界面模塊：用戶進(jìn)入游戲，首先是歡迎界面，既游戲開始界面，玩家點(diǎn)擊開始游戲按鈕，進(jìn)入游戲。棋盤設(shè)計(jì)：玩家進(jìn)入游戲后，生成初始棋盤，棋盤為10*10共一百個(gè)格子，棋盤設(shè)計(jì)格子為黑白兩色分別交錯排布，便與玩家區(qū)分，棋子設(shè)計(jì)要求與棋盤形成對比色彩，便于玩家操作。人機(jī)對弈模塊：本模塊為程序設(shè)計(jì)的核心模塊，玩家落子后，電腦根據(jù)搜索算法找到最優(yōu)落子方法，可與玩家進(jìn)行對弈。下棋規(guī)則模塊：本模塊為西陽跳棋程序的基礎(chǔ)模塊，判斷落子地方和吃子情況。勝負(fù)判斷模塊：本模塊的目的是判斷游戲勝負(fù)。以上為游戲軟件主要功能設(shè)計(jì)，系統(tǒng)功能模塊如圖2.1所示軟件功能模塊圖西洋跳棋游戲規(guī)則說明游戲雙方輪流走棋。棋子為成為王棋前，棋子只能向左上角或者右上角且無人占據(jù)的格子斜走一格。吃子時(shí)，敵方的棋子必須在己方棋子的左上角或者右上角的格子，而且該敵方棋子對應(yīng)的左上角或者右上角必須沒有棋子。當(dāng)棋子到了對方底線，該棋子就可以加冕成王棋，王棋可以向后移動。若一個(gè)棋子可以吃棋，則必須吃子。若一方無法行走或者所有棋子均被吃，則該方算輸。相關(guān)技術(shù)介紹本軟件利用Qt5.2.0軟件編寫，編程語言為C++計(jì)算機(jī)編程語言編寫。Qt軟件簡介Qt是一個(gè)跨平臺的C++應(yīng)用程序和圖形界面開發(fā)框架。于1991年由奇趣科技研發(fā)，2007年之后，Qt跨平臺開發(fā)戰(zhàn)略得以迅速發(fā)展，現(xiàn)在廣泛用于圖形用戶界面程序開發(fā)。Qt的特點(diǎn)：優(yōu)良的跨平臺特性：Qt支持多平臺運(yùn)行，在不同平臺下無需修改源代碼便可以生成特有的圖形界面風(fēng)格。面向?qū)ο螅河捎赒t擁有非常良好的封裝機(jī)制，所以，Qt的模塊化程度較高，不同元件之間協(xié)同工作簡方便。豐富的應(yīng)用程序接口(API):Qt擁有非常多的C++類。除此之外，Qt還擁有大量的開發(fā)文檔，支持XML技術(shù)。自Qt4.6之后Qt中引進(jìn)QtQuick，開發(fā)人員與設(shè)計(jì)人員可以協(xié)同創(chuàng)建動畫模式界面和應(yīng)用程序。Qt擁有簡單漂亮的界面，同時(shí)簡單易學(xué)并且資料豐富，實(shí)用性很強(qiáng)。C++編程語言介紹C++編程語言是一種面向?qū)ο蟮某绦蛟O(shè)計(jì)語言，是由C語言發(fā)展而來。C++繼承了C語言大部分特點(diǎn)，并在C語言的基礎(chǔ)上進(jìn)行了完善，添加了類，C++能夠與C語言相互兼容。C++編程語言的優(yōu)勢：在高級語言中處理運(yùn)行速度最快的面向?qū)ο蟪绦蛟O(shè)計(jì)語言，目前市面上大多數(shù)游戲軟件都是又C++來實(shí)現(xiàn)的。語言靈活，功能強(qiáng)大，特別是類層次結(jié)構(gòu)的設(shè)計(jì)。C++標(biāo)準(zhǔn)定義細(xì)致，具有嚴(yán)謹(jǐn)、精確的特性，語法思路參差分明，語法結(jié)構(gòu)明確。

系統(tǒng)技術(shù)需求本程序采用Qt開發(fā)環(huán)境，編程語言使用C++編程語言的西洋跳棋游戲。開發(fā)環(huán)境：QtCreator5.2.0運(yùn)行環(huán)境：Windows7x64系統(tǒng)分析及設(shè)計(jì)本章內(nèi)容是在第二章的需求分析的基礎(chǔ)上形成的程序設(shè)計(jì)藍(lán)圖，作為后續(xù)編碼設(shè)計(jì)的依據(jù)。本章主要介紹了西洋跳棋程序開發(fā)的總體設(shè)計(jì)。系統(tǒng)總體設(shè)計(jì)模塊化設(shè)計(jì)流程根據(jù)需求分析，游戲設(shè)計(jì)需要六大模塊，每個(gè)模塊功能實(shí)現(xiàn)如下：開設(shè)界面模塊：設(shè)計(jì)開始界面。繪制棋盤與棋子設(shè)計(jì)設(shè)計(jì)模塊：繪制棋盤，設(shè)計(jì)棋子。人機(jī)對弈模塊：設(shè)計(jì)算法，實(shí)現(xiàn)人機(jī)對弈。下棋規(guī)則模塊：根據(jù)規(guī)則判斷落子地方和吃子情況。勝負(fù)判斷模塊：設(shè)計(jì)算法判斷游戲勝負(fù)。系統(tǒng)總體構(gòu)成流程西洋跳棋博弈軟件構(gòu)成如圖3.1所示西洋跳棋博弈軟件構(gòu)成圖乙方為玩家，甲方為電腦。乙方遵循游戲規(guī)則落子，甲方通過對當(dāng)前局面進(jìn)行局面評估，然后進(jìn)行博弈樹搜索算法進(jìn)行搜索，形成當(dāng)前最優(yōu)落子，生成走法并落子，甲、乙雙方落子后，當(dāng)前局面在棋盤顯示，電腦循環(huán)對棋盤當(dāng)前局面掃描，經(jīng)當(dāng)前局面反饋給甲方機(jī)器博弈系統(tǒng)，甲方重新進(jìn)行局面評估，生成走法。系統(tǒng)算法設(shè)計(jì)概述西洋跳棋人機(jī)對弈模塊為系統(tǒng)的核心模塊，算法采用極大極小值算法，算法的本質(zhì)思想是：一方總是尋找對己方最有利的的走法，而另一方總是尋找對對方最不利的走法，其搜索樹如圖3.2所示圖3.2極大—極小搜索算法樹根據(jù)算法樹可知Min節(jié)點(diǎn)總是從其下一層Max中挑選估值最小的節(jié)點(diǎn)進(jìn)行估值，Max節(jié)點(diǎn)剛好相反。在走棋過程中，遍歷整顆搜索樹，尋找對己方最有利的走法走子。系統(tǒng)特點(diǎn)及功能結(jié)構(gòu)系統(tǒng)特點(diǎn)具有和諧的界面。界面設(shè)計(jì)美觀，簡潔。具有易操作性。本系統(tǒng)避免過多按鈕在游戲中給玩家?guī)淼牟槐?，設(shè)計(jì)簡單，已于操作。適用于廣大西洋跳棋愛好者，面向性廣闊。本系統(tǒng)是本地游戲，安全可靠功能結(jié)構(gòu)通過上文需求分析和總體設(shè)計(jì)，本系統(tǒng)以5個(gè)模塊為目標(biāo)設(shè)計(jì)。其中，下棋規(guī)則模塊為基礎(chǔ)，為玩家和電腦落子提供基礎(chǔ)規(guī)則，人機(jī)對弈模塊為系統(tǒng)核心，本次設(shè)計(jì)采用極大極小人機(jī)博弈搜索算法設(shè)計(jì)了合理的電腦落子算法，繪制棋盤模塊和勝負(fù)判斷模塊為本次設(shè)計(jì)的前提，為游戲的可行性提供保障，最后是游戲界面設(shè)計(jì)，為整體游戲進(jìn)行美化。其具體模塊及主要功能結(jié)構(gòu)圖如圖3.2所示西洋跳棋整體設(shè)計(jì)及主要功能結(jié)構(gòu)圖詳細(xì)設(shè)計(jì)游戲界面模塊詳細(xì)設(shè)計(jì)為了使游戲界面美觀大方，從網(wǎng)絡(luò)上選取圖片，并用美圖秀秀軟件對所選圖片進(jìn)行美圖修改，利用Qt庫自帶的paintEvent(QPaintEvent

*e)函數(shù)設(shè)計(jì)了游戲開始界面，開始界面采用綠色圖片作為背景圖片，一方面可以緩解玩家視覺疲勞，另一方面，背景顏色與開始游戲按鈕色彩區(qū)分明確，使整體設(shè)計(jì)達(dá)到簡單、美觀的效果。游戲界面模塊流程圖如圖4.1所示游戲界面模塊流程圖程序運(yùn)行首先進(jìn)入游戲開始界面，點(diǎn)擊開始游戲按鈕，將進(jìn)入游戲。界面設(shè)計(jì)尺寸長為10cm，寬為8cm，并在界面中添加“開始游戲”按鈕，該按鈕有Qt編程工具中的界面布局工具完成，關(guān)鍵代碼如圖4.2所示界面設(shè)計(jì)模塊開始游戲按鈕添加關(guān)鍵程序通過界面背景設(shè)計(jì)和按鈕添加，開始界面模塊設(shè)計(jì)完成，開始界面模塊設(shè)計(jì)效果圖如圖4.3所示界面設(shè)計(jì)效果圖棋盤設(shè)計(jì)模塊詳細(xì)設(shè)計(jì)該模塊的主要功能是繪制棋盤和設(shè)計(jì)棋子，棋盤與棋子分為兩種狀態(tài)，一種是初始化狀態(tài)，當(dāng)點(diǎn)擊開始游戲按鈕后，進(jìn)入游戲，此時(shí)，棋盤顯示為初始化狀態(tài)。初始化狀態(tài)時(shí)，甲、乙雙方各持有15枚棋子處于雙方邊界。另一種狀態(tài)是走子或者吃子時(shí)，棋盤中棋子位置發(fā)生改變，甲、乙雙方輪流走子，每次走子之后都將跟新一遍棋盤。棋盤繪制與棋子設(shè)計(jì)模塊流程圖如圖4.4所示棋盤繪制與棋子設(shè)計(jì)模塊棋盤設(shè)計(jì)包括棋盤繪制和棋子設(shè)計(jì)在高性能的博弈設(shè)計(jì)中，比特棋盤應(yīng)用較為廣泛，西洋跳棋智能程序設(shè)計(jì)也采用比特棋盤設(shè)計(jì)而成。棋盤設(shè)計(jì)了10*10共100個(gè)格子，其中50個(gè)格子用來落子，棋盤設(shè)計(jì)用4個(gè)64位無符號整型設(shè)計(jì)而成，如表4.2所示棋子位置與對應(yīng)比特關(guān)系表494847464544434241403938373635343332313029282726252423222120191817161514131211109876543210由<黑棋，黑王棋，白棋，白王棋>四元素組生成棋盤，棋盤初始狀態(tài)為<0X0003FFFFC00000,0,0X000000000FFFFF,0>, 棋盤設(shè)計(jì)效果圖如圖4.2所示棋盤設(shè)計(jì)效果圖人機(jī)博弈模塊設(shè)計(jì)詳細(xì)設(shè)計(jì)博弈樹算法設(shè)計(jì)人機(jī)博弈模塊為本次設(shè)計(jì)核心模塊，而博弈樹算法為本次設(shè)計(jì)核心算法。該模塊設(shè)計(jì)主要目的是完成人機(jī)對弈過程。該過程設(shè)計(jì)核心算法為極大-極小搜索算法，算法的核心思想是，一方總是尋找對己方最有利的走法，另一方總是尋找對對方最不利的走法。在本次設(shè)計(jì)中，設(shè)計(jì)玩家為藍(lán)色方，電腦為紅色方，紅色方為極大方，博弈樹搜算算法設(shè)計(jì)的核心是紅方通過搜索算法和局面評估函數(shù)找到對自己最有利的走法。計(jì)算機(jī)走棋由函數(shù)computer_go()設(shè)計(jì)完成。局面評估設(shè)計(jì)西洋跳棋是零和游戲，局面評估影響因素眾多，本次設(shè)計(jì)主要對以下幾個(gè)方面進(jìn)行評估，分別為棋子和王棋的數(shù)量，處于安全位置的棋子和王棋的數(shù)量（安全位置是指處于底邊或者邊界無法被對方吃子的位置），可以移動的棋子和王棋數(shù)量，還有防御棋子數(shù)量和進(jìn)攻棋子數(shù)量。估值函數(shù)設(shè)計(jì)思路為：估值方法=電腦棋子數(shù)-選手棋子數(shù)-0.5*威脅棋子數(shù)(可能會被吃掉的棋子)估值函數(shù)最重要的任務(wù)是找到威脅棋子，在程序中由CalValue（）函數(shù)設(shè)計(jì)完成。在設(shè)計(jì)中，函數(shù)InThreat（）判斷該棋子是否有可能被對方棋子吃掉，判斷標(biāo)準(zhǔn)是對該棋子左上、右上、左下、右下分別判斷。函數(shù)InBoard（）則判斷棋子當(dāng)前位置是否處于邊界。走法生成普通棋子走法生成普通棋子走棋規(guī)則為棋子可沿對角線對方方向棋子周邊移動一個(gè)，移動方向的格子為空。遇到吃子時(shí)，被吃的棋子周圍有空格才可以吃子，其設(shè)計(jì)流程如下，普通棋子走棋流程圖如圖4.6所示若棋子列表不為空，則從棋子列表中取出一個(gè)棋子；對該棋子相鄰四個(gè)方向進(jìn)行判斷，若存在對方棋子且對方棋子后方格子為空，則將該走法加入走法棧中，否則到第③步；若走法棧不為空，則從走法棧中取出一個(gè)走法；如果從棋子位置可以繼續(xù)吃子，則按照第②步繼續(xù)走子；否則若當(dāng)前吃子數(shù)量大于最大吃子數(shù)量，則清空吃子走法列表；若當(dāng)前吃子數(shù)量等于最大吃子數(shù)量，則將該走法加入走法列表；否則到第③步；若該走法最后一步落在加冕線上，則棋子加冕成王，否則到第①步；否則吃子走法終結(jié)普通棋子走法生成流程圖王棋走法生成王棋是由普通棋子到達(dá)加冕線轉(zhuǎn)換而來，因此王棋走法與普通棋子走法有部分相同，王棋走發(fā)生成流程圖如圖4.7所示，王棋走法流程如下，若棋子列表不為空，則從棋子列表中取出一個(gè)棋子；對該棋子相鄰四個(gè)方向進(jìn)行判斷，若從在對方棋子且對方棋子為空，則將該走法加入走法棧中，將后面所有空格子走法加入走法棧中，否則到第④步；若走法棧不為空，則從走法棧中取出一個(gè)走法；如果從棋子位置可以繼續(xù)吃子，則按照第②步繼續(xù)走子；否則若當(dāng)前吃子數(shù)量大于最大吃子數(shù)量，則清空吃子走法列表；否則若當(dāng)前吃子數(shù)量等于最大吃子數(shù)量，則將該走法加入走法列表；否則到第④步；否則到第①步；否則吃子走法終結(jié)王棋走法生成流程圖游戲規(guī)則模塊詳細(xì)設(shè)計(jì)本模塊主要功能是實(shí)現(xiàn)游戲按照規(guī)則落子，西洋跳棋游戲規(guī)則為，游戲雙方輪流走棋。棋子為成為王棋前，棋子只能向左上角或者右上角且無人占據(jù)的格子斜走一格。吃子時(shí)，敵方的棋子必須在己方棋子的左上角或者右上角的格子，而且該敵方棋子對應(yīng)的左上角或者右上角必須沒有棋子。當(dāng)棋子到了對方底線，該棋子就可以加冕成王棋，王棋可以向后移動。若一個(gè)棋子可以吃棋，則必須吃子。若一方無法行走或者所有棋子均被吃，則該方算輸。游戲規(guī)則在程序中有函數(shù)CanMove（）設(shè)計(jì)完成，普通走子規(guī)則由函數(shù)Computer_Can_Move（）生成，普通棋子吃子規(guī)則由函數(shù)Computer_Can_Eat（）設(shè)計(jì)完成。代碼if(_piece->GetStatus()!=piece::king)returnfalse;完成了普通棋子不能后退，王棋可以后退的游戲規(guī)則。游戲規(guī)則模塊流程圖如圖4.8所示游戲規(guī)則模塊流程勝負(fù)判斷模塊詳細(xì)設(shè)計(jì)本模塊設(shè)計(jì)主要是在游戲結(jié)束后判斷玩家和電腦的勝負(fù)情況。勝負(fù)判斷有兩種情況，一種是一方無法走棋，則該方判定為輸，另一種是一方在棋盤中棋子數(shù)目為零。勝負(fù)判斷流程圖如下圖4.8所示勝負(fù)判斷模塊流程圖雙方輪流落子之后，每次落子都會更新棋盤，根據(jù)流程圖設(shè)計(jì)，首先由系統(tǒng)判定游戲是否結(jié)束，在程序設(shè)計(jì)中，游戲是否結(jié)束設(shè)計(jì)函數(shù)GameOver()判定，判定標(biāo)準(zhǔn)為一方棋子數(shù)目為零或者無法走子，判定游戲結(jié)束之后，判定玩家和電腦的贏家。程序中函數(shù)IsHostWin()判定電腦是否取得勝利，玩家勝負(fù)判定由函IsAwayWin()設(shè)計(jì)，評定流程與計(jì)算機(jī)是否勝利流程相同，判定條件為客隊(duì)棋子是否可以移動，計(jì)算機(jī)判定勝利過程流程圖如圖4.9所示 計(jì)算機(jī)勝負(fù)判定流程圖運(yùn)行及調(diào)試開始界面調(diào)試情況程序運(yùn)行，進(jìn)入游戲開始界面，如圖5.1所示游戲開始界面運(yùn)行情況說明：程序運(yùn)行，進(jìn)入游戲開始界面，界面畫質(zhì)清楚，點(diǎn)擊開始游戲按鈕，進(jìn)入游戲良好。棋盤初始化調(diào)試情況游戲開始，進(jìn)入游戲，此時(shí)棋盤為初始化狀態(tài)，如圖5.2所示棋盤初始化界面運(yùn)行情況說明：棋盤初始化狀態(tài)良好，按照詳細(xì)設(shè)計(jì)，棋盤為10*10共100個(gè)棋格，棋盤底色為黑白兩色，雙方各15個(gè)棋子排布在雙方底界。棋子與棋盤顏色分明。走棋調(diào)試玩家執(zhí)藍(lán)旗現(xiàn)行，電腦后手，走子按照規(guī)則沿斜對角線方向現(xiàn)行，每次移動一個(gè)棋子，可吃子，運(yùn)行結(jié)果如圖5.3，5.4所示普通棋子走棋圖王棋走子運(yùn)行圖運(yùn)行情況說明：普通棋子走棋良好，遇到可吃棋子自動吃子，普通棋子到對方底線變成王棋，王棋走子狀況良好，測試表如表5.1所示表5.1走棋測試表步驟測試描述預(yù)期結(jié)果測試結(jié)果1玩家先手走子，電腦后手輪流走棋輪流按照規(guī)則走子雙方輪流走自，可按規(guī)則走子2遇到可吃子必須吃子雙方均在可吃子時(shí)吃子雙方可按規(guī)則吃子3棋子到對方底線加冕成王棋普通棋子變成王棋普通棋子變成王棋4王棋吃子王棋按照規(guī)則吃子王棋按規(guī)則吃子勝負(fù)判斷調(diào)試當(dāng)一方棋子為零或一方無棋可走時(shí)，系統(tǒng)判斷勝負(fù)并作出評斷。一方棋子數(shù)目為零時(shí)系統(tǒng)做出評判如圖所5.5所示一方棋子數(shù)目為零系統(tǒng)做出勝負(fù)評判當(dāng)一方無法走棋時(shí)，電腦做出勝負(fù)判斷如圖5.6所示一方無法走棋時(shí)系統(tǒng)做出勝負(fù)評判圖運(yùn)行結(jié)果說明：當(dāng)一方棋子為零或者無棋可走時(shí)，系統(tǒng)做出勝負(fù)評判并作出提示，運(yùn)行狀況穩(wěn)定?？偨Y(jié)本章主要內(nèi)容是對西洋跳棋智能程序設(shè)計(jì)的總結(jié)。本次設(shè)計(jì)應(yīng)用C++編程語言，在Qt開發(fā)平臺設(shè)計(jì)編寫，完成了游戲開始界面設(shè)計(jì)、棋盤繪制、棋子走法生成、勝負(fù)判斷等項(xiàng)目，設(shè)計(jì)完成的西洋跳棋智能程序界面精美，走棋合理，操作簡單，符合本次設(shè)計(jì)要求。項(xiàng)目優(yōu)勢：優(yōu)良的游戲界面。與網(wǎng)絡(luò)上流傳的西洋跳棋程序比較，本次設(shè)計(jì)擁有精美的界面設(shè)計(jì)，開始界面簡單易用，避免了玩家錯誤點(diǎn)擊導(dǎo)致無法運(yùn)行的難題，同時(shí)棋盤棋子設(shè)計(jì)風(fēng)格獨(dú)特黑白底色的棋盤設(shè)計(jì)，玩家可以清楚的思考下一步走棋，紅色與藍(lán)色棋子色彩分明，玩家在走棋過程中能夠清楚看清自己的棋子位置，便于掌控全局。棋盤與棋子形成強(qiáng)烈的色彩感，可吸引玩家。合理的走棋算法。本次設(shè)計(jì)采用經(jīng)典的極大—極小搜算算法設(shè)計(jì)，在設(shè)計(jì)過程中，難度適中。設(shè)計(jì)中，較高的電腦棋藝水平可以提高玩家的棋藝水平，游戲設(shè)置水平適中，玩家在娛樂中不會感到枯燥。項(xiàng)目不足：游戲設(shè)計(jì)中，注重走棋的設(shè)計(jì)，對娛樂性設(shè)計(jì)不足，缺少一些音樂文等娛樂項(xiàng)目。無法人人對戰(zhàn)，按照設(shè)計(jì)要求，本次設(shè)計(jì)是人機(jī)對弈，在設(shè)計(jì)過程中，沒有設(shè)計(jì)人人對弈模式，整體游戲有所欠缺。本次畢業(yè)設(shè)計(jì)過程中，出現(xiàn)了很多問題，是對平時(shí)學(xué)習(xí)能力欠缺最直觀的反映，在設(shè)計(jì)中，通過多方面的學(xué)習(xí)，完善了之前學(xué)習(xí)的不足，同時(shí)，設(shè)計(jì)中要求的Qt軟件在此之前沒有使用過，通過本次設(shè)計(jì)，學(xué)會了使用新的工具。在設(shè)計(jì)中，不僅學(xué)到了許多技術(shù)，同時(shí)不斷克服自身不夠嚴(yán)謹(jǐn)?shù)膽B(tài)度，收益良多。參考文獻(xiàn)譚浩強(qiáng).Java語言程序設(shè)計(jì)(第三版)[M].北京:清華大學(xué)出版社,2008焦尚斌，劉丁.博弈樹置換表啟發(fā)式算法研究[J].計(jì)算機(jī)工程應(yīng)用，2010（06）王嬌，徐興和.計(jì)算機(jī)博弈：人工智能的前沿領(lǐng)域—全國大學(xué)生計(jì)算機(jī)博弈大賽[J].計(jì)算機(jī)教育.2012（07）張利群.五道棋計(jì)算機(jī)博弈程序設(shè)計(jì)[J].計(jì)算機(jī)工程.2010（10）李天明.并行計(jì)算機(jī)博弈系統(tǒng)設(shè)計(jì)與改進(jìn)[J].電子制作.2014（21）張穎，李祖樞.棋類計(jì)算機(jī)博弈系統(tǒng)的主要研究方法及在6子棋上的應(yīng)用[J].重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版）.2008（09）MustaphaLakrib,TewfikSari.

Timeaveragingforordinarydifferentialequationsandretardedfunctionaldifferentialequations[J].

ElectronicJournalofDifferentialEquations,2010,2010(40,).MerrickJ.DeWitt,BradleyS.Prall,RobertJ.Levis.

Orientationalaveragingintheintensefieldtunnelionizationofmolecules[J].

TheJournalofChe