五子棋游戲的設(shè)計

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