五子棋畢業(yè)論文

1、<p>　　本科畢業(yè)論文（設(shè)計(jì)）</p><p>　　學(xué)院、系 計(jì)算機(jī)學(xué)院 </p><p>　　專(zhuān)業(yè)名稱(chēng) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　年 級(jí) </p><p>　　學(xué)生姓名 </p>

2、<p>　　指導(dǎo)教師 </p><p><b>　　abstract</b></p><p>　　As a puzzle game，gobang can develop the thinking ability and intelligence of players，which is interesting a

3、nd absorbing。The version of this software，includes two kinds of patterns，standalone mode and network mode。The former uses a game-tree search algorithm，which can only predict a follow-up move after calculation。Moreover, t

4、he network mode needs to be brought online, in other words, first need a player in a computer start game as the server-side, then the other enter the servers ip to connect a</p><p><b>　　五子棋</b>&l

5、t;/p><p>　　摘要 五子棋是一種益智游戲，它能增強(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ù)端。兩種模式都有悔棋功能

6、，網(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ī)記錄。</p><p>　　關(guān)鍵詞 人機(jī)對(duì)戰(zhàn)，網(wǎng)絡(luò)對(duì)戰(zhàn)，算法，消息 </p><p><b>　　目

7、錄</b></p><p>　　第一章 緒論3</p><p>　　1.1 五子棋介紹3</p><p>　　1.2 開(kāi)發(fā)背景4</p><p>　　1.3 開(kāi)發(fā)環(huán)境及運(yùn)行環(huán)境5</p><p>　　1.3.1 開(kāi)發(fā)環(huán)境5</p><p>　　1.3.2 運(yùn)行環(huán)境5&

8、lt;/p><p>　　第二章 邏輯架構(gòu)與設(shè)計(jì)6</p><p><b>　　2.1 棋盤(pán)類(lèi)7</b></p><p>　　2.1.1 棋盤(pán)類(lèi)主要成員變量說(shuō)明7</p><p>　　2.1.2 棋盤(pán)類(lèi)主要成員函數(shù)說(shuō)明8</p><p>　　2.2 游戲模式類(lèi)9</p>&l

9、t;p>　　2.2.1 游戲模式類(lèi)主要成員變量說(shuō)明10</p><p>　　2.2.2 游戲模式類(lèi)主要成員函數(shù)說(shuō)明10</p><p>　　第三章 消息機(jī)制13</p><p>　　3.1消息機(jī)制的架構(gòu)13</p><p>　　3.2各種消息說(shuō)明13</p><p>　　3.2.1落子消息——MSG

10、_PUTSTEP13</p><p>　　3.2.2 悔棋消息——MSG_BACK13</p><p>　　3.2.3同意悔棋消息——MSG_AGREEBACK14</p><p>　　3.2.4拒絕悔棋消息——MSG_REFUSEBACK14</p><p>　　3.2.5和棋消息——MSG_DRAW14</p>&

11、lt;p>　　3.2.6同意和棋消息——MSG_AGREEDRAW14</p><p>　　3.2.7拒絕和棋消息——MSG_REFUSEDRAW14</p><p>　　3.2.8認(rèn)輸消息——MSG_GIVEUP15</p><p>　　3.2.9聊天消息——MSG_CHAT15</p><p>　　3.2.10對(duì)方信息消息—

12、—MSG_INFORMATION15</p><p>　　第四章 人機(jī)對(duì)戰(zhàn)主要算法16</p><p>　　4.1 落子時(shí)是否構(gòu)成五子連珠的算法16</p><p>　　4.1.1 判斷水平方向是否構(gòu)成五子連珠16</p><p>　　4.1.2判斷豎直方向是否構(gòu)成五子連珠17</p><p>　　4.1.3

13、判斷左下方向是否構(gòu)成五子連珠17</p><p>　　4.1.4判斷右下方向是否構(gòu)成五子連珠18</p><p>　　4.2 計(jì)算機(jī)落子時(shí)的算法[6]19</p><p>　　4.2.1　計(jì)算落子時(shí)的所有獲勝可能性19</p><p>　　4.2.2　落子后計(jì)算得分19</p><p>　　4.2.3　查找棋

14、盤(pán)上的空位置20</p><p>　　4.2.4　為每一個(gè)可以落子的位置打分21</p><p>　　4.2.5　防守策略21</p><p>　　4.2.6　選取最佳落子21</p><p><b>　　總結(jié)23</b></p><p><b>　　第一章 緒論</

15、b></p><p><b>　　1.1 五子棋介紹</b></p><p>　　五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。它不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋最先發(fā)展于日本，流行于歐美。它既有現(xiàn)代休閑的明顯特征，又有古典哲學(xué)的高深學(xué)問(wèn)；它既有簡(jiǎn)單易學(xué)的特性，為人民群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧和高水平的國(guó)際性比賽。</p&

16、gt;<p>　　傳統(tǒng)五子棋的棋具與圍棋相同，棋子分為黑白兩色，棋盤(pán)為15×15，棋子放置于棋盤(pán)線交叉點(diǎn)上。兩人對(duì)局，各執(zhí)一色，輪流下一子，先將橫、豎或斜線的5</p><p>　　個(gè)或5個(gè)以上同色棋子連成不間斷的一排者為勝。</p><p>　　目前五子棋游戲有兩種模式，一種是網(wǎng)絡(luò)五子棋游戲，一種是單機(jī)五子棋游戲。網(wǎng)絡(luò)五子棋編程有兩種實(shí)現(xiàn)方式：一種是基于C/S(C

17、lient/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ù)器端的多線程交互性。

18、隨著網(wǎng)絡(luò)協(xié)議這一關(guān)鍵性問(wèn)題得到了解決和完善使網(wǎng)絡(luò)游戲的設(shè)計(jì)和實(shí)現(xiàn)成為可能。對(duì)于眾多的基層網(wǎng)絡(luò)協(xié)議，Winsock(Windows Socket 即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ù)雜的過(guò)程，但是需要有力的算法支撐，算法的性能決定程序的性能，也能決定游戲的難易程度

19、</p><p><b>　　1.2 開(kāi)發(fā)背景</b></p><p>　　五子棋是一款益智小游戲，對(duì)于玩家來(lái)說(shuō)，該小游戲其樂(lè)無(wú)窮，引人入勝。對(duì)于開(kāi)發(fā)者來(lái)說(shuō)，也具有一定的挑戰(zhàn)和樂(lè)趣。隨著Internet的迅速發(fā)展，網(wǎng)絡(luò)游戲迅猛發(fā)展，國(guó)家也開(kāi)始大力支持游戲產(chǎn)業(yè)，由于網(wǎng)絡(luò)游戲的強(qiáng)大市場(chǎng)驅(qū)動(dòng)力，它必將成為最有活力的新文化事業(yè)。隨著Internet的普及，互聯(lián)網(wǎng)游戲作為網(wǎng)上娛

20、樂(lè)的一個(gè)重要內(nèi)容，是互聯(lián)網(wǎng)技術(shù)與互聯(lián)網(wǎng)經(jīng)營(yíng)不可忽略的一個(gè)組成部分。電子娛樂(lè)業(yè)在全球被認(rèn)為是極有前景的一項(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)入中

21、國(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)了。因</p><p>　　1.3 開(kāi)發(fā)環(huán)境及運(yùn)行環(huán)境</p><p>　　1.3.1 開(kāi)發(fā)環(huán)境</p><p&

22、gt;　　Microsoft® Visual C++ 6.0</p><p>　　1.3.2 運(yùn)行環(huán)境</p><p>　　64M以上內(nèi)存，4G以上硬盤(pán)</p><p>　　Microsoft® Window IP操作系統(tǒng)</p><p>　　800*600或以上的屏幕分辨率</p><p>　　第

23、二章 邏輯架構(gòu)與設(shè)計(jì)</p><p>　　軟件的邏輯架構(gòu)如圖2.1和圖2.2：</p><p><b>　　單機(jī)模式：</b></p><p>　　否 否</p><p><b>　　是</b></p

24、><p><b>　　是</b></p><p><b>　　圖2.1 單機(jī)模式</b></p><p><b>　　圖2.2 網(wǎng)絡(luò)模式</b></p><p>　　整個(gè)的下棋過(guò)程（無(wú)論對(duì)方是電腦抑或其他網(wǎng)絡(luò)玩家）可以分為：自己走棋、等待對(duì)手走棋、對(duì)手走棋后設(shè)置己方棋盤(pán)數(shù)據(jù)這一系列

25、過(guò)程，因此一人游戲類(lèi)、二人游戲類(lèi)和棋盤(pán)類(lèi)共用一個(gè)棋盤(pán)類(lèi)，以實(shí)現(xiàn)對(duì)兩個(gè)不同模塊中相同功能的操作。</p><p><b>　　2.1 棋盤(pán)類(lèi)</b></p><p>　　該類(lèi)封裝了棋盤(pán)的各種可能用到的功能，如保存棋盤(pán)數(shù)據(jù)、初始化、判斷勝負(fù)等。用戶(hù)操作主界面，主界面與CTable進(jìn)行交互來(lái)完成對(duì)游戲的操作。</p><p>　　2.1.1 棋盤(pán)類(lèi)主

26、要成員變量說(shuō)明</p><p>　　2.1.1.1 網(wǎng)絡(luò)連接標(biāo)志——m_bConnected</p><p>　　它是用來(lái)區(qū)分當(dāng)前游戲模式的唯一標(biāo)志，用來(lái)表示當(dāng)前網(wǎng)絡(luò)連接的情況，TRUE時(shí)表明網(wǎng)絡(luò)連接成功，F(xiàn)ALSE時(shí)默認(rèn)為人機(jī)對(duì)戰(zhàn)。</p><p>　　2.1.1.2 棋盤(pán)等待標(biāo)志——m_bWait與m_bOldWait</p><p>　

27、　由于在玩家落子后需要等待對(duì)方落子，m_bWait標(biāo)志就用來(lái)標(biāo)識(shí)棋盤(pán)的等待狀態(tài)。當(dāng)m_bWait為T(mén)RUE時(shí)，是不允許玩家落子的。</p><p>　　2.1.1.3 網(wǎng)絡(luò)套接字——m_sock和m_conn</p><p>　　在網(wǎng)絡(luò)對(duì)弈游戲模式下，需要用到這兩個(gè)套接字對(duì)象。其中m_sock對(duì)象用于做服務(wù)器時(shí)的監(jiān)聽(tīng)之用，m_conn用于網(wǎng)絡(luò)連接的傳輸。</p><p&

28、gt;　　2.1.1.4 棋盤(pán)數(shù)據(jù)——m_data</p><p>　　這是一個(gè)15*15的二位數(shù)組，用來(lái)保存當(dāng)前棋盤(pán)的落子數(shù)據(jù)。其中對(duì)于每個(gè)成員來(lái)說(shuō)，0表示落黑子，1表示落白子，-1表示無(wú)子。</p><p>　　2.1.1.5 游戲模式指針——m_pGame</p><p>　　這個(gè)CGame類(lèi)的對(duì)象指針是CTable類(lèi)的核心內(nèi)容。它所指向的對(duì)象實(shí)體決定了CTa

29、ble在執(zhí)行一件事情時(shí)候的不同行為，具體的內(nèi)容請(qǐng)參見(jiàn)“游戲模式”一節(jié)。</p><p>　　2.1.2 棋盤(pán)類(lèi)主要成員函數(shù)說(shuō)明</p><p>　　2.1.2.1 套接字的回調(diào)處理——Accept、Connect、Receive</p><p>　　本程序的套接字派生自MFC的CAsjncSocket類(lèi)，CTable的這三個(gè)成員函數(shù)就分別提供了對(duì)套接字回調(diào)事件OnA

30、ccept、OnConnect、OnReceive的實(shí)際處理，其中尤以Receive成員函數(shù)重要，它之中包含了對(duì)所有網(wǎng)絡(luò)消息的分發(fā)處理。</p><p>　　2.1.2.2清空棋盤(pán)——Clear</p><p>　　在每一局游戲開(kāi)始的時(shí)候都需要調(diào)用這個(gè)函數(shù)將棋盤(pán)清空，也就是棋盤(pán)的初始化工作。在這個(gè)函數(shù)中，主要發(fā)生了這么幾件事情：</p><p>　　將m_data中

31、每一個(gè)落子位都置為無(wú)子狀態(tài)（-1）。</p><p>　　按照傳入的參數(shù)設(shè)置棋盤(pán)等待標(biāo)志m_bWait，以供先、后手的不同情況之用。</p><p>　　使用delete將m_pGame指針?biāo)赶虻脑杏螒蚰Ｊ綄?duì)象從堆上刪除。</p><p>　　2.1.2.3 繪制棋子——Draw</p><p>　　這無(wú)疑是很重要的一個(gè)函數(shù)，它根據(jù)參數(shù)給

32、定的坐標(biāo)和顏色繪制棋子。繪制的詳細(xì)過(guò)程如下：</p><p>　　將給定的棋盤(pán)坐標(biāo)換算為繪圖的像素坐標(biāo)。</p><p>　　根據(jù)坐標(biāo)繪制棋子位圖。</p><p>　　如果先前曾下過(guò)棋子，則利用R2_NOTIORPEN將上一個(gè)繪制棋子上的最后落子指示矩形擦除。</p><p>　　在剛繪制完成的棋子四周繪制最后落子指示矩形。</p&g

33、t;<p>　　2.1.2.4 左鍵消息——OnLButtonUp</p><p>　　作為棋盤(pán)唯一響應(yīng)的左鍵消息，也需要做不少的工作：</p><p>　　如果棋盤(pán)等待標(biāo)志m_bWait為T(mén)RUE，則直接發(fā)出警告聲音并返回，即禁止落子。</p><p>　　如果點(diǎn)擊時(shí)的鼠標(biāo)坐標(biāo)在合法坐標(biāo)(0, 0)～(14, 14)之外，亦禁止落子。</p&g

34、t;<p>　　如果走的步數(shù)大于1步，方才允許悔棋。</p><p>　　進(jìn)行勝利判斷，如勝利則修改UI狀態(tài)并增加勝利數(shù)的統(tǒng)計(jì)。</p><p>　　如未勝利，則向?qū)Ψ桨l(fā)送已經(jīng)落子的消息。</p><p>　　落子完畢，將m_bWait標(biāo)志置為T(mén)RUE，開(kāi)始等待對(duì)方回應(yīng)。</p><p>　　2.1.2.5 繪制棋盤(pán)——OnPa

35、int</p><p>　　每當(dāng)WM_PAINT消息觸發(fā)時(shí)，都需要對(duì)棋盤(pán)進(jìn)行重繪。OnPaint作為響應(yīng)繪制消息的消息處理函數(shù)使用了雙緩沖技術(shù)，減少了多次繪圖可能導(dǎo)致的圖像閃爍問(wèn)題。這個(gè)函數(shù)主要完成了以下工作：</p><p>　　裝載棋盤(pán)位圖并進(jìn)行繪制。</p><p>　　根據(jù)棋盤(pán)數(shù)據(jù)繪制棋子。</p><p>　　繪制最后落子指示矩形。

36、</p><p><b>　　2.2 游戲模式類(lèi)</b></p><p>　　用來(lái)管理人機(jī)對(duì)弈/網(wǎng)絡(luò)對(duì)弈兩種游戲模式，類(lèi)名為CGame。CGame是一個(gè)抽象類(lèi)，經(jīng)由它派生出一人游戲類(lèi)COneGame和網(wǎng)絡(luò)游戲類(lèi)CTwoGame，這樣，CTable類(lèi)就可以通過(guò)一個(gè)CGame類(lèi)的指針，在游戲初始化的時(shí)候根據(jù)具體游戲模式的要求實(shí)例化COneGame或CTwoGame類(lèi)的對(duì)象

37、；然后利用多態(tài)性[3]，使用CGame類(lèi)提供的公有接口就可以完成不同游戲模式下的不同功能了。</p><p>　　2.2.1 游戲模式類(lèi)主要成員變量說(shuō)明</p><p>　　2.2.1.1 棋盤(pán)指針——m_pTable</p><p>　　由于在游戲中需要對(duì)棋盤(pán)以及棋盤(pán)的父窗口——主對(duì)話框進(jìn)行操作及UI狀態(tài)設(shè)置，故為CGame類(lèi)設(shè)置了這個(gè)成員。當(dāng)對(duì)主對(duì)話框進(jìn)行操作時(shí)

38、，可以使用m_pTable->GetParent()得到它的窗口指針。</p><p>　　2.2.1.2落子步驟——m_StepList</p><p>　　一個(gè)好的棋類(lèi)程序必須要考慮到的功能就是它的悔棋功能，所以需要為游戲類(lèi)設(shè)置一個(gè)落子步驟的列表。由于人機(jī)對(duì)弈和網(wǎng)絡(luò)對(duì)弈中都需要這個(gè)功能，故將這個(gè)成員直接設(shè)置到基類(lèi)CGame中。另外，考慮到使用的簡(jiǎn)便性，這個(gè)成員使用了C++標(biāo)準(zhǔn)模板

39、庫(kù)[4]（Standard Template Librarj，STL）中的std::list，而不是MFC的CList。</p><p>　　2.2.2 游戲模式類(lèi)主要成員函數(shù)說(shuō)明</p><p>　　2.2.2.1 悔棋操作——Back</p><p>　　在不同的游戲模式下，悔棋的行為是不一樣的。</p><p>　　人機(jī)對(duì)弈模式下，計(jì)算

40、機(jī)是完全允許玩家悔棋的，但是出于對(duì)程序負(fù)荷的考慮，只允許玩家悔當(dāng)前的兩步棋（計(jì)算機(jī)一步，玩家一步）。</p><p>　　雙人網(wǎng)絡(luò)對(duì)弈模式下，悔棋的過(guò)程為：首先由玩家向?qū)Ψ桨l(fā)送悔棋請(qǐng)求（悔棋消息），然后由對(duì)方?jīng)Q定是否允許玩家悔棋，在玩家得到對(duì)方的響應(yīng)消息（允許或者拒絕）之后，才進(jìn)行悔棋與否的操作。</p><p>　　2.2.2.2 初始化操作——Init</p><p

41、>　　對(duì)于不同的游戲模式而言，也就有不同的初始化方式。對(duì)于人機(jī)對(duì)弈模式而言，初始化操作包括以下幾個(gè)步驟：</p><p>　　設(shè)置網(wǎng)絡(luò)連接狀態(tài)m_bConnected為FALSE。</p><p>　　設(shè)置主界面計(jì)算機(jī)玩家的姓名。</p><p>　　初始化所有的獲勝組合。</p><p>　　如果是計(jì)算機(jī)先走，則占據(jù)天元（棋盤(pán)正中央）

42、的位置。</p><p>　　網(wǎng)絡(luò)對(duì)弈的初始化工作暫為空，以供以后擴(kuò)展之用。</p><p>　　2.2.2.3接收來(lái)自對(duì)方的消息——ReceiveMsg</p><p>　　這個(gè)成員函數(shù)由CTable棋盤(pán)類(lèi)的Receive成員函數(shù)調(diào)用，用于接收來(lái)自對(duì)方的消息。對(duì)于人機(jī)對(duì)弈游戲模式來(lái)說(shuō)，所能接收到的就僅僅是本地模擬的落子消息MSG_PUTSTEP；對(duì)于網(wǎng)絡(luò)對(duì)弈游戲模

43、式來(lái)說(shuō)，這個(gè)成員函數(shù)則負(fù)責(zé)從套接字讀取對(duì)方發(fā)過(guò)來(lái)的數(shù)據(jù)，然后將這些數(shù)據(jù)解釋為自定義的消息結(jié)構(gòu)，并回到CTable::Receive來(lái)進(jìn)行處理。</p><p>　　2.2.2.4 發(fā)送落子消息——SendStep</p><p>　　在玩家落子結(jié)束后，要向?qū)Ψ桨l(fā)送自己落子的消息。對(duì)于不同的游戲模式，發(fā)送的目標(biāo)也不同：</p><p>　　對(duì)于人機(jī)對(duì)弈游戲模式，將直接

44、把落子的信息（坐標(biāo)、顏色）發(fā)送給COneGame類(lèi)相應(yīng)的計(jì)算函數(shù)。</p><p>　　對(duì)于網(wǎng)絡(luò)對(duì)弈游戲模式，將把落子消息發(fā)送給套接字，并由套接字轉(zhuǎn)發(fā)給對(duì)方。</p><p>　　2.2.2.5勝利后的處理——Win</p><p>　　這個(gè)成員函數(shù)主要針對(duì)CTwoGame網(wǎng)絡(luò)對(duì)弈模式。在玩家贏得棋局后，這個(gè)函數(shù)仍然會(huì)調(diào)用SendStep將玩家所下的制勝落子步驟發(fā)送

45、給對(duì)方玩家，然后對(duì)方的游戲端經(jīng)由CTable::Win來(lái)判定自己失敗。</p><p>　　第三章 消息機(jī)制</p><p>　　Windows系統(tǒng)擁有自己的消息機(jī)制，在不同事件發(fā)生的時(shí)候，系統(tǒng)也可以提供不同的響應(yīng)方式。五子棋程序也模仿Windows系統(tǒng)實(shí)現(xiàn)了自己的消息機(jī)制，主要為網(wǎng)絡(luò)對(duì)弈服務(wù)，以響應(yīng)多種多樣的網(wǎng)絡(luò)消息。</p><p>　　3.1消息機(jī)制的架構(gòu)

46、</p><p>　　當(dāng)CTable獲得了來(lái)自網(wǎng)絡(luò)的消息之后，就可以使用一個(gè)switch結(jié)構(gòu)來(lái)進(jìn)行消息的分發(fā)了。如圖3.1所示：</p><p>　　. . . . . .</p><p>　　switch判斷是哪個(gè)消息</p><p><b>　　圖3.1 請(qǐng)求悔棋</b></p><p>&l

47、t;b>　　3.2各種消息說(shuō)明</b></p><p>　　3.2.1落子消息——MSG_PUTSTEP</p><p>　　表明對(duì)方落下了一個(gè)棋子，其中i、j和color成員有效，szMsg成員無(wú)效。在人機(jī)對(duì)弈游戲模式下，亦會(huì)模擬發(fā)送此消息以達(dá)到程序模塊一般化的效果。</p><p>　　3.2.2 悔棋消息——MSG_BACK</p>

48、;<p>　　表明對(duì)方請(qǐng)求悔棋，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，會(huì)彈出MessageBoi詢(xún)問(wèn)是否接受對(duì)方的請(qǐng)求，并根據(jù)玩家的選擇回返MSG_AGREEBACK或MSG_REFUSEBACK消息。</p><p>　　3.2.3同意悔棋消息——MSG_AGREEBACK</p><p>　　表明對(duì)方接受了玩家的悔棋請(qǐng)求，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)

49、消息后，將進(jìn)行正常的悔棋操作。</p><p>　　3.2.4拒絕悔棋消息——MSG_REFUSEBACK</p><p>　　表明對(duì)方拒絕了玩家的悔棋請(qǐng)求，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，整個(gè)界面將恢復(fù)發(fā)送悔棋請(qǐng)求前的狀態(tài)。</p><p>　　3.2.5和棋消息——MSG_DRAW</p><p>　　表明對(duì)方請(qǐng)求和棋，除

50、uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，會(huì)彈出MessageBoi詢(xún)問(wèn)是否接受對(duì)方的請(qǐng)求，并根據(jù)玩家的選擇回返MSG_AGREEDRAW或MSG_REFUSEDRAW消息。</p><p>　　3.2.6同意和棋消息——MSG_AGREEDRAW</p><p>　　表明對(duì)方接受了玩家的和棋請(qǐng)求，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，雙方和棋。</p><

51、;p>　　3.2.7拒絕和棋消息——MSG_REFUSEDRAW</p><p>　　表明對(duì)方拒絕了玩家的和棋請(qǐng)求，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，整個(gè)界面將恢復(fù)發(fā)送和棋請(qǐng)求前的狀態(tài)。</p><p>　　3.2.8認(rèn)輸消息——MSG_GIVEUP</p><p>　　表明對(duì)方已經(jīng)投子認(rèn)輸，除uMsg成員外其余成員皆無(wú)效。接到這個(gè)消息后，整個(gè)界

52、面將轉(zhuǎn)換為勝利后的狀態(tài)。</p><p>　　3.2.9聊天消息——MSG_CHAT</p><p>　　表明對(duì)方發(fā)送了一條聊天信息，szMsg表示對(duì)方的信息，其余成員無(wú)效。接到這個(gè)信息后，會(huì)將對(duì)方聊天的內(nèi)容顯示在主對(duì)話框的聊天記錄窗口內(nèi)。</p><p>　　3.2.10對(duì)方信息消息——MSG_INFORMATION</p><p>　　用

53、來(lái)獲取對(duì)方玩家的姓名，szMsg表示對(duì)方的姓名，其余成員無(wú)效。在開(kāi)始游戲的時(shí)候，由客戶(hù)端向服務(wù)端發(fā)送這條消息，服務(wù)端接到后設(shè)置對(duì)方的姓名，并將自己的姓名同樣用這條消息回發(fā)給客戶(hù)端。</p><p>　　第四章 人機(jī)對(duì)戰(zhàn)主要算法</p><p>　　在兩個(gè)主機(jī)間玩該游戲時(shí)，不需要什么算法，只需要判斷每一次落棋時(shí)是否贏了。而在和電腦玩該游戲時(shí)，就需要設(shè)計(jì)一些算法。目前網(wǎng)絡(luò)上流行的一些五子棋游戲

54、都有兩類(lèi)模式，一類(lèi)是無(wú)禁手模式，即落子時(shí)沒(méi)有任何限制，只要有空位置就可放置。另一類(lèi)是有禁手模式，即落子時(shí)有限制，不是每一個(gè)空位置都可以放置棋子的，國(guó)際上規(guī)定的禁手有三三禁手、四四禁手、長(zhǎng)連禁手[5]。由于我個(gè)人能力有限，對(duì)于禁手模式研究的還不是很透徹，在此五子棋游戲中就沒(méi)有設(shè)置禁手模式。</p><p>　　本五子棋游戲設(shè)計(jì)時(shí)，涉及的算法主要有兩個(gè)，一個(gè)是判斷輸贏的算法，一個(gè)是電腦落子時(shí)的算法。下面分別介紹這兩個(gè)

55、算法。</p><p>　　4.1 落子時(shí)是否構(gòu)成五子連珠的算法</p><p>　　五子連珠看起來(lái)很容易判斷，只要判斷在水平，豎直方向以及斜著的方向上是否有同色的五顆棋子即可。但在實(shí)際操作中，判斷起來(lái)卻不是那么簡(jiǎn)單。在該程序的判斷中，我采用了遍歷的方式，從棋盤(pán)的左上角開(kāi)始判斷。依次進(jìn)行水平，豎直，左下方向，右下方向的判斷。</p><p>　　4.1.1 判斷水平

56、方向是否構(gòu)成五子連珠</p><p>　　由于棋盤(pán)是15*15的規(guī)格，故需從上到下掃描每一行，每一行從第一個(gè)位置掃描到第11個(gè)位置即可，后面四個(gè)無(wú)需掃描，因?yàn)椴豢赡軜?gòu)成五子連珠。程序如下：</p><p>　　for ( j = 0; j < 15; j++ ) // 掃描每一行</p><p><b>　　{</b

57、></p><p>　　for ( i = 0; i < 11; i++ )//每一行從第一個(gè)位置掃描到第十一個(gè)位置</p><p><b>　　{</b></p><p>　　if ( color == m_data[i][j] &&</p><p>　　color == m_data[i

58、+ 1][j] &&</p><p>　　color == m_data[i + 2][j] &&</p><p>　　color == m_data[i + 3][j] &&</p><p>　　color == m_data[i + 4][j] )</p><p><b>　　{&

59、lt;/b></p><p>　　return TRUE;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.1.2判斷豎直方向是否構(gòu)成五子連珠</p><p>　　豎直方向上的判斷和上面相似，從左到右掃描每一列，從

60、上到下掃描第1到第11個(gè)棋盤(pán)的位置。原因與水平方向一樣。程序如下：</p><p>　　for ( j = 0; j < 11; j++ ) //掃描列的第一行到第十一行的位置</p><p><b>　　{</b></p><p>　　for ( i = 0; i < 15; i++ ) //掃描每一列</p>

61、<p><b>　　{</b></p><p>　　if ( color == m_data[i][j] &&</p><p>　　color == m_data[i][j + 1] &&</p><p>　　color == m_data[i][j + 2] &&</p>

62、;<p>　　color == m_data[i][j + 3] &&</p><p>　　color == m_data[i][j + 4] )</p><p><b>　　{</b></p><p>　　return TRUE;</p><p><b>　　}</b>

63、;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　4.1.3判斷左下方向是否構(gòu)成五子連珠</p><p>　　由于當(dāng)前判斷的棋子約定的是第一顆棋子，故只需要從第五列判斷到最后一列，從第一行判斷到第十一行。程序如下：</p><

64、p>　　for ( j = 0; j < 11; j++ ) //第一行到第十一行</p><p><b>　　{</b></p><p>　　for ( i = 4; i < 15; i++ ) //第五列到最后一列</p><p><b>　　{</b></p><p&

65、gt;　　if ( color == m_data[i][j] &&</p><p>　　color == m_data[i - 1][j + 1] &&</p><p>　　color == m_data[i - 2][j + 2] &&</p><p>　　color == m_data[i - 3][j + 3]

66、 &&</p><p>　　color == m_data[i - 4][j + 4] )</p><p><b>　　{</b></p><p>　　return TRUE;</p><p><b>　　}</b></p><p><b>　　}

67、</b></p><p><b>　　}</b></p><p>　　4.1.4判斷右下方向是否構(gòu)成五子連珠</p><p>　　判斷右下方向時(shí)，與左下方向相似，都需要從第一行判斷到第十一行，但是右下方向判斷時(shí)需要從第一列判斷到第十一列。程序如下：</p><p>　　for ( j = 0; j <

68、11; j++ ) //第一行到第十一行</p><p><b>　　{</b></p><p>　　for ( i = 0; i < 11; i++ ) //第一列到第十一列</p><p><b>　　{</b></p><p>　　if ( color == m_data[i

69、][j] &&</p><p>　　color == m_data[i + 1][j + 1] &&</p><p>　　color == m_data[i + 2][j + 2] &&</p><p>　　color == m_data[i + 3][j + 3] &&</p><

70、p>　　color == m_data[i + 4][j + 4] )</p><p><b>　　{</b></p><p>　　return TRUE;</p><p><b>　　}</b></p><p><b>　　}</b></p><p&

71、gt;<b>　　}</b></p><p>　　以上四個(gè)判斷看起來(lái)寫(xiě)的復(fù)雜，時(shí)間復(fù)雜度有些高，但是每一個(gè)都是很有限的判斷，計(jì)算機(jī)執(zhí)行起來(lái)的時(shí)間基本都是0ms。所以程序中也不用怎么優(yōu)化。</p><p>　　4.2 計(jì)算機(jī)落子時(shí)的算法[6]</p><p>　　4.2.1　計(jì)算落子時(shí)的所有獲勝可能性</p><p>　　

72、該程序?yàn)橥婕液碗娔X都設(shè)置了一個(gè)三維數(shù)組，用于儲(chǔ)存落子時(shí)的所有獲勝的可能情況。根據(jù)上面判斷落子時(shí)是否五子連珠，所有的可能性有以下幾種。水平方向上：11*15；</p><p>　　豎直方向上：11*15；左下方向上：11*11；右下方向上：11*11。故落子時(shí)所有的獲勝可能有 15 * 11 * 2 + 11 * 11 * 2 = 572種。</p><p>　　有了這些獲勝的可能性，就可以

73、對(duì)棋盤(pán)上當(dāng)前落子進(jìn)行打分，即對(duì)每一個(gè)位置進(jìn)行分?jǐn)?shù)計(jì)算，給出最有進(jìn)攻優(yōu)勢(shì)或者防守力度的坐標(biāo)值。那么任何一方都需要一個(gè)15*15*572的數(shù)組來(lái)記錄每一個(gè)坐標(biāo)處的獲勝可能性。</p><p>　　五子棋是兩方的對(duì)弈，因此需要計(jì)算出雙方的落子得分。電腦的落子得分與玩家的落子得分計(jì)算都是參考上面的規(guī)則。</p><p>　　另外，每次進(jìn)入游戲時(shí)，所有的獲勝可能都一樣，需要在COneGame::In

74、it中初始化一下，都是572種。</p><p>　　4.2.2　落子后計(jì)算得分</p><p>　　只要棋盤(pán)上有落子，都需要作如下處理：</p><p>　　如果當(dāng)前位置可以落子，并且落子后無(wú)論在哪個(gè)方向上，只要有一個(gè)方向能獲勝，則將獲勝可能性數(shù)組加1。（此時(shí)并未落子，只是計(jì)算每個(gè)坐標(biāo)的得分。）</p><p>　　如果對(duì)方在此坐標(biāo)有可能獲

75、勝，則將對(duì)方在此坐標(biāo)的獲勝可能性置為false，并將對(duì)方此獲勝組合添加棋子數(shù)置為-1（不可能靠此組合獲勝）。</p><p>　　以玩家落子為例，代碼為：</p><p>　　for ( i = 0; i < 572; i++ )</p><p><b>　　{</b></p><p><b>　　//

76、修改狀態(tài)變化</b></p><p>　　if ( m_Plajer[stepPut.i][stepPut.j][i] &&</p><p>　　m_Win[0][i] != -1 )</p><p>　　m_Win[0][i]++;</p><p>　　if ( m_Computer[stepPut.i][ste

77、pPut.j][i] )</p><p><b>　　{</b></p><p>　　m_Computer[stepPut.i][stepPut.j][i] = false;</p><p>　　m_Win[1][i] = -1;</p><p><b>　　}</b></p><

78、;p><b>　　}</b></p><p>　　4.2.3　查找棋盤(pán)上的空位置</p><p>　　在電腦每一次落子之前，都有掃描一下棋盤(pán)，找出空位置。程序中的SearchBlank就是負(fù)責(zé)該功能的。SearchBlank函數(shù)進(jìn)行不重復(fù)的查找，對(duì)已查找過(guò)的坐標(biāo)進(jìn)行標(biāo)記，以便返回。其代碼如下：</p><p>　　bool COneGam

79、e::SearchBlank( int &i, int &j,</p><p>　　int nowTable[][15] )</p><p><b>　　{</b></p><p><b>　　int i, j;</b></p><p>　　for ( i = 0; i < 1

80、5; i++ )</p><p><b>　　{</b></p><p>　　for ( j = 0; j < 15; j++ )</p><p><b>　　{</b></p><p>　　if ( nowTable[i][j] == -1 && nowTable[i][j]

81、 != 2 )</p><p><b>　　{</b></p><p><b>　　i = i;</b></p><p><b>　　j = j;</b></p><p>　　return true;</p><p><b>　　}</b

82、></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return false;</p><p><b>　　}</b></p><p>　　4.2.4　為每一個(gè)可以落子的位置打分</p>

83、;<p>　　對(duì)于玩家有利的位置，就是對(duì)計(jì)算機(jī)不利的位置，故玩家的分?jǐn)?shù)設(shè)為負(fù)值，對(duì)計(jì)算機(jī)來(lái)說(shuō)就是既考慮了進(jìn)攻，又考慮了防守。這就是整個(gè)程序的核心算法。上面的SearchBlank函數(shù)找到空位后，需要對(duì)當(dāng)前坐標(biāo)的落子進(jìn)行打分，這個(gè)分對(duì)于這個(gè)坐標(biāo)來(lái)說(shuō)，就是落子后該棋子放在坐標(biāo)處的價(jià)值。</p><p>　　m_Plajer[stepPut.i][stepPut.j][i]表示該坐標(biāo)處的分?jǐn)?shù)，若是玩家走棋

84、時(shí)的分?jǐn)?shù)則設(shè)為相反數(shù)，若是電腦走棋的分?jǐn)?shù)就設(shè)為本身。</p><p>　　4.2.5　防守策略</p><p>　　落子的考慮不單單要從進(jìn)攻考慮，還要從防守考慮。這一細(xì)節(jié)的實(shí)現(xiàn)其實(shí)就是讓計(jì)算機(jī)從玩家棋盤(pán)布局分析戰(zhàn)況，然后找出對(duì)玩家最有利的落子位置。</p><p>　　4.2.6　選取最佳落子</p><p>　　在循環(huán)結(jié)束的時(shí)候，就可以根據(jù)

85、攻、守兩方面的打分綜合地考慮落子位置了。代碼如下：</p><p>　　if ( ctemp + pscore > cscore )</p><p><b>　　{</b></p><p>　　cscore = ctemp + pscore;</p><p>　　besti = pi;</p><

86、;p>　　bestj = pj;</p><p><b>　　}</b></p><p><b>　　總結(jié)</b></p><p>　　剛開(kāi)始確定這個(gè)題目的時(shí)候，覺(jué)得挺簡(jiǎn)單的，因?yàn)樯蠈W(xué)期編過(guò)類(lèi)似的游戲，但是在編寫(xiě)程序的前兩天，寫(xiě)了不少的代碼，感覺(jué)很亂，沒(méi)有清楚的結(jié)構(gòu)和設(shè)計(jì)。后來(lái)我認(rèn)認(rèn)真真的探究了該游戲的架構(gòu)和模式，畫(huà)

87、出了游戲架構(gòu)圖，有了該架構(gòu)圖之后一切代碼就躍然紙上了。這讓我又一次體會(huì)到了寫(xiě)程序時(shí)不要急于編寫(xiě)代碼，即使程序結(jié)構(gòu)很清楚，也要先將它一點(diǎn)一點(diǎn)剖析，只有各個(gè)模塊都分析透徹了，寫(xiě)起程序來(lái)才不會(huì)感覺(jué)亂。</p><p>　　該程序中有關(guān)網(wǎng)絡(luò)套接字的部分之前沒(méi)接觸過(guò)，通過(guò)改程序的編寫(xiě)，又學(xué)到了一些新知識(shí)，增強(qiáng)了自學(xué)能力。游戲中人機(jī)對(duì)戰(zhàn)模式的核心是簡(jiǎn)單博弈樹(shù)算法，即每次只向前預(yù)測(cè)一步，沒(méi)有較高的“智商”。游戲中的消息有落子消

88、息、聊天消息和按鈕消息。</p><p>　　通過(guò)編寫(xiě)這個(gè)程序，我深刻體會(huì)到系統(tǒng)架構(gòu)和設(shè)計(jì)模式的重要性。即使是對(duì)于一個(gè)并不大的程序，代碼的組織都是非常重要的，因?yàn)檫@關(guān)系到日后的維護(hù)以及擴(kuò)展。更讓我認(rèn)清了即使對(duì)于幾千上萬(wàn)行的代碼，只要通過(guò)合適的方法組織起來(lái)，就會(huì)使程序員編寫(xiě)代碼時(shí)更加有條理，更加符合軟件工程的標(biāo)準(zhǔn)。</p><p><b>　　參考文獻(xiàn)</b></

89、p><p>　　《ASP五子棋在線游戲設(shè)計(jì)》</p><p>　　http://202.113.96.26/wlkc/rengongzhineng/rengongzhineng/kejian/AI/Ai/chapter3/33.htm</p><p>　　http://home.nuc.edu.cn/~titilima/readarticle.php?id=53<