畢業(yè)設(shè)計（論文）基于visual-c++的五子棋設(shè)計與實現(xiàn)

1、太原科技大學(xué)畢 業(yè) 設(shè) 計（論 文）設(shè)計(論文)題目：基于Visual C+的五子棋設(shè)計與實現(xiàn)姓 名_ _學(xué)院（系）_電子信息工程系_專 業(yè)_ 通信工程_年 級_ 通信082201H_ 指導(dǎo)教師_ _2012年 6 月 14 日 太原科技大學(xué)畢業(yè)設(shè)計（論文）任務(wù)書學(xué)院（直屬系）：電子信息工程系 時間： 2012年1月14日學(xué) 生 姓 名陳磊指 導(dǎo) 教 師司秉楠設(shè)計（論文）題目基于Visual C+的五子棋設(shè)計與實現(xiàn)主要研究內(nèi)容學(xué)習(xí)C+編程語言，在Visual C+6.0環(huán)境中實現(xiàn)五子棋的設(shè)計。研究方法通過Visual C+6.0編寫程序和編譯程序，并成功運行五子棋游戲，實現(xiàn)五子棋的相關(guān)功能。主

2、要技術(shù)指標(或研究目標)1.掌握Visual C+6.0的應(yīng)用，并進行程序的編譯和運行。2.編寫五子棋的相關(guān)程序，以實現(xiàn)五子棋的走棋、悔棋、判斷輸贏、英雄榜記錄等功能。教研室 意見 教研室主任（專業(yè)負責(zé)人）簽字： 年 月 日說明：一式兩份，一份裝訂入學(xué)生畢業(yè)設(shè)計（論文）內(nèi)，一份交學(xué)院（直屬系）目錄 TOC o 1-3 h z u HYPERLINK l _Toc12710071摘要HYPERLINK l _Toc12710072AbstractHYPERLINK l _Toc12710073第1章 緒論-1- HYPERLINK l _Toc127100741.1課題背景-1- HYPERLI

3、NK l _Toc127100761.2五子棋介紹-1- HYPERLINK l _Toc127100761.3目的和意義-2- HYPERLINK l _Toc127100761.4系統(tǒng)設(shè)計思想-3- HYPERLINK l _Toc127100761.5開發(fā)工具簡介-3-HYPERLINK l _Toc12710076第2章 可行性研究與算法分析-5- HYPERLINK l _Toc127100762.1本系統(tǒng)的可行性研究-5- HYPERLINK l _Toc127100762.2算法分析-6- HYPERLINK l _Toc12710076 2.2.1HYPERLINK l _To

4、c12710076博弈樹-6- 2.2.2極大極小值算法-7- HYPERLINK l _Toc127100762.2.3負極大值算法-8- HYPERLINK l _Toc127100762.2.4 Alpha-Beta搜索-8- HYPERLINK l _Toc127100762.2.5 置換表-9- HYPERLINK l _Toc127100762.2.6 哈希表-10- HYPERLINK l _Toc127100762.2.7 歷史啟發(fā)-11- HYPERLINK l _Toc127100762.3 本章小結(jié)-12-HYPERLINK l _Toc12710076第3章 總體設(shè)計-

5、13- HYPERLINK l _Toc127100763.1 總體設(shè)計過程-13- HYPERLINK l _Toc127100763.2 系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計-13- HYPERLINK l _Toc127100763.2.1 系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計-13- HYPERLINK l _Toc127100763.2.2 系統(tǒng)的算法設(shè)計-14- HYPERLINK l _Toc127100763.3 系統(tǒng)模型設(shè)計-15- HYPERLINK l _Toc127100763.4 本章小結(jié)-16-HYPERLINK l _Toc12710076第4章 詳細設(shè)計-17- HYPERLINK l _Toc1

6、27100764.1系統(tǒng)運行平臺設(shè)計-17- HYPERLINK l _Toc127100764.2系統(tǒng)的程序流程圖-17- HYPERLINK l _Toc127100764.3系統(tǒng)主要功能的實現(xiàn)-18- HYPERLINK l _Toc127100764.3.1 新局-18- HYPERLINK l _Toc127100764.3.2 菜單及提示-20- HYPERLINK l _Toc127100764.3.3 游戲結(jié)束-23- HYPERLINK l _Toc127100764.3.4 英雄榜-24- HYPERLINK l _Toc127100764.4本章小結(jié)-26-HYPERLI

7、NK l _Toc12710076第5章 系統(tǒng)測試-27- HYPERLINK l _Toc127100765.1系統(tǒng)軟件測試-27-HYPERLINK l _Toc12710076結(jié)論-30-HYPERLINK l _Toc12710076致謝-32-HYPERLINK l _Toc12710076參考文獻-33-HYPERLINK l _Toc12710076附錄-34-摘要 自從計算機作為游戲?qū)?zhàn)平臺以來，各種棋類游戲如雨后春筍般紛紛冒出。使得那些喜愛下棋，又常?？嘤跊]有對手的棋迷們能隨時過足棋癮。而五子棋游戲由于其規(guī)則簡單，變化多端，深受大眾喜愛。 五子棋不僅能增強人們的抽象思維能力、

8、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。它既有簡單易學(xué)的特點，為人民群眾所喜聞樂見，又有深奧的技巧。既能組織群眾性的比賽、活動，又能舉辦高水平的國際性比賽。 基于五子棋游戲以上的優(yōu)點，開發(fā)五子棋是一個非常有價值的課題。本系統(tǒng)具有功能齊全、簡單易學(xué)、既動手又動腦的特點。尤其是游戲的同時，還有聲音效果的配合，使游戲更加富有趣味性和消遣性。本系統(tǒng)基于Visual C+6.0軟件，主要應(yīng)用估值函數(shù)、負極大值搜索算法、Alpha-Beta剪枝等算法來完成人機對弈功能的實現(xiàn)。本系統(tǒng)的成功開發(fā)，能夠使人們的日常娛樂生活更加豐富多彩。關(guān)鍵詞:五子棋；國際性比賽；人

9、機對弈；Visual C+6.0AbstractSince the computer as a game platform, various board games have mushroomed out. Makes those who love chess, and often do not have the Jimi opponents will be able to keep a full game addiction. Gobang game and its rules are simple, making love by the public. Gobang can not onl

10、y enhance peoples ability to abstract thinking, logical reasoning, spatial imagination and enhancing peoples memory, mental arithmetic ability, but also with deep philosophical, self-help and support. It has easy to learn the characteristics of the eye and ear, other esoteric skills. Can organize th

11、e masses of competitions, activities, but also organized a high level of international competition. Gobang game based on the merits of the above, the development of Gobang is a very valuable subject. The system is fully functional, easy to learn, hands and both mental and physical characteristics. E

12、specially games at the same time, there are sound effects with them to games more interesting and full of fun. Application of this system is mainly valuation function, the negative Maxima search algorithm, such as Alpha-Beta search algorithm to complete the function of the realization of human chess

13、board. The successful development of the system will enable peoples daily life more colorful entertainment.Key words:Gobang International Competition Human Chessboard Visual C+6.0基于Visual C+的五子棋設(shè)計與實現(xiàn)第1章緒論1.1課題背景計算機技術(shù)的發(fā)展，使得計算機在現(xiàn)代企業(yè)、家庭中得以普及，應(yīng)用計算機成為現(xiàn)代人生活中非常重要的一部分。大到政府辦公、教育事業(yè)、商業(yè)活動，小到生活中的每一個細節(jié)。隨著社會進步的節(jié)奏越

14、來越快，人們的生活壓力也越來越大。每天奔波于不同的目的地，忙得沒有時間和朋友見面，忙得想找個釋放壓力的機會都沒有。這個時候，你是不是非常希望有個游戲，能夠陪你輕松愉快度過周末。自從計算機作為游戲?qū)?zhàn)平臺以來，各種棋類游戲如雨后春筍般紛紛冒出。使得那些喜愛下棋，又常常苦于沒有對手的棋迷們能隨時過足棋癮，而且這類軟件大都水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍”便是最具說服力的代表。五子棋是一種受大眾廣泛喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性和消遣性。同時具有簡單易學(xué)、既動手又動腦的特點。1.2五子棋介紹五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一?，F(xiàn)

15、代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five In a Row的縮寫)，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。相傳早在堯造圍棋之前，五子棋游戲在民間已經(jīng)相當(dāng)盛行了。據(jù)增山海經(jīng)中記載：“休輿之山有石焉，名曰帝臺之棋，五色而文狀鶉卵。”辭海中亦言：“五子棋中棋類游戲，棋具與圍棋相同，兩人對局，輪流下子，先將五子連成一行者為勝?！碧茣r由高麗使者帶到高麗，后來輾轉(zhuǎn)反復(fù)，流傳到日本。起先是在日本皇宮內(nèi)盛行的游戲，只限于王室成員、貴族階層之間的對弈，后來據(jù)說被出入皇宮的挑夫看見，由此便流行民間。五子棋起源于古代

16、中國，發(fā)展于日本，風(fēng)靡于歐洲。對于它與圍棋的關(guān)系有兩種說法，一種說法是早于圍棋，早在“堯造圍棋”之前，民間就已有五子棋游戲；另一說法是源于圍棋，是圍棋發(fā)展的一個分支。在中國的文化里，倍受人們的青睞。古代的五子棋的棋具與圍棋相同，縱橫各十七道。五子棋大約隨圍棋一起在我國南北朝時先后傳入朝鮮、日本等地。據(jù)日本史料文獻介紹，中國古代的五子棋是經(jīng)由高麗(朝鮮)，于1688年至1704年的日本元祿時代傳到日本的。到日本明治32年(公元1899年)，經(jīng)過公開征名，“連珠”這一名稱才被正式確定下來，取意于“日月如合壁，五星如連珠”。從此，連珠活動經(jīng)過了不斷的改良，主要是規(guī)則的變化(即對執(zhí)黑棋一方的限制)。例

17、如，1899年規(guī)定，禁止黑白雙方走“雙三” ；1903年規(guī)定，只禁止黑方走“雙三” ；1912年規(guī)定，黑方被迫走“雙三”亦算輸；1916年規(guī)定，黑方不許走“長連” ；1918年規(guī)定，黑方不許走“四、三、三” ；1931年規(guī)定，黑方不許走“雙四” ，并規(guī)定將1919的圍棋盤改為1515的連珠專用棋盤。本世紀初五子棋傳入歐洲并迅速風(fēng)靡全歐。通過一系列的變化，使五子棋這一簡單的游戲復(fù)雜化、規(guī)范化，而最終成為今天的職業(yè)連珠五子棋，同時也成為一種國際比賽棋?，F(xiàn)代五子棋（連珠）的基本下法是：先由執(zhí)黑棋一方將一枚棋子落在天元點上，為了尊重對方和出于禮貌，持白棋的一方通常將盤面的第二手棋布在天元下方周圍。1.

18、3目的和意義五子棋游戲不僅能增強人們的抽象思維能力、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑方式所特有的特征“短、平、快” ，又有中國古典哲學(xué)所包含的高深學(xué)問“陰陽易理” ；它既有簡單易學(xué)的特點，為人民群眾所喜聞樂見，又有深奧的技巧；既能組織舉辦群眾性的比賽、活動，又能組織舉辦高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀，它是中西方文化的交融點，也是中西方文化交流的一個平臺。五子棋的根在中國，在這個國境里，他有著廣泛的群眾基礎(chǔ)。但與世界先進的五子棋技術(shù)相比，我們的棋藝水平還要繼續(xù)提高，所以我們要推廣五子棋，宣

19、傳五子棋，爭取在較短的時間內(nèi)趕上和超過世界五子棋壇的先進水平。在這種環(huán)境下，開發(fā)一個易學(xué)實用的五子棋游戲軟件是很有必要的。中國作為五子棋的發(fā)源國，要對五子棋在下個世紀的發(fā)展起到世界性的推動作用。五子棋的發(fā)展在中國出現(xiàn)方興未艾、星火燎原之勢。同時還有一大批的中生代棋手和充滿希望的“明日之星”。相信，中國棋手攀登五子棋巔峰的日子會早日來到。1.4系統(tǒng)設(shè)計思想一個優(yōu)秀的游戲軟件，必須有一個正確的設(shè)計思想，通過合理地選擇數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)以及開發(fā)環(huán)境，構(gòu)成一個完善的體系結(jié)構(gòu)，才能充分發(fā)揮計算機應(yīng)用的優(yōu)勢。根據(jù)游戲玩家的實際需求，本系統(tǒng)的設(shè)計按照下述原則進行。（1）實用性：系統(tǒng)以用戶需求為目標，以方便用

20、戶為原則，同時融入先進的設(shè)計思想。根據(jù)用戶實際的需求情況，量身制作一個功能齊全、操作簡單、實用性強的游戲軟件。充分滿足游戲玩家的需求，真正成為為玩家提供輕松、娛樂、休閑的工具。（2）先進性：本軟件將充分應(yīng)用現(xiàn)有成熟的計算機技術(shù)、軟件開發(fā)技術(shù)，為用戶提供高性能的系統(tǒng)，可以方便的實現(xiàn)玩家的需要。（3）高可靠性：一個實用的系統(tǒng)同時必須是可靠的，本系統(tǒng)通過合理而先進的結(jié)構(gòu)設(shè)計以及軟、硬件的優(yōu)化選型，可保證系統(tǒng)的可靠性與容錯性。（4）可維護性：系統(tǒng)的設(shè)計要求方便維護，包括硬件的維護，軟件的維護（更改，升級等）。（5）可擴展性及靈活性：系統(tǒng)的設(shè)計以方便未來業(yè)務(wù)的擴展和系統(tǒng)擴充為目標，系統(tǒng)要求能夠方便的升級

21、，充分保護系統(tǒng)的投資。玩家可以根據(jù)自己的需要，靈活設(shè)置自己的游戲。（6）智能性：智能化是這個游戲軟件的一大特色。系統(tǒng)在設(shè)計時，充分考慮系統(tǒng)運行的智能性，如果有充足的時間改進，計算機就可以實現(xiàn)更高的AI，在游戲中走的每一步就會考慮得更周密。1.5開發(fā)工具簡介Visual C+6.0是Microsoft公司開發(fā)的基于C/C+的面向?qū)ο蟮目梢暬砷_發(fā)工具，它是Visual Studio中功能最為強大、代碼效率最高的開發(fā)工具。Visual C+6.0與以前的版本相比有了多方面的改進。它的編譯器、調(diào)試器、連接器、編輯器、資源編輯器都有所加強。在編輯器中還提供了自動語句生成功能，編輯器會像Visual

22、Basic一樣自動提示函數(shù)的參數(shù)、對象的成員。另外，Visual C+ 6.0還提供了很多向?qū)АFC提供了一些新的類，提供了更強大的數(shù)據(jù)訪問功能。用戶可利用Visual C+6.0以兩種方式編寫Win32應(yīng)用程序，一種方式是基于Windows API的C編程方式，另一種是基于MFC的C+編程方式。Visual C+ 6.0的主要特點如下：Visual C+ 6.0的最大特色就是提供面向?qū)ο蠹夹g(shù)的支持，它利用類把大部分與用戶界面設(shè)計有關(guān)的Windows API函數(shù)封裝起來，通過MFC（Microsoft Foundation Class）類庫的方式提供給開發(fā)人員使用，大大提高了程序代碼的重用性

23、。Visual C+ 6.0提供一個功能強大的應(yīng)用程序生成向?qū)ppWizard，這也是其得意之處。有了AppWizard，用戶將不會為創(chuàng)建繁瑣的初始化代碼而苦惱。AppWizard將幫助MFC類庫的用戶自動生成一個運行程序框架一個空的不能做任何事情的應(yīng)用程序，而用戶只需要在該框架的適當(dāng)部分添加擴充代碼就可以得到一個滿意的應(yīng)用程序。Visual C+ 6.0的另一個強大工具就是Class Wizard，用戶通過它能夠方便而有效地使用和管理MFC類庫。以前，繼承和派生一個類是一件很麻煩的事，而現(xiàn)在簡單了，只需在Class Wizard中指定一些必要信息，Visual C+ 6.0將自動為你生成類

24、的框架和代碼。Visual C+ 6.0利用“所見即所得”的方式完成程序界面的設(shè)計，大大減輕了程序設(shè)計人員的勞動強度，提高了開發(fā)效率。Visual C+ 6.0的功能強大，用途廣泛。不僅可以編寫普通的應(yīng)用程序，還能很好的進行系統(tǒng)及通信軟件的開發(fā)。第2章可行性研究與算法分析2.1本系統(tǒng)的可行性研究本系統(tǒng)要實現(xiàn)的目標：作為一個悠閑的小游戲軟件，首先應(yīng)該為用戶提供一套方便的操作方法，在游戲模式、用戶操作、反饋信息方面應(yīng)該有明確的說明，能夠讓大多數(shù)玩家能快速上手，使該游戲看上去是一款悠閑的精品。本系統(tǒng)的流程圖描述如下：玩家在新開局后，可以設(shè)置本局游戲，包括對弈模式、游戲級別、中英文菜單、聲音效果等進行

25、設(shè)置，即初始化棋盤。初始化棋盤完成后，玩家和計算機就可以在分析了當(dāng)前棋局以后下棋，即對弈階段。在玩家和計算機每下了一手棋以后，都會進行勝負的判斷，如有勝負，則結(jié)束此局游戲。如果此局玩家的成績比英雄榜里的成績更好，則把玩家的姓名和成績記錄到英雄榜中，覆蓋原來的玩家名和成績。本游戲軟件的系統(tǒng)流程圖，如圖2.1所示。圖2.1系統(tǒng)流程圖本系統(tǒng)是一款休閑的小游戲，是人們?nèi)粘Ｉ願蕵返墓ぞ?。只要針對大眾的喜好，使系統(tǒng)功能齊全，操作簡單，界面美觀大方，就一定會有市場潛力。根據(jù)該系統(tǒng)目標來衡量所需的技術(shù)是否具備，一般可從軟硬件的性能要求、環(huán)境條件、操作人員水平和數(shù)量等方面去考慮和分析?？紤]到系統(tǒng)實施的可行性，

26、在軟件方面選擇了性能穩(wěn)定的VC+6.0開發(fā)環(huán)境、C+語言來進行開發(fā)。VC+是非常成熟的開發(fā)工具，因此無論在安全性、可用性及可靠性等方面都毫無置疑，因此軟件方面是可行的。在硬件方面，則選擇空間較大，只要是Pentium III系列及以上的計算機，內(nèi)存在256M以上，硬盤在1GB，都可以滿足系統(tǒng)的開發(fā)需要。當(dāng)然，硬件的配置越高，系統(tǒng)的開發(fā)與運行會更流暢。考慮到如今的家用或商用電腦硬件的整體配置水平，系統(tǒng)在硬件方面是可行的。2.2算法分析五子棋游戲的開發(fā)在搜索算法方面，可以有多種選擇。通過從不同的角度分析各種搜索方法的效率，來考慮本系統(tǒng)的算法應(yīng)用。開局時計算機每走一步的平均耗時(ms)，如表2.1所

27、示。表2.1各種算法每走一步平均耗時(ms) 通過上表，可以看出使用置換表技術(shù)和歷史啟發(fā)技術(shù)可以增強搜索效率。綜合分析表中幾種算法的效率，本系統(tǒng)按照計算機下每一手棋所應(yīng)用的算法的大致順序，采用的主要算法有博弈樹、負極大值算法、Alpha-Beta剪枝算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。下面詳細地介紹一下這些算法。2.2.1博弈樹設(shè)想下五子棋的情形，兩人對弈，我們將其中一位叫做甲，另一位叫做乙。假定現(xiàn)在該甲下棋，甲可以有225種走法（不論好壞）；而對甲的任一走法，乙也可以有與之相對的若干種下法。然后又輪到甲走棋，對乙的下法甲又有若干種方法應(yīng)對。如此往復(fù)。顯然，我們可以依此構(gòu)建一棵博弈樹，將

28、所有的走法羅列出來。在這棵樹的根部是棋局的初始局面。根的若干子節(jié)點則是由甲的每一種可能走法所生成的局面，而這些節(jié)點的子節(jié)點則是由與之相對的乙的每一種可能走法所生成的局面。在這棵樹的末梢，是結(jié)束的棋局，甲勝或者乙勝或者是雙方都無法取勝的平局。如果我們令甲勝的局面值為WIN，乙勝的局面值為LOST，而和局的值為DRAW。當(dāng)輪到甲走時，甲定會選擇子節(jié)點值為WIN或DRAW（如果沒有值為WIN的子節(jié)點的話）的下法；而輪到乙時，乙則會選擇子節(jié)點值為LOST或DRAW（如果沒有值為LOST的子節(jié)點的話）的下法。對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應(yīng)的局面輪到甲下棋，則該節(jié)點的值是其所有子節(jié)點

29、中值最佳（對甲而言）的一個的值；如果該節(jié)點所對應(yīng)的局面輪到乙走棋，則該節(jié)點的值是其所有子節(jié)點中值最差（對甲而言）的一個的值。這樣看來從這棵樹的葉子節(jié)點倒推向根部，就可以得出所有節(jié)點的值。雙方就可以從其所面臨的棋局中選擇一步好棋。然后一步步走向勝利。博弈樹是從根部向下遞歸產(chǎn)生的一棵包含所有可能的對弈過程的搜索樹，這里稱為完全搜索樹。Neill Graham形容此過程類似于在一個狀態(tài)圖中尋求從初始狀態(tài)通向終了狀態(tài)的過程。只是狀態(tài)圖搜索僅有一個主體參加，僅是單方面做出的路徑選擇。而博弈樹的搜索則有對立的雙方參加，一方只能做出一半選擇，而這一半選擇的目的是使對方遠離其竭力靠近的目標。也就是說狀態(tài)圖搜索

30、是純粹的或樹（OR tree），而博弈樹搜索是與或樹（AND/OR tree）。但是在五子棋游戲中，我們沒有建立完全搜索樹的可能。一方面是因為很多情形根本就到達不了葉子節(jié)點。另一方面，這棵樹上的節(jié)點數(shù)量也已多到了無法處理的程度。所以我們需要其它的算法來減少搜索的數(shù)量。2.2.2極大極小值算法（Minimax Algorithm）在上面的博弈樹中，如果我們令甲勝的局面值為1，乙勝的局面值為-1，而和局的值為0。當(dāng)輪到甲下棋時，甲定會選擇子節(jié)點值最大的下法；而輪到乙時，乙則會選擇子節(jié)點值最小的下法。所以，對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應(yīng)的局面輪到甲下棋，則該節(jié)點的值是其所有子節(jié)

31、點中值最大的一個的值。而如果該節(jié)點所對應(yīng)的局面輪到乙下棋，則該節(jié)點的值是其所有子節(jié)點中值最小的一個的值。對博弈樹的這個變化僅僅是形式上的，本質(zhì)上絲毫未變，但是這個形式更容易推廣以運用到一般實際的情形。既然建立整棵的搜索樹不可能，那么，為當(dāng)前所面臨的局面找出一步好棋如何？也就是通過少量的搜索，為當(dāng)前局面選擇一步較好的走法。在通常的棋局當(dāng)中，一個局面的評估往往并不像輸、贏、平3種狀態(tài)這么簡單，在分不出輸贏的局面中棋局也有優(yōu)劣之分。也就是說，要用更細致的方法來刻畫局面的優(yōu)劣，而不是僅僅使用1、-1、0三個數(shù)字刻畫3種終了局面。假定我們有一個函數(shù)可以為每一局面的優(yōu)劣評分。例如甲勝為+；乙勝為-；和局為

32、0；這樣我們可以建立一棵固定深度的搜索樹，其葉子節(jié)點不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點，其值由上述函數(shù)評出；對于中間節(jié)點，如同前面提到的那樣，甲方取子節(jié)點的最大值，乙方取子節(jié)點的最小值。這個評分的函數(shù)稱作靜態(tài)估值函數(shù)（Static Evaluation Function）。用以取代超出固定深度的搜索。顯然，我們無法擁有絕對精確的靜態(tài)估值函數(shù)。否則，只要這個靜態(tài)估值函數(shù)就可以解決所有的棋局了。估值函數(shù)給出的只是一個較粗略的評分，在此基礎(chǔ)上進行的少量搜索的可靠性，理論上是不如前述的WIN，LOST，DRAW三種狀態(tài)的博弈樹的，但這個方法卻是可實現(xiàn)的。利用具體的知識構(gòu)成評估函數(shù)的搜索叫做

33、啟發(fā)式搜索（Heuristic Search）。估值函數(shù)在有些文獻中也稱為啟發(fā)函數(shù)（Heuristic Function）。在博弈樹搜索的文獻當(dāng)中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。MinMax算法是對弈的基礎(chǔ)思想。2.2.3負極大值算法（Negamax Algorithm）普通的極大極小值算法看起來有一點笨，既然一方試圖取極大值而另一方試圖取極小值也就是說我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動作。Knuth和Moore在1975年提出了負極大值（Negamax）方法，消除了兩方的差別，而且簡潔優(yōu)雅。使用負極大值方法，博弈雙方都取極大值。

34、2.2.4Alpha-Beta搜索在極大極小搜索的過程中，存在著一定程度的數(shù)據(jù)冗余。舉一個最簡單的例子：在象棋博弈的過程中，如果某一個節(jié)點輪到甲走棋，而甲向下搜索節(jié)點時發(fā)現(xiàn)第一個子節(jié)點就可以將死乙（節(jié)點值為最大值），則剩下的節(jié)點就無需再搜索了，甲的值就是第一個子節(jié)點的值。這個過程，就可以將大量冗余的（不影響結(jié)果的）節(jié)點拋棄。圖2.2A lpha-Beta剪枝示例圖將上述這個情形推廣一下，設(shè)想有如圖2.1左半部所示的一棵極大極小樹的片斷，節(jié)點下面數(shù)字為該節(jié)點的值，節(jié)點B的值為18，節(jié)點D的值為16，由此我們可以判斷節(jié)點C的值將小于等于16（取極小值）；而節(jié)點A的值為節(jié)點Max（B,C），為18，

35、也就是說不再需要估算節(jié)點C的其他子節(jié)點如E、F的值就可以得出父節(jié)點A的值了。這樣將節(jié)點D的后繼兄弟節(jié)點減去稱為Alpha剪枝（alpha cutoff）。設(shè)想有如圖2-2右半部所示的一棵極大極小樹的片斷，節(jié)點B的估值為8，節(jié)點D的估值為18，由此我們可以判斷節(jié)點C的值將大于等于18（取極大值）；而節(jié)點A的值為節(jié)點Min（B,C），為8。也就是說不再需要求節(jié)點C的其他子節(jié)點如E、F的值就可以得出父節(jié)點A的值了。這樣將節(jié)點D的后繼兄弟節(jié)點減去稱為Beta剪枝（beta cutoff）。2.2.5置換表（Transposition Table）在極大極小搜索的過程中，改進搜索算法的目標在于將不必搜索

36、的（冗余）分枝從搜索的過程中盡量剔除，以達到搜索盡量少的分枝來降低運算量的目的。在先前談到的幾種搜索算法中，我們看到可以通過 Alpha-Beta剪枝來剪除兩種類型的冗余分枝/節(jié)點，但是已經(jīng)搜索過的節(jié)點不可以免于搜索。從圖2-2的極大極小樹的片斷中，我們可以看出，該片斷從節(jié)點A開始，有兩個分B和C（為簡化問題，其他節(jié)點從略），B 有子節(jié)點D，C有子節(jié)點E，再往下D有子節(jié)點F，E有子節(jié)點G。讀者可以看到，在極大極小樹的不同分枝上，存在著完全相同的節(jié)點。在上圖中，節(jié)點F和G完全相同。對于節(jié)點F，在搜索分枝的時候，就可能已經(jīng)搜索過了。那么，在搜索節(jié)點G的子節(jié)點時，我們能不能直接利用已經(jīng)搜索過的節(jié)點F

37、的結(jié)果，而不是重新搜索一遍節(jié)點G？想法是可行的。如果要利用已經(jīng)搜索過的節(jié)點的結(jié)果，我們就要用一張表把搜索過的節(jié)點記錄下來。然后在后續(xù)的搜索中，察看記錄在表中的這些結(jié)果，如果將要搜索的某個節(jié)點已有記錄，就直接利用記錄下來的結(jié)果。這種方法叫做置換表（Transposition Table，簡稱TT）。如果將Alpha-Beta搜索過程中每一節(jié)點的結(jié)果都記錄下來，則在任意節(jié)點向下搜索之前先查看這些紀錄，就可避免上述重復(fù)的操作。但是這個置換表如何實現(xiàn)的？困難集中在時間和空間復(fù)雜度上。1可能的節(jié)點可以認為是無窮多，將其存入一張表中要占據(jù)多少存儲空間呢？2即使有無窮多內(nèi)存空間，一個節(jié)點要從表中找到自己對應(yīng)

38、的一項，需要花費多少時間？雖然有序表可用二分查找等快速的算法，但要維持表中內(nèi)容有序，又要進行大量排序操作，會耗費更多時間。如何解決？2.2.6哈希表（Hash Table）置換表的實現(xiàn)在時間和空間復(fù)雜度上的疑問。實際上已經(jīng)明確了要實現(xiàn)置換表必須要滿足如下條件：1查找記錄中的節(jié)點數(shù)據(jù)時速度要非?？欤詈檬穷愃朴陔S機存取。2將節(jié)點數(shù)據(jù)放入記錄的速度也要非常快。這就意味著數(shù)據(jù)項插入的過程不可有數(shù)據(jù)移動排序等操作。3要能在有限的存儲空間內(nèi)進行。可以利用哈希表，哈希方法的思想為每一個學(xué)過數(shù)據(jù)結(jié)構(gòu)或算法課程的開發(fā)人員所熟知。對棋類博弈來說，定義一個巨大的數(shù)組，將每一局面記入其中，每一局面在數(shù)組中對應(yīng)惟一的

39、位置。這樣，將數(shù)據(jù)記入和取出就類似于隨機讀寫，不會有耗時的查找和插入過程。但是，以象棋而論，如果為每一局面在數(shù)組中對應(yīng)一個與其他局面不同的位置的話，則組合的結(jié)果是全世界所有的計算機內(nèi)存加起來也不夠這樣一個數(shù)組用。那么讓每一局面在數(shù)組中對應(yīng)惟一的位置，但并不保證數(shù)組中每一個數(shù)據(jù)項對應(yīng)惟一的局面如何呢？比如將所有的局面對應(yīng)在106單位的數(shù)組上。這樣，必然有一些局面對應(yīng)在相同的位置上；但是對一次搜索而言，這種情況發(fā)生的概率并不高。一旦某個搜索過的局面在該數(shù)組中未找到，我們不過是對它進行Alpha-Beta搜索而已。不同的局面對應(yīng)在數(shù)組中同一存儲單元上的情形，叫做沖突。我們將利用哈希方法實現(xiàn)置換表的方

40、法敘述如下。定義哈希數(shù)組如下：structHASHITEMint64 checksum；/64位哈希值，用以驗證表中數(shù)據(jù)是否是要找的局面int depth；/該表項求值時的搜索深度enum exact，lower_bound，upper_bound entry_type；/表項值的類型double eval； /所代表的節(jié)點的值hashtableHASH_TABLE_SIZE；/定義大小為 HASH_TABLE_SIZE 的哈希數(shù)組對要搜索的每一節(jié)點，計算出它的一個哈希值（hashIndex，通常是一個32位數(shù)對哈希表大小取模）以確定此局面在哈希表中的位置。計算另一個64位的哈希值（Check

41、sum）來校驗表中的數(shù)據(jù)項是否是所要的那一項。在對某一局面搜索之前，先查看哈希表項 hashTablehashIndex，如果 hashTablehashIn-dex.checksum=Checksum并且hashTablehashIndex.depth 大于等于最大搜索深度減去當(dāng)前層數(shù)，就返回hashTablehashIndex.eval作為當(dāng)前局面的估值。當(dāng)對一個局面的搜索完成之后，將Checksum、當(dāng)前層數(shù)和估值結(jié)果保存到 hashTablehashIndex當(dāng)中，以備后面的搜索使用。2.2.7歷史啟發(fā)（History Heuristic）在前面的章節(jié)我們曾經(jīng)提到過，Alpha-Bet

42、a搜索的剪枝效率，幾乎完全取決于節(jié)點的排列順序。在節(jié)點排列順序處于理想狀態(tài)的情況下，Alpha-Beta搜索需遍歷的節(jié)點數(shù)僅為極大極小算法所需遍歷的節(jié)點數(shù)的平方根的兩倍左右。也就是說對一棵極大極小樹來說，如果極大極小搜索需遍歷106個節(jié)點求得結(jié)果，那么處于理想狀態(tài)的 Alpha-Beta搜索僅需遍歷約2000個節(jié)點就可求得結(jié)果。而在節(jié)點的排序最不理想的情況下，Alpha-Beta搜索要遍歷的結(jié)點數(shù)同極大極小算法一樣多。如何調(diào)整待展開的走法排列的順序，是提高搜索效率的關(guān)鍵。根據(jù)部分已經(jīng)搜索的結(jié)果來調(diào)整將要進行搜索的節(jié)點順序是一個可行的方向。通常一個局面經(jīng)搜索得知較好時，在其后繼節(jié)點當(dāng)中往往有一些

43、相似的局面，比如僅有一些無關(guān)緊要的棋子位置不同等等。這些相似的局面往往也是較好的。可以通過一些較復(fù)雜的判斷來找出這些相似的局面，率先搜索，從而提高剪枝效率。但這一方法需要具體棋類相關(guān)的知識，并且往往判斷復(fù)雜而效果不彰。J.Schaeffer提出了History Heuristic的方法，在基于Alpha-Beta的搜索當(dāng)中，一個好的走法可以定義如下：1由其產(chǎn)生的節(jié)點引發(fā)了剪枝。2未引發(fā)剪枝，但是其兄弟走法中的最佳者。在搜索的過程中，每當(dāng)找到一個好的走法，就將與該走法相對應(yīng)的歷史得分作一個增量，一個多次被搜索并確認為好的走法的歷史紀錄就會較高，當(dāng)搜索中間節(jié)點時，將走法根據(jù)其歷史得分排列順序，以獲

44、得較佳的排列順序。這比采用基于棋類知識而對節(jié)點排序的方法要容易得多。由于歷史得分表隨搜索而改變，對節(jié)點順序的排列也會隨之動態(tài)改變。2.3本章小結(jié)本系統(tǒng)的可行性研究，從市場可行性、技術(shù)可行性方面著手進行考慮。市場可行性主要研究五子棋游戲的潛在市場；技術(shù)可行性主要研究系統(tǒng)開發(fā)軟硬件條件。綜上考慮，本項目的開發(fā)技術(shù)成熟、完備，運行環(huán)境優(yōu)良，具有一定的開發(fā)前景。算法分析部分主要介紹了五子棋游戲開發(fā)用到的算法。按照計算機下每一手棋時，應(yīng)用算法的大致順序，本系統(tǒng)使用的主要算法有極大極小值算法、負極大值算法、Alpha-Beta算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。其中的極大極小值算法是對弈算法的基礎(chǔ)。

45、哈希表技術(shù)的使用，是置換表技術(shù)能夠?qū)崿F(xiàn)的基礎(chǔ)。各種算法的綜合使用，得以提高算法的效率。第3章總體設(shè)計3.1總體設(shè)計過程總體設(shè)計過程通常由四個主要階段組成：系統(tǒng)體系結(jié)構(gòu)設(shè)計，確定系統(tǒng)的具體體系結(jié)構(gòu)實現(xiàn)方案；系統(tǒng)模塊設(shè)計，確定系統(tǒng)模塊層次；結(jié)構(gòu)算法設(shè)計，確定軟件結(jié)構(gòu)和典型算法；交互設(shè)計，確定系統(tǒng)的交互界面?？傮w設(shè)計的典型過程包括如下七個階段：（1）選取合理的體系結(jié)構(gòu)方案（2）推薦最佳方案（3）系統(tǒng)模塊設(shè)計（4）數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計（5）交互設(shè)計（6）編寫文檔（7）審查和復(fù)審由于本系統(tǒng)應(yīng)用到算法的設(shè)計，下面詳細描述一下第四個階段。高效率的程序基于良好的數(shù)據(jù)結(jié)構(gòu)與算法，一般來說，數(shù)據(jù)結(jié)構(gòu)與算法就是一類數(shù)

46、據(jù)的表示及其相關(guān)的操作。從數(shù)據(jù)表示的觀點來看，存儲在數(shù)組中的一個有序整數(shù)表也是一種數(shù)據(jù)結(jié)構(gòu)。算法是指對數(shù)據(jù)結(jié)構(gòu)施加的一些操作。一個算法如果能在所要求的資源限制范圍內(nèi)將問題解決好，則稱這個算法是有效率的。一個算法如果比其他已知算法所需要的資源都少，這個算法也稱為是有效率的。算法的代價是指消耗的資源量。一般來說，代價是由一個關(guān)鍵資源，例如時間或空間來評估的。3.2系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計3.2.1系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計本系統(tǒng)在開發(fā)過程中，為了設(shè)計更合理的數(shù)據(jù)結(jié)構(gòu)，使用了用戶自定義數(shù)據(jù)類型結(jié)構(gòu)體和枚舉類型。 1利用哈希表方法實現(xiàn)置換表，哈希表中元素的結(jié)構(gòu)定義如下：typedef struct HASHI

47、TEMLONGLONG checksum; /哈希值，用以驗證表中數(shù)據(jù)是否是要找的局面EnterType enterType; / 數(shù)據(jù)類型short nPly; / 取到此值時的層次short value; / 節(jié)點的值 HashItem;2用以表示走法的結(jié)構(gòu)：typedef struct STONEMOVE int x; / 棋子的橫坐標 int y; / 棋子的縱坐標 int score; / 此走法的分數(shù)StoneMove;3枚舉類型的使用enum EnterTypeexam,lower,uper;/搜索的精確值、下邊界、上邊界enum IDD = IDD_BEST ;enum IDD

48、 = IDD_PENTE_DIALOG ;3.2.2系統(tǒng)的算法設(shè)計本系統(tǒng)是通過多個算法的結(jié)合使用來增強算法的效率。應(yīng)用的主要算法有博弈樹、負極大值算法、Alpha-Beta剪枝算法、置換表、哈希表、歷史啟發(fā)等。其中的博弈樹算法是搜索算法的基礎(chǔ)，但是它的搜索量太大，在實現(xiàn)的過程中，我們不可能讓系統(tǒng)搜索所有的結(jié)點，于是使用極大極小值算法對博弈樹進行了改進。極大極小值算法是對弈算法的基礎(chǔ)。普通的極大極小值算法看起來有一點笨，既然一方試圖取極大值而另一方試圖取極小值，也就是說我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動作。而負極大值方法，消除了兩方的差別，博弈雙方都取極大值。在極大

49、極小搜索的過程中，存在著一定程度的數(shù)據(jù)冗余。這就需要Alpha-Beta算法的剪枝功能來消除冗余。在搜索過程中，利用置換表技術(shù)將 Alpha-Beta搜索過程中每一節(jié)點的結(jié)果都記錄下來，則在任意節(jié)點向下搜索之前先查看這些記錄，就可避免重復(fù)搜索，以提高搜索效率。而置換表的實現(xiàn)則是依賴哈希表。這種算法之間的優(yōu)化組合，使得本系統(tǒng)能夠?qū)崿F(xiàn)它有效的搜索。3.3系統(tǒng)模塊設(shè)計五子棋游戲是在系統(tǒng)地分析了游戲玩家的各項需求，以實際為基礎(chǔ)進行設(shè)計的。本系統(tǒng)可以進行人與計算機的對弈，還可以實現(xiàn)兩個人在同一臺計算機上對弈。本系統(tǒng)包括三大模塊：游戲模塊、設(shè)置模塊、幫助模塊。每個模塊包括的主要內(nèi)容如下： 1游戲模塊：新局

50、、初級、中級、專家、英雄榜。2設(shè)置模塊：悔棋、提示、英文菜單、聲音效果。3幫助模塊：有關(guān)本系統(tǒng)的介紹其中：在新局對話框下，可以對本局游戲進行設(shè)置：（1）對弈方式選擇：人與計算機對弈、人與人對弈（2）先手選擇：玩家執(zhí)黑先下、計算機執(zhí)黑先下（3）是否選擇聲音效果本系統(tǒng)的功能模塊，如下圖3.1所示。圖3.1系統(tǒng)功能模塊圖3.4本章小結(jié)本系統(tǒng)按照總體設(shè)計典型過程的七個階段進行，詳細介紹了系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計。本系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)主要采用了用戶自定義數(shù)據(jù)類型結(jié)構(gòu)體和枚舉類型。算法設(shè)計是利用各種算法的優(yōu)化組合來提高算法的效率。本系統(tǒng)主要包括三大功能模塊游戲模塊、選項模塊、功能模塊。每個功能模塊包括若干子功

51、能。本系統(tǒng)以需求分析結(jié)論為基礎(chǔ)，考慮得比較全面。 第4章詳細設(shè)計4.1系統(tǒng)運行平臺設(shè)置1硬件環(huán)境：臺式計算機（PC）一臺，如表4.1所示。表4.1運行環(huán)境硬件配置硬件配置處理器Pentium III800以上內(nèi)存256M以上硬盤空間1G以上2軟件環(huán)境：Windows 2000 Professional /Server or Windows XP操作系統(tǒng)。4.2系統(tǒng)的程序流程圖1程序流程圖的作用程序流程圖是人們對解決問題的方法、思路或算法的一種描述。2流程圖的優(yōu)點：（1）采用簡單規(guī)范的符號，畫法簡單；（2）結(jié)構(gòu)清晰，邏輯性強；（3）便于描述，容易理解。3本系統(tǒng)的程序流程為玩家首先為新一局游戲的對

52、弈模式、先手、游戲級別、是否有聲音效果、使用中/英文菜單等功能進行設(shè)置，玩家確定設(shè)置完棋局以后，就進入人與計算機或是人與人的對弈階段，在對弈的過程中，每下一手棋，都會進行本局游戲是否結(jié)束的判斷，結(jié)束的標志是游戲的一方有五個棋子相連。如果本局游戲沒有結(jié)束，則玩家可以選擇使用悔棋或讓計算機向玩家提示兩項功能。如果本局游戲結(jié)束，判斷玩家的成績是否優(yōu)于英雄榜里的成績，如果是，就會出現(xiàn)喜登英雄榜界面（如圖4.8），玩家可以輸入自己的大名，之后就可以進行新一局游戲的設(shè)置。本系統(tǒng)的程序流程，如圖4.1所示。圖4.1系統(tǒng)的程序流程圖4.3系統(tǒng)主要功能的實現(xiàn)4.3.1新局1實現(xiàn)目標在主窗體菜單下，單擊新局菜單項

53、，就會出現(xiàn)新一局的設(shè)置界面。在這個界面中，可以對本局游戲的對弈方式、先手和聲音效果進行設(shè)置。在對弈方式方面，可以單擊單選按鈕或是使用快捷鍵，選擇是與計算機對弈還是兩人在同一計算機上對弈，游戲默認的選擇是與計算機對弈。在先手方面，可以選擇是玩家執(zhí)黑先下還是計算機執(zhí)黑先下，默認的選擇是玩家執(zhí)黑先下。在聲音效果方面，可以單擊復(fù)選框，選擇是否在下棋的過程中有聲音效果，默認選擇有聲音效果。在對這三項設(shè)置完成之后，單擊確定按鈕，則保存對本局游戲的設(shè)置，即初始化棋盤結(jié)束，進入人與計算機或人與人的對弈階段。本系統(tǒng)的新局設(shè)置，如圖4.2所示。圖4.2新局界面2實現(xiàn)過程實現(xiàn)新局界面的流程，如圖4.3所示。圖4.3

54、新局界面流程圖4.3.2菜單及提示1實現(xiàn)目標在主窗體的選項菜單下，可以選擇游戲過程中是使用中文菜單還是英文菜單。游戲默認的選擇是中文菜單。如果你選擇了英文菜單，則在游戲過程中所有出現(xiàn)的界面都是用英文表示的。在游戲過程中，可以使用主窗體的選項菜單下的提示功能。當(dāng)你對棋局感到不知所措的時候，可以讓計算機給你一些提示。提示的方式是在棋盤上計算機覺得最佳的位置出現(xiàn)一個矩形框。你可以參考他的提示，這可能會對你下棋有些幫助。當(dāng)你在棋盤上一個棋子都沒有的時候，使用此功能，按照國際正規(guī)比賽的規(guī)則，計算機會提示你在天元的位置下第一個子。菜單及提示功能的設(shè)置，如圖4.4、圖4.5、圖4.6所示。圖4.4游戲菜單圖

55、4.5選項菜單 圖4.6提示效果2實現(xiàn)過程實現(xiàn)菜單及提示界面的流程，如圖4.7所示。圖4.7菜單及提示界面流程圖4.3.3游戲結(jié)束1實現(xiàn)目標 當(dāng)每局游戲結(jié)束的時候，會出現(xiàn)一個對話框。在對話框上，會顯示本局游戲是黑棋勝還是白棋勝，雙方共下了多少手棋。如果玩家使用黑棋則顯示黑棋悔棋幾次，如果玩家使用白棋則顯示白棋悔棋幾次。如果在雙方共下了不到二十手棋就輸了的話，在對話框上就會顯示：“哎，你也實在太差了，難道你不知道該好好學(xué)習(xí)嗎？”否則顯示：“哈哈，你輸了，去多學(xué)幾招兒吧”。單擊確定按鈕之后，就可以對下一局游戲進行設(shè)置。每一局游戲結(jié)束界面，如圖4.8所示。圖4.8游戲結(jié)束界面2實現(xiàn)過程實現(xiàn)游戲結(jié)束界

56、面的流程，如圖4.9所示。圖4.9結(jié)束界面流程圖4.3.4英雄榜1實現(xiàn)目標英雄榜里按初級、中級、專家級三個級別記錄玩家的姓名和成績。每一局游戲結(jié)束的時候，如果玩家獲勝，而且成績優(yōu)于英雄榜里的成績，系統(tǒng)就會彈出喜登英雄榜界面。在這個界面中，顯示著此局游戲所選的級別，可以輸入玩家的姓名，單擊確定按鈕之后，玩家的大名和此局游戲的成績就會出現(xiàn)在英雄榜的相應(yīng)級別的記錄里。單擊英雄榜界面的重置按鈕，則英雄榜里的記錄就恢復(fù)到初始默認狀態(tài)。喜登英雄榜的界面，如圖4.10所示。圖4.10喜登英雄榜界面英雄榜的界面，如圖4.11所示。圖4.11英雄榜界面2實現(xiàn)過程實現(xiàn)英雄榜的流程，如圖4.12所示。圖4.12英雄

57、榜界面流程圖4.4本章小結(jié)本章主要介紹了系統(tǒng)將要運行的軟硬件環(huán)境，系統(tǒng)程序開發(fā)的總體流程，并根據(jù)此流程，完成了代碼的編寫工作。依據(jù)本系統(tǒng)的總體設(shè)計，在這個階段實現(xiàn)了各個功能模塊的程序?qū)崿F(xiàn)工作。這里詳細介紹了新局界面、菜單及提示界面、游戲結(jié)束界面、英雄榜及喜登英雄榜界面的實現(xiàn)目標和實現(xiàn)過程。每一個界面的實現(xiàn)過程都用程序流程圖描述出來，使得每一個功能模塊的實現(xiàn)過程都更直觀易懂。第5章系統(tǒng)測試5.1系統(tǒng)軟件測試選擇游戲菜單下的人機對戰(zhàn)的初級選項，以下中白棋為電腦方,測試結(jié)果如圖5.1。圖5.1初級測試結(jié)果選中中級選項，測試結(jié)果如圖5.2。圖5.2中級測試結(jié)果選中專家選項，測試結(jié)果如圖5.3。圖5.3

58、專家測試結(jié)果喜登英雄榜的測試，其結(jié)果如圖5.4。 圖5.4喜登英雄榜測試結(jié)果英雄榜測試結(jié)果如圖5.5。圖5.5英雄榜測試結(jié)果從測試結(jié)果可以看出，游戲模塊、設(shè)置模塊、幫助模塊中的主要內(nèi)容都實現(xiàn)了，達到了預(yù)期的設(shè)計要求，本次設(shè)計比較成功。結(jié)論隨著近幾十年來人工智能的飛速發(fā)展，越來越多的具有智能的機器進入了人類的生活，人工智能的重要性如今顯而易見。而五子棋人機對弈程序的設(shè)計與實現(xiàn)這個課題，正好提供了這樣一個研究的機會，通過對人工智能中博弈方面的研究（人機對弈），在簡單的人機對弈全局設(shè)計方面，以及具體到相關(guān)的算法上，都有了深入的了解。通過編寫這個程序，體會最為深刻的一點是系統(tǒng)架構(gòu)和設(shè)計模式的重要性。即

59、使是對于一個并不大的程序，代碼的組織都是非常重要的，因為這關(guān)系到日后的維護以及擴展。這個游戲之中，有關(guān)博弈樹算法的知識都可以直接從無所不包的Internet上獲取，甚至可以直接獲得一個完整的五子棋人機對弈算法的源代碼級模塊。但是對于系統(tǒng)的架構(gòu)，卻完全是自己的事情，成千上萬行的代碼需要通過合適的方法組織起來，使程序員編寫代碼更加有條理，更加符合軟件工程的標準，這才是最重要的。本系統(tǒng)實現(xiàn)了五子棋游戲的設(shè)計，總結(jié)起來，主要完成了以下工作。首先，對五子棋游戲有了更加深刻的理解。五子棋游戲起源于中國古代，發(fā)展于日本，風(fēng)靡于歐洲，它是中西文化的交流點，是古今哲理的結(jié)晶。五子棋不僅能增強人們的抽象思維能力、

60、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。它既有簡單易學(xué)的特點，為人民群眾所喜聞樂見，又有深奧的技巧；既能組織群眾性的比賽、活動，又能舉辦高水平的國際性比賽。在可行性研究階段，確定了本系統(tǒng)要實現(xiàn)的目標。作為一個悠閑的小游戲系統(tǒng)，首先應(yīng)該為用戶提供一套方便的操作方法，在游戲模式，用戶操作,反饋信息方面應(yīng)該有明確的說明，能夠讓大多數(shù)玩家能快速上手。使該游戲看上去是一款悠閑的精品。在需求分析階段，按需求的業(yè)務(wù)需求、用戶需求、功能需求三個層次來完成。其中的用戶需求就是市場的需求，它是需求分析階段最重要的工作。本系統(tǒng)在詳細設(shè)計階段實現(xiàn)了人與人在同一臺計算機上對