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

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

2、要技術指標(或研究目標)1.掌握Visual C+6.0的應用，并進行程序的編譯和運行。2.編寫五子棋的相關程序，以實現(xiàn)五子棋的走棋、悔棋、判斷輸贏、英雄榜記錄等功能。教研室 意見 教研室主任（專業(yè)負責人）簽字： 年 月 日說明：一式兩份，一份裝訂入學生畢業(yè)設計（論文）內，一份交學院（直屬系）目錄 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)設計思想-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 本章小結-12-HYPERLINK l _Toc12710076第3章 總體設計-

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

6、27100764.1系統(tǒng)運行平臺設計-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 游戲結束-23- HYPERLINK l _Toc127100764.3.4 英雄榜-24- HYPERLINK l _Toc127100764.4本章小結-26-HYPERLI

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

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

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+的五子棋設計與實現(xiàn)第1章緒論1.1課題背景計算機技術的發(fā)展，使得計算機在現(xiàn)代企業(yè)、家庭中得以普及，應用計算機成為現(xiàn)代人生活中非常重要的一部分。大到政府辦公、教育事業(yè)、商業(yè)活動，小到生活中的每一個細節(jié)。隨著社會進步的節(jié)奏越

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、中值最佳（對甲而言）的一個的值；如果該節(jié)點所對應的局面輪到乙走棋，則該節(jié)點的值是其所有子節(jié)點中值最差（對甲而言）的一個的值。這樣看來從這棵樹的葉子節(jié)點倒推向根部，就可以得出所有節(jié)點的值。雙方就可以從其所面臨的棋局中選擇一步好棋。然后一步步走向勝利。博弈樹是從根部向下遞歸產生的一棵包含所有可能的對弈過程的搜索樹，這里稱為完全搜索樹。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。當輪到甲下棋時，甲定會選擇子節(jié)點值最大的下法；而輪到乙時，乙則會選擇子節(jié)點值最小的下法。所以，對于中間節(jié)點的值可以有如下計算方法：如果該節(jié)點所對應的局面輪到甲下棋，則該節(jié)點的值是其所有子節(jié)

31、點中值最大的一個的值。而如果該節(jié)點所對應的局面輪到乙下棋，則該節(jié)點的值是其所有子節(jié)點中值最小的一個的值。對博弈樹的這個變化僅僅是形式上的，本質上絲毫未變，但是這個形式更容易推廣以運用到一般實際的情形。既然建立整棵的搜索樹不可能，那么，為當前所面臨的局面找出一步好棋如何？也就是通過少量的搜索，為當前局面選擇一步較好的走法。在通常的棋局當中，一個局面的評估往往并不像輸、贏、平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ù)給出的只是一個較粗略的評分，在此基礎上進行的少量搜索的可靠性，理論上是不如前述的WIN，LOST，DRAW三種狀態(tài)的博弈樹的，但這個方法卻是可實現(xiàn)的。利用具體的知識構成評估函數(shù)的搜索叫做

33、啟發(fā)式搜索（Heuristic Search）。估值函數(shù)在有些文獻中也稱為啟發(fā)函數(shù)（Heuristic Function）。在博弈樹搜索的文獻當中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。MinMax算法是對弈的基礎思想。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é)點拋棄。圖2.2A lpha-Beta剪枝示例圖將上述這個情形推廣一下，設想有如圖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）。設想有如圖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é)點，但是已經搜索過的節(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，在搜索分枝的時候，就可能已經搜索過了。那么，在搜索節(jié)點G的子節(jié)點時，我們能不能直接利用已經搜索過的節(jié)點F

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

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

39、位置。這樣，將數(shù)據(jù)記入和取出就類似于隨機讀寫，不會有耗時的查找和插入過程。但是，以象棋而論，如果為每一局面在數(shù)組中對應一個與其他局面不同的位置的話，則組合的結果是全世界所有的計算機內存加起來也不夠這樣一個數(shù)組用。那么讓每一局面在數(shù)組中對應惟一的位置，但并不保證數(shù)組中每一個數(shù)據(jù)項對應惟一的局面如何呢？比如將所有的局面對應在106單位的數(shù)組上。這樣，必然有一些局面對應在相同的位置上；但是對一次搜索而言，這種情況發(fā)生的概率并不高。一旦某個搜索過的局面在該數(shù)組中未找到，我們不過是對它進行Alpha-Beta搜索而已。不同的局面對應在數(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 大于等于最大搜索深度減去當前層數(shù)，就返回hashTablehashIndex.eval作為當前局面的估值。當對一個局面的搜索完成之后，將Checksum、當前層數(shù)和估值結果保存到 hashTablehashIndex當中，以備后面的搜索使用。2.2.7歷史啟發(fā)（History Heuristic）在前面的章節(jié)我們曾經提到過，Alpha-Bet

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

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

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

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

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

47、TEMLONGLONG checksum; /哈希值，用以驗證表中數(shù)據(jù)是否是要找的局面EnterType enterType; / 數(shù)據(jù)類型short nPly; / 取到此值時的層次short value; / 節(jié)點的值 HashItem;2用以表示走法的結構：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)的算法設計本系統(tǒng)是通過多個算法的結合使用來增強算法的效率。應用的主要算法有博弈樹、負極大值算法、Alpha-Beta剪枝算法、置換表、哈希表、歷史啟發(fā)等。其中的博弈樹算法是搜索算法的基礎，但是它的搜索量太大，在實現(xiàn)的過程中，我們不可能讓系統(tǒng)搜索所有的結點，于是使用極大極小值算法對博弈樹進行了改進。極大極小值算法是對弈算法的基礎。普通的極大極小值算法看起來有一點笨，既然一方試圖取極大值而另一方試圖取極小值，也就是說我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動作。而負極大值方法，消除了兩方的差別，博弈雙方都取極大值。在極大

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

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

51、能。本系統(tǒng)以需求分析結論為基礎，考慮得比較全面。 第4章詳細設計4.1系統(tǒng)運行平臺設置1硬件環(huán)境：臺式計算機（PC）一臺，如表4.1所示。表4.1運行環(huán)境硬件配置硬件配置處理器Pentium III800以上內存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）結構清晰，邏輯性強；（3）便于描述，容易理解。3本系統(tǒng)的程序流程為玩家首先為新一局游戲的對

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

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

54、新局界面流程圖4.3.2菜單及提示1實現(xiàn)目標在主窗體的選項菜單下，可以選擇游戲過程中是使用中文菜單還是英文菜單。游戲默認的選擇是中文菜單。如果你選擇了英文菜單，則在游戲過程中所有出現(xiàn)的界面都是用英文表示的。在游戲過程中，可以使用主窗體的選項菜單下的提示功能。當你對棋局感到不知所措的時候，可以讓計算機給你一些提示。提示的方式是在棋盤上計算機覺得最佳的位置出現(xiàn)一個矩形框。你可以參考他的提示，這可能會對你下棋有些幫助。當你在棋盤上一個棋子都沒有的時候，使用此功能，按照國際正規(guī)比賽的規(guī)則，計算機會提示你在天元的位置下第一個子。菜單及提示功能的設置，如圖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游戲結束1實現(xiàn)目標 當每局游戲結束的時候，會出現(xiàn)一個對話框。在對話框上，會顯示本局游戲是黑棋勝還是白棋勝，雙方共下了多少手棋。如果玩家使用黑棋則顯示黑棋悔棋幾次，如果玩家使用白棋則顯示白棋悔棋幾次。如果在雙方共下了不到二十手棋就輸了的話，在對話框上就會顯示：“哎，你也實在太差了，難道你不知道該好好學習嗎？”否則顯示：“哈哈，你輸了，去多學幾招兒吧”。單擊確定按鈕之后，就可以對下一局游戲進行設置。每一局游戲結束界面，如圖4.8所示。圖4.8游戲結束界面2實現(xiàn)過程實現(xiàn)游戲結束界

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

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

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

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

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