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