154.A五子棋游戲的單機(jī)版及網(wǎng)絡(luò)版的實現(xiàn) 畢業(yè)論文

1、本本 科科 生生 畢畢 業(yè)業(yè) 論論 文文 題 目：五子棋游戲的單機(jī)版及網(wǎng)絡(luò)版的實現(xiàn) 院 系：信息科學(xué)與技術(shù)學(xué)院 計算機(jī)科學(xué)系 專 業(yè)： 網(wǎng)絡(luò)工程 學(xué)生姓名： xxx 學(xué) 號： xxx 指導(dǎo)教師： xxx 源代碼聯(lián)系本人 二九 年 三 月 摘摘 要要 隨著 it 技術(shù)的發(fā)展，很多日常生活中的游戲都被搬到了計算機(jī)里供大眾娛樂，尤其是博弈 類的棋類游戲，如中國象棋，圍棋，五子棋等，近年來人們對人工智能技術(shù)的研究成果更使得 計算機(jī)在這些博弈游戲中能戰(zhàn)勝很多玩家。 本文結(jié)合五子棋這個游戲的特點，將闡述單機(jī)版五子棋的算法設(shè)計，突出人工智能在博弈 方面的應(yīng)用，旨在試驗人工智能里的一些搜索算法，最終確定人工智

2、能在未來各學(xué)科里的重要 應(yīng)用性；最后還涉及網(wǎng)絡(luò)版五子棋的設(shè)計實現(xiàn)，同時介紹一般網(wǎng)絡(luò)游戲的架構(gòu)。 第一章簡要介紹五子棋相關(guān)的狀況。第二章概述了人工智能與五子棋相關(guān)的各種算法。第 三章詳細(xì)描述本設(shè)計所使用的人工智能算法。第四章講述一般網(wǎng)絡(luò)游戲的架構(gòu)以及本設(shè)計中網(wǎng) 絡(luò)版五子棋的實現(xiàn)細(xì)則。第五章總結(jié)本次設(shè)計過程中的各種收獲。 關(guān)鍵詞：關(guān)鍵詞：五子棋； 人工智能； 博弈； 網(wǎng)絡(luò)游戲 abstract with the development of it technology, a lot games in daily life have been moved to the computer for pu

3、blic entertainment, especially the game of chess-type games, such as chinese chess, the game of go , gobang , etc., in recent years , artificial intelligence research makes the results that computer can overcome a lot of players in these games. in this paper, with the characteristics of gobang ,i wi

4、ll describe algorithm design on stand-alone version of gobang ,to highlight the application of artificial intelligence in the game , and test some search algorithms of artificial intelligence , and ultimately determine the important application of artificial intelligence in the various disciplines ;

5、 finally the paper also involves the design of implementation gobang online version , at the same time introduces the general architecture of online games. chapter i briefly introduce the relevant situation of gobang. chapter ii provides an overview of artificial intelligence and gobang related algo

6、rithms. chapter iii detailed description of the design of algorithms used in artificial intelligence. chapter iv on the general network architecture of the games as well as the online version of the design in the implementation details.chapter v summarized the harvest of the designing. keywords: gob

7、ang；artificial intelligence；game；online game 目目 錄錄 第一章第一章前言前言.1 1.1 五子棋的棋盤.1 1.2 五子棋的基本規(guī)則.2 第二章第二章 人工智能的應(yīng)用人工智能的應(yīng)用.5 2.1 人工智能的發(fā)展歷史.5 2.2 人工智能研究的特點.7 2.3 人工智能的應(yīng)用.7 2.4 博弈算法極大極小搜索算法.9 第三章第三章 五子棋單機(jī)部分詳細(xì)設(shè)計五子棋單機(jī)部分詳細(xì)設(shè)計.12 第四章第四章 五子棋聯(lián)機(jī)部分詳細(xì)設(shè)計五子棋聯(lián)機(jī)部分詳細(xì)設(shè)計.19 4.1 聯(lián)機(jī)網(wǎng)絡(luò)游戲概述.19 4.2 聯(lián)機(jī)五子棋的設(shè)計.20 第五章第五章 結(jié)論結(jié)論.24 參考文獻(xiàn)參考

8、文獻(xiàn).29 致謝致謝.30 第一章第一章前言前言 五子棋是我國古代的、傳統(tǒng)的黑白棋種之一，大約在南北朝時期隨圍棋一起 先后傳入朝鮮、日本等地。五子棋在日本叫“連珠棋” ，英文稱之為“gobang” 或者 fir(five in a row 的縮寫) ， 亦有“連五子” ， “五子連” ， “串珠”.， “五目” ， “五目碰”等多種稱謂1。 通過一系列的規(guī)則變化使連珠五子棋這一簡單的游戲復(fù)雜化、規(guī)范化，而最終成為今天的職業(yè) 連珠五子棋，同時也成為一種國際比賽棋。 1988 年 8 月 8 日，國際連珠聯(lián)盟( ri f )由日 本、 俄羅斯、瑞典、亞美尼亞等九個成員 國在瑞典宣告成立。五子棋在國

9、內(nèi)外發(fā)展速度相當(dāng)快，預(yù)計在幾年后，五子棋能在很多國家形 成熱門運動。 我國也不例外， 在很多熱衷于五子棋事業(yè)的棋手的共同努力下，有望在不久的 將來成為五子棋運動的中心。 隨著我國經(jīng)濟(jì)社會的快速發(fā)展，人們生活水平不斷提高，人們的生活觀念發(fā)生改變，高質(zhì) 量的生活、現(xiàn)代化的生活方式成為人們追求的目標(biāo)，休閑、 娛樂性體育活動作為時尚生活的一 部分， 被越來越多的人所追捧。 棋類項目作為一種智力性體育項目， 可以修身養(yǎng)性、 益智 健心， 也可以滿足人們對于休閑和娛樂的需求. 一些項目如五子棋等由于項目自身的特點和生 命力， 也一直被人們所喜愛， 因此得以生存和發(fā)展， 成為許多人喜愛的休閑娛樂性棋類項目。

10、 隨著時代的發(fā)展、社會的進(jìn)步和人民生活水平的提高， 人們對業(yè)余體育文化生活方面的需求會 不斷增加， 這些“ 趣味性”棋類項目 將會越來越受到關(guān)注和重視。 1.1 五子棋的棋盤五子棋的棋盤 五子棋的棋盤如圖 1 所示，正中一點為“天元” 。棋盤兩端的橫線稱端線。棋盤左右最外 邊的兩條縱線稱邊線。從兩條端線和兩條邊線向正中發(fā)展而縱橫交叉在第四條線形成的四個點 稱為“星” 。天元和星應(yīng)在棋盤上用直徑約為 0.5 厘米的實心小圓點標(biāo)出。 圖 1 五子棋棋盤示意圖 以持黑方為準(zhǔn)，棋盤上的縱軸線從左到右用英文字母 ao 標(biāo)記。橫行線從近到遠(yuǎn)用數(shù)字 115 標(biāo)記。縱橫軸上的橫縱線交叉點分別用橫縱線標(biāo)記的名稱

11、合寫成。如“天元”h8，四個 “星”分別為 d4，d12，l12，l4。 1.2 五子棋的基本規(guī)則五子棋的基本規(guī)則 黑白雙方依次落子， 任一方先在棋盤上形成橫向，豎向，斜向的連續(xù)的相同顏 色的五個( 含五個以上) 棋子的一方為勝。2 1）連 在棋陽線和陰線的任意一條線上形成的有 5 個或 5 個以上的同色棋子不間 隔地緊緊相連。五連:在棋盤上形成的 5 個同色棋子的“ 連” 。長連:在棋盤上形成的 6 個或 6 個以上同色棋子的“ 連” 。 2） “四”包括“活四”和“沖四” 。 活四：如圖 2 所示，在棋盤某一條陽線或陰線上有同色 4 子不間隔地緊緊相連，且在此 4 子兩端延長線上各有一個無

12、子的交叉點與此 4 子緊密相連。 圖 2 活四 沖四:除“ 活四” 外的，再下一著棋便可形成五連，并且存在五連的可能性的局面。白棋 再下一著可形成長連的局面也視為“四” ，如圖 3 所示。 圖 3 黑棋各種不同的沖四 3） “三”指活三，包括“連三”和“跳三” 。 連三:在棋盤某一條陽線或陰線上有同色三子相連，且在此三子兩端延長線 上有一端至少有一個，另一端至少有兩個無子的交叉點與此三子緊密相連。 跳三:中間僅間隔一個無子交叉點的連三， 但兩端延長線均至少有一個無子 的交叉點與此三子相連。 4）禁手：對局中禁止使用的著法。 黑棋禁手包括“三三” ， “ 四四” 和“ 長連” ， 禁手只對黑棋而

13、言。 三三:由于黑方走一著在無子交叉點上同時形成二個或二個以上黑方“ 活” 的局面，如圖 4 所示。 圖 4 三三禁手 四四:由于黑方走一著在無子交叉點上同時形成二個或二個以上黑方“ 四” 的局面。 5 )先手 對方必須應(yīng)答的著法，其中“ 沖四“ 稱為絕對先手。 6 )四三 指某一方同時具備兩個先手，其中一個是“ 四” ，一個是“ 活三”. 7 )三手可交換 是指黑棋下盤面第 3 著棋后，白方在應(yīng)白之前，如感覺黑方棋形不利于己方，可提出交 換，即執(zhí)白棋一方變?yōu)閳?zhí)黑棋一方，而黑方不可以不換。 8 )五手兩打 是指黑棋在下盤面上關(guān)鍵的第五手棋時， 必須下兩步棋，讓白 棋在這兩步棋中任選一步， 然后

14、再繼續(xù)對弈。一般說來，白棋肯定拿掉對白方不利的一點， 而 保留對黑方較為不利的那點讓黑方行棋。 第二章第二章 人工智能的應(yīng)用人工智能的應(yīng)用 2.1 人工智能的發(fā)展歷史人工智能的發(fā)展歷史 1.1. 萌芽時期（萌芽時期（19561956 年以前）年以前） 17 世紀(jì)，法國物理學(xué)家 b.pascalb.pascal 制成的機(jī)械加法器機(jī)械加法器； 在其基礎(chǔ)上，德國數(shù)學(xué)家 leibnizleibniz 制成了四則運算的計算器計算器。 1936 年 英國數(shù)學(xué)家 turningturning 提出了圖靈機(jī)模型； 1938 年 德國工程師 zusezuse 研制成了第一臺累計數(shù)字計算機(jī)數(shù)字計算機(jī)； 1946

15、年 美國誕生了第一臺電子數(shù)字計算機(jī)電子數(shù)字計算機(jī) eniaceniac； 1945 年，奧地利學(xué)者系統(tǒng)論的創(chuàng)立 1948 年，美國數(shù)學(xué)家 n.wiener 控制論的創(chuàng)立； 1948 年，美國數(shù)學(xué)家 c.e.shannon 信息論的創(chuàng)立； 2.2. 形成時期（形成時期（1956-19611956-1961 年）年） 1956 年，在美國 dartmouth 大學(xué)的一次歷史性聚會是人 工智能學(xué)科正式誕生的標(biāo)志。有三個較有影響的研究團(tuán)隊： 心理學(xué)小組心理學(xué)小組：a.newella.newell、j.shawj.shaw 和和 h.simonh.simon 等人于等人于 1957 年編制出邏輯理論機(jī)

16、lt，證 明了數(shù)學(xué)原理中第 2 章的 38 條定理，1963 年的新版 lt 證明了該章全部共 52 條定 理。1960 年，通用問題求解器 gps 能求解 10 種不同類課題的問題 ibmibm 研究小組研究小組：a.samuela.samuel 研究的具有自學(xué)習(xí)、自組織和自適應(yīng)能力的西洋跳棋程序， 1959 年，該程序戰(zhàn)勝了設(shè)計者，1962 年，戰(zhàn)勝了美國的一個州冠軍。 mitmit 研究小組：研究小組：1959 年，mccarthy 發(fā)明了人工智能主要的語言 lisp。1958 年開發(fā)了行 動計劃咨詢系統(tǒng)。1960 年 minsky 的論文：走向人工智能的步驟。 其他：其他：1956 年

17、 n.chomsky 的文法體系、1958 年 shelffridge 的模式識別系統(tǒng)等，都對 人工智能研究產(chǎn)生了有益的影響。 3.3. 發(fā)展時期（發(fā)展時期（19611961 年以后）年以后） 符號主義學(xué)派方面： 1965 年，j.a.robinson 的歸結(jié)原理，推動了定理機(jī)器證明技術(shù)的發(fā)展： 1965 年，e.a.feigenbaum 研制的基于領(lǐng)域知識和專家知識的 dendral 程序，能根據(jù)質(zhì) 譜儀的數(shù)據(jù)并利用相關(guān)知識，推斷出有機(jī)化合物的分子結(jié)構(gòu)，達(dá)到甚至超過了化學(xué)家的 水平。后來又有醫(yī)學(xué)專家系統(tǒng) mycin 系統(tǒng)、地質(zhì)礦產(chǎn)勘探專家系統(tǒng) prospector、計算機(jī) 配置專家系統(tǒng) r1

18、 等等。 1969 年，c.green 提出了基于一階謂詞演算方法。 1973 年，r.f.simmon 提出語義網(wǎng)結(jié)構(gòu)。 1972 年，m.minsky 提出框架結(jié)構(gòu)。 1972 年，法國馬賽大學(xué) a.colmerauer 等提出了邏輯程序設(shè)計語言 prolog。 1977 年，e.a.feigenbaum 提出了“知識工程”的概念，人工智能的研究從以推理為中 心轉(zhuǎn)向以知識為中心，進(jìn)入了所謂的知識期。 進(jìn)入 20 世紀(jì) 80 年代后，專家系統(tǒng)和知識工程在理論、技術(shù)和應(yīng)用方面都有長足的進(jìn)步 和發(fā)展。 o專家系統(tǒng)的建造進(jìn)入了應(yīng)用高級開發(fā)工具階段。 o出現(xiàn)了多專家系統(tǒng)、大型專家系統(tǒng)、微專家系統(tǒng)等。

19、 o專家系統(tǒng)和知識工程技術(shù)已應(yīng)用到各種計算機(jī)應(yīng)用系統(tǒng)中，出現(xiàn)了智能管理信息系統(tǒng)、 智能決策支持系統(tǒng)、智能控制系統(tǒng)、智能 cad 系統(tǒng)、智能 cai 系統(tǒng)、智能數(shù)據(jù)庫系統(tǒng)和 智能多媒體系統(tǒng)等等。 o知識表示、不確定性推理等方面都取得了重大的進(jìn)展。 連接主義學(xué)派方面 1943 年，mcculloch 和 pitts 第 1 次提出模擬神經(jīng)元 。 1957 年，p.rosenblatp.rosenblat 開發(fā)了所謂感知機(jī)(perception)的單層神經(jīng)網(wǎng)絡(luò)。 1962 年，b.windrow.windrow 提出了自適應(yīng)線性元件(asaline)，并應(yīng)用于天氣預(yù)報、電子線路 板分析、人工視覺等許

20、多問題。 1969 年，m.l.minskym.l.minsky 應(yīng)用數(shù)學(xué)理論深入分析了單層神經(jīng)網(wǎng)絡(luò)，證明它不能實現(xiàn)異或門 的功能，使神經(jīng)網(wǎng)絡(luò)系統(tǒng)研究熱潮迅速降溫。 1982 年，j.hopfield.hopfield 提出了一種全互聯(lián)的神經(jīng)元網(wǎng)絡(luò)，并于 19851985 年成功地求解了 tsptsp 問題（幾秒內(nèi)求解（幾秒內(nèi)求解有 3131 個城市的 tsptsp 問題） 。 1985 年，rumelhart 提出了反向傳播(bp)算法，解決了多層人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)問題， 使冷落了 20 多年的神經(jīng)網(wǎng)絡(luò)研究又東山再起。 此后神經(jīng)網(wǎng)絡(luò)在智能控制、語言識別、圖形文字識別、最優(yōu)化問題求解和智能計算

21、機(jī) 等領(lǐng)域進(jìn)行了實踐并取得了一系列的成果。3 2.2 人工智能研究的特點人工智能研究的特點 人工智能是一門知識的科學(xué)。以知識為對象，研究知識的獲取、表示和使用。 人工智能的系統(tǒng)過程是，數(shù)據(jù)處理-知識處理，數(shù)據(jù)-符號。符號表示的是知識而不是數(shù)值、 數(shù)據(jù)。 問題求解過程有啟發(fā)，有推導(dǎo)。 人工智能是引起爭論最多的科學(xué)之一。 問題焦點：當(dāng)前人工智能的研究應(yīng)該以人類的普遍思維規(guī)律為主，還是以特定知識的處理 和運用為主？智能的本質(zhì)是什么？機(jī)器能達(dá)到人的水平嗎？總而言之，人工智能研究是非常困 難的。 萬能的邏輯推理體系至今沒有創(chuàng)造出來，并不是因為人工智能專家的本事不夠，而是因為 這種萬能的體系從根本上就是不

22、可能有的。他最大的弱點就是缺乏知識，缺乏人類在幾千年的 文明史上積累起來的知識，在實際生活中，人是根據(jù)知識行事的，而不是根據(jù)在抽象原則上的 推理行事的。 即使就推理體系來說，它的主要技術(shù)是狀態(tài)空間搜索，而在執(zhí)行中遇到的主要困難就是 組合爆炸 ，事實表明，單靠一些思維原則是解決不了組合爆炸問題的，要擺脫困境，只有大 量使用理性的知識。 2.3 人工智能的應(yīng)用人工智能的應(yīng)用 1、問題求解。 人工智能的第一大成就是下棋程序，在下棋程度中應(yīng)用的某些技術(shù)，如向前看幾步，把 困難的問題分解成一些較容易的子問題，發(fā)展成為搜索和問題歸納這樣的人工智能基本技術(shù)。 今天的計算機(jī)程序已能夠達(dá)到下各種方盤棋和國際象棋

23、的錦標(biāo)賽水平。但是，尚未解決包括人 類棋手具有的但尚不能明確表達(dá)的能力。如國際象棋大師們洞察棋局的能力。另一個問題是涉 及問題的原概念，在人工智能中叫問題表示的選擇，人們常能找到某種思考問題的方法，從而 使求解變易而解決該問題。到目前為止，人工智能程序已能知道如何考慮它們要解決的問題， 即搜索解答空間，尋找較優(yōu)解答。 2、 自然語言處理。 自然語言的處理是人工智能技術(shù)應(yīng)用于實際領(lǐng)域的典型范例，經(jīng)過多年艱苦努力，這一 領(lǐng)域已獲得了大量令人注目的成果。目前該領(lǐng)域的主要課題是：計算機(jī)系統(tǒng)如何以主題和對話 情境為基礎(chǔ)，注重大量的常識世界知識和期望作用，生成和理解自然語言。這是一個極其 復(fù)雜的編碼和解碼

24、問題。 3、邏輯推理與定理證明。 邏輯推理是人工智能研究中最持久的領(lǐng)域之一，其中特別重要的是要找到一些方法，只 把注意力集中在一個大型的數(shù)據(jù)庫中的有關(guān)事實上，留意可信的證明，并在出現(xiàn)新信息時適時 修正這些證明。對數(shù)學(xué)中臆測的題。定理尋找一個證明或反證，不僅需要有根據(jù)假設(shè)進(jìn)行演繹 的能力，而且許多非形式的工作，包括醫(yī)療診斷和信息檢索都可以和定理證明問題一樣加以形 式化，因此，在人工智能方法的研究中定理證明是一個極其重要的論題。 4、專家系統(tǒng)。 專家系統(tǒng)是目前人工智能中最活躍、最有成效的一個研究領(lǐng)域,它是一種具有特定領(lǐng)域內(nèi) 大量知識與經(jīng)驗的程序系統(tǒng)。近年來，在“ 專家系統(tǒng)”或“ 知識工程”的研究中

25、已出現(xiàn)了成 功和有效應(yīng)用人工智能技術(shù)的趨勢。人類專家由于具有豐富的知識，所以才能達(dá)到優(yōu)異的解決 問題的能力。那么計算機(jī)程序如果能體現(xiàn)和應(yīng)用這些知識，也應(yīng)該能解決人類專家所解決的問 題，而且能幫助人類專家發(fā)現(xiàn)推理過程中出現(xiàn)的差錯，現(xiàn)在這一點已被證實。如在礦物勘測、 化學(xué)分析、規(guī)劃和醫(yī)學(xué)診斷方面，專家系統(tǒng)已經(jīng)達(dá)到了人類專家的水平。成功的例子如： prospector 系統(tǒng)發(fā)現(xiàn)了一個鉬礦沉積，價值超過 1 億美元。dendrl 系統(tǒng)的性能已超過一 般專家的水平，可供數(shù)百人在化學(xué)結(jié)構(gòu)分析方面的使用。my cin 系統(tǒng)可以對血液傳染病的診斷 治療方案提供咨詢意見。經(jīng)正式鑒定結(jié)果，對患有細(xì)菌血液病、腦膜炎

26、方面的診斷和提供治療 方案已超過了這方面的專家。 5、智能信息檢索技術(shù)。 信息獲取和精化技術(shù)已成為當(dāng)代計算機(jī)科學(xué)與技術(shù)研究中迫切需要研究的課題，將人工 智能技術(shù)應(yīng)用于這一領(lǐng)域的研究是人工智能走向廣泛實際應(yīng)用的契機(jī)與突破口。 4 2.4 博弈算法極大極小搜索算法博弈算法極大極小搜索算法 1 . 博弈樹一與或圖博弈樹一與或圖 grundy 游戲 有一堆數(shù)目為 n 的錢幣，由兩位選手輪流進(jìn)行分堆，要求每個選手每次只把其中某一堆分 成數(shù)目不等的兩小堆。 例如選手甲把 n 分成兩堆后， 輪到乙就可以挑其中一堆來分， 如此進(jìn) 行下去， 直到有一位選手先無法把錢幣分成不相等的兩堆時就得認(rèn)輸. 5 錢幣問題分

27、析: 如果用數(shù)字序列 x1 xn 表示 n 堆錢幣不同個數(shù)，再用兩個說明符號 max,min 表示選手，那 么(x1, ,xn,m)表示某個選手的走步狀態(tài)，規(guī)則 if(x1, ,xn,max) and (xi=y+z 而對于 ma x 擴(kuò)展出的所有 mi n 節(jié)點， 要確保 ma x 節(jié)點獲勝，必須所有 mi n 節(jié)點都是必敗節(jié)點;因此對 ma x 層節(jié)點來說，是一個“ 或”的概 念，而對于 mi n 層節(jié)點，是一個“ 與”的概念。由此擴(kuò)展出來的博弈樹，稱為“與或圖” 。 2.極大極小算法極大極小算法 博弈程序的任務(wù)就是對博弈樹進(jìn)行搜索找出當(dāng)前最優(yōu)的一步行棋。 對博弈樹進(jìn)行極大極小搜索， 可以

28、達(dá)到這一目的。極大極小搜索，是因為博弈雙方所要達(dá)到的目的相反， 一方要尋找的利 益恰是一方失去的利益， 所以博弈的一方總是希望下一走是兒子節(jié)點中取值最大者， 而另一 方恰恰相反。 這便形成了極大極小過程。 當(dāng)然，程序不能也沒有必要做到搜索整棵博弈樹的所有節(jié)點，對于一些已經(jīng)確定為不佳的 走步可以將以它為根節(jié)點的子樹剪掉。 而且，搜索也不必真地進(jìn)行到分出勝負(fù)的棋局，只需要在一定深度范圍內(nèi)對局面進(jìn)行評價 即可。 只有搜索空間縮小到一定程度， 搜索才可以真正的進(jìn)行。當(dāng)搜索進(jìn)行到一定深度， 用 局面評價機(jī)制來評價棋局， 按照極大極小的原則選出最優(yōu)，向上回溯， 給出這一局面的父親 節(jié)點的價值評價，然后再繼

29、續(xù)向上回溯，一 直到根節(jié)點，最優(yōu)走步就是這樣搜索出來的。例如： 設(shè)計一個評估函數(shù) f，對所有棋局進(jìn)行評估。 = 我方勝定的棋局 n 0 對我方有利的棋局 n， f(n) =0 和局或雙方勢均力敵的棋局 n， 0 對我方不利的棋局 n =- 我方敗定的棋局 n 基本思想：考慮雙方向前對弈若干步，然后作出決策，從可能的走法中選擇對自己最有利的走 法。即考慮與或樹(狀態(tài)空間)的若干層，我方(max)走棋時，選擇下一層評估值最大的方向走棋， 對方(min)的走法選擇下一層評估值最小的方向走棋，最后一層的結(jié)點直接用評估函數(shù)估算，然 后計算上層結(jié)點的倒推值，一般來說，考慮的層數(shù)越多，得到的倒推值就更準(zhǔn)確。

30、 3.極大極小法過程描述極大極小法過程描述 a)t:=(s,max), open:=s, closed=(); b)loop1: if open=() then go loop2; c)n:=first(open), remove(n,open), add(n,closed) d)if n 可以直接判定勝、負(fù)或平局 then f(n) =或 -或 0 else expend(n)ni,add(ni,t) if d(ni)k then add(ni,open), go loop 1; else 計算 f(ni), go loop1 /到達(dá)深度 k e)loop2 :if closed=() th

31、en go loop3 else n =first(closed); f)if (npmax)且(f（ncimin）有值) then f(np)=max(f(nci),remove(np ,closed) /若 max 所有子節(jié)點均有值，則該 max 取其極大值 if (npmin)且(f（ncimax）有值) then f(np)=min(f(nci),remove(np ,closed /若 min 所有子節(jié)點均有值，則該 min 取其極小值 g)go loop2 h)loop3: if f(s) nil then exit(end m(move,t) 算法補充說明： 分兩個階段計算 f(

32、s) 用寬度優(yōu)先法生成規(guī)定深度的全部博弈樹，然后對其所有端節(jié)點計算其靜態(tài)估計函數(shù)值。 從底向上逐級求非端節(jié)點的倒推估計值，直到求出初始節(jié)點的倒推值 f(s)為止。 根據(jù) f(s)即可取得較好的走步 等對手響應(yīng)后，再以當(dāng)前狀態(tài)為初始狀態(tài)，重復(fù)調(diào)用該過程即可。 第三章第三章 五子棋單機(jī)部分詳細(xì)設(shè)計五子棋單機(jī)部分詳細(xì)設(shè)計 在本次“五子棋單機(jī)部分“程序的編寫中，運用了博弈樹進(jìn)行搜索，在選取最優(yōu)的走步時使用極 大極小分析法，考慮到搜索的時間復(fù)雜度和空間復(fù)雜度，在程序中只進(jìn)行了2步搜索，即計算機(jī) 在考慮下一步的走法時，只對玩家進(jìn)行一步的推測。 （程序中的棋盤規(guī)格為15*15） 下面對具體做法進(jìn)行描述： 3

33、.13.1數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)定義： 棋盤定義：int board1515； 在15*15的棋盤上，獲勝的情況總共有572種， 表 1 獲勝的情況 * 如表1中的第一行“*“所代表的格子就是一種獲勝組合。 計算機(jī)和玩家的獲勝組合情況bool ctable1515572, bool ptable1515572，來表示棋盤上的各個位置都在那種獲勝組合中。 計算機(jī)和玩家在各個獲勝組合中所填入的棋子數(shù)int win2572,如有一方在某一獲勝組合 的棋子數(shù)達(dá)到5個，該方即獲勝。 bool player:是否輪到玩家下棋 bool computer:是否輪到計算機(jī)下棋 bool start:游戲是否開

34、始 bool pwin:玩家是否獲勝 bool cwin:計算機(jī)是否獲勝 cpoint m_pplastpos;/玩家走的前一步棋 cpoint m_pclastpos;/計算機(jī)走的前一步棋 為便于說明程序的主要算法，這里先說本程序中估價函數(shù)的選取方法： e=p1+p2; p1為下完當(dāng)前這步棋時計算機(jī)的得分；p2為下完當(dāng)前這步棋時玩家的得分（p2其實為負(fù)） ， 這樣做即考慮了進(jìn)攻的因數(shù)，由考慮了防守的因數(shù)，兩個方面都進(jìn)行了考慮，防止計算機(jī)只考 慮進(jìn)攻而忽略防守，同時也防止計算機(jī)只考慮防守而忽略進(jìn)攻，從而達(dá)到比較好的情況。 3.23.2主要流程描述主要流程描述 其程序流程如下： （1）初始化棋盤

35、：判斷哪方先開始， （2）初始化計算機(jī)和玩家的獲勝組合情況 bool ctable1515572,bool ptable1515572 void initializeboard()，里面設(shè)置好ctable ptable win 等變量 （3）給出下了一個子后的分?jǐn)?shù)：根據(jù)各個獲勝組合里擁有的不同棋數(shù)來給不同的分?jǐn)?shù) int givescore(int type, int x, int y) int i,score=0; for(i=0;i572;i+) /計算機(jī)下 if(type=1) if(ctablexyi) switch(win1i) case 1: score+=5; break; cas

36、e 2: score+=50; break; case 3: score+=100; break; case 4: score+=10000; break; default: break; /人下 else if(ptablexyi) switch(win0i) case 1: score-=5; break; case 2: score-=50; break; case 3: score-=500; break; case 4: score-=5000; break; default: break; return score; （4）核心程序 ， （5）即計算機(jī)如何運用極小極大法分析， （6

37、）選取最優(yōu)走法， （7）在程序中極小極大法即體現(xiàn)在兩個while循環(huán)前后及之間的內(nèi)容，其估價函數(shù)的體現(xiàn)在 ctemp+pscore中 void comturn() /bestx,best為當(dāng)前最佳位置，i，j是人能下的各種位置；pi，pj是計算機(jī)能下的各種位置 int bestx,besty,i,j,pi,pj,ptemp,ctemp,pscore=10,cscore=-10000, ctempboard1515,ptempboard1515; int m,n,temp120,temp220;/暫存第一步搜索的信息 if(start) if(board77=2) bestx=7; besty=

38、7; else bestx=8; besty=8; start=false; else /尋找最佳位置 getboard(ctempboard,board); while(searchblank(i,j,ctempboard) /進(jìn)行第一步查找 n=0; pscore=10; getboard(ptempboard,board);/獲取當(dāng)前棋盤狀態(tài) ctempboardij=3;/標(biāo)記已被查找 ctemp=givescore(1,i,j); for(m=0;mptemp)/此時為玩家下子，運用極小極大法時應(yīng)選取最小值 pscore=ptemp; for(m=0;mcscore) /此時為計算機(jī)

39、下子，運用極小極大法時應(yīng)選取最最大值 cscore=ctemp+pscore; bestx=pi; besty=pj; boardbestxbesty=1; if(m_pclastpos.x!=-1 else drawwhitechess(m_pclastpos.x,m_pclastpos.y); if(!m_bwfirst) drawnowblack(bestx,besty); else drawnowwhite(bestx,besty); m_pclastpos.x=bestx; m_pclastpos.y=besty; for(i=0;i572;i+) /修改計算機(jī)下子后，棋盤的變化狀況

40、 if(ctablebestxbestyi if(ptablebestxbestyi) ptablebestxbestyi=false; win0i=7; computer=false; player=true; （8）玩家下棋：（其中坐標(biāo)（9） 加減目的是調(diào)整圖片的位置和棋盤對齊） void onlbuttondown(uint nflags, cpoint point) int x,y,tx,ty; / todo: add your message handler code here and/or call default if(player while(ty=36) ty-=36; tx

41、+=x/36; ty+=y/36; if(tx18) x=x/36+1; else x=x/36; if(ty18) y=y/36+1; else y=y/36; if(boardxy=2) boardxy=0;/設(shè)為玩家的棋子 if(m_pplastpos.x!=-1 else drawblackchess(m_pplastpos.x,m_pplastpos.y); if(!m_bwfirst) drawnowwhite(x,y); else drawnowblack(x,y); m_pplastpos.x=x; m_pplastpos.y=y; for(int i=0;i572;i+)/修

42、改玩家下子后棋盤狀態(tài)的變化 if(i=80) i=80; if(ptablexyi if(ctablexyi) ctablexyi=false; win1i=7; player=false; computer=true; cdialog:onlbuttondown(nflags, point); （10） 程序流程的部分控制： void ontimer(uint nidevent) / todo: add your message handler code here and/or call default iswin();/是否已有一方獲勝 if(pwin) /玩家獲勝 killtimer(0

43、); messagebox(恭喜，您真厲害!); player=false; computer=false; m_binit=true; else if(cwin) /計算機(jī)獲勝 killtimer(0); messagebox(抱歉，您輸了); player=false; computer=false; m_binit=true; else /雙方都沒有獲勝 if(computer) comturn(); cdialog:ontimer(nidevent); 第四章第四章 五子棋聯(lián)機(jī)部分詳細(xì)設(shè)計五子棋聯(lián)機(jī)部分詳細(xì)設(shè)計 4.1 聯(lián)機(jī)網(wǎng)絡(luò)游戲概述聯(lián)機(jī)網(wǎng)絡(luò)游戲概述 本設(shè)計里的網(wǎng)絡(luò)版部分并不是平時的

44、網(wǎng)絡(luò)游戲，它不需要另外的服務(wù)器，客戶端程序同時 擁有了服務(wù)端的功能，但只能供兩個直連用戶（例如在同一局域網(wǎng)的用戶）連機(jī)對戰(zhàn)，概括的 說，它其實是一個簡化后的“網(wǎng)絡(luò)游戲” 。我們先了解一下一般網(wǎng)絡(luò)游戲的架構(gòu)。 系統(tǒng)大多數(shù)采用客戶端/服務(wù)器（c/s）編程模式，tcp/ip 協(xié)議作為客戶端和服務(wù)器的通信 網(wǎng)絡(luò)層，.客戶端采用 winsocket api 作為網(wǎng)絡(luò)層。 系統(tǒng)采用多服務(wù)器分布式架構(gòu)，由一個主服務(wù)器（mainserver）和多個從服務(wù)器（playserver） 同時工作以實現(xiàn)游戲邏輯和用戶管理及通訊的功能。主服務(wù)器管理客戶端用戶身份驗證、登錄 以及管理從服務(wù)器的建立,由多個從服務(wù)器管理游戲

45、通信,大廳及房間,從服務(wù)器可任意添加、刪除、 修改等。 系統(tǒng)首先啟動主服務(wù)器（mainserver） ，主服務(wù)器從數(shù)據(jù)庫中讀取從服務(wù)器的所有信息到主 服務(wù)器的內(nèi)存。首先讀取 gametype 表以建立所有的游戲類型的基本信息，然后讀取 serviceinfo（界面樹結(jié)點信息表）以獲得包括客戶端界面結(jié)構(gòu)、從服務(wù)器的信息、大廳和房間的 一切信息。當(dāng)有客戶端請求登錄并成功和主服務(wù)器連接的時候，主服務(wù)器將這所有的信息一次 性發(fā)到客戶端內(nèi)存，客戶端根據(jù)這些信息生成界面結(jié)構(gòu)樹。 主服務(wù)器啟動后還可以在主服務(wù)器里創(chuàng)建多個從服務(wù)器及房間，創(chuàng)建完成后從服務(wù)器的 ip 地址及端口號就作為它的唯一標(biāo)識被同時寫進(jìn)數(shù)據(jù)

46、庫和主服務(wù)器的內(nèi)存；房間號、房間所屬的 游戲類型、所屬的從服務(wù)器號也作為房間的唯一標(biāo)識被同時寫進(jìn)數(shù)據(jù)庫和主服務(wù)器的內(nèi)存。 從服務(wù)器創(chuàng)建以后就在它所屬的機(jī)器上啟動。 客戶端登錄后首先和主服務(wù)器建立連接（并且一直到客戶端退出才斷開）連接成功后生成 界面結(jié)構(gòu)樹（前述） ，當(dāng)用戶點擊某個游戲房間的時候系統(tǒng)從內(nèi)存中讀出這個房間的所有信息 （前述） ，根據(jù)房間所屬從服務(wù)器的 ip 地址及端口號試圖和這個從服務(wù)器建立連接，連接成功 后相應(yīng)的從服務(wù)器就將這個房間的所有信息發(fā)到這個客戶端，客戶端收到以后就根據(jù)這些信息 生成房間。每當(dāng)有客戶端的游戲位置發(fā)生改變的時候就向從服務(wù)器發(fā)送改變信息，從服務(wù)器保 存、修改所

47、有與它連接的客戶端的位置信息列表。 當(dāng)一張桌子坐滿時游戲開始。游戲開始后客戶端也是和從服務(wù)器通信以更新游戲信息。 當(dāng)客戶端退出游戲后就回到大廳的這個房間，當(dāng)退出大廳的時候首先和從服務(wù)器斷開連接，然 后和主服務(wù)器斷開連接，最后終止整個客戶端程序。 三 模塊結(jié)構(gòu) 系統(tǒng)包括三大主要模塊結(jié)構(gòu)：mainserver，playserver，game.此外還有客戶端安裝，更新模 塊等。在三大主要模塊結(jié)構(gòu)中還有子 dll（動態(tài)鏈接庫）模塊。 1）mainserver（exe 項目）：封裝主服務(wù)器功能，包括管理客戶端用戶身份驗證、登錄以及管 理從服務(wù)器的建立，數(shù)據(jù)庫讀寫等。 2）playserver（exe 項

48、目）：封裝從服務(wù)器功能，包括管理客戶端游戲通信,游戲邏輯，大廳及 房間等。 3）game（exe 項目）：封裝客戶端所有功能，包括客戶端登錄，大廳及房間，客戶端游戲通 信,游戲邏輯等。 4.2 聯(lián)機(jī)五子棋的設(shè)計聯(lián)機(jī)五子棋的設(shè)計 棋盤等的結(jié)構(gòu)與前面的單機(jī)版是一樣的，這里重點闡述聯(lián)機(jī)版相關(guān)的操作： 4.2.1 與游戲相關(guān)的各種網(wǎng)絡(luò)信息 消息類型，網(wǎng)絡(luò)上傳遞的消息的類型，游戲開始，退出游戲，悔棋等 enum msg_type msg_startgame, msg_agreegame, msg_move, msg_chat, msg_back, msg_gameinfo, msg_exitgame,

49、; 傳送的信息，傳遞消息的緩沖區(qū)以及消息的類型，類型就是上面的枚舉類型 typedef struct _transfer_info msg_type msgtype; char datamax_transferbuf_size; transfer_buf,*ptransfer_buf; 用戶信息，這個結(jié)構(gòu)包括用戶的名字，計算機(jī) ip，輸贏記錄等 typedef struct _user_info char name24; char ip20; int win; int lose; int peace; int fasthand; user_info,*puser_info; 開始游戲，請求開始

50、游戲的用戶名 typedef struct _startgame_info char name24; startgame_info,*pstartgame_info; 同意游戲，同意開始游戲的另一個用戶名 typedef struct _agreegame_info char name24; agreegame_info,*pagreegame_info; 游戲過程中關(guān)于游戲的狀態(tài)信息 typedef struct _game_info int gameinfo; / 1 認(rèn)輸 2 同意認(rèn)輸 4 平局 5 同一平局 6 不同意平局 / 7 悔棋 8 同意 9 不同意 game_info,*pg

51、ame_info; 聊天內(nèi)容，加入聊天功能時要用到 typedef struct _chat_info char *chat; chat_info,*pchat_info; 落子信息，包括誰下子了，下到了哪個位置上 typedef struct _move_info int m_turn; intm_x; intm_y; move_info,*pmove_info; 總共落子信息 typedef struct _record_info int rear; move_info move225; record_info,*precord_info; 4.2.2 相關(guān)的類 由于是博弈游戲，所以我們需

52、要一個裁判類，該類管理棋盤的下子情況（哪些地方下了白 棋，哪些地方下了黑棋，哪些地方是空白的） ，管理某個位置是否能下棋，是否有一方已經(jīng)勝出， 是否和棋等。 class cmatch /裁判類 public: cmatch(); virtual cmatch(); public: int chessboardlwlw; /0 表示沒有子落下;1 表示黑子落下；2 表示白子落下 public: bool candown(int x,int y,int who); bool iswin(int who,int pos52); bool isheqi(); void clear(); ; 同時為便于

53、網(wǎng)絡(luò)編程，我們還用到一個套接字類，用于方便我們初始化網(wǎng)絡(luò)，連接另一臺 計算機(jī)，發(fā)送和接收消息等。 class cmysocket public: cmysocket(); virtual cmysocket(); public: bool initsocket(hwnd hwnd); / 初始化網(wǎng)絡(luò) socket createsocket(); / 創(chuàng)建套接字 bool connectserver(socket sock,cstring ip); / 連接服務(wù)器 bool setclientasyncmodel(socket sock); / 設(shè)置客戶端異步選擇模型 bool setserve

54、rasyncmodel(socket sock); / 設(shè)置服務(wù)端異步選擇模型 bool initserver(socket sock,cstring ip); / 初始化服務(wù)器 void recvbuf(socket sock); / tcp 接收消息 void sendbuf(socket sock,char *buf,int len); / tcp 發(fā)送消息 private: hwnd m_hwnd; ; 比較簡單的游戲流程，當(dāng)一玩家下一步棋后，首先調(diào)用裁判類看這步棋是否合規(guī)則，然后 更新相關(guān)的顯示，同時調(diào)用 cmysocket 把相應(yīng)的消息發(fā)到另一玩家，另一玩家收到消息后就 作出相關(guān)的

55、界面更新及相關(guān)變量的設(shè)置。 第五章第五章 結(jié)論結(jié)論 程序運行結(jié)果如下： 單機(jī)，如圖 6 所示： 圖 6 單機(jī)五子棋運行結(jié)果 聯(lián)機(jī)： 打開聯(lián)機(jī)五子棋程序，如圖 7. 圖 7 聯(lián)機(jī)五子棋 設(shè)置主機(jī)，如圖 8 所示。 圖 8 設(shè)置主機(jī) 連接成功，開始游戲，如圖 9. 圖 9 連接成功 開始游戲 游戲結(jié)束，如圖 10 所示： 圖 10 游戲結(jié)束 本設(shè)計的優(yōu)點：運用了人工智能的算法，能使計算機(jī)模擬人思考五子棋的過程，同時它把 網(wǎng)絡(luò)版也整合到一起，方便聯(lián)機(jī)對戰(zhàn)。 另外，此設(shè)計還存在一些不完美的地方：1.人工智能算法不夠高級或者可以考慮加入等級 調(diào)節(jié)的操作，讓不同玩家能選擇不同的難度進(jìn)行游戲。2.聯(lián)機(jī)對戰(zhàn)只

56、限于局域網(wǎng)，如果有獨立的 服務(wù)端程序就可以消除這個缺點，但考慮到設(shè)計的復(fù)雜程序及時間問題，所以最終設(shè)計成目前 的情況。3.程序的界面可以改善，通過參考目前網(wǎng)絡(luò)上的游戲軟件，界面都很華麗，目的應(yīng)該是 為了吸引玩家，這個也是本設(shè)計需要改進(jìn)的地方。 通過本設(shè)計我進(jìn)一步了解到人工智能算法在計算機(jī)科學(xué)里是多么的重要，同時也進(jìn)一步了 解到面向?qū)ο笤O(shè)計帶來的便利。 參考文獻(xiàn)參考文獻(xiàn) 1鄭煒旸 鋤大地與五子棋網(wǎng)絡(luò)游戲的設(shè)計與實現(xiàn) 20040511 2孫宏偉 何豐泉 五子連珠棋初步 哈爾濱 黑龍江科技出版社 1999 3馬少平等 人工智能，清華大學(xué)出版社 4蔡自興 徐光 人工智能及其應(yīng)用 第三版 清華大學(xué)出版社

57、 200309 5朱全民 博弈機(jī)器人系統(tǒng)的設(shè)計及關(guān)鍵技術(shù)研究 20060424 致謝致謝 本論文是在導(dǎo)師 xxx 悉心指導(dǎo)下完成的，同時也感謝導(dǎo)師給我一次參與實際商業(yè)項目 的機(jī)會，雖然我沒有從頭到尾都參與到項目里，但這過程里真正學(xué)到很多，這些在學(xué)校里 都是無法領(lǐng)會到的。導(dǎo)師淵博的專業(yè)知識，嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度，精益求精的工作作風(fēng)，誨人 不倦的高尚師德，嚴(yán)以律己、寬以待人的崇高風(fēng)范，樸實無華、平易近人的人格魅力對我 影響深遠(yuǎn)。不僅使我樹立了遠(yuǎn)大的學(xué)術(shù)目標(biāo)、掌握了基本的研究方法，還使我明白了許多 待人接物與為人處世的道理。本論文從選題到完成，每一步都是在導(dǎo)師的指導(dǎo)下完成的， 傾注了導(dǎo)師大量的心血。在此，謹(jǐn)向?qū)煴硎境绺叩木匆夂椭孕牡母兄x！本論文的順利完 成，離不開各位老師、同學(xué)和朋友的關(guān)心和幫助。在此感謝所有人的指導(dǎo)和幫助。在四年 的學(xué)習(xí)期間，曾得到很多同學(xué)的關(guān)心和幫助，在此表示深深的感謝。沒有他們的幫助和支 持是沒有辦法完成我的論文的，同窗之間的友誼永遠(yuǎn)長存. 畢業(yè)論文開題報告畢業(yè)論文開題報告 論文（設(shè)計）題目：五子棋游戲的單機(jī)版及網(wǎng)絡(luò)版的實現(xiàn) （簡述選題的目的、思路、方法、相關(guān)支持條件及