五子棋畢業(yè)論文-1

五子棋畢業(yè)論文abstractAsapuzzlegame，gobangcandevelopthethinkingabilityandintelligenceofplayers，whichisinterestingandabsorbing。Theversionofthissoftware，includestwokindsofpatterns，standalonemodeandnetworkmode。Theformerusesagame-treesearchalgorithm，whichcanonlypredictafollow-upmoveaftercalculation。Moreover,thenetworkmodeneedstobebroughtonline,inotherwords,firstneedaplayerinacomputerstartgameastheserver-side,thentheotherentertheserversiptoconnectandjoingameinanothercomputerastheclient.Bothmodessupportundofunctions，andthenetworkmodehasdrawandgiving-upfunction。Whilenetworkgamingoneplayersendthecoordinatemessageofpiecesreceivedbyanother，whichcallsfunctionstodealwithmessage。Beyondthat，thegamehasalsobackgroundmusicandchatfunction。五子棋摘要五子棋是一種益智游戲，它能加強(qiáng)玩家的思維能力，提高智力，而且趣味橫生，引人入勝。該版本的五子棋設(shè)置了兩類(lèi)形式，單機(jī)形式和網(wǎng)絡(luò)形式。游戲中根據(jù)網(wǎng)絡(luò)連接標(biāo)志來(lái)判定當(dāng)前是網(wǎng)絡(luò)對(duì)戰(zhàn)還是人機(jī)對(duì)戰(zhàn)。人機(jī)對(duì)戰(zhàn)形式使用的是簡(jiǎn)單的博弈樹(shù)搜索算法，即只向前搜索一步，僅能預(yù)測(cè)到下一步會(huì)發(fā)生什么情況。網(wǎng)絡(luò)對(duì)戰(zhàn)形式中一方先建立游戲，作為游戲的服務(wù)器端，對(duì)方輸入服務(wù)器IP后參加游戲，作為客戶(hù)端。兩種形式都有悔棋功能，網(wǎng)絡(luò)對(duì)戰(zhàn)還有認(rèn)輸、和棋請(qǐng)求的功能。發(fā)送五子棋消息主要發(fā)送落子坐標(biāo)，對(duì)方接遭到消息后會(huì)調(diào)用相應(yīng)的函數(shù)處理接收的消息。該游戲還設(shè)置了聲音背景，當(dāng)玩家落子時(shí)會(huì)有落子的聲音，當(dāng)玩家勝了或輸了都會(huì)有背景聲音。另外該游戲還設(shè)置了聊天功能，戰(zhàn)績(jī)統(tǒng)計(jì)等基本游戲功能，以方便對(duì)弈雙方聊天和查看戰(zhàn)績(jī)記錄。關(guān)鍵詞人機(jī)對(duì)戰(zhàn)，網(wǎng)絡(luò)對(duì)戰(zhàn)，算法，消息目錄第一章緒論(3)1.1五子棋介紹(3)1.2開(kāi)發(fā)背景(4)1.3開(kāi)發(fā)環(huán)境及運(yùn)行環(huán)境(5)1.3.1開(kāi)發(fā)環(huán)境(5)1.3.2運(yùn)行環(huán)境(5)第二章邏輯架構(gòu)與設(shè)計(jì)(6)2.1棋盤(pán)類(lèi)(7)2.1.1棋盤(pán)類(lèi)主要成員變量講明(7)2.1.2棋盤(pán)類(lèi)主要成員函數(shù)講明(8)2.2游戲形式類(lèi)(9)2.2.1游戲形式類(lèi)主要成員變量講明(10)2.2.2游戲形式類(lèi)主要成員函數(shù)講明(10)第三章消息機(jī)制(13)3.1消息機(jī)制的架構(gòu)(13)3.2各種消息講明(13)3.2.1落子消息——MSG_PUTSTEP(13)3.2.2悔棋消息——MSG_BACK(13)3.2.3同意悔棋消息——MSG_AGREEBACK(14)3.2.4拒絕悔棋消息——MSG_REFUSEBACK(14)3.2.5和棋消息——MSG_DRAW(14)3.2.6同意和棋消息——MSG_AGREEDRAW(14)3.2.7拒絕和棋消息——MSG_REFUSEDRAW(14)3.2.8認(rèn)輸消息——MSG_GIVEUP(15)3.2.9聊天消息——MSG_CHAT(15)3.2.10對(duì)方信息消息——MSG_INFORMATION(15)第四章人機(jī)對(duì)戰(zhàn)主要算法(16)4.1落子時(shí)能否構(gòu)成五子連珠的算法(16)4.1.1判定水平方向能否構(gòu)成五子連珠(16)4.1.2判定豎直方向能否構(gòu)成五子連珠(17)4.1.3判定左下方向能否構(gòu)成五子連珠(17)4.1.4判定右下方向能否構(gòu)成五子連珠(18)4.2計(jì)算機(jī)落子時(shí)的算法[6](19)4.2.1計(jì)算落子時(shí)的所有獲勝可能性(19)4.2.2落子后計(jì)算得分(19)4.2.3查找棋盤(pán)上的空位置(20)4.2.4為每一個(gè)能夠落子的位置打分(21)4.2.5防守策略(21)4.2.6選取最佳落子(21)總結(jié)(23)第一章緒論1.1五子棋介紹五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。它不僅能加強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋最先發(fā)展于日本，流行于歐美。它既有當(dāng)代休閑的明顯特征，又有古典哲學(xué)的高深學(xué)問(wèn)；它既有簡(jiǎn)單易學(xué)的特性，為人民群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧和高水平的國(guó)際性比賽。傳統(tǒng)五子棋的棋具與圍棋一樣，棋子分為黑白兩色，棋盤(pán)為15×15，棋子放置于棋盤(pán)線(xiàn)穿插點(diǎn)上。兩人對(duì)局，各執(zhí)一色，輪流下一子，先將橫、豎或斜線(xiàn)的5個(gè)或5個(gè)以上同色棋子連成不間斷的一排者為勝。目前五子棋游戲有兩種形式，一種是網(wǎng)絡(luò)五子棋游戲，一種是單機(jī)五子棋游戲。網(wǎng)絡(luò)五子棋編程有兩種實(shí)現(xiàn)方式：一種是基于C/S(Client/Server即C/S)形式；另一種是基于B/S(Brower/Server即B/S)形式。C/S程序具有很好的交互性，功能很強(qiáng)大，但是客戶(hù)端必須安裝客戶(hù)端軟件，限制了其應(yīng)用；B/S形式的程序要求客戶(hù)端必須裝有閱讀器，但是閱讀器在安全性、交互性與功能方面有一些限制。目前網(wǎng)絡(luò)五子棋游戲大部分是在C/S形式下實(shí)現(xiàn)的，其功能不斷的完善和加強(qiáng)，而且五子棋的博弈算法研究到達(dá)了智能化的程度，并能實(shí)現(xiàn)了客戶(hù)端和服務(wù)器端的多線(xiàn)程交互性。隨著網(wǎng)絡(luò)協(xié)議這一關(guān)鍵性問(wèn)題得到了解決和完善使網(wǎng)絡(luò)游戲的設(shè)計(jì)和實(shí)現(xiàn)成為可能。對(duì)于諸多的基層網(wǎng)絡(luò)協(xié)議，Winsock(WindowsSocket即Winsock)是五子棋游戲網(wǎng)絡(luò)連接的首選接口。Winsock是網(wǎng)絡(luò)編程接口，而不是協(xié)議。Winsock提供一個(gè)大家都很熟悉的接口，為實(shí)現(xiàn)網(wǎng)絡(luò)五子棋的功能得到了簡(jiǎn)化[1]。單機(jī)版的五子棋游戲省去了網(wǎng)絡(luò)傳輸這一復(fù)雜的經(jīng)過(guò)，但是需要有力的算法支撐，算法的性能決定程序的性能，也能決定游戲的難易程度。五子棋是一個(gè)比擬特殊的游戲，跟象棋類(lèi)的游戲很不一樣，它只需要判定有五子連珠就能決定勝負(fù)，因而在采用博弈樹(shù)搜索形式時(shí)，只需要向前搜索一步，找出最優(yōu)的位置，基本就能知足程序的需求。1.2開(kāi)發(fā)背景五子棋是一款益智小游戲，對(duì)于玩家來(lái)講，該小游戲其樂(lè)無(wú)窮，引人入勝。對(duì)于開(kāi)發(fā)者來(lái)講，也具有一定的挑戰(zhàn)和樂(lè)趣。隨著Internet的迅速發(fā)展，網(wǎng)絡(luò)游戲迅猛發(fā)展，國(guó)家也開(kāi)場(chǎng)大力支持游戲產(chǎn)業(yè)，由于網(wǎng)絡(luò)游戲的強(qiáng)大市場(chǎng)驅(qū)動(dòng)力，它必將成為最有活力的新文化事業(yè)。隨著Internet的普及，互聯(lián)網(wǎng)游戲作為網(wǎng)上娛樂(lè)的一個(gè)重要內(nèi)容，是互聯(lián)網(wǎng)技術(shù)與互聯(lián)網(wǎng)經(jīng)營(yíng)不可忽略的一個(gè)組成部分。電子娛樂(lè)業(yè)在全球被以為是極有前景的一項(xiàng)產(chǎn)業(yè)。在國(guó)內(nèi)市場(chǎng)，游戲業(yè)潛力宏大，據(jù)統(tǒng)計(jì)顯示，中國(guó)在2006年一年時(shí)間內(nèi)就產(chǎn)生了大約340萬(wàn)新生玩家，游戲人口的整體數(shù)量接近3750萬(wàn)，其中90%是網(wǎng)絡(luò)游戲玩家。隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)游戲的發(fā)展正成為新的互聯(lián)網(wǎng)公司的主要業(yè)務(wù)方向之一。網(wǎng)絡(luò)游戲還能夠降低游戲開(kāi)發(fā)成本，有利于游戲成本的回收。面對(duì)游戲產(chǎn)業(yè)發(fā)達(dá)國(guó)家的游戲企業(yè)有序、高效的進(jìn)入中國(guó)市場(chǎng)的現(xiàn)狀，國(guó)內(nèi)的游戲公司由于不能有效溝通合作，經(jīng)常容易陷入孤立無(wú)援、內(nèi)部競(jìng)爭(zhēng)、競(jìng)相抬價(jià)，最終被各個(gè)擊破的局面。近年來(lái)，中國(guó)的游戲產(chǎn)業(yè)十分是網(wǎng)絡(luò)游戲領(lǐng)域得到了長(zhǎng)足發(fā)展，隨著政府監(jiān)管力度的不斷加強(qiáng)，各種法規(guī)、條例的不斷出臺(tái)，都表明中國(guó)游戲娛樂(lè)產(chǎn)業(yè)的春天就要到來(lái)了。因而開(kāi)發(fā)自主的網(wǎng)絡(luò)游戲，是推動(dòng)國(guó)內(nèi)游戲娛樂(lè)產(chǎn)業(yè)的關(guān)鍵。目前，隨著網(wǎng)絡(luò)游戲用戶(hù)日益增加，網(wǎng)絡(luò)游戲服務(wù)器端的設(shè)計(jì)顯得尤為重要。首先，由于游戲數(shù)據(jù)日益增大，各服務(wù)器間游戲數(shù)據(jù)的交互特別重要；其次，由于游戲外掛的日益猖獗游戲的可玩性和公平性都遭到了挑戰(zhàn)。因而進(jìn)行網(wǎng)絡(luò)游戲的研究，無(wú)論對(duì)于游戲產(chǎn)業(yè)和現(xiàn)行游戲的開(kāi)發(fā)都有積極的意義。近年來(lái)，中國(guó)的網(wǎng)絡(luò)游戲產(chǎn)業(yè)高速增長(zhǎng)，并成為增值服務(wù)外最賺錢(qián)的網(wǎng)絡(luò)業(yè)務(wù)。隨著網(wǎng)絡(luò)游戲產(chǎn)業(yè)的蓬勃發(fā)展，和國(guó)家政策對(duì)游戲產(chǎn)業(yè)的支持。網(wǎng)絡(luò)游戲產(chǎn)業(yè)進(jìn)而具有了廣闊的發(fā)展空間和發(fā)展前景。然而當(dāng)今中國(guó)網(wǎng)絡(luò)游戲市場(chǎng)，占主導(dǎo)地位的卻是以日、韓為代表的外國(guó)網(wǎng)絡(luò)游戲，而國(guó)內(nèi)廠家則基本上處于運(yùn)營(yíng)商地位。因而開(kāi)發(fā)有自主產(chǎn)權(quán)網(wǎng)絡(luò)游戲產(chǎn)品是擺在國(guó)內(nèi)游戲廠商面前的緊要任務(wù)。國(guó)家體育總局在2003年已經(jīng)把電子競(jìng)技項(xiàng)目作為正式的體育項(xiàng)目，這為電子游戲產(chǎn)業(yè)帶來(lái)了又一個(gè)契機(jī)，單機(jī)游戲和網(wǎng)絡(luò)游戲己經(jīng)逐步從民間組織走向職業(yè)化的道路上，網(wǎng)絡(luò)游戲正以每年市場(chǎng)份額翻倍的勢(shì)態(tài)迅猛發(fā)展。因而對(duì)網(wǎng)絡(luò)游戲的開(kāi)發(fā)和研究具有鮮明的現(xiàn)實(shí)意義。一是由于網(wǎng)絡(luò)游戲有強(qiáng)大的市場(chǎng)驅(qū)動(dòng)力，而網(wǎng)絡(luò)游戲產(chǎn)業(yè)是一個(gè)蓬勃發(fā)展的新興市場(chǎng)，成功的網(wǎng)絡(luò)游戲基本收益率可高達(dá)八成。因而網(wǎng)絡(luò)游戲的市場(chǎng)潛能特別宏大，對(duì)網(wǎng)絡(luò)游戲模型的研究和開(kāi)發(fā)就更有其宏大的市場(chǎng)價(jià)值和經(jīng)濟(jì)利益。二是開(kāi)發(fā)具有自主知識(shí)產(chǎn)權(quán)的網(wǎng)絡(luò)游戲?qū)Υ蚱仆鈬?guó)公司在我國(guó)市場(chǎng)的技術(shù)壟斷局面具有重大的意義。國(guó)家正在大力發(fā)展和扶持游戲產(chǎn)業(yè)，建立國(guó)人網(wǎng)絡(luò)游戲，則是改變當(dāng)今市場(chǎng)外國(guó)網(wǎng)絡(luò)游戲產(chǎn)品壟斷市場(chǎng)的唯一出路。[2]1.3開(kāi)發(fā)環(huán)境及運(yùn)行環(huán)境1.3.1開(kāi)發(fā)環(huán)境●Microsoft?VisualC++6.01.3.2運(yùn)行環(huán)境●64M以上內(nèi)存，4G以上硬盤(pán)●Microsoft?WindowIP操作系統(tǒng)●800*600或以上的屏幕分辨率整個(gè)的下棋經(jīng)過(guò)〔無(wú)論對(duì)方是電腦抑或其他網(wǎng)絡(luò)玩家〕能夠分為：本人走棋、等待對(duì)手走棋、對(duì)手走棋后設(shè)置己方棋盤(pán)數(shù)據(jù)這一系列經(jīng)過(guò)，因而一人游戲類(lèi)、二人游戲類(lèi)和棋盤(pán)類(lèi)共用一個(gè)棋盤(pán)類(lèi)，以實(shí)現(xiàn)對(duì)兩個(gè)不同模塊中一樣功能的操作。2.1棋盤(pán)類(lèi)該類(lèi)封裝了棋盤(pán)的各種可能用到的功能，如保存棋盤(pán)數(shù)據(jù)、初始化、判定勝負(fù)等。用戶(hù)操作主界面，主界面與CTable進(jìn)行交互來(lái)完成對(duì)游戲的操作。2.1.1棋盤(pán)類(lèi)主要成員變量講明2.1.1.1網(wǎng)絡(luò)連接標(biāo)志——m_bConnected它是用來(lái)區(qū)分當(dāng)前游戲形式的唯一標(biāo)志，用來(lái)表示當(dāng)前網(wǎng)絡(luò)連接的情況，TRUE時(shí)表明網(wǎng)絡(luò)連接成功，F(xiàn)ALSE時(shí)默以為人機(jī)對(duì)戰(zhàn)。2.1.1.2棋盤(pán)等待標(biāo)志——m_bWait與m_bOldWait由于在玩家落子后需要等待對(duì)方落子，m_bWait標(biāo)志就用來(lái)標(biāo)識(shí)棋盤(pán)的等待狀態(tài)。當(dāng)m_bWait為T(mén)RUE時(shí)，是不允許玩家落子的。2.1.1.3網(wǎng)絡(luò)套接字——m_sock和m_conn在網(wǎng)絡(luò)對(duì)弈游戲形式下，需要用到這兩個(gè)套接字對(duì)象。其中m_sock對(duì)象用于做服務(wù)器時(shí)的監(jiān)聽(tīng)之用，m_conn用于網(wǎng)絡(luò)連接的傳輸。2.1.1.4棋盤(pán)數(shù)據(jù)——m_data這是一個(gè)15*15的二位數(shù)組，用來(lái)保存當(dāng)前棋盤(pán)的落子數(shù)據(jù)。其中對(duì)于每個(gè)成員來(lái)講，0表示落黑子，1表示落白子，-1表示無(wú)子。2.1.1.5游戲形式指針——m_pGame這個(gè)CGame類(lèi)的對(duì)象指針是CTable類(lèi)的核心內(nèi)容。它所指向的對(duì)象實(shí)體決定了CTable在執(zhí)行一件事情時(shí)候的不同行為，詳細(xì)的內(nèi)容請(qǐng)參見(jiàn)“游戲形式〞一節(jié)。2.1.2棋盤(pán)類(lèi)主要成員函數(shù)講明2.1.2.1套接字的回調(diào)處理——Accept、Connect、Receive本程序的套接字派生自MFC的CAsjncSocket類(lèi)，CTable的這三個(gè)成員函數(shù)就分別提供了對(duì)套接字回調(diào)事件OnAccept、OnConnect、OnReceive的實(shí)際處理，其中尤以Receive成員函數(shù)重要，它之中包含了對(duì)所有網(wǎng)絡(luò)消息的分發(fā)處理。2.1.2.2清空棋盤(pán)——Clear在每一局游戲開(kāi)場(chǎng)的時(shí)候都需要調(diào)用這個(gè)函數(shù)將棋盤(pán)清空，也就是棋盤(pán)的初始化工作。在這個(gè)函數(shù)中，主要發(fā)生了這么幾件事情：●將m_data中每一個(gè)落子位都置為無(wú)子狀態(tài)〔-1〕?！窀鶕?jù)傳入的參數(shù)設(shè)置棋盤(pán)等待標(biāo)志m_bWait，以供先、后手的不同情況之用。●使用delete將m_pGame指針?biāo)赶虻脑杏螒蛐问綄?duì)象從堆上刪除。2.1.2.3繪制棋子——Draw這無(wú)疑是很重要的一個(gè)函數(shù)，它根據(jù)參數(shù)給定的坐標(biāo)和顏色繪制棋子。繪制的具體經(jīng)過(guò)如下：●將給定的棋盤(pán)坐標(biāo)換算為繪圖的像素坐標(biāo)?！窀鶕?jù)坐標(biāo)繪制棋子位圖?！窦偃缦惹霸逻^(guò)棋子，則利用R2_NOTIORPEN將上一個(gè)繪制棋子上的最后落子指示矩形擦除。●在剛繪制完成的棋子四周繪制最后落子指示矩形。2.1.2.4左鍵消息——OnLButtonUp作為棋盤(pán)唯一響應(yīng)的左鍵消息，也需要做不少的工作：●假如棋盤(pán)等待標(biāo)志m_bWait為T(mén)RUE，則直接發(fā)出警告聲音并返回，即禁止落子。●假如點(diǎn)擊時(shí)的鼠標(biāo)坐標(biāo)在合法坐標(biāo)(0,0)～(14,14)之外，亦禁止落子?！窦偃缱叩牟綌?shù)大于1步，方才允許悔棋。●進(jìn)行勝利判定，如勝利則修改UI狀態(tài)并增加勝利數(shù)的統(tǒng)計(jì)。●如未勝利，則向?qū)Ψ桨l(fā)送已經(jīng)落子的消息?！衤渥油戤叄瑢_bWait標(biāo)志置為T(mén)RUE，開(kāi)場(chǎng)等待對(duì)方回應(yīng)。2