五子棋畢業(yè)論文--人工智能課題

1、<p>　　本科畢業(yè)論文(設(shè)計(jì))</p><p>　　題 目五子棋AI算法和網(wǎng)絡(luò)通信的研究</p><p>　　學(xué)生姓名 </p><p>　　學(xué) 號(hào) </p><p>　　系 別 計(jì)算機(jī)科學(xué)系 &

2、lt;/p><p>　　年 級(jí) 2004 </p><p>　　專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　指導(dǎo)教師 </p><p>　　職 稱 講師

3、 </p><p>　　完成日期 2008-4-01 </p><p>　　五子棋AI算法和網(wǎng)絡(luò)通信的研究</p><p><b>　　摘要：</b></p><p>　　本系統(tǒng)將利用五子棋游戲作為研究對(duì)象，通過(guò)設(shè)計(jì)出一個(gè)能夠?qū)崿F(xiàn)兩種不同對(duì)戰(zhàn)模式的五子棋游戲。并對(duì)所涉及到的相關(guān)技

4、術(shù)進(jìn)行初步的探討，將重點(diǎn)放在人機(jī)對(duì)奕中AI算法研究方面。</p><p>　　游戲中提供兩種選擇模式：人機(jī)對(duì)戰(zhàn)和人人對(duì)戰(zhàn)。在人機(jī)對(duì)戰(zhàn)中玩家通過(guò)選擇不同的AI等級(jí)和電腦一決高下。在人人對(duì)戰(zhàn)中雙方可以進(jìn)行下棋，悔棋但要通過(guò)對(duì)方的同意。同時(shí)還可以實(shí)現(xiàn)在線聊天。AI的不同等級(jí)是以不同的搜索深度確定的。本系統(tǒng)以深度為2，3，4分別為初級(jí)，中級(jí)，高級(jí)。網(wǎng)絡(luò)對(duì)戰(zhàn)中則使用Socket實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)通信。</p><

5、;p>　　關(guān)鍵字：五子棋 、博奕AI算法、網(wǎng)絡(luò)通信</p><p>　　Research the AIof Renju and the Communication </p><p><b>　　Summary:</b></p><p>　　This system will use Renju as research objects,

6、passing to design a Renju game that can provide two kinds of dissimilarities to the play mode. to involve to of the related technique carry on the study of the first step, play more attention in the AI calculate way rese

7、arch aspect.</p><p>　　It provide two kinds of choice modes in the game:Person's machine to the war and the everyone to war.The player passes to choose the different AI grade and computer in person's

8、machine the rightness the war a definitely superiority.Both parties can carry on play chess in the everyone the rightness the war, the regrets chess but want to pass the approval of the other party.Can also carry out on-

9、line chat in the meantime.AI different grade with search the depth assurance differently.This system ta</p><p>　　Key word: Renju ,AI,networks </p><p><b>　　目 錄</b></p><p

10、>　　第一章 引言……………………………………………………………........................................4</p><p>　　1.1問(wèn)題背景……………………………………………………………………………4</p><p>　　1.2五子棋簡(jiǎn)介…………………………………………………………………………5</p><p>　　第

11、二章 詳細(xì)設(shè)計(jì)過(guò)程……………………………………………………………………………5</p><p>　　2.1．概要介紹…………………………………………………………………………….5</p><p>　　2.1.1 本程序介紹…………………………………………………………………5</p><p>　　2.1.2 本程序優(yōu)點(diǎn)…………………………………………………………………

12、5</p><p>　　2.2用軟件工程方法學(xué)指導(dǎo)開(kāi)發(fā)過(guò)程……………………………………………………5</p><p>　　2.2.1 問(wèn)題定義………………………………………………………………………6</p><p>　　2.2.2 可行性研究……………………………………………………………………7</p><p>　　2.2.3 需求分析………

13、………………………………………………………………8</p><p>　　2.2.4總體設(shè)計(jì)……………………………………………………………………….9</p><p>　　2.2.5 詳細(xì)設(shè)計(jì)………………………………………………………………………10</p><p>　　2.2.6 編碼和單元測(cè)試………………………………………………………………10</p>

14、<p>　　2.3用戶界面………………………………………………………………………………10</p><p>　　2.4系統(tǒng)解析………………………………………………………………………………11</p><p>　　2.4.1 界面部分.........................................................................

15、.....................................11</p><p>　　2.4.1.1 CFiveChessView的屬性……………………………………………..11</p><p>　　2.4.1.2 CFiveChessView的函數(shù)……………………………………………..12</p><p>　　2.4.2 通信部分…………………………

16、……………………………………………14</p><p>　　2.4.3 其他部分………………………………………………………………………15</p><p>　　2.4.3.1 CMatch---棋盤類…………………………………………………….16</p><p>　　2.4.3.2 CMessg—消息類…………………………………………………….17</p>

17、;<p>　　2.4.3.3 CComputer—電腦類…………………………………………………18</p><p>　　2.5．人機(jī)對(duì)戰(zhàn)中的AI算法………………………………………………………………18</p><p>　　2.5.1 極大極小樹(shù)…………………………………………………………………….19</p><p>　　2.5.2深度優(yōu)先搜索（DFS

18、）…………………………………………………………19</p><p>　　2.5.3 剪枝方法……………………………………………………………………….20</p><p>　　2.5.4 靜態(tài)估值函數(shù)………………………………………………………………….21</p><p>　　2.5.5 AI算法的分析和改進(jìn)………………………………………………………….21</

19、p><p>　　2.5.5.1算法分析………………………………………………………………..22</p><p>　　2.5.5.2 算法改進(jìn)………………………………………………………………..24</p><p>　　第三章 運(yùn)行測(cè)試…………………………………………………………………………………25</p><p>　　3.1 網(wǎng)絡(luò)部分……………

20、………………………………………………………………...25</p><p>　　3.2 人機(jī)部分……………………………………………………………………………...25</p><p>　　第四章 總結(jié)部分…………………………………………………………………………………27</p><p>　　4.1 系統(tǒng)總結(jié)……………………………………………………………………………..

21、.29</p><p>　　4.2 不足說(shuō)明……………………………………………………………………………...29</p><p>　　4.3 致謝…………………………………………………………………………………...28</p><p>　　參考文獻(xiàn)…………………………………………………………………………………..29</p><p><

22、b>　　第一章 引言</b></p><p><b>　　1.1 問(wèn)題背景</b></p><p>　　計(jì)算機(jī)運(yùn)算速度一直遵循著摩爾定律在飛速的發(fā)展，隨著這些技術(shù)的快速發(fā)展，使得大規(guī)模的運(yùn)算得以在很短的時(shí)間內(nèi)實(shí)現(xiàn)。正是基于這些技術(shù)，近年來(lái)各式各樣的棋類游戲軟件也紛紛出現(xiàn)在了電腦熒屏上，使得那些喜愛(ài)下棋，又常?？嘤跊](méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮。所以

23、如果能設(shè)計(jì)一款兼有人工智能和網(wǎng)絡(luò)聯(lián)機(jī)的五子棋軟件則對(duì)五子棋棋迷們來(lái)說(shuō)無(wú)疑是個(gè)“福音”。在人機(jī)智能方面其中戰(zhàn)勝過(guò)國(guó)際象棋世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說(shuō)服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛(ài)；</p><p>　　本系統(tǒng)將重點(diǎn)放在人工智能方面，采用不同的策略將人工中的智能分為不同的等級(jí)。選擇五子棋游戲作為本設(shè)計(jì)的課題，是因?yàn)樵撚螒虻囊?guī)則簡(jiǎn)單，所涉及的方向比較少。這

24、樣才能將問(wèn)題的重點(diǎn)放在人工智能解決上，而非規(guī)則的解決，有更多的精力放在高效算法和通信過(guò)程的優(yōu)化。希望能通過(guò)本次系統(tǒng)的設(shè)計(jì)，整合所學(xué)的知識(shí)，實(shí)現(xiàn)從理論到實(shí)踐上的升華。</p><p><b>　　1.2 五子棋簡(jiǎn)介</b></p><p>　　下面就五子棋的背景和規(guī)則做一些簡(jiǎn)單的介紹。</p><p>　　五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一

25、。現(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five in a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。       五子棋不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑的明顯特征“短、平、快”，又有古典哲學(xué)的高深學(xué)問(wèn)“陰陽(yáng)易理”；它既有簡(jiǎn)單易學(xué)的

26、特性，為人民群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧和高水平的國(guó)際性比賽；它的棋文化源淵流長(zhǎng)，具有東方的神秘和西方的直觀；既有“場(chǎng)”的概念，亦有“點(diǎn)”的連接。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。</p><p>　　五子棋的規(guī)則如下：棋盤：采用同圍棋盤一樣的15 路或19 路線的棋盤，為了減小問(wèn)題的規(guī)模，本系統(tǒng)將采用15 路線的棋盤。下法：兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個(gè)無(wú)子的交叉點(diǎn)落子。無(wú)子的交叉點(diǎn)又被稱

27、為空點(diǎn)。輸贏判斷：黑、白雙方有一方的5個(gè)棋子在橫、豎或斜方向上連接成一線即為該方贏。</p><p>　　第二章 詳細(xì)設(shè)計(jì)過(guò)程</p><p><b>　　2.1概要介紹</b></p><p>　　2.1.1本程序介紹</p><p>　　游戲中提供兩種選擇模式：人機(jī)對(duì)戰(zhàn)和人人對(duì)戰(zhàn)。在人機(jī)對(duì)戰(zhàn)中玩家通過(guò)選擇不同的等級(jí)

28、和電腦一決高下，可以向后悔棋。在人人對(duì)戰(zhàn)中雙方通過(guò)選擇一方作為服務(wù)器，通過(guò)彈出對(duì)話框設(shè)置本地應(yīng)用程序監(jiān)聽(tīng)端口，而另外一方則作為客戶端，通過(guò)連接服務(wù)器選項(xiàng)，在彈出的對(duì)話框中設(shè)置要連接的服務(wù)器的IP地址和端口號(hào)。當(dāng)雙方都提示連接成功后，兩方才可以進(jìn)行下棋。如要悔棋則需要通過(guò)對(duì)方的同意。同時(shí)還可以實(shí)現(xiàn)在線聊天。AI的不同等級(jí)是以不同的搜索深度確定的。本系統(tǒng)以深度為2，3，4分別為初級(jí)，中級(jí)，高級(jí)。網(wǎng)絡(luò)對(duì)戰(zhàn)中則使用Socket實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)通信。&

29、lt;/p><p>　　2.1.2本程序特點(diǎn)</p><p>　　五子棋游戲程序由于規(guī)則簡(jiǎn)單操作簡(jiǎn)便等特點(diǎn)，自然就成為程序員對(duì)人工智能研究的首選對(duì)象。所以網(wǎng)絡(luò)上關(guān)于這類的程序很多，但是由于主要都是采用搜索窮舉技術(shù)作為解決方案，這將使得問(wèn)題的規(guī)模變的很龐大如當(dāng)搜索深度為3時(shí)，每走一步電腦在將最壞的情況下需要搜索的點(diǎn)將達(dá)到225*225*225=11390625個(gè)。即使采用的剪枝技術(shù)，其某些點(diǎn)的響

30、應(yīng)的時(shí)間也是讓人無(wú)法忍受的，如開(kāi)局時(shí)，因?yàn)檫@個(gè)時(shí)候每個(gè)點(diǎn)都是空的，沒(méi)有可以剪枝的點(diǎn)，必須遍歷真?zhèn)€盤面，所以很耗時(shí)間，大約需要30多秒的時(shí)間，這個(gè)顯然是不可接受的。為了程序設(shè)計(jì)和玩家的忍受時(shí)間的需要。不得不減小深度，所以絕大部分都采用深度為2的檢索，很明顯深度越低系統(tǒng)的智力也相對(duì)的降低，需要代價(jià)的。</p><p>　　本程序的一個(gè)主要特點(diǎn)是，采用了高效的優(yōu)化方法，使得在相同的搜索規(guī)模中所花費(fèi)的計(jì)算時(shí)間大幅度的減小

31、。響應(yīng)時(shí)間明顯得到提高。即使搜索深度達(dá)到4的時(shí)候，其響應(yīng)時(shí)間在絕大部分的情況下還是可以接受的。</p><p>　　2.2用軟件工程方法學(xué)指導(dǎo)開(kāi)發(fā)過(guò)程</p><p>　　在小規(guī)模的程序開(kāi)發(fā)中，很多人都不太注意用軟件工程的方法學(xué)設(shè)計(jì)系統(tǒng)，包括我本人，在開(kāi)發(fā)一些小功能程序時(shí)總是隨心所欲的添加需求：有時(shí)為了類與類之間的通信需要，往類中添加不相關(guān)的變量，直接修改變量的屬性或者聲明一大堆的全局變量

32、。雖然最后系統(tǒng)都能夠”笨重”的運(yùn)行起來(lái)，但這是明顯違背程序設(shè)計(jì)方法學(xué)?？删S護(hù)行，易修改性嚴(yán)重降低。后期如果需要添加某些功能的時(shí)候?qū)⒆兊檬值姆爆??？梢韵胂笤诙鄠€(gè)團(tuán)隊(duì)一起開(kāi)發(fā)的大型系統(tǒng)中這種粗陋的開(kāi)發(fā)方法根本是行不通的。所以要養(yǎng)成用正確的方法指導(dǎo)開(kāi)發(fā)過(guò)程的習(xí)慣，雖然有時(shí)候看起來(lái)有點(diǎn)大題小做，但我覺(jué)的這是作為一名合格的軟件開(kāi)發(fā)工程師所必須掌握的技能。通過(guò)長(zhǎng)期不斷的積累才能增加我們參與大型項(xiàng)目開(kāi)發(fā)的能力。</p><p&g

33、t;　　下面對(duì)軟件工程作下簡(jiǎn)單的介紹：</p><p>　　軟件工程一直以來(lái)都缺乏一個(gè)統(tǒng)一的定義，很多學(xué)者、組織機(jī)構(gòu)都分別給出了自己的定義：</p><p>　　Boehm：運(yùn)用現(xiàn)代科學(xué)技術(shù)知識(shí)來(lái)設(shè)計(jì)并構(gòu)造計(jì)算機(jī)程序及為開(kāi)發(fā)、運(yùn)行和維護(hù)這些程序所必需的相關(guān)文件資料。 IEEE：軟件工程是開(kāi)發(fā)、運(yùn)行、維護(hù)和修復(fù)軟件的系統(tǒng)方法。 Fritz Bauer：建立并使用完善的工程

34、化原則，以較經(jīng)濟(jì)的手段獲得能在實(shí)際機(jī)器上有效運(yùn)行的可靠軟件的一系列方法。 目前比較認(rèn)可的一種定義認(rèn)為：軟件工程是研究和應(yīng)用如何以系統(tǒng)性的、規(guī)范化的、可定量的過(guò)程化方法去開(kāi)發(fā)和維護(hù)軟件，以及如何把經(jīng)過(guò)時(shí)間考驗(yàn)而證明正確的管理技術(shù)和當(dāng)前能夠得到的最好的技術(shù)方法結(jié)合起來(lái)。 </p><p>　　我個(gè)人對(duì)軟件工程理解是，它一種工程上的方法學(xué)，用一種有步驟，有計(jì)劃的正確有效方法指導(dǎo)開(kāi)發(fā)過(guò)程。</p>

35、<p>　　軟件工程的精髓可以用著名的軟件工程專家B.Boehm的七條基本原理來(lái)概括。</p><p>　　（1）用分階段的生存周期計(jì)劃進(jìn)行嚴(yán)格的管理。（2）堅(jiān)持進(jìn)行階段評(píng)審。（3）實(shí)行嚴(yán)格的產(chǎn)品控制。（4）采用現(xiàn)代程序設(shè)計(jì)技術(shù)。（5）軟件工程結(jié)果應(yīng)能清楚地審查。（6）開(kāi)發(fā)小組的人員應(yīng)該少而精。（7）承認(rèn)不斷改進(jìn)軟件工程實(shí)踐的必要性。</p><p>　　目前絕大部

36、分的軟件方法都可以從這七條基本推倒出來(lái)。B.Boehm指出，遵循前六條基本原理，能夠?qū)崿F(xiàn)軟件的工程化生產(chǎn)；按照第七條原理，不僅要積極主動(dòng)地采納新的軟件技術(shù)，而且要注意不斷總結(jié)經(jīng)驗(yàn)。</p><p>　　下面扼要介紹軟件生存周期在本次每個(gè)階段的基本任務(wù)</p><p><b>　　2.2.1問(wèn)題定義</b></p><p>　　問(wèn)題定義的一個(gè)的關(guān)

37、鍵問(wèn)題是“要解決的問(wèn)題是什么”，這個(gè)是這個(gè)階段必須要明確要回答的問(wèn)題。在沒(méi)將問(wèn)題定義好，試圖準(zhǔn)備下個(gè)階段的任務(wù)。這明顯是不成熟，甚至不可能的事。</p><p><b>　　選擇操作</b></p><p><b>　　調(diào)用</b></p><p><b>　　圖2.1 系統(tǒng)模型</b></p&

38、gt;<p>　　本次系統(tǒng)設(shè)計(jì)中首先明確了需要解決的問(wèn)題是五子棋AI算法和網(wǎng)絡(luò)通信的研究，基本的要求是設(shè)計(jì)一款能夠?qū)崿F(xiàn)網(wǎng)絡(luò)和單機(jī)對(duì)戰(zhàn)的五子棋游戲，提供一些基本的操作如退出系統(tǒng)，向后悔棋等操作，重點(diǎn)是放在AI算法和網(wǎng)絡(luò)通信的研究。而并不是美工設(shè)計(jì)，也不是為了提供各種操作豐富的接口。主要是通過(guò)這種可視化的界面探討AI，當(dāng)然增加可玩性和美工會(huì)給系統(tǒng)潤(rùn)色不少。</p><p>　　上面只是很粗略的明確大概的

39、方向，嚴(yán)格按照軟件工程的方法這個(gè)階段需要生產(chǎn)一份書面報(bào)告。需要通過(guò)對(duì)系統(tǒng)的實(shí)際用戶訪問(wèn)調(diào)查，扼要地寫出他對(duì)問(wèn)題的理解，并在用戶和使用部門負(fù)責(zé)人的會(huì)議上認(rèn)真討論這份書面報(bào)告，澄清含糊不精的地方，改正理解不正確的地方，最后得出一份雙方都滿意的文檔。本系統(tǒng)的需求很少也很明顯了。</p><p>　　2.2.2可行性研究</p><p>　　這個(gè)階段要回答的關(guān)鍵問(wèn)題：“對(duì)于上一個(gè)階段所確定的問(wèn)題是

40、否可行？”為了回答這個(gè)問(wèn)題，我們需要進(jìn)行一次大大壓縮和簡(jiǎn)化了的系統(tǒng)分析和設(shè)計(jì)的過(guò)程，也就是在較抽象的高層次上進(jìn)行的分析和設(shè)計(jì)的過(guò)程。</p><p>　　可行性研究應(yīng)該比較簡(jiǎn)短，這個(gè)階段的任務(wù)不是具體解決問(wèn)題，而是研究問(wèn)題的范圍，探索這個(gè)問(wèn)題是否值得去解，是否有可行的解決辦法?！　】尚行匝芯繎?yīng)該比較簡(jiǎn)短，這個(gè)階段的任務(wù)不是具體解決問(wèn)題，而是研究問(wèn)題的范圍，探索這個(gè)問(wèn)題是否值得去解，是否有可行的解決辦法?？尚行?/p>

41、研究以后的那些階段將需要投入要多的人力物力。及時(shí)中止不值得投資的工程項(xiàng)目，可以避免更大的浪費(fèi)。</p><p>　　根據(jù)這些基本的概念，我在技術(shù)上主要是通過(guò)相關(guān)文檔資料的查找后確定可行性，憑著大學(xué)期間打下厚實(shí)的專業(yè)科基礎(chǔ)，特別是數(shù)據(jù)結(jié)構(gòu)和算法，能夠在這段時(shí)間內(nèi)理解通透并應(yīng)該有所改進(jìn)，后來(lái)證明是對(duì)的。利用剩下時(shí)間也應(yīng)該來(lái)說(shuō)也比較充裕的。經(jīng)濟(jì)上暫不考慮。</p><p>　　下面主要從技術(shù)上進(jìn)

42、行分析：</p><p>　　工具： VC++是一款經(jīng)久不衰的開(kāi)發(fā)工具，它代表了基于Windows的C++語(yǔ)言產(chǎn)品，完美地集成了傳統(tǒng)的編程工具，也集成了Windows中特殊的工具箱，如MFC（Microsoft Foundation Classes）和Windows資源編輯器（App Studio）。另外還加入了幾種新工具，如輪廓應(yīng)用程序生成器（App Wizard）、C++類管理器（Class Wizard）

43、和類瀏覽器（Class Browser），以及各種各樣為開(kāi)發(fā)Microsoft Windows下的C/C++程序而設(shè)計(jì)的工具，MFC類庫(kù)為我們提供了豐富的類資源。所以VC++是最好的選擇。</p><p>　　本程序?qū)⒉捎肰C＋＋的單文檔的視圖框架，這樣可以簡(jiǎn)化程序的開(kāi)發(fā)。網(wǎng)絡(luò)通信方面將從MFC封裝socket的類CSocket實(shí)現(xiàn)點(diǎn)對(duì)點(diǎn)通信。</p><p>　　算法： 在這圖論搜索技術(shù)

44、這方面，前人已有很成熟的算法。如粗糙的有深度優(yōu)先算法(DFS)和廣度優(yōu)先算法(BFS)這兩個(gè)基本的算法，關(guān)鍵需要解決的是能夠設(shè)計(jì)出一種高效的剪枝函數(shù)，減小搜索問(wèn)題的規(guī)模。目前博弈類游戲中的人工智能基本都采用極大極小值方法這對(duì)我來(lái)說(shuō)是個(gè)挑戰(zhàn)，而剪枝的則采用Alpha-Beta，通過(guò)豐富的文檔資料初步了解到這些技術(shù)已經(jīng)很成熟了。我有信心能解決好這個(gè)問(wèn)題。</p><p>　　Socket：聯(lián)機(jī)對(duì)戰(zhàn)中的數(shù)據(jù)傳輸量很少，

45、利用Socket編程是在好不過(guò)了，而且在這方面的掌握程度不存在有問(wèn)題。</p><p>　　所以通過(guò)對(duì)以上關(guān)鍵問(wèn)題的分析，可以很明確了該系統(tǒng)的可行性。這個(gè)階段的任務(wù)告一段落了?？梢灾窒乱粋€(gè)階段的任務(wù)了。軟件工程很強(qiáng)調(diào)文檔驅(qū)動(dòng)開(kāi)發(fā)過(guò)程，只有完成了上個(gè)階段的工作后，才能開(kāi)始下一步驟，這是傳統(tǒng)的瀑布開(kāi)發(fā)方法。當(dāng)然不同的開(kāi)發(fā)模型，過(guò)程也會(huì)有所區(qū)別，大體上都遵循軟件工程的這個(gè)步驟。這個(gè)階段應(yīng)該要產(chǎn)生一份《可行性分析報(bào)告》

46、。</p><p>　　2.2.3 需求分析</p><p>　　這個(gè)階段的任務(wù)仍然不是具體地解決問(wèn)題，而是準(zhǔn)確地確定“為了解決這個(gè)問(wèn)題，目標(biāo)系統(tǒng)需要做什么”，主要是確定目標(biāo)系統(tǒng)必須具備哪些功能。</p><p>　　用戶了解他們所面對(duì)的問(wèn)題，知道必須做什么，但是通常不能完整準(zhǔn)確地表達(dá)出他們的要求，更不知道怎樣利用計(jì)算機(jī)解決他們的問(wèn)題；軟件開(kāi)發(fā)人員知道怎樣使用軟件實(shí)

47、現(xiàn)人們的要求，但是對(duì)特定用戶的具體要求并不完全清楚。因此在需求分析階段必須和用戶密切配合，充分交流信息，以得出經(jīng)過(guò)用戶確認(rèn)的系統(tǒng)邏輯模型。通常用數(shù)據(jù)流圖、數(shù)據(jù)字典和簡(jiǎn)要的算法描述表示系統(tǒng)的邏輯模型。</p><p>　　在設(shè)計(jì)本系統(tǒng)時(shí)考慮到用戶需要的是一個(gè)操作簡(jiǎn)便界面簡(jiǎn)單的游戲軟件。同時(shí)要提供人機(jī)和人人這樣的功能。特別是人機(jī)部分，要考慮到不同級(jí)別的用戶。電腦智能不能太低需要有一定的智能下棋功能。</p>

48、;<p>　　本系統(tǒng)用提供平常下棋的一些步驟操作。</p><p>　　網(wǎng)絡(luò)聯(lián)機(jī)：提供向服務(wù)器一方發(fā)出連接請(qǐng)求的操作，并從彈出的對(duì)話框中設(shè)置IP和端口號(hào)；服務(wù)器提供監(jiān)聽(tīng)的操作同樣在彈出的對(duì)話框中設(shè)置端口號(hào)。任何一方需要悔棋請(qǐng)求，則必須通過(guò)對(duì)方的確定后方可。連接成功后雙方可以開(kāi)始游戲，決定在界面中提供在線聊天功能。用戶可以通過(guò)主界面的上的菜單操作執(zhí)行響應(yīng)的功能和請(qǐng)求，如向?qū)Ψ桨l(fā)處向后悔棋一步，重新開(kāi)始

49、，認(rèn)輸?shù)?，另一方在接到?qǐng)求后決定接受或拒絕。</p><p>　　人機(jī)對(duì)戰(zhàn)：選擇和電腦對(duì)弈的等級(jí)操作，同樣也可以執(zhí)行網(wǎng)絡(luò)聯(lián)機(jī)的悔棋等功能，只是因?yàn)槭侨藱C(jī)所以無(wú)需通過(guò)確認(rèn)。</p><p><b>　　2.2.4總體設(shè)計(jì)</b></p><p>　　這個(gè)階段必須回答的關(guān)鍵問(wèn)題是：“概括地說(shuō)，應(yīng)該如何解決這個(gè)問(wèn)題？” 　　首先，應(yīng)該考慮幾種可能的解

50、決方案。如，目標(biāo)系統(tǒng)的一些主要功能是用計(jì)算機(jī)自動(dòng)完成還是用人工完成；如果使用計(jì)算機(jī)，那么是使用批處理方式還是人機(jī)交互方式；信息存儲(chǔ)使用傳統(tǒng)的文件系統(tǒng)還是數(shù)據(jù)庫(kù)……。通常至少應(yīng)該考慮下述幾類可能的方案：</p><p>　　低成本的解決方案。系統(tǒng)只能完成最必要的工作，不能多做一點(diǎn)額處的工作。本系統(tǒng)的最基本要求就是能夠?qū)崿F(xiàn)必要的操作，其他額外的一些工作在后面完成</p><p>　　中等成本的

51、解決方案。這樣的系統(tǒng)不僅能夠很好地完成預(yù)定的任務(wù)，使用起來(lái)很方便，而且可能還具有用戶沒(méi)有具體指定的某些功能和特點(diǎn)。雖然用戶沒(méi)有提出這些具體要求，但是系統(tǒng)分析員根據(jù)自己的知識(shí)和經(jīng)驗(yàn)斷定，這些附加的能力在實(shí)踐中將證明是很有價(jià)值的。</p><p>　　這個(gè)成本方案在完成上面的低成本方案后添加的。如增加保存棋局，美化界面，實(shí)現(xiàn)觀看電腦與電腦之間的對(duì)戰(zhàn)等功能。</p><p>　　高成本的“十全十

52、美”的系統(tǒng)。這樣的系統(tǒng)具有用戶可能希望有的所有功能和特點(diǎn)。</p><p>　　結(jié)構(gòu)設(shè)計(jì)的一條基本原理就是程序應(yīng)該模塊化，也就是一個(gè)大程序應(yīng)該由許多規(guī)模適中的模塊按合理的層次結(jié)構(gòu)組織而成?？傮w設(shè)計(jì)階段的第二項(xiàng)主要任務(wù)就是設(shè)計(jì)軟件的結(jié)構(gòu)，也就是確定程序由哪些模塊組成以及模塊間的關(guān)系。通常用層次圖或結(jié)構(gòu)圖描繪軟件的結(jié)構(gòu)。</p><p><b>　　2.2結(jié)構(gòu)圖</b>&

53、lt;/p><p><b>　　2.2.5詳細(xì)設(shè)計(jì)</b></p><p>　　這個(gè)階段的具體內(nèi)容我把放到模塊分析的章節(jié)去分析。下面僅作個(gè)簡(jiǎn)要的概述。</p><p>　　總體設(shè)計(jì)階段以比較抽象概括的方式提出了解決問(wèn)題的辦法。詳細(xì)設(shè)計(jì)階段的任務(wù)就是把解法具體化，也就是回答下面這個(gè)關(guān)鍵問(wèn)題：“應(yīng)該怎樣具體地實(shí)現(xiàn)這個(gè)系統(tǒng)呢？”</p>&

54、lt;p>　　這個(gè)階段的任務(wù)還不是編寫程序，而是設(shè)計(jì)出程序的詳細(xì)規(guī)格說(shuō)明。這種規(guī)格說(shuō)明的作用很類似于其他工程領(lǐng)域中工程師經(jīng)常使用的工程藍(lán)圖，它們應(yīng)該包含必要的細(xì)節(jié)，程序員可以根據(jù)它們寫出實(shí)際的程序代碼。</p><p>　　2.2.6編碼和單元測(cè)試　　這個(gè)階段的關(guān)鍵任務(wù)是根據(jù)以上階段分析的軟件模型，編寫各個(gè)功能模塊。 要注意的是程序的擴(kuò)張性和可讀性。以便以后軟件的升級(jí)修改。同時(shí)要仔細(xì)的測(cè)試每個(gè)功能

55、編寫好的功能模塊。</p><p>　　這個(gè)內(nèi)容也放到下面編譯運(yùn)行章節(jié)去?！?lt;/p><p><b>　　2.3 用戶界面</b></p><p>　　用戶界面在整個(gè)系統(tǒng)的使用中起著很大的作用，它將直接影響到用戶對(duì)軟件的評(píng)價(jià)。界面是人機(jī)交互的平臺(tái)，所以在設(shè)計(jì)時(shí)盡量往用戶方考慮。提供操作簡(jiǎn)便和友好界面。</p><p>　

56、　以下是系統(tǒng)使用的界面，感覺(jué)還有很多地方需要改進(jìn)和完善。但是總體來(lái)說(shuō)已經(jīng)能夠基本滿足系統(tǒng)的需要。擁有較為良好的交互功能。</p><p>　　圖 2.3 用戶界面</p><p><b>　　2.4 系統(tǒng)解析</b></p><p>　　下面結(jié)合操作對(duì)各個(gè)功能模塊設(shè)計(jì)進(jìn)行相應(yīng)的解析。</p><p>　　2.4.1 界

57、面部分</p><p>　　這部分我采用的是vc++提供的單文檔視圖框架，該框架為我們生成了Window應(yīng)用程序最基本的界面無(wú)需自己動(dòng)手編寫復(fù)雜的菜單模塊等代碼，只要在基于這個(gè)框架的基礎(chǔ)上對(duì)相應(yīng)的功能進(jìn)行補(bǔ)充和擴(kuò)展。</p><p>　　2.4.1.1 CFiveChessView的屬性</p><p>　　CView 類是該框架中一個(gè)很重要的類，它提供了大部分的交

58、互功能，如菜單，鼠標(biāo)左鍵等消息的的響應(yīng)。下面對(duì)本系統(tǒng)中的CFiveChessView類的幾個(gè)重點(diǎn)內(nèi)容做個(gè)介紹。</p><p>　　m_ListenSocket和m_ClientSocket變量，這兩個(gè)類成員均是派生自CSocket類，前者定義為一個(gè)服務(wù)端的套接字（Socket）變量，它用于服務(wù)端負(fù)責(zé)監(jiān)聽(tīng)，當(dāng)它收到某個(gè)主機(jī)發(fā)來(lái)的連接請(qǐng)求時(shí)，將m_ClientSocket和遠(yuǎn)程主機(jī)端的套接字關(guān)聯(lián)。這樣雙方可以進(jìn)行通

59、信了。</p><p>　　CMatch m_match 這是一個(gè)棋盤類的一個(gè)變量。關(guān)于這個(gè)類將在后面做詳細(xì)的講解，將棋盤單獨(dú)抽象為一個(gè)類，并向外部提供棋盤的一些操作。這比較符合面向?qū)ο缶幊獭?lt;/p><p>　　CComputer m_computer 這也是一個(gè)很重要的成員，它將人機(jī)對(duì)戰(zhàn)中的電腦方抽象成一個(gè)類，該類提供不同的等級(jí)的下棋功能。根據(jù)當(dāng)前棋盤的局勢(shì)給出最佳的下棋點(diǎn)。該類也將

60、在后面給出詳細(xì)的介紹。</p><p>　　m_mode 這是用于標(biāo)記當(dāng)前系統(tǒng)的是屬于哪種模式人機(jī)或者聯(lián)機(jī)，當(dāng)它是人機(jī)的狀態(tài)時(shí)值為P_PK_C（枚舉類型的值），同樣當(dāng)它是聯(lián)機(jī)狀態(tài)就為P_PK_P。若當(dāng)前沒(méi)有選擇的狀態(tài)值就為NOCHOOSE，表示當(dāng)前還為進(jìn)行選擇。</p><p>　　m_who 用于標(biāo)記使用棋子的類型，1代表黑色，2代表白色。</p><p>　　m

61、_turn 這是聯(lián)機(jī)中用于標(biāo)識(shí)當(dāng)前是輪到哪方下棋了。</p><p>　　m_bWin標(biāo)識(shí)本機(jī)方贏的狀態(tài)。</p><p>　　m_bOver 標(biāo)識(shí)游戲是否已經(jīng)結(jié)束。</p><p>　　2.4.1.2 CFiveChessView的函數(shù)</p><p>　　以下的五個(gè)變量均為CBitmap類對(duì)象，m_lastwhitechess加載的是位圖

62、。m_whitechess加載的是位圖，m_lastblackchess加載 m_blackchess加載 位圖 ，m_black 加載位圖。m_board加載的是棋盤位圖。</p><p>　　下面對(duì)該視圖類一些重要的成員函數(shù)做些介紹。</p><p>　　DrawWhiteChess(int i,int j,CDC *pDC);</p><p>　　DrawB

63、lackChess(int i,int j,CDC *pDC);</p><p>　　這兩個(gè)函數(shù)根據(jù)傳遞進(jìn)來(lái)的參數(shù)，確定要在棋盤的哪個(gè)位置和畫的類型，如當(dāng)該點(diǎn)是最近下的一個(gè)棋子，則把它用m_lastblackchess或m_lastwhitechess加載的位圖貼出來(lái)。否則使用m_whitechess或m_blackchess位圖。</p><p>　　這兩個(gè)函數(shù)是在OnDraw(CDC*

64、 pDC)函數(shù)中被調(diào)用的。這個(gè)函數(shù)在窗口初始化或者需要重繪的時(shí)候被調(diào)用的。系統(tǒng)會(huì)發(fā)出一個(gè)重繪消息，調(diào)用OnPaint()，在這個(gè)函數(shù)中又調(diào)用了OnDraw（），將整個(gè)界面畫出來(lái)。</p><p>　　OnLButtonDown(UINT nFlags, CPoint point)是該類中一個(gè)非常重要的函數(shù)，用戶的下棋的操作都是由這個(gè)函數(shù)完成的。當(dāng)左鍵被點(diǎn)擊的時(shí)，Window會(huì)產(chǎn)生一個(gè)左鍵消息放到該應(yīng)用程序的消息隊(duì)

65、列中，而該應(yīng)用系統(tǒng)取出消息并通過(guò)消息映射確定調(diào)用的函數(shù)，最后由操作系統(tǒng)調(diào)用該函數(shù)。我們可以將其簡(jiǎn)化理解為用戶點(diǎn)擊了左鍵后，該函數(shù)就響應(yīng)了該操作。</p><p>　　該函數(shù)首先判讀游戲是否已經(jīng)結(jié)束，如果是那么會(huì)彈出對(duì)話框詢問(wèn)用戶是否要繼續(xù)。</p><p>　　如果沒(méi)結(jié)束的話，并且當(dāng)前的模式不是NOCHOOSE則根據(jù)鼠標(biāo)的坐標(biāo)計(jì)算出該點(diǎn)對(duì)應(yīng)的是棋盤的哪個(gè)位置，把它保存起來(lái)。若是則提醒用戶選

66、擇模式。</p><p>　　然后判讀當(dāng)前的下棋模式，進(jìn)入到響應(yīng)的模塊中，在模塊中需要判讀該點(diǎn)是否是合法的，若不是則返回。</p><p>　　人機(jī)模式：判讀該點(diǎn)是否合法，如果是則更新該點(diǎn)（該點(diǎn)區(qū)域重繪），并且記錄下該點(diǎn)作為最新下棋點(diǎn)。接著判斷該點(diǎn)是否能行成五連子。如果不能，則調(diào)用m_computer 成員的響應(yīng)等級(jí)算法，給出電腦的棋子的坐標(biāo)。同樣需要判斷該點(diǎn)能否行成五連子，最后更新該點(diǎn)。

67、</p><p>　　聯(lián)機(jī)模式：判讀是否輪到己方下棋，若是則判斷該點(diǎn)是否合法，若是修改相應(yīng)的狀態(tài)變量，并且發(fā)送消息棋盤狀態(tài)給對(duì)方。同樣判斷是否行成了五連子。</p><p>　　下面再介紹一些菜單上的消息響應(yīng)函數(shù)。</p><p>　　void OnSetclient()------連接服務(wù)器</p><p>　　該函數(shù)用于響應(yīng)菜單項(xiàng)游戲的子

68、菜單下的連接服務(wù)器選項(xiàng)，響應(yīng)后將彈出</p><p>　　如下的對(duì)話框，要求用戶設(shè)置好需要連接的服務(wù)器端的IP和監(jiān)聽(tīng)端口。</p><p>　　圖 2.4 連接服務(wù)器</p><p>　　void OnSetserver()------開(kāi)啟服務(wù)器</p><p>　　該函數(shù)也是用于響應(yīng)游戲菜單下的開(kāi)啟服務(wù)器選項(xiàng)，點(diǎn)擊后也彈出如下要求設(shè)置的監(jiān)聽(tīng)

69、端口。</p><p>　　圖 2.5 開(kāi)啟服務(wù)器</p><p>　　void OnPrimary()--------初級(jí)選項(xiàng)</p><p>　　void OnSecondary();-------中級(jí)選項(xiàng)</p><p>　　void OnSenior();---------高級(jí)選項(xiàng)</p><p>　　這三個(gè)函

70、數(shù)響應(yīng)用戶要選擇人機(jī)對(duì)戰(zhàn)中電腦的等級(jí)，點(diǎn)擊該菜單將m_computer的成員m_grade分別設(shè)置成1，2或3，并且模式變量m_mode被設(shè)置成P_PK_C.</p><p>　　void OnRollback();--------悔棋選項(xiàng)</p><p>　　悔棋選項(xiàng)分為兩個(gè)部分：一種是人機(jī)對(duì)戰(zhàn)狀態(tài)中的悔棋，該模式下用戶只需點(diǎn)擊該選項(xiàng)，棋局將回退到上一個(gè)狀態(tài)。另一種是；聯(lián)機(jī)對(duì)戰(zhàn)的模式，用

71、戶在該模式下選擇該選項(xiàng)，發(fā)出請(qǐng)求消息。若對(duì)方同意悔棋，同樣將回退到上一個(gè)棋局狀態(tài)。</p><p>　　void OnRestart();---------重新開(kāi)始</p><p>　　該函數(shù)和以上提到的OnRollback（）很相似，事實(shí)上是他的特殊情況，如果將當(dāng)前的回退的參數(shù)改為目前已經(jīng)走的步數(shù)。那么就轉(zhuǎn)化為重新開(kāi)始了。這就提高了該類的簡(jiǎn)潔性，很值得提倡的一種的方法。</p>

72、;<p>　　到此基本上把CFiveChessView類的關(guān)鍵部分講解完了。還剩下的其他的一些內(nèi)容需要結(jié)合到其他類中。</p><p>　　2.4.2 通信部分</p><p>　　下面對(duì)Winsock編程做個(gè)講解，部分內(nèi)容引用自網(wǎng)絡(luò)。 </p><p>　　微軟的MFC把復(fù)雜的WinSock API函數(shù)封裝到類里，這使得編寫網(wǎng)絡(luò)應(yīng)用程序更容易。CAs

73、yncSocket類逐個(gè)封裝了WinSock API，為高級(jí)網(wǎng)絡(luò)程序員 提供了更加有力而靈活的方法。這個(gè)類基于程序員了解網(wǎng)絡(luò)通訊的假設(shè)，目的是為了在MFC中使用WinSock，程序員有責(zé)任處理諸如阻塞、字節(jié)順序和在Unicode與MBCS 間轉(zhuǎn)換字符的任務(wù)。為了給程序員提供更方便的接口以自動(dòng)處理這些任務(wù)，MFC給出 了CSocket類，這個(gè)類是由CAsyncSocket類繼承下來(lái)的，它提供了比CAsyncSocket更高層的WinSoc

74、k API接口。Csocket類和CsocketFile類可以與Carchive類一起合作來(lái)管理發(fā)送和接收的數(shù)據(jù)，這使管理數(shù)據(jù)收發(fā)更加便利。CSocket對(duì)象提供阻塞模式，這對(duì)于Carchive的同步操作是至關(guān)重要的。阻塞函數(shù)（如Receive()、Send()、ReceiveFrom()、SendTo() 和Accept()）直到操作完成后才返回控制權(quán)，因此如果需要低層控制和高效率，就使用CasyncSock類；如果需要方便，則可使用

75、Csocket類。</p><p>　　使用CSocket對(duì)象涉及CArchive和CSocketFile 類對(duì)象。以下介紹的針對(duì)字節(jié)流型套接字的操作步驟中，只有第3步對(duì)于客戶方和服務(wù)方操作是不同的，其他步驟都相同。 1、構(gòu)造一個(gè)CSocket對(duì)象。 2、使用這個(gè)對(duì)象的Create（）成員函數(shù)產(chǎn)生一個(gè)socket對(duì)象。在客戶方程序中，除非需要數(shù)據(jù)報(bào)套接字，Create（）函數(shù)一般情況下應(yīng)該

76、使用默認(rèn)參數(shù)。而對(duì)于服務(wù)方程序，必須在調(diào)用Create時(shí)指定一個(gè)端口。需要注意的是，Carchive類對(duì)象不能與數(shù)據(jù)報(bào)（UDP）套接字一起工作，因此對(duì)于數(shù)據(jù)報(bào)套接字，CAsyncSocket和CSocket 的使用方法是一樣的。 3、如果是客戶方套接字，則調(diào)用CAsyncSocket ∷Connect（）函數(shù)與服務(wù)方套接字連接；如果是服務(wù)方套接字，則調(diào)用CAsyncSocket∷Listen（）開(kāi)始監(jiān)聽(tīng)來(lái)自客戶方的連 接請(qǐng)求

77、，收到連接請(qǐng)求后，調(diào)用CAsyncSocket∷Accept（）函數(shù)接受請(qǐng)求，建立連接。請(qǐng)注意Accept（）成員函數(shù)需要一個(gè)新的并且為空的CSocket對(duì)象作為它的參數(shù)，解釋同上。 </p><p>　　該部分主要定義了兩個(gè)類：CClientSocket 和CServerSocket它們均繼承自CSocket類。前者作為客戶端用于向服務(wù)端發(fā)送數(shù)據(jù)的套接字，后者則作為服務(wù)端的用于與監(jiān)聽(tīng)的套接字關(guān)于CSocket類

78、可參考網(wǎng)絡(luò)編程章節(jié)。</p><p>　　這兩個(gè)類中都分別定義了一個(gè)iCFiveChessView * m_view;成員，用于綁定與該CSocket類關(guān)聯(lián)的視圖窗口。以便于該類訪問(wèn)棋盤類的相關(guān)成員和操作。</p><p>　　它們的通信模型如下圖所示。</p><p>　　2.4.3 其他部分</p><p>　　這一部分將介紹一下棋盤類和

79、消息類，而電腦類則放到AI算法部分詳細(xì)的講解。</p><p>　　CMatch-----棋盤類</p><p>　　以下是該類的數(shù)據(jù)成員：</p><p>　　int chessboard[LW][LW]; //0表示沒(méi)有子落下;1表示黑子落下，2表示白子落下</p><p>　　Point *BK_Black,*BK_White; //

80、用于保存棋局的每一步，但是目前只是用于悔棋</p><p>　　//和保存最新的一步以便于繪圖。</p><p>　　int m_bcur; //表示黑棋子走了幾步或者說(shuō)最近一步的下標(biāo)</p><p>　　int m_wcur; //同上</p><p>　　CFiveChe

81、ssView * m_view; //與視圖類關(guān)聯(lián)，以便于訪問(wèn)它的數(shù)據(jù)成員和操作。</p><p>　　CMatch的成員函數(shù)：</p><p>　　void Rollback(int ,int)-----回滾（悔棋）</p><p>　　該函數(shù)實(shí)現(xiàn)黑白棋的回滾，兩個(gè)參數(shù)分別表示第黑棋子和白棋子要回滾</p><p>　　步數(shù)。利用保存在*

82、BK_Black,*BK_White的兩個(gè)數(shù)組中記錄的下棋軌跡。很容易能夠?qū)崿F(xiàn)這個(gè)功能。如黑白子向后悔棋一步應(yīng)該寫成Rollback（1，1）。</p><p>　　void Init(CFiveChessView * view)---------初始化該類</p><p>　　該類實(shí)現(xiàn)的是初始化過(guò)程，也許你很疑惑。為什么不把他放到構(gòu)造函數(shù)中去呢？起初我也是這么認(rèn)為的，后來(lái)在CFiveCh

83、essView類中定義棋盤成員時(shí)發(fā)現(xiàn)CMatch m_match(this)是不能實(shí)現(xiàn)的。這里有兩種方法可以解決這個(gè)問(wèn)題，如聲明一個(gè)棋盤類指針，然后在CFiveChessView中去初始化也就是動(dòng)態(tài)申請(qǐng)一個(gè)棋盤變量用this做參數(shù)；當(dāng)然還有一種方法就是另外再寫個(gè)函數(shù)如init(CFiveChessView * view)然后在CFiveChessView中調(diào)用，同樣也可以實(shí)現(xiàn)，明顯前者會(huì)結(jié)構(gòu)更符合。采用了后者是因?yàn)楫?dāng)初在解決這個(gè)問(wèn)題時(shí)還

84、沒(méi)想到這種解決方法。</p><p>　　BOOL CanDown(int x,int y,int who)--------判斷該點(diǎn)是否可合法</p><p>　　這個(gè)函數(shù)根據(jù)傳入進(jìn)來(lái)的參數(shù)，判斷該點(diǎn)是否合法。若是則修改該點(diǎn)棋盤上該點(diǎn)的值。當(dāng)初只是根據(jù)直覺(jué)把修改棋盤值功能也合并到這個(gè)函數(shù)中去，現(xiàn)在想想似乎有些不妥，至少在結(jié)構(gòu)上是如此。破壞了模塊間的耦合度，也就是做了不該由該函數(shù)完成的動(dòng)作。

85、理想的函數(shù)只做一件事，也即是只要判斷改點(diǎn)是否合法，然后在返回布爾變量。修改的步驟應(yīng)該由其他操作完成。但是由于時(shí)間所限，目前只要完成基本功能后，修改后將影響到其他部分的代碼修改，所以將更加完善的部分放到后期完成。</p><p>　　BOOL IsWin(int who,int pos[5][2])--------判斷是否已經(jīng)贏了</p><p>　　該功能判斷是否who已經(jīng)形成了五連子了，

86、若是則將其記錄到pos[5][2]中去，便于在棋盤上標(biāo)示出來(lái)，同時(shí)返回判斷的結(jié)果。因?yàn)樵摵瘮?shù)實(shí)現(xiàn)的思路是逐個(gè)的遍歷每個(gè)棋盤點(diǎn)進(jìn)行判斷。明顯這個(gè)是很沒(méi)必要的，當(dāng)棋盤很大時(shí)候是很費(fèi)時(shí)間的需要優(yōu)化。我們可以做個(gè)簡(jiǎn)單的證明；假設(shè)當(dāng)前棋盤沒(méi)有形成五連子，那么我們往棋盤下一個(gè)子，若會(huì)形成五連子的則該點(diǎn)一定在這五連子中。其他的子由于在上面的假設(shè)中不會(huì)形成五連子所以也不可能形成。 這樣一來(lái)我們只要判斷該點(diǎn)的四個(gè)方向就足夠了。這也是一個(gè)良好編程的思維。同

87、樣由于時(shí)間有限，只能將更完善的修改放到后期去。</p><p>　　void Clear()-------清空棋盤</p><p>　　這個(gè)函數(shù)是將chessboard二元數(shù)組全部值修改0，表明棋盤全部置空。</p><p>　　CMessg------消息類 </p><p>　　1.消息類的數(shù)據(jù)成員：</p><p&g

88、t;　　CString m_strText; // 用于發(fā)送聊天信息的字符變量</p><p>　　BOOL m_restart; // 用于表識(shí)對(duì)方是否發(fā)送重新開(kāi)始請(qǐng)求</p><p>　　BOOL m_restartconfirm; // 發(fā)出重新開(kāi)始請(qǐng)求是否得到對(duì)方的確認(rèn)</p><p>　　BOOL m_rollback

89、; / /標(biāo)識(shí)對(duì)方是否發(fā)送了悔棋的請(qǐng)求</p><p>　　BOOL m_rollbackconfirm; //發(fā)出的悔棋請(qǐng)求是否得到了對(duì)方確認(rèn)</p><p>　　BOOL m_fail; // 發(fā)出認(rèn)輸請(qǐng)求</p><p>　　BOOL m_failconfirm; // 發(fā)出認(rèn)輸確認(rèn)回復(fù)</p><p

90、>　　BOOL m_dogfail; // 發(fā)出和棋請(qǐng)求</p><p>　　BOOL m_dogfailconfirm; //發(fā)出和棋確認(rèn)回復(fù)</p><p>　　intm_turn; //當(dāng)前輪到哪方下棋了</p><p>　　intm_x; //對(duì)方下的棋子的橫坐標(biāo)</p>&l

91、t;p>　　intm_y; //對(duì)方下的棋子的縱坐標(biāo)</p><p>　　2.消息類的成員函數(shù)：</p><p>　　void Init()--------初始化函數(shù) </p><p>　　在該函數(shù)中將全部的值置為不可用狀態(tài)。</p><p>　　virtual void Serialize(CArchive&

92、amp; ar)------序列化函數(shù)</p><p>　　Cobject類擁有序列化虛函數(shù)，消息類派生自該類，根據(jù)C++繼承性質(zhì)子類就可以重寫該函數(shù)。從傳遞進(jìn)來(lái)的Carchive 的類型進(jìn)入相應(yīng)的函數(shù)部分。當(dāng)它是load類型時(shí)將數(shù)據(jù)寫入ar中也就是相當(dāng)于接收到了對(duì)方發(fā)過(guò)來(lái)的消息；當(dāng)它是store類型時(shí)該函數(shù)就將值讀入ar中，實(shí)現(xiàn)了向?qū)Ψ桨l(fā)送數(shù)據(jù)的功能。</p><p>　　Ccomput

93、er-----電腦類</p><p><b>　　消息類的數(shù)據(jù)成員：</b></p><p>　　int m_step; //表示當(dāng)前電腦走了幾步</p><p>　　int m_grade; //表示電腦的等級(jí)</p><p>　　int x,y; //電腦給出的最佳位置</p><p&

94、gt;<b>　　消息類的成員函數(shù)：</b></p><p>　　OptimizeLayChess_MaxMin4(chessboard[][LW],depth,*px,py,Alpha, Beta);</p><p>　　OptimizeLayChess_MaxMin_2_1(chessboard[][LW],depth,*px,*py, Alpha, Beta);

95、 </p><p>　　LayChess_MaxMin2(chessboard[][LW], depth, *px,i*py, Alpha, Beta); </p><p>　　以上三個(gè)函數(shù)分別對(duì)應(yīng)電腦中的高級(jí)，中級(jí)，初級(jí)智能。第一個(gè)采用了動(dòng)態(tài)優(yōu)化功能深度為4；第二用也采用了動(dòng)態(tài)優(yōu)化，深度為3；第三個(gè)只用了剪枝。關(guān)于他們?cè)敿?xì)的介紹參看算法分析部分。</p><p>

96、　　Repair(chessboard[][LW],*px,*py);</p><p>　　由于AI算法中本身存在的問(wèn)題(詳細(xì)見(jiàn)4.2節(jié) 不足說(shuō)明),所以需要進(jìn)行必要的修補(bǔ).這個(gè)函數(shù)遵循的原則是:己五必填,活四看對(duì)方,若對(duì)方不可能形成連五,同樣必填.不是活四也不是死四的話,若對(duì)方可形成連五,必堵!</p><p>　　Int Count_135(chessboard[][LW],i*p_1

97、35,*p_315, i,j,who);</p><p>　　int Count_90(chessboard[][LW],i*p_90, *p_270, i, j, who);</p><p>　　int Count_45(chessboard[][LW], *p_45, *p_225, i, j, who);</p><p>　　int Count_0(

98、chessboard[][LW],*p_0,*p_180, i,j, who);</p><p>　　這組函數(shù)是用于計(jì)算i,j點(diǎn)的各個(gè)方向上連續(xù)的who類型的棋子數(shù),并且將每個(gè)方向上的被”阻礙”的類型.</p><p>　　GetScorce(int total,int edge1,int edge2);</p><p>　　Get_0_Scorce(chessbo

99、ard[][LW],Eva_Tab ScoTab,i,j);</p><p>　　Get_45_Scorce(chessboard[][LW],Eva_TabScoTab,i,;</p><p>　　Get_90_Scorce(chessboard[][LW], ScoTab, i, j); </p><p>　　Get_135_Scorce(chessboard[

100、][LW], ScoTab, i,ij);</p><p>　　evaluate(int chessboard[][LW]);</p><p>　　這幾個(gè)函數(shù)是分別用于計(jì)算，一個(gè)棋子在四個(gè)方向上的值。就是對(duì)應(yīng)水平上，45度，90度，135度調(diào)用GetScorce計(jì)算。</p><p><b>　　人機(jī)對(duì)戰(zhàn)中AI算法</b></p>

101、<p>　　人工智能(Artificial Intelligence) ，英文縮寫為AI。它是研究、開(kāi)發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。 人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式作出反應(yīng)的智能機(jī)器，該領(lǐng)域的研究包括機(jī)器人、語(yǔ)言識(shí)別、圖像識(shí)別、自然語(yǔ)言處理和專家系統(tǒng)等。</p><p>　　在該部分我們盡量去

102、模擬人類在下棋中思考的方式，找出一種合乎邏輯的規(guī)則。</p><p>　　根據(jù)我們平常下棋的經(jīng)驗(yàn)，當(dāng)放入一個(gè)棋子時(shí)總是盡量的往利于己方的位置也既是“攻”；同時(shí)要提防對(duì)方使其不能得逞也既是“防”；我們可以用計(jì)算機(jī)模擬這個(gè)過(guò)程。假設(shè)我們?cè)谄灞P中放入一個(gè)己方棋子，然后考慮對(duì)方最可能下的棋子位置，也就是最有利于對(duì)方的點(diǎn)。（我們假設(shè)只進(jìn)行兩次的探索），再逐個(gè)的比較每個(gè)可下棋的點(diǎn)，最后得出最有利于我方的點(diǎn)。這就是本個(gè)系統(tǒng)中所

103、采用的一個(gè)思路。對(duì)于人說(shuō)用手工去比較計(jì)算是不現(xiàn)實(shí)的。當(dāng)考慮的深度加深的話甚至無(wú)法在有效的時(shí)間內(nèi)實(shí)現(xiàn)的。我們正是利用計(jì)算機(jī)快速的計(jì)算機(jī)能力進(jìn)行這樣的笨重檢索，就能夠在很短的時(shí)間內(nèi)計(jì)算完。下面對(duì)AI算法中所涉及的幾個(gè)重要概念作下介紹。</p><p>　　2.5.1 極大極小樹(shù)</p><p>　　目前絕大部分的博弈類游戲中的人工算法都采用這種方法。假設(shè)己方為MAX點(diǎn)，對(duì)方則為MIN點(diǎn)。如果當(dāng)

104、層的節(jié)點(diǎn)為奇數(shù)時(shí)那么就為MAX層，同樣為偶數(shù)時(shí)就為MIN層。當(dāng)在MAX層時(shí)，該層的值就應(yīng)該為下一個(gè)MIN層中的最大一個(gè)的值。當(dāng)在MIN層是，該層的值就應(yīng)該為它子層MAX的最小的一個(gè)。通俗的說(shuō)就是當(dāng)輪到我方時(shí)，我們就應(yīng)該選擇一個(gè)最有利于我們的點(diǎn)，預(yù)測(cè)對(duì)方可能下的最有利他方的點(diǎn)（相對(duì)我方來(lái)說(shuō)就是最壞的點(diǎn)）。這樣反復(fù)計(jì)算下去就能夠得到根節(jié)點(diǎn)的最大值，這個(gè)點(diǎn)也就是我們最佳下棋點(diǎn)。在計(jì)算這個(gè)點(diǎn)時(shí)可以很明顯的看出這是一個(gè)不斷遞歸的過(guò)程，到達(dá)葉子節(jié)點(diǎn)

105、時(shí)根據(jù)相關(guān)的計(jì)算規(guī)則算出該值然后向上一層不斷的返回。下圖中矩形代表極大層，橢圓代表極小層。</p><p>　　圖 2.7 極大極小樹(shù)</p><p>　　2.5.2 深度優(yōu)先搜索（DFS）</p><p>　　在圖論中有兩個(gè)很重要的遍歷的方法，一個(gè)是深度優(yōu)先搜索（DFS）,另外一個(gè)是廣度優(yōu)先搜索(BFS).這兩個(gè)方法的主要區(qū)別在于下一個(gè)節(jié)點(diǎn)的選擇。DFS首先選擇它

106、的連接節(jié)點(diǎn)，若它的下個(gè)節(jié)點(diǎn)已經(jīng)全部被遍歷過(guò)或者不存在的話。則向上返回到上一個(gè)節(jié)點(diǎn)，在遍其他的未被訪問(wèn)過(guò)的點(diǎn)。很容易想到這要用到堆棧結(jié)構(gòu)，使用一個(gè)遞歸來(lái)實(shí)現(xiàn)。而B(niǎo)FS則是逐個(gè)的遍歷它的聯(lián)接接點(diǎn)，將已經(jīng)訪問(wèn)過(guò)的點(diǎn)放入隊(duì)列中。然后再依次取出繼續(xù)這個(gè)過(guò)程。</p><p><b>　　圖2.8 </b></p><p>　　DFS遍歷過(guò)程如下：</p><

107、p>　　首先從A點(diǎn)出發(fā)訪問(wèn)它的領(lǐng)接點(diǎn)B，因?yàn)锽的領(lǐng)接點(diǎn)C,F均未被訪問(wèn)過(guò)，所以B點(diǎn)選擇C（當(dāng)然也可以選擇F點(diǎn)）作為下一個(gè)要訪問(wèn)的點(diǎn)，C點(diǎn)的領(lǐng)接點(diǎn)是D,F選擇下個(gè)節(jié)點(diǎn)D，而D的鄰接點(diǎn)只有一個(gè)E且未被訪問(wèn)過(guò)，就將E作為了它下個(gè)節(jié)點(diǎn)。這時(shí)因?yàn)镋已經(jīng)沒(méi)有可訪問(wèn)的鄰點(diǎn)，所以向上一層返回到D，發(fā)現(xiàn)D也已經(jīng)沒(méi)有可訪問(wèn)的點(diǎn)了，繼續(xù)向上層返回到C，由于C的鄰節(jié)點(diǎn)F未被訪問(wèn)過(guò)，那么就訪問(wèn)F。所以整個(gè)過(guò)程的遍歷結(jié)果為：A-->BCDEF。<

108、/p><p>　　BFS的的遍歷過(guò)程為：ABECFD。</p><p>　　2.5.3 剪枝方法</p><p>　　在上面中提到當(dāng)預(yù)測(cè)的深度達(dá)到3的時(shí)候，最壞情況下225*225*225=11390625個(gè)，這在目前的一些常規(guī)平均的機(jī)器性能下也需要40多秒的時(shí)間，這是不能夠容忍的。那么是否有很好的改進(jìn)技術(shù)，去除哪些不必要的節(jié)點(diǎn)，并且在剪去了這些點(diǎn)后不影響結(jié)果呢？答案是

109、肯定的，這種方法就是Alpha---Beta剪枝。</p><p>　　下面通過(guò)圖來(lái)說(shuō)明，矩形代表極大層，橢圓代表極小層。</p><p>　　圖 2.9 Alpha—Beta剪枝</p><p>　　從上圖可以看出，由于C節(jié)點(diǎn)的值肯定不大于30而B(niǎo)節(jié)點(diǎn)的值為40大于C節(jié)點(diǎn)，那么目前為止可以很肯定的說(shuō)A節(jié)點(diǎn)值一定不小于40。 所以C點(diǎn)的其他子節(jié)點(diǎn)無(wú)須去訪問(wèn)也不會(huì)對(duì)結(jié)