五子棋畢業(yè)論文

1、<p>　　本科畢業(yè)論文（設(shè)計）</p><p>　　學(xué)院、系 計算機學(xué)院 </p><p>　　專業(yè)名稱 計算機科學(xué)與技術(shù) </p><p>　　年 級 </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>　　摘要 五子棋是一種益智游戲，它能增強玩家的思維能力，提高智力，而且趣味橫生，引人入勝。該版本的五子棋設(shè)置了兩類模式，單機模式和網(wǎng)絡(luò)模式。游戲中根據(jù)網(wǎng)絡(luò)連接標(biāo)志來判斷當(dāng)前是網(wǎng)絡(luò)對戰(zhàn)還是人機對戰(zhàn)。人機對戰(zhàn)模式使用的是簡單的博弈樹搜索算法，即只向前搜索一步，僅能預(yù)測到下一步會發(fā)生什么情況。網(wǎng)絡(luò)對戰(zhàn)模式中一方先建立游戲，作為游戲的服務(wù)器端，對方輸入服務(wù)器IP后加入游戲，作為客戶端。兩種模式都有悔棋功能

6、，網(wǎng)絡(luò)對戰(zhàn)還有認(rèn)輸、和棋請求的功能。發(fā)送五子棋消息主要發(fā)送落子坐標(biāo)，對方接受到消息后會調(diào)用相應(yīng)的函數(shù)處理接收的消息。該游戲還設(shè)置了聲音背景，當(dāng)玩家落子時會有落子的聲音，當(dāng)玩家勝了或輸了都會有背景聲音。另外該游戲還設(shè)置了聊天功能，戰(zhàn)績統(tǒng)計等基本游戲功能，以方便對弈雙方聊天和查看戰(zhàn)績記錄。</p><p>　　關(guān)鍵詞 人機對戰(zhàn)，網(wǎng)絡(luò)對戰(zhàn)，算法，消息 </p><p><b>　　目

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

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

9、t;p>　　2.2.1 游戲模式類主要成員變量說明10</p><p>　　2.2.2 游戲模式類主要成員函數(shù)說明10</p><p>　　第三章 消息機制13</p><p>　　3.1消息機制的架構(gòu)13</p><p>　　3.2各種消息說明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對方信息消息—

12、—MSG_INFORMATION15</p><p>　　第四章 人機對戰(zhàn)主要算法16</p><p>　　4.1 落子時是否構(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 計算機落子時的算法[6]19</p><p>　　4.2.1　計算落子時的所有獲勝可能性19</p><p>　　4.2.2　落子后計算得分19</p><p>　　4.2.3　查找棋

14、盤上的空位置20</p><p>　　4.2.4　為每一個可以落子的位置打分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>　　五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。它不僅能增強思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋最先發(fā)展于日本，流行于歐美。它既有現(xiàn)代休閑的明顯特征，又有古典哲學(xué)的高深學(xué)問；它既有簡單易學(xué)的特性，為人民群眾所喜聞樂見，又有深奧的技巧和高水平的國際性比賽。</p&

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

17、lient/Server 即C/S)模式；另一種是基于B/S(Brower/Server 即B/S)模式。C/S程序具有很好的交互性，功能很強大，但是客戶端必須安裝客戶端軟件，限制了其應(yīng)用； B/S模式的程序要求客戶端必須裝有瀏覽器，但是瀏覽器在安全性、交互性與功能方面有一些限制。目前網(wǎng)絡(luò)五子棋游戲大部分是在C/S模式下實現(xiàn)的，其功能不斷的完善和加強，而且五子棋的博弈算法研究達到了智能化的程度，并能實現(xiàn)了客戶端和服務(wù)器端的多線程交互性。

18、隨著網(wǎng)絡(luò)協(xié)議這一關(guān)鍵性問題得到了解決和完善使網(wǎng)絡(luò)游戲的設(shè)計和實現(xiàn)成為可能。對于眾多的基層網(wǎng)絡(luò)協(xié)議，Winsock(Windows Socket 即Winsock) 是五子棋游戲網(wǎng)絡(luò)連接的首選接口。Winsock是網(wǎng)絡(luò)編程接口，而不是協(xié)議。Winsock提供一個大家都很熟悉的接口，為實現(xiàn)網(wǎng)絡(luò)五子棋的功能得到了簡化[1]。單機版的五子棋游戲省去了網(wǎng)絡(luò)傳輸這一復(fù)雜的過程，但是需要有力的算法支撐，算法的性能決定程序的性能，也能決定游戲的難易程度

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

20、樂的一個重要內(nèi)容，是互聯(lián)網(wǎng)技術(shù)與互聯(lián)網(wǎng)經(jīng)營不可忽略的一個組成部分。電子娛樂業(yè)在全球被認(rèn)為是極有前景的一項產(chǎn)業(yè)。在國內(nèi)市場，游戲業(yè)潛力巨大，據(jù)統(tǒng)計顯示，中國在2006年一年時間內(nèi)就產(chǎn)生了大約340萬新生玩家，游戲人口的整體數(shù)量接近3750萬，其中90%是網(wǎng)絡(luò)游戲玩家。隨著互聯(lián)網(wǎng)的發(fā)展，網(wǎng)絡(luò)游戲的發(fā)展正成為新的互聯(lián)網(wǎng)公司的主要業(yè)務(wù)方向之一。網(wǎng)絡(luò)游戲還可以降低游戲開發(fā)成本，有利于游戲成本的回收。面對游戲產(chǎn)業(yè)發(fā)達國家的游戲企業(yè)有序、高效的進入中

21、國市場的現(xiàn)狀，國內(nèi)的游戲公司由于不能有效溝通合作，經(jīng)常容易陷入孤立無援、內(nèi)部競爭、競相抬價，最終被各個擊破的局面。近年來，中國的游戲產(chǎn)業(yè)特別是網(wǎng)絡(luò)游戲領(lǐng)域得到了長足發(fā)展，隨著政府監(jiān)管力度的不斷加強，各種法規(guī)、條例的不斷出臺，都表明中國游戲娛樂產(chǎn)業(yè)的春天就要到來了。因</p><p>　　1.3 開發(fā)環(huán)境及運行環(huán)境</p><p>　　1.3.1 開發(fā)環(huán)境</p><p&

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

57、></p><p>　　for ( i = 0; i < 11; i++ )//每一行從第一個位置掃描到第十一個位置</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個棋盤的位置。原因與水平方向一樣。程序如下：</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>　　判斷右下方向時，與左下方向相似，都需要從第一行判斷到第十一行，但是右下方向判斷時需要從第一列判斷到第十一列。程序如下：</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>　　以上四個判斷看起來寫的復(fù)雜，時間復(fù)雜度有些高，但是每一個都是很有限的判斷，計算機執(zhí)行起來的時間基本都是0ms。所以程序中也不用怎么優(yōu)化。</p><p>　　4.2 計算機落子時的算法[6]</p><p>　　4.2.1　計算落子時的所有獲勝可能性</p><p>　　

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

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

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

75、勝，則將對方在此坐標(biāo)的獲勝可能性置為false，并將對方此獲勝組合添加棋子數(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><p>　　在電腦每一次落子之前，都有掃描一下棋盤，找出空位置。程序中的SearchBlank就是負責(zé)該功能的。SearchBlank函數(shù)進行不重復(fù)的查找，對已查找過的坐標(biāo)進行標(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　為每一個可以落子的位置打分</p>

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

84、時的分?jǐn)?shù)則設(shè)為相反數(shù)，若是電腦走棋的分?jǐn)?shù)就設(shè)為本身。</p><p>　　4.2.5　防守策略</p><p>　　落子的考慮不單單要從進攻考慮，還要從防守考慮。這一細節(jié)的實現(xiàn)其實就是讓計算機從玩家棋盤布局分析戰(zhàn)況，然后找出對玩家最有利的落子位置。</p><p>　　4.2.6　選取最佳落子</p><p>　　在循環(huán)結(jié)束的時候，就可以根據(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>　　剛開始確定這個題目的時候，覺得挺簡單的，因為上學(xué)期編過類似的游戲，但是在編寫程序的前兩天，寫了不少的代碼，感覺很亂，沒有清楚的結(jié)構(gòu)和設(shè)計。后來我認(rèn)認(rèn)真真的探究了該游戲的架構(gòu)和模式，畫

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

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

89、p><p>　　《ASP五子棋在線游戲設(shè)計》</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<