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

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

2、lt;/p><p>　　年 級 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)將利用五子棋游戲作為研究對象，通過設(shè)計(jì)出一個能夠?qū)崿F(xiàn)兩種不同對戰(zhàn)模式的五子棋游戲。并對所涉及到的相關(guān)技

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

11、二章 詳細(xì)設(shè)計(jì)過程……………………………………………………………………………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)開發(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總體設(shè)計(jì)……………………………………………………………………….9</p><p>　　2.2.5 詳細(xì)設(shè)計(jì)………………………………………………………………………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．人機(jī)對戰(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算法的分析和改進(jìn)………………………………………………………….21</

19、p><p>　　2.5.5.1算法分析………………………………………………………………..22</p><p>　　2.5.5.2 算法改進(jìn)………………………………………………………………..24</p><p>　　第三章 運(yùn)行測試…………………………………………………………………………………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 不足說明……………………………………………………………………………...29</p><p>　　4.3 致謝…………………………………………………………………………………...28</p><p>　　參考文獻(xiàn)…………………………………………………………………………………..29</p><p><

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

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

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

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

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

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

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

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

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

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

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

33、t;　　下面對軟件工程作下簡單的介紹：</p><p>　　軟件工程一直以來都缺乏一個統(tǒng)一的定義，很多學(xué)者、組織機(jī)構(gòu)都分別給出了自己的定義：</p><p>　　Boehm：運(yùn)用現(xiàn)代科學(xué)技術(shù)知識來設(shè)計(jì)并構(gòu)造計(jì)算機(jī)程序及為開發(fā)、運(yùn)行和維護(hù)這些程序所必需的相關(guān)文件資料。 IEEE：軟件工程是開發(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ī)范化的、可定量的過程化方法去開發(fā)和維護(hù)軟件，以及如何把經(jīng)過時間考驗(yàn)而證明正確的管理技術(shù)和當(dāng)前能夠得到的最好的技術(shù)方法結(jié)合起來。 </p><p>　　我個人對軟件工程理解是，它一種工程上的方法學(xué)，用一種有步驟，有計(jì)劃的正確有效方法指導(dǎo)開發(fā)過程。</p>

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

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

37、鍵問題是“要解決的問題是什么”，這個是這個階段必須要明確要回答的問題。在沒將問題定義好，試圖準(zhǔn)備下個階段的任務(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ì)中首先明確了需要解決的問題是五子棋AI算法和網(wǎng)絡(luò)通信的研究，基本的要求是設(shè)計(jì)一款能夠?qū)崿F(xiàn)網(wǎng)絡(luò)和單機(jī)對戰(zhàn)的五子棋游戲，提供一些基本的操作如退出系統(tǒng)，向后悔棋等操作，重點(diǎn)是放在AI算法和網(wǎng)絡(luò)通信的研究。而并不是美工設(shè)計(jì)，也不是為了提供各種操作豐富的接口。主要是通過這種可視化的界面探討AI，當(dāng)然增加可玩性和美工會給系統(tǒng)潤色不少。</p><p>　　上面只是很粗略的明確大概的

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

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

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

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

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

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

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

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

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

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

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

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

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

52、美”的系統(tǒng)。這樣的系統(tǒng)具有用戶可能希望有的所有功能和特點(diǎn)。</p><p>　　結(jié)構(gòu)設(shè)計(jì)的一條基本原理就是程序應(yīng)該模塊化，也就是一個大程序應(yīng)該由許多規(guī)模適中的模塊按合理的層次結(jié)構(gòu)組織而成。總體設(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>　　這個階段的具體內(nèi)容我把放到模塊分析的章節(jié)去分析。下面僅作個簡要的概述。</p><p>　　總體設(shè)計(jì)階段以比較抽象概括的方式提出了解決問題的辦法。詳細(xì)設(shè)計(jì)階段的任務(wù)就是把解法具體化，也就是回答下面這個關(guān)鍵問題：“應(yīng)該怎樣具體地實(shí)現(xiàn)這個系統(tǒng)呢？”</p>&

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

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

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

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

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

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

60、在后面給出詳細(xì)的介紹。</p><p>　　m_mode 這是用于標(biāo)記當(dāng)前系統(tǒng)的是屬于哪種模式人機(jī)或者聯(lián)機(jī)，當(dāng)它是人機(jī)的狀態(tài)時值為P_PK_C（枚舉類型的值），同樣當(dāng)它是聯(lián)機(jī)狀態(tài)就為P_PK_P。若當(dāng)前沒有選擇的狀態(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)識當(dāng)前是輪到哪方下棋了。</p><p>　　m_bWin標(biāo)識本機(jī)方贏的狀態(tài)。</p><p>　　m_bOver 標(biāo)識游戲是否已經(jīng)結(jié)束。</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ù)傳遞進(jìn)來的參數(shù)，確定要在棋盤的哪個位置和畫的類型，如當(dāng)該點(diǎn)是最近下的一個棋子，則把它用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ù)完成的。當(dāng)左鍵被點(diǎn)擊的時，Window會產(chǎn)生一個左鍵消息放到該應(yīng)用程序的消息隊(duì)

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

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)等級算法，給出電腦的棋子的坐標(biāo)。同樣需要判斷該點(diǎn)能否行成五連子，最后更新該點(diǎn)。

67、</p><p>　　聯(lián)機(jī)模式：判讀是否輪到己方下棋，若是則判斷該點(diǎn)是否合法，若是修改相應(yīng)的狀態(tài)變量，并且發(fā)送消息棋盤狀態(tài)給對方。同樣判斷是否行成了五連子。</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>　　如下的對話框，要求用戶設(shè)置好需要連接的服務(wù)器端的IP和監(jiān)聽端口。</p><p>　　圖 2.4 連接服務(wù)器</p><p>　　void OnSetserver()------開啟服務(wù)器</p><p>　　該函數(shù)也是用于響應(yīng)游戲菜單下的開啟服務(wù)器選項(xiàng)，點(diǎn)擊后也彈出如下要求設(shè)置的監(jiān)聽

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

70、數(shù)響應(yīng)用戶要選擇人機(jī)對戰(zhàn)中電腦的等級，點(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)分為兩個部分：一種是人機(jī)對戰(zhàn)狀態(tài)中的悔棋，該模式下用戶只需點(diǎn)擊該選項(xiàng)，棋局將回退到上一個狀態(tài)。另一種是；聯(lián)機(jī)對戰(zhàn)的模式，用

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

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

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

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

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

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

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

78、可參考網(wǎng)絡(luò)編程章節(jié)。</p><p>　　這兩個類中都分別定義了一個iCFiveChessView * m_view;成員，用于綁定與該CSocket類關(guān)聯(liá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表示沒有子落下;1表示黑子落下，2表示白子落下</p><p>　　Point *BK_Black,*BK_White; //

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

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

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

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

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

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

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

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ā)出重新開始請求是否得到對方的確認(rèn)</p><p>　　BOOL m_rollback

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

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

91、t;p>　　intm_y; //對方下的棋子的縱坐標(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)來的Carchive 的類型進(jìn)入相應(yīng)的函數(shù)部分。當(dāng)它是load類型時將數(shù)據(jù)寫入ar中也就是相當(dāng)于接收到了對方發(fā)過來的消息；當(dāng)它是store類型時該函數(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; //表示電腦的等級</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ù)分別對應(yīng)電腦中的高級，中級，初級智能。第一個采用了動態(tài)優(yōu)化功能深度為4；第二用也采用了動態(tài)優(yōu)化，深度為3；第三個只用了剪枝。關(guān)于他們詳細(xì)的介紹參看算法分析部分。</p><p>

96、　　Repair(chessboard[][LW],*px,*py);</p><p>　　由于AI算法中本身存在的問題(詳細(xì)見4.2節(jié) 不足說明),所以需要進(jìn)行必要的修補(bǔ).這個函數(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ù)是用于計(jì)算i,j點(diǎn)的各個方向上連續(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ù)是分別用于計(jì)算，一個棋子在四個方向上的值。就是對應(yīng)水平上，45度，90度，135度調(diào)用GetScorce計(jì)算。</p><p><b>　　人機(jī)對戰(zhàn)中AI算法</b></p>

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

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

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

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

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

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

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

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

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