北京信息科技大學(xué)畢 業(yè) 設(shè) 計(jì) （論 文）題 目： 五子棋游戲的設(shè)計(jì)與實(shí)現(xiàn)學(xué) 院： 計(jì)算機(jī)學(xué)院專 業(yè)： 計(jì)算科學(xué)與技術(shù)學(xué)生姓名： 龍濤 班級(jí)/學(xué)號(hào) 計(jì)科 0701/0755指導(dǎo)老師/督導(dǎo)老師： 李聞起止時(shí)間：2011 年 1 月 21 日 至 2011 年 5 月 30 日摘要摘 要隨著經(jīng)濟(jì)的發(fā)展，社會(huì)競(jìng)爭(zhēng)的激烈，現(xiàn)在社會(huì)進(jìn)入了競(jìng)爭(zhēng)的時(shí)代。上班族為了完成公司業(yè)務(wù)，每天超負(fù)荷的工作；學(xué)生為了不落后他人每天早起晚睡不斷地學(xué)習(xí),壓力巨大。所以為了緩解大家的壓力，使大家在工作、學(xué)習(xí)之余娛樂一下，活躍大腦，提高工作、學(xué)習(xí)效率，我本人設(shè)計(jì)了一個(gè)簡(jiǎn)易的五子棋游戲。本系統(tǒng)將利用五子棋游戲作為研究對(duì)象，在 Windows 平臺(tái)下，運(yùn)用 java 語言設(shè)計(jì)的一個(gè)能夠?qū)崿F(xiàn)人機(jī)對(duì)戰(zhàn)的簡(jiǎn)單游戲。該系統(tǒng)涉及到人工智能方面的知識(shí)，而計(jì)算機(jī)博弈是人工智能研究的一個(gè)重要分支，其中還包括幾個(gè)重要的搜索算法。只有通過一定的研究，才能實(shí)現(xiàn)五子棋的人機(jī)對(duì)戰(zhàn)功能。關(guān)鍵詞：人工智能； 計(jì)算機(jī)博弈 ； 搜索算法 ； 五子棋；AbstractAbstractWith development of economy, social competition is intense, now society has entered into the competition era. Office worker in order to complete the company business, overworked every day; For catching up with others, the student rises early, sleeps late and studies hard. The pressure builds up. So in order to alleviate the pressure, make everyone all over the job, study entertained, active brain, improve work, learning efficiency, I design a simple renju.This system will take the object of study using the renju, designs one to be able to realize the man-machine under the Windows platform with Java language to the simple game which fights.The system involves knowledge of artificial intelligence, and the computer game is one of the important research on artificial intelligence branch, including several important search algorithm. Only through certain research, can realize renju against function Man-machine. Keywords: artificial intelligence ； computer game ； search algorithm ；renju ；目錄目錄摘 要 .IAbstract.II第一章 概述 .11.1 開發(fā)背景 .11.2 課題意義 .11.3 五子棋的發(fā)展與現(xiàn)狀 .21.4 研究?jī)?nèi)容 .4第二章 五子棋程序的介紹 .52.1 五子棋程序的基本功能 .52.2 開發(fā)運(yùn)行環(huán)境 .52.3 軟件開發(fā)工具及開發(fā)語言介紹 .52.4 五子棋程序功能的設(shè)計(jì) .7第三章 五子棋的總體設(shè)計(jì) .83.1 人機(jī)界面的實(shí)現(xiàn)及鼠標(biāo)事件的監(jiān)聽 .83.2 按鈕功能的實(shí)現(xiàn) .113.3 棋子表示 .123.4 下棋表示 .13第四章 五子棋的 AI 算法 .154.1 電腦智能搜索 .154.2 電腦勝負(fù)的判斷 .16第五章 五子棋軟件測(cè)試 .185.1 軟件測(cè)試的定義 .185.2 界面測(cè)試 .185.3 數(shù)據(jù)的測(cè)試 .225.4 用戶驗(yàn)收測(cè)試 .22結(jié)束語 .23參考文獻(xiàn) .25目錄1第一章 概述本章主要介紹畢業(yè)設(shè)計(jì)的開發(fā)背景、課題意義，有關(guān)計(jì)算機(jī)人工智能方面的知識(shí)以及五子棋的發(fā)展與現(xiàn)狀，以及畢業(yè)設(shè)計(jì)的研究?jī)?nèi)容、方向。 1.1 開發(fā)背景隨著計(jì)算機(jī)技術(shù)和互聯(lián)網(wǎng)的飛速發(fā)展，游戲軟件是當(dāng)今世界發(fā)展最迅速,最有影響力,最有潛力與活力的領(lǐng)域之一電腦游戲的出現(xiàn)為人們提供了新的娛樂平臺(tái)，豐富了人們的業(yè)余生活。因此與游戲有關(guān)的軟件深受廣大青少年的喜愛。隨著近幾年來軟件技術(shù)的不斷進(jìn)步、不斷發(fā)展，軟件游戲的操作要求越來越簡(jiǎn)單，大多數(shù)游戲普通人學(xué)幾分鐘就能會(huì)玩，甚至連老年人也慢慢愛上了它。第二次世界大戰(zhàn)以后,電子計(jì)算機(jī)技術(shù)得到了突飛猛進(jìn)的發(fā)展在眾多國(guó)家中美國(guó)的計(jì)算機(jī)技術(shù)發(fā)展最為迅速。1946 年 2 月，世界上第一臺(tái)電子數(shù)字計(jì)算機(jī)(ENIAC)在美國(guó)賓夕法尼亞大學(xué)建造完成。ENIAC 機(jī)的問世,表明了電子數(shù)字計(jì)算機(jī)時(shí)代的到來，具有劃時(shí)代的偉大意義，是科學(xué)技術(shù)發(fā)展史上的重大里程碑。我國(guó)也不落后，在 1956 年研制成功國(guó)產(chǎn)計(jì)算機(jī)的。1958 年和 1959 年我國(guó)先后自主研制成功國(guó)產(chǎn)小型和大型電子管計(jì)算機(jī)。后來出現(xiàn)了集成電路和大規(guī)模集成電路,使電子子計(jì)算機(jī)一代一代實(shí)現(xiàn)更新,性能越來越高，計(jì)算速度越來越快，硬件方面的不斷發(fā)展促使了軟件技術(shù)也迅速發(fā)展。在美國(guó),集中了許多計(jì)算機(jī)軟件的設(shè)計(jì)人才,他們工作之余,時(shí)常喜愛編一種能與人斗智的“游戲”,以此來鍛煉編程的能力這種“游戲 ”花樣繁多,但其特點(diǎn)都是利用計(jì)算機(jī)軟件事先設(shè)計(jì)好的“分析”“ 判斷”能力反過來與人較量 由于不斷修改更新,使計(jì)算機(jī)的“智力”水平與人難分高低到了 90 年代，游戲軟件已經(jīng)為世界各國(guó)的人使用，所謂游戲軟件通常是指用各種程序和動(dòng)畫效果相結(jié)合起來的軟件產(chǎn)品，我們稱之為“游戲軟件“。目前，在網(wǎng)絡(luò)上我們經(jīng)常看到的大型 3D 網(wǎng)絡(luò)游戲和 WEBGAME 網(wǎng)頁游戲等都是通過用“3DMAX、MAYA、FLASH、等動(dòng)畫軟件和JAVA、C+、VB、等程序語言相結(jié)合而開發(fā)出來的，所以叫游戲軟件。其中 BLACKISLAND 和Blizzard.這兩個(gè)強(qiáng)大的游戲制作組對(duì)游戲軟件的發(fā)展起到了巨大的帶動(dòng)作用，還有中國(guó)的洛河工作室在國(guó)內(nèi)也起到了巨大作用，他們讓很多很多人喜歡上了游戲軟件，打開了這個(gè)市場(chǎng)。如今游戲軟件產(chǎn)業(yè)已經(jīng)受到了廣泛的關(guān)注，它年輕有潛力而且吸引人，讓人們?nèi)找尕S富的生活需求得以滿足。而五子棋游戲的誕生更是吸引著不同年齡段的人群，無論男女老少都可以玩，都喜歡玩，而當(dāng)前微型計(jì)算機(jī)已經(jīng)是在廣大人群中流行著，用電腦來下五子棋更是一種時(shí)尚。現(xiàn)在網(wǎng)絡(luò)上出現(xiàn)了各種各樣的五子棋軟件，有大師級(jí)的、新手級(jí)的等等。所有這些都滿足了不同人群的需要，所以當(dāng)前五子棋越來越被許多人所熟悉。目前的五子棋程序的發(fā)展也非?？欤瑥淖畛醯碾p人發(fā)展到人機(jī)（有 AI） ，然后到現(xiàn)在的網(wǎng)絡(luò)對(duì)戰(zhàn)，已經(jīng)受到越來越多人的喜愛和重視。1.2 課題意義人類社會(huì)經(jīng)歷了五千多年的農(nóng)業(yè)文明時(shí)代，又經(jīng)歷了三百多年的工業(yè)文明時(shí)代。經(jīng)過漫長(zhǎng)時(shí)間的發(fā)展，人類文明取得的不可想象的進(jìn)步，人也變的越來越聰明了。人類之所以變得聰明，是因?yàn)槲覀內(nèi)祟愐恢辈粩嗟卦賹?shí)踐中思考，在思考中實(shí)踐。五子棋不目錄2僅能增強(qiáng)思維能力，提高記憶力，而且富含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑的明顯特征“短、平、快” ，又有古典哲學(xué)的高深學(xué)問“陰陽易理” ；它既有簡(jiǎn)單易學(xué)的特性，為人民群眾所喜聞樂見，又有深?yuàn)W的技巧和高水平的國(guó)際性比賽；它的棋文化源淵流長(zhǎng)，具有東方的神秘和西方的直觀；既有“場(chǎng)”的概念，亦有“點(diǎn)”的連接。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。五子棋游戲不但容易上手，而且它區(qū)別于別的游戲，它不但能使人娛樂，而且能使人的頭腦變得更加聰明。而五子棋對(duì)戰(zhàn)有兩種模式：一.人機(jī)對(duì)戰(zhàn)；二.雙人對(duì)戰(zhàn)。這些給人無限樂趣的用途正是人工智能的杰作。正因?yàn)檫@樣它鼓勵(lì)著人們對(duì)它不斷研究，這在很大程度上促進(jìn)了人工智能的發(fā)展，反過來人工智能的理論和技術(shù)上的突破能夠使五子棋程序更完美、更受歡迎！同時(shí)，五子棋游戲程序的開發(fā)也使得五子棋這個(gè)游戲得到了廣泛的推廣，讓世界各地的人們知道五子棋，隨時(shí)地玩上五子棋，這已經(jīng)不再是夢(mèng)想了。五子棋游戲程序使得越來越多的人喜歡上了五子棋，熱愛下五子棋，它是具有很好的帶動(dòng)性的。隨著互聯(lián)網(wǎng)絡(luò)的不斷普及，越來越多的人可以在網(wǎng)絡(luò)上就能夠與他人下五子棋了。1.3 人工智能介紹人類的自然智能伴隨著人類活動(dòng)時(shí)時(shí)處處都存在。人類的許多活動(dòng)，如解題、下猜謎、討論、編制計(jì)劃和編程，甚至駕車、騎車等，都需要智能。如果機(jī)器能夠完成這些任務(wù)，那么就可以認(rèn)為機(jī)器已經(jīng)具有某種程度的“人工智能” 。正因?yàn)檫@樣積累了很多與人工智能有關(guān)的知識(shí)。在一次歷史性的聚會(huì)中人工智能誕生了。為使計(jì)算機(jī)變得更“聰明” ，或者說是計(jì)算機(jī)具有智能，1965 年夏季，在美國(guó)達(dá)特莫斯大學(xué)舉行了一次為期兩個(gè)月的夏季學(xué)術(shù)研討會(huì)。10 位來自美國(guó)數(shù)學(xué)、神經(jīng)學(xué)、心理學(xué)、信息科學(xué)和計(jì)算機(jī)科學(xué)方面的杰出年輕科學(xué)家，在一起共同學(xué)習(xí)和探討了用機(jī)器模擬人類智能的有關(guān)問題，并且麥卡錫提議正式采用了“人工智能 AI(Artificial Intelligence)”這一術(shù)語。從而，一個(gè)以研究如何用機(jī)器來模擬人類智能的新興學(xué)科-人工智能誕生了。人工智能(Artificial Intelligence) ，英文縮寫為 AI。它是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支，它企圖了解智能的實(shí)質(zhì)，并生產(chǎn)出一種新的能以人類智能相似的方式做出反應(yīng)的智能機(jī)器，該領(lǐng)域的研究包括機(jī)器人、語言識(shí)別、圖像識(shí)別、自然語言處理和專家系統(tǒng)等。人工智能的發(fā)展給五子棋賦予了新的生命。隨著對(duì)人工智能的不斷研究，計(jì)算機(jī)博弈也得到了飛速發(fā)展。機(jī)器博弈被認(rèn)為是人工智能領(lǐng)域最具挑戰(zhàn)性的研究方向之一。國(guó)際象棋的計(jì)算機(jī)博弈已經(jīng)有了很長(zhǎng)的歷史,并且經(jīng)歷了一場(chǎng)波瀾壯闊的“搏殺“,“深藍(lán)“計(jì)算機(jī)的勝利也給人類留下了難以忘懷的記憶。經(jīng)過 30 多年的研究，人工智能在現(xiàn)實(shí)生活中得到了不少矚目的成果，而這些成果已經(jīng)建立了一些具有一定“智能”的 AI系統(tǒng)，例如專家系統(tǒng)、定理證明系統(tǒng)、集成電路設(shè)計(jì)與分析系統(tǒng)、自然語言翻譯系統(tǒng)、智能信息檢索系統(tǒng)、疾病診斷系統(tǒng)等。除了這重要的成果之外，還有大受人們歡迎的“智能系統(tǒng)” ，比如現(xiàn)在在網(wǎng)絡(luò)上出現(xiàn)的網(wǎng)絡(luò)游戲、圍棋、象棋、五子棋游戲程序等等，這些都是人工智能的成果，它們極大地改變了人們的生活、給人類帶來了快樂。1.4 五子棋的發(fā)展與現(xiàn)狀1.4.1 五子棋游戲規(guī)則對(duì)局開始時(shí)，先由執(zhí)黑棋一方將一枚棋子落在天元點(diǎn)上，然后由執(zhí)白棋一方在黑棋周圍的交目錄3叉點(diǎn)上落子。但是，為了尊重對(duì)方和禮貌起見，持白棋的一方通常將盤面的第二著棋布在自己河界的一側(cè)，即直止或斜止。此后黑白雙方輪流落子，直到某一方首先在棋盤的橫線、縱線或斜線上形成連續(xù)五子或五子以上僅對(duì)白棋而言 ，則該方就算獲勝。連珠五子棋的一個(gè)特點(diǎn)是先行的一方優(yōu)勢(shì)很大，因此在職業(yè)比賽中對(duì)黑方做了種種限制，以利公平競(jìng)爭(zhēng)。目前五子棋的比賽規(guī)則如下： 1 黑先、白后，從天元開始相互順序落子； 2 最先在棋盤橫向、縱向或斜向形成連續(xù)的同色五個(gè)棋子的一方為勝； 3 黑棋禁手判負(fù)、白棋無禁手。黑棋禁手有“三、三” 、 “四、四”和“長(zhǎng)連”,包括“四、三、三”和“四、四、三” 。黑棋只能以“四、三”取勝； 4 如分不出勝負(fù)，則到為平局； 5 五連與禁手同時(shí)形成，判勝； 6 黑方禁手形成時(shí)，白方應(yīng)立即指出。若白方未發(fā)現(xiàn)或發(fā)現(xiàn)后不立即指出，反而繼續(xù)落子，則禁手失效，不再判黑方負(fù)?！?】 五子棋是黑白雙方或兩個(gè)人之間的競(jìng)技活動(dòng)，由于對(duì)黑白雙方規(guī)則不同，黑棋必須先行。一般采用猜先的方法來決定誰執(zhí)黑先行，即雙方各抓一種顏色的幾枚棋子，大數(shù)減小數(shù)，單數(shù)雙方交換，偶數(shù)不換； 【2】 禁手示例： X X X X 為三、三禁手 X X X 為四、四禁手 X X 為長(zhǎng)連禁手【3】 黑方在落下關(guān)鍵的第五子即形成五連的同時(shí)，如又形成禁手，此時(shí)因黑方已經(jīng)成五，而“五”在五子棋中是至高無上的，故禁手失效，黑方勝； 目錄4【4】 所謂黑方形成禁手，是指黑方落下一子同時(shí)形成兩個(gè)或兩個(gè)以上的活三、沖四及長(zhǎng)連等。此時(shí)白方應(yīng)立即指出，自然而勝。1.4.2 五子棋的發(fā)展與現(xiàn)狀五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠” ，英譯為“Renju”，英文稱之為“Gobang”或“FIR” （Five in a Row 的縮寫） ，亦有“連五子” 、 “五子連” 、“串珠” 、 “五目” 、 “五目碰” 、 “五格”等多種稱謂。到了 21 世紀(jì)已經(jīng)出現(xiàn)了不少棋類，目前按棋類的屬性分類如下:1.按參與人數(shù)分類（Player）：?jiǎn)稳擞螒?，如華容道等滑塊類游戲；雙人游戲，如象棋、圍棋、五子棋等。在棋類中雙人參與的棋類占絕大多數(shù)； 多人游戲，如跳棋。一般說來，參與人數(shù)越多，對(duì)手就越多，情況就越發(fā)復(fù)雜。2.按兵種多少分類（Pieces, Materials）單一兵種，如圍棋、五子棋、蘇拉卡爾塔（Surakarta） 、亞馬遜（Amazons）等；多兵種，如國(guó)際象棋、中國(guó)象棋、日本將棋等。兵種的增加，意味著著法的復(fù)雜程度增加，掌握起來更加困難。3.按著法分類（Move） 走子類：開局前雙方擺好，開局后輪流走動(dòng)棋子。如象棋、國(guó)際象棋、跳棋等；添子類：開局前盤面無子，開局后輪流放入棋子。如圍棋、五子棋、六子棋等；吃子類：對(duì)局過程中可以吃掉對(duì)方的棋子。如象棋、國(guó)際象棋、圍棋等；混合類：在填子的過程中可以吃子（圍棋） ；在走子過程中可以吃子，還可以填子（日本將棋） 。通常情況弈棋雙方輪流施著，各走（下）一步。但是有的棋類在一定條件下一方是可以連續(xù)施著的，即連續(xù)走多步，可成為輪（Turn） 。如跳棋、西洋跳棋、黑白棋（Reversi, Othello） 、點(diǎn)格棋（Dots and Boxes）等。4.按勝負(fù)判決分類（Win-Lose-Draw） 擒獲首領(lǐng)：象棋，國(guó)際象棋等；擺成形狀：連珠類井字棋、五子棋、六子棋等；占領(lǐng)地域：圍棋、點(diǎn)格棋等；剩余子粒：黑白棋、蘇拉卡爾塔等；活動(dòng)余地：亞馬遜等；到目標(biāo)地：跳棋、一字棋、牛角棋等。在所有棋類中五子棋發(fā)展最為迅速，在人群中最受歡迎！這一棋類運(yùn)動(dòng)已迅速在國(guó)際上發(fā)展起來。外國(guó)人都十分看好這一毫不起眼的智力游戲，并認(rèn)為五子棋不僅能提高思維、開發(fā)智力、手腦并用、修身養(yǎng)性 而且富含哲理，具有東方的神秘和西方的直觀，是中西文化的交匯點(diǎn)。許多國(guó)家的人對(duì)五子棋都有不同的愛稱，例如韓國(guó)人把五子棋稱之為“情侶棋”，言下之意是情人之間下五子棋有利于增加情感的交流；歐洲人稱之為“中老年棋”，表示五子棋適合中老年人的生理特點(diǎn)和思維方式；美洲人喜歡將五子棋稱之為“商業(yè)棋”，就是目錄5說商人談生意時(shí)可邊下棋邊談生意，棋下完了生意也談成了。由此可見，盡管國(guó)度不同，語言各異，但人們都可以借助五子棋這一簡(jiǎn)單而又深?yuàn)W的棋藝進(jìn)行交流、比賽，增進(jìn)友誼。十余年來，隨著各地五子棋組織的建立和五子棋的逐步普及，各種五子棋比賽應(yīng)運(yùn)而生，一些民間五子棋組織自籌經(jīng)費(fèi)與地方有關(guān)部門合作，運(yùn)作了不少民間比賽。從國(guó)內(nèi)的比賽來看，北京、天津、上海、鎮(zhèn)江、吉林、黑龍江、安徽、浙江等地先后自籌經(jīng)費(fèi)舉辦了地方性的五子棋比賽，同時(shí)，地區(qū)間的交流也不斷增加，如 1997 年舉辦的京津冀五子棋對(duì)抗賽、2000 年京津五子棋團(tuán)體對(duì)抗賽、2000 年在遼寧鐵嶺舉辦的“中行杯”北方五子棋友好邀請(qǐng)賽、在江蘇鎮(zhèn)江舉辦的“一品梅杯”江蘇五子棋邀請(qǐng)賽等。2001 年國(guó)家體育總局批準(zhǔn)試辦全國(guó)性五子棋比賽后，中國(guó)棋院在 2002年和 2003 年連續(xù)舉辦了兩屆全國(guó)五子棋邀請(qǐng)賽，吸引了全國(guó)各地的高手參加，取得了圓滿成功。2004 年 10 月，中國(guó)棋院將舉辦第四屆全國(guó)五子棋邀請(qǐng)賽。全國(guó)五子棋邀請(qǐng)賽作為全國(guó)參賽人數(shù)最多，規(guī)模最大，水平最高的比賽，已經(jīng)成為一項(xiàng)全國(guó)性五子棋的傳統(tǒng)賽事。到了 21 世紀(jì)五子棋游戲在網(wǎng)絡(luò)上面是非?；鸨┑模以谄迮朴螒蚶锩嫱婕胰藬?shù)排名總會(huì)占到很前面，不愧是風(fēng)靡全球的棋牌游戲啊！在未來中，將會(huì)有越來越多的人關(guān)注五子棋，喜歡五子棋，那么將其變?yōu)樯虡I(yè)化也會(huì)越來越多，而且還可以以教育孩子的方式來將其嵌套進(jìn)去，或者用來做測(cè)試等等。隨著人工智能技術(shù)的不斷進(jìn)步，我相信今后的五子棋游戲?qū)?huì)更加精彩、更加完善，讓我們拭目以待吧。1.5 研究?jī)?nèi)容本游戲是在 Windows 環(huán)境下完成一個(gè)簡(jiǎn)易五子棋游戲的設(shè)計(jì)。五子棋是人工智能的一個(gè)成果之一，它涉及到計(jì)算機(jī)博弈理論，棋盤表示、走法生成以及搜索算法等知識(shí)，最終實(shí)現(xiàn)人機(jī)對(duì)戰(zhàn)。完成后，要提交演示系統(tǒng)和相關(guān)程序、提交畢業(yè)論文。演示系統(tǒng)要能夠運(yùn)行正常、能夠進(jìn)行人機(jī)對(duì)戰(zhàn)，并通過此次畢業(yè)設(shè)計(jì)，對(duì)計(jì)算機(jī)博弈理論有了更加深入、透徹的了解。通過這次實(shí)踐最終能夠提高自己的學(xué)習(xí)能力、思維能力且培養(yǎng)了一定的開發(fā)能力。目錄6第二章 五子棋程序的介紹本章主要是介紹該五子棋系統(tǒng)的基本功能和其結(jié)構(gòu)圖,并對(duì)實(shí)現(xiàn)該系統(tǒng)的開發(fā)工具、運(yùn)行環(huán)境和開發(fā)語言做了較為詳細(xì)的闡釋。2.1 五子棋程序的基本功能1.顯示一