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

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

2、lt;/p><p>　　年 級 2004 </p><p>　　專 業(yè) 計算機科學與技術 </p><p>　　指導教師 </p><p>　　職 稱 講師

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

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

5、;p>　　關鍵字：五子棋 、博奕AI算法、網(wǎng)絡通信</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問題背景……………………………………………………………………………4</p><p>　　1.2五子棋簡介…………………………………………………………………………5</p><p>　　第

11、二章 詳細設計過程……………………………………………………………………………5</p><p>　　2.1．概要介紹…………………………………………………………………………….5</p><p>　　2.1.1 本程序介紹…………………………………………………………………5</p><p>　　2.1.2 本程序優(yōu)點…………………………………………………………………

12、5</p><p>　　2.2用軟件工程方法學指導開發(fā)過程……………………………………………………5</p><p>　　2.2.1 問題定義………………………………………………………………………6</p><p>　　2.2.2 可行性研究……………………………………………………………………7</p><p>　　2.2.3 需求分析………

13、………………………………………………………………8</p><p>　　2.2.4總體設計……………………………………………………………………….9</p><p>　　2.2.5 詳細設計………………………………………………………………………10</p><p>　　2.2.6 編碼和單元測試………………………………………………………………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．人機對戰(zhàn)中的AI算法………………………………………………………………18</p><p>　　2.5.1 極大極小樹…………………………………………………………………….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算法的分析和改進………………………………………………………….21</

19、p><p>　　2.5.5.1算法分析………………………………………………………………..22</p><p>　　2.5.5.2 算法改進………………………………………………………………..24</p><p>　　第三章 運行測試…………………………………………………………………………………25</p><p>　　3.1 網(wǎng)絡部分……………

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

21、.29</p><p>　　4.2 不足說明……………………………………………………………………………...29</p><p>　　4.3 致謝…………………………………………………………………………………...28</p><p>　　參考文獻…………………………………………………………………………………..29</p><p><

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

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

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

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

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

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

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

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

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

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

32、。雖然最后系統(tǒng)都能夠”笨重”的運行起來，但這是明顯違背程序設計方法學?？删S護行，易修改性嚴重降低。后期如果需要添加某些功能的時候將變得十分的繁瑣?？梢韵胂笤诙鄠€團隊一起開發(fā)的大型系統(tǒng)中這種粗陋的開發(fā)方法根本是行不通的。所以要養(yǎng)成用正確的方法指導開發(fā)過程的習慣，雖然有時候看起來有點大題小做，但我覺的這是作為一名合格的軟件開發(fā)工程師所必須掌握的技能。通過長期不斷的積累才能增加我們參與大型項目開發(fā)的能力。</p><p&g

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

59、信了。</p><p>　　CMatch m_match 這是一個棋盤類的一個變量。關于這個類將在后面做詳細的講解，將棋盤單獨抽象為一個類，并向外部提供棋盤的一些操作。這比較符合面向對象編程。</p><p>　　CComputer m_computer 這也是一個很重要的成員，它將人機對戰(zhàn)中的電腦方抽象成一個類，該類提供不同的等級的下棋功能。根據(jù)當前棋盤的局勢給出最佳的下棋點。該類也將

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

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

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

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

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

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

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

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

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

69、端口。</p><p>　　圖 2.5 開啟服務器</p><p>　　void OnPrimary()--------初級選項</p><p>　　void OnSecondary();-------中級選項</p><p>　　void OnSenior();---------高級選項</p><p>　　這三個函

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

87、樣由于時間有限，只能將更完善的修改放到后期去。</p><p>　　void Clear()-------清空棋盤</p><p>　　這個函數(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; // 用于表識對方是否發(fā)送重新開始請求</p><p>　　BOOL m_restartconfirm; // 發(fā)出重新開始請求是否得到對方的確認</p><p>　　BOOL m_rollback

89、; / /標識對方是否發(fā)送了悔棋的請求</p><p>　　BOOL m_rollbackconfirm; //發(fā)出的悔棋請求是否得到了對方確認</p><p>　　BOOL m_fail; // 發(fā)出認輸請求</p><p>　　BOOL m_failconfirm; // 發(fā)出認輸確認回復</p><p

90、>　　BOOL m_dogfail; // 發(fā)出和棋請求</p><p>　　BOOL m_dogfailconfirm; //發(fā)出和棋確認回復</p><p>　　intm_turn; //當前輪到哪方下棋了</p><p>　　intm_x; //對方下的棋子的橫坐標</p>&l

91、t;p>　　intm_y; //對方下的棋子的縱坐標</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ù)。從傳遞進來的Carchive 的類型進入相應的函數(shù)部分。當它是load類型時將數(shù)據(jù)寫入ar中也就是相當于接收到了對方發(fā)過來的消息；當它是store類型時該函數(shù)就將值讀入ar中，實現(xiàn)了向對方發(fā)送數(shù)據(jù)的功能。</p><p>　　Ccomput

93、er-----電腦類</p><p><b>　　消息類的數(shù)據(jù)成員：</b></p><p>　　int m_step; //表示當前電腦走了幾步</p><p>　　int m_grade; //表示電腦的等級</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>　　以上三個函數(shù)分別對應電腦中的高級，中級，初級智能。第一個采用了動態(tài)優(yōu)化功能深度為4；第二用也采用了動態(tài)優(yōu)化，深度為3；第三個只用了剪枝。關于他們詳細的介紹參看算法分析部分。</p><p>

96、　　Repair(chessboard[][LW],*px,*py);</p><p>　　由于AI算法中本身存在的問題(詳細見4.2節(jié) 不足說明),所以需要進行必要的修補.這個函數(shù)遵循的原則是:己五必填,活四看對方,若對方不可能形成連五,同樣必填.不是活四也不是死四的話,若對方可形成連五,必堵!</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ù)是用于計算i,j點的各個方向上連續(xù)的who類型的棋子數(shù),并且將每個方向上的被”阻礙”的類型.</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>　　這幾個函數(shù)是分別用于計算，一個棋子在四個方向上的值。就是對應水平上，45度，90度，135度調(diào)用GetScorce計算。</p><p><b>　　人機對戰(zhàn)中AI算法</b></p>

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

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

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

104、層的節(jié)點為奇數(shù)時那么就為MAX層，同樣為偶數(shù)時就為MIN層。當在MAX層時，該層的值就應該為下一個MIN層中的最大一個的值。當在MIN層是，該層的值就應該為它子層MAX的最小的一個。通俗的說就是當輪到我方時，我們就應該選擇一個最有利于我們的點，預測對方可能下的最有利他方的點（相對我方來說就是最壞的點）。這樣反復計算下去就能夠得到根節(jié)點的最大值，這個點也就是我們最佳下棋點。在計算這個點時可以很明顯的看出這是一個不斷遞歸的過程，到達葉子節(jié)點

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

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

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

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

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