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

1、<p><b>　　太原科技大學(xué)</b></p><p>　　畢 業(yè) 設(shè) 計(jì)（論 文）</p><p>　　設(shè)計(jì)(論文)題目：基于Visual C++的五子棋設(shè)計(jì)與實(shí)現(xiàn)</p><p>　　姓 名____ _______</p><p>　　學(xué)院（系）_電子信息工程系__</p>&l

2、t;p>　　專 業(yè)___ 通信工程_____</p><p>　　年 級(jí)___ 通信082201H___ </p><p>　　指導(dǎo)教師__ ___</p><p>　　2012年 6 月 14 日</p><p>　　太原科技大學(xué)畢業(yè)設(shè)計(jì)（論文）任務(wù)書(shū)</p><p>　　學(xué)院（直屬系）

3、：電子信息工程系 時(shí)間： 2012年1月14日</p><p>　　說(shuō)明：一式兩份，一份裝訂入學(xué)生畢業(yè)設(shè)計(jì)（論文）內(nèi)，一份交學(xué)院（直屬系）</p><p><b>　　目錄</b></p><p><b>　　摘要Ⅰ</b></p><p>　　AbstractⅡ<

4、/p><p>　　第1章 緒論-1-</p><p>　　1.1課題背景-1-</p><p>　　1.2五子棋介紹-1-</p><p>　　1.3目的和意義-2-</p><p>　　1.4系統(tǒng)設(shè)計(jì)思想-3-</p><p>　　1.5開(kāi)發(fā)工具簡(jiǎn)介-3-</p><

5、;p>　　第2章 可行性研究與算法分析-5-</p><p>　　2.1本系統(tǒng)的可行性研究-5-</p><p>　　2.2算法分析-6-</p><p>　　2.2.1博弈樹(shù)-6-</p><p>　　2.2.2極大極小值算法-7-</p><p>　　2.2.3負(fù)極大值算法-8-</p>

6、;<p>　　2.2.4 Alpha-Beta搜索-8-</p><p>　　2.2.5 置換表-9-</p><p>　　2.2.6 哈希表-10-</p><p>　　2.2.7 歷史啟發(fā)-11-</p><p>　　2.3 本章小結(jié)-12-</p><p>　　第3章 總體設(shè)計(jì)-13-&

7、lt;/p><p>　　3.1 總體設(shè)計(jì)過(guò)程-13-</p><p>　　3.2 系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-13-</p><p>　　3.2.1 系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)-13-</p><p>　　3.2.2 系統(tǒng)的算法設(shè)計(jì)-14-</p><p>　　3.3 系統(tǒng)模型設(shè)計(jì)-15-</p><p>

8、;　　3.4 本章小結(jié)-16-</p><p>　　第4章 詳細(xì)設(shè)計(jì)-17-</p><p>　　4.1系統(tǒng)運(yùn)行平臺(tái)設(shè)計(jì)-17-</p><p>　　4.2系統(tǒng)的程序流程圖-17-</p><p>　　4.3系統(tǒng)主要功能的實(shí)現(xiàn)-18-</p><p>　　4.3.1 新局-18-</p>&l

9、t;p>　　4.3.2 菜單及提示-20-</p><p>　　4.3.3 游戲結(jié)束-23-</p><p>　　4.3.4 英雄榜-24-</p><p>　　4.4本章小結(jié)-26-</p><p>　　第5章 系統(tǒng)測(cè)試-27-</p><p>　　5.1系統(tǒng)軟件測(cè)試-27-</p>

10、<p><b>　　結(jié)論-30-</b></p><p><b>　　致謝-32-</b></p><p><b>　　參考文獻(xiàn)-33-</b></p><p><b>　　附錄-34-</b></p><p><b>　　摘要

11、</b></p><p>　　自從計(jì)算機(jī)作為游戲?qū)?zhàn)平臺(tái)以來(lái)，各種棋類游戲如雨后春筍般紛紛冒出。使得那些喜愛(ài)下棋，又常?？嘤跊](méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮。而五子棋游戲由于其規(guī)則簡(jiǎn)單，變化多端，深受大眾喜愛(ài)。</p><p>　　五子棋不僅能增強(qiáng)人們的抽象思維能力、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。它既有簡(jiǎn)單易學(xué)的特點(diǎn)，為人民

12、群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧。既能組織群眾性的比賽、活動(dòng)，又能舉辦高水平的國(guó)際性比賽。</p><p>　　基于五子棋游戲以上的優(yōu)點(diǎn)，開(kāi)發(fā)五子棋是一個(gè)非常有價(jià)值的課題。本系統(tǒng)具有功能齊全、簡(jiǎn)單易學(xué)、既動(dòng)手又動(dòng)腦的特點(diǎn)。尤其是游戲的同時(shí)，還有聲音效果的配合，使游戲更加富有趣味性和消遣性。本系統(tǒng)基于Visual C++6.0軟件，主要應(yīng)用估值函數(shù)、負(fù)極大值搜索算法、Alpha-Beta剪枝等算法來(lái)完成人機(jī)對(duì)弈功能的

13、實(shí)現(xiàn)。本系統(tǒng)的成功開(kāi)發(fā)，能夠使人們的日常娛樂(lè)生活更加豐富多彩。</p><p>　　關(guān)鍵詞:　五子棋；國(guó)際性比賽；人機(jī)對(duì)弈；Visual C++6.0</p><p><b>　　Abstract</b></p><p>　　Since the computer as a game platform, various board games h

14、ave 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. </p><p>　

15、　Gobang can not only enhance people's ability to abstract thinking, logical reasoning, spatial imagination and enhancing people's memory, mental arithmetic ability, but also with deep philosophical, self-help and

16、 support. It has easy to learn the characteristics of the eye and ear, other esoteric skills. Can organize the masses of competitions, activities, but also organized a high level of international competition. </p>

17、<p>　　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. Especiall

18、y 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 sea

19、rch algorithm to complete the function of the realization of human chess</p><p>　　Key words:　Gobang International Competition Human Chessboard Visual C++6.0</p><p>　　基于Visual C++的五子棋設(shè)計(jì)與實(shí)現(xiàn)<

20、/p><p><b>　　第1章　緒論</b></p><p><b>　　1.1　課題背景</b></p><p>　　計(jì)算機(jī)技術(shù)的發(fā)展，使得計(jì)算機(jī)在現(xiàn)代企業(yè)、家庭中得以普及，應(yīng)用計(jì)算機(jī)成為現(xiàn)代人生活中非常重要的一部分。大到政府辦公、教育事業(yè)、商業(yè)活動(dòng)，小到生活中的每一個(gè)細(xì)節(jié)。隨著社會(huì)進(jìn)步的節(jié)奏越來(lái)越快，人們的生活壓力也越來(lái)

21、越大。每天奔波于不同的目的地，忙得沒(méi)有時(shí)間和朋友見(jiàn)面，忙得想找個(gè)釋放壓力的機(jī)會(huì)都沒(méi)有。這個(gè)時(shí)候，你是不是非常希望有個(gè)游戲，能夠陪你輕松愉快度過(guò)周末。自從計(jì)算機(jī)作為游戲?qū)?zhàn)平臺(tái)以來(lái)，各種棋類游戲如雨后春筍般紛紛冒出。使得那些喜愛(ài)下棋，又常常苦于沒(méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮，而且這類軟件大都水平頗高，大有與人腦分庭抗禮之勢(shì)。其中戰(zhàn)勝過(guò)國(guó)際象棋世界冠軍-卡斯帕羅夫的“深藍(lán)”便是最具說(shuō)服力的代表。五子棋是一種受大眾廣泛喜愛(ài)的游戲，其規(guī)則簡(jiǎn)單，

22、變化多端，非常富有趣味性和消遣性。同時(shí)具有簡(jiǎn)單易學(xué)、既動(dòng)手又動(dòng)腦的特點(diǎn)。</p><p><b>　　1.2　五子棋介紹</b></p><p>　　五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“Renju”，英文稱之為“Gobang”或“FIR”(Five In a Row的縮寫(xiě))，亦有“連五子”、“五子連”、“串珠”、“五目”、“

23、五目碰”、“五格”等多種稱謂。相傳早在堯造圍棋之前，五子棋游戲在民間已經(jīng)相當(dāng)盛行了。據(jù)《增山海經(jīng)》中記載：“休輿之山有石焉，名曰帝臺(tái)之棋，五色而文狀鶉卵。”《辭?！分幸嘌裕骸拔遄悠逯衅孱愑螒颍寰吲c圍棋相同，兩人對(duì)局，輪流下子，先將五子連成一行者為勝?！碧茣r(shí)由高麗使者帶到高麗，后來(lái)輾轉(zhuǎn)反復(fù)，流傳到日本。起先是在日本皇宮內(nèi)盛行的游戲，只限于王室成員、貴族階層之間的對(duì)弈，后來(lái)?yè)?jù)說(shuō)被出入皇宮的挑夫看見(jiàn)，由此便流行民間。</p>

24、<p>　　五子棋起源于古代中國(guó)，發(fā)展于日本，風(fēng)靡于歐洲。對(duì)于它與圍棋的關(guān)系有兩種說(shuō)法，一種說(shuō)法是早于圍棋，早在“堯造圍棋”之前，民間就已有五子棋游戲；另一說(shuō)法是源于圍棋，是圍棋發(fā)展的一個(gè)分支。在中國(guó)的文化里，倍受人們的青睞。古代的五子棋的棋具與圍棋相同，縱橫各十七道。五子棋大約隨圍棋一起在我國(guó)南北朝時(shí)先后傳入朝鮮、日本等地。據(jù)日本史料文獻(xiàn)介紹，中國(guó)古代的五子棋是經(jīng)由高麗(朝鮮)，于1688年至1704年的日本元祿時(shí)代傳到日本

25、的。到日本明治32年(公元1899年)，經(jīng)過(guò)公開(kāi)征名，“連珠”這一名稱才被正式確定下來(lái)，取意于“日月如合壁，五星如連珠”。從此，連珠活動(dòng)經(jīng)過(guò)了不斷的改良，主要是規(guī)則的變化(即對(duì)執(zhí)黑棋一方的限制)。例如，1899年規(guī)定，禁止黑白雙方走“雙三” ；1903年規(guī)定，只禁止黑方走“雙三” ；1912年規(guī)定，黑方被迫走“雙三”亦算輸；1916年規(guī)定，黑方不許走“長(zhǎng)連” ；1918年規(guī)定，黑方不許走“四、三、三” ；1931年規(guī)定，黑方不許走“雙四

26、” ，并規(guī)定將19×19的圍棋盤(pán)改為15×15的連珠專用棋盤(pán)。</p><p>　　本世紀(jì)初五子棋傳入歐洲并迅速風(fēng)靡全歐。通過(guò)一系列的變化，使五子棋這一簡(jiǎn)單的游戲復(fù)雜化、規(guī)范化，而最終成為今天的職業(yè)連珠五子棋，同時(shí)也成為一種國(guó)際比賽棋。</p><p>　　現(xiàn)代五子棋（連珠）的基本下法是：先由執(zhí)黑棋一方將一枚棋子落在天元點(diǎn)上，為了尊重對(duì)方和出于禮貌，持白棋的一方通常將盤(pán)

27、面的第二手棋布在天元下方周圍。</p><p><b>　　1.3　目的和意義</b></p><p>　　五子棋游戲不僅能增強(qiáng)人們的抽象思維能力、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑方式所特有的特征“短、平、快” ，又有中國(guó)古典哲學(xué)所包含的高深學(xué)問(wèn)“陰陽(yáng)易理” ；它既有簡(jiǎn)單易學(xué)的特點(diǎn)，為人民群眾所喜

28、聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧；既能組織舉辦群眾性的比賽、活動(dòng)，又能組織舉辦高水平的國(guó)際性比賽；它的棋文化源淵流長(zhǎng)，具有東方的神秘和西方的直觀，它是中西方文化的交融點(diǎn)，也是中西方文化交流的一個(gè)平臺(tái)。</p><p>　　五子棋的根在中國(guó)，在這個(gè)國(guó)境里，他有著廣泛的群眾基礎(chǔ)。但與世界先進(jìn)的五子棋技術(shù)相比，我們的棋藝水平還要繼續(xù)提高，所以我們要推廣五子棋，宣傳五子棋，爭(zhēng)取在較短的時(shí)間內(nèi)趕上和超過(guò)世界五子棋壇的先進(jìn)水平。在這種

29、環(huán)境下，開(kāi)發(fā)一個(gè)易學(xué)實(shí)用的五子棋游戲軟件是很有必要的。</p><p>　　中國(guó)作為五子棋的發(fā)源國(guó)，要對(duì)五子棋在下個(gè)世紀(jì)的發(fā)展起到世界性的推動(dòng)作用。五子棋的發(fā)展在中國(guó)出現(xiàn)方興未艾、星火燎原之勢(shì)。同時(shí)還有一大批的中生代棋手和充滿希望的“明日之星”。相信，中國(guó)棋手攀登五子棋巔峰的日子會(huì)早日來(lái)到。</p><p>　　1.4　系統(tǒng)設(shè)計(jì)思想</p><p>　　一個(gè)優(yōu)秀的游

30、戲軟件，必須有一個(gè)正確的設(shè)計(jì)思想，通過(guò)合理地選擇數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)以及開(kāi)發(fā)環(huán)境，構(gòu)成一個(gè)完善的體系結(jié)構(gòu)，才能充分發(fā)揮計(jì)算機(jī)應(yīng)用的優(yōu)勢(shì)。根據(jù)游戲玩家的實(shí)際需求，本系統(tǒng)的設(shè)計(jì)按照下述原則進(jìn)行。</p><p>　?。?）實(shí)用性：系統(tǒng)以用戶需求為目標(biāo)，以方便用戶為原則，同時(shí)融入先進(jìn)的設(shè)計(jì)思想。根據(jù)用戶實(shí)際的需求情況，量身制作一個(gè)功能齊全、操作簡(jiǎn)單、實(shí)用性強(qiáng)的游戲軟件。充分滿足游戲玩家的需求，真正成為為玩家提供輕松、娛樂(lè)

31、、休閑的工具。</p><p>　?。?）先進(jìn)性：本軟件將充分應(yīng)用現(xiàn)有成熟的計(jì)算機(jī)技術(shù)、軟件開(kāi)發(fā)技術(shù)，為用戶提供高性能的系統(tǒng)，可以方便的實(shí)現(xiàn)玩家的需要。</p><p>　　（3）高可靠性：一個(gè)實(shí)用的系統(tǒng)同時(shí)必須是可靠的，本系統(tǒng)通過(guò)合理而先進(jìn)的結(jié)構(gòu)設(shè)計(jì)以及軟、硬件的優(yōu)化選型，可保證系統(tǒng)的可靠性與容錯(cuò)性。</p><p>　?。?）可維護(hù)性：系統(tǒng)的設(shè)計(jì)要求方便維護(hù)，包

32、括硬件的維護(hù)，軟件的維護(hù)（更改，升級(jí)等）。</p><p>　?。?）可擴(kuò)展性及靈活性：系統(tǒng)的設(shè)計(jì)以方便未來(lái)業(yè)務(wù)的擴(kuò)展和系統(tǒng)擴(kuò)充為目標(biāo)，系統(tǒng)要求能夠方便的升級(jí)，充分保護(hù)系統(tǒng)的投資。玩家可以根據(jù)自己的需要，靈活設(shè)置自己的游戲。</p><p>　　（6）智能性：智能化是這個(gè)游戲軟件的一大特色。系統(tǒng)在設(shè)計(jì)時(shí)，充分考慮系統(tǒng)運(yùn)行的智能性，如果有充足的時(shí)間改進(jìn)，計(jì)算機(jī)就可以實(shí)現(xiàn)更高的AI，在游戲中走

33、的每一步就會(huì)考慮得更周密。</p><p>　　1.5　開(kāi)發(fā)工具簡(jiǎn)介</p><p>　　Visual C++6.0是Microsoft公司開(kāi)發(fā)的基于C/C++的面向?qū)ο蟮目梢暬砷_(kāi)發(fā)工具，它是Visual Studio中功能最為強(qiáng)大、代碼效率最高的開(kāi)發(fā)工具。Visual C++6.0與以前的版本相比有了多方面的改進(jìn)。它的編譯器、調(diào)試器、連接器、編輯器、資源編輯器都有所加強(qiáng)。在編輯器中還

34、提供了自動(dòng)語(yǔ)句生成功能，編輯器會(huì)像Visual Basic一樣自動(dòng)提示函數(shù)的參數(shù)、對(duì)象的成員。另外，Visual C++ 6.0還提供了很多向?qū)АFC提供了一些新的類，提供了更強(qiáng)大的數(shù)據(jù)訪問(wèn)功能。用戶可利用Visual C++6.0以兩種方式編寫(xiě)Win32應(yīng)用程序，一種方式是基于Windows API的C編程方式，另一種是基于MFC的C++編程方式。</p><p>　　Visual C++ 6.0的主要特點(diǎn)如

35、下：</p><p>　　Visual C++ 6.0的最大特色就是提供面向?qū)ο蠹夹g(shù)的支持，它利用類把大</p><p>　　部分與用戶界面設(shè)計(jì)有關(guān)的Windows API函數(shù)封裝起來(lái)，通過(guò)MFC（Microsoft Foundation Class）類庫(kù)的方式提供給開(kāi)發(fā)人員使用，大大提高了程序代碼的重用性。</p><p>　　Visual C++ 6.0提供一個(gè)

36、功能強(qiáng)大的應(yīng)用程序生成向?qū)А狝ppWizard，這也是其得意之處。有了AppWizard，用戶將不會(huì)為創(chuàng)建繁瑣的初始化代碼而苦惱。AppWizard將幫助MFC類庫(kù)的用戶自動(dòng)生成一個(gè)運(yùn)行程序框架——一個(gè)空的不能做任何事情的應(yīng)用程序，而用戶只需要在該框架的適當(dāng)部分添加擴(kuò)充代碼就可以得到一個(gè)滿意的應(yīng)用程序。</p><p>　　Visual C++ 6.0的另一個(gè)強(qiáng)大工具就是Class Wizard，用戶通過(guò)它能夠

37、方便而有效地使用和管理MFC類庫(kù)。以前，繼承和派生一個(gè)類是一件很麻煩的事，而現(xiàn)在簡(jiǎn)單了，只需在Class Wizard中指定一些必要信息，Visual C++ 6.0將自動(dòng)為你生成類的框架和代碼。</p><p>　　Visual C++ 6.0利用“所見(jiàn)即所得”的方式完成程序界面的設(shè)計(jì)，大大減輕了程序設(shè)計(jì)人員的勞動(dòng)強(qiáng)度，提高了開(kāi)發(fā)效率。</p><p>　　Visual C++ 6.0的

38、功能強(qiáng)大，用途廣泛。不僅可以編寫(xiě)普通的應(yīng)用程序，還能很好的進(jìn)行系統(tǒng)及通信軟件的開(kāi)發(fā)。</p><p>　　第2章　可行性研究與算法分析</p><p>　　2.1　本系統(tǒng)的可行性研究</p><p>　　本系統(tǒng)要實(shí)現(xiàn)的目標(biāo)：作為一個(gè)悠閑的小游戲軟件，首先應(yīng)該為用戶提供一套方便的操作方法，在游戲模式、用戶操作、反饋信息方面應(yīng)該有明確的說(shuō)明，能夠讓大多數(shù)玩家能快速上手，

39、使該游戲看上去是一款悠閑的精品。</p><p>　　本系統(tǒng)的流程圖描述如下：玩家在新開(kāi)局后，可以設(shè)置本局游戲，包括對(duì)弈模式、游戲級(jí)別、中英文菜單、聲音效果等進(jìn)行設(shè)置，即初始化棋盤(pán)。初始化棋盤(pán)完成后，玩家和計(jì)算機(jī)就可以在分析了當(dāng)前棋局以后下棋，即對(duì)弈階段。在玩家和計(jì)算機(jī)每下了一手棋以后，都會(huì)進(jìn)行勝負(fù)的判斷，如有勝負(fù)，則結(jié)束此局游戲。如果此局玩家的成績(jī)比英雄榜里的成績(jī)更好，則把玩家的姓名和成績(jī)記錄到英雄榜中，覆蓋原

40、來(lái)的玩家名和成績(jī)。</p><p>　　本游戲軟件的系統(tǒng)流程圖，如圖2.1所示。</p><p>　　圖2.1　系統(tǒng)流程圖</p><p>　　本系統(tǒng)是一款休閑的小游戲，是人們?nèi)粘Ｉ願(yuàn)蕵?lè)的工具。只要針對(duì)大眾的喜好，使系統(tǒng)功能齊全，操作簡(jiǎn)單，界面美觀大方，就一定會(huì)有市場(chǎng)潛力。根據(jù)該系統(tǒng)目標(biāo)來(lái)衡量所需的技術(shù)是否具備，一般可從軟硬件的性能要求、環(huán)境條件、操作人員水平和數(shù)

41、量等方面去考慮和分析。</p><p>　　考慮到系統(tǒng)實(shí)施的可行性，在軟件方面選擇了性能穩(wěn)定的VC++6.0開(kāi)發(fā)環(huán)境、C++語(yǔ)言來(lái)進(jìn)行開(kāi)發(fā)。VC++是非常成熟的開(kāi)發(fā)工具，因此無(wú)論在安全性、可用性及可靠性等方面都毫無(wú)置疑，因此軟件方面是可行的。</p><p>　　在硬件方面，則選擇空間較大，只要是Pentium III系列及以上的計(jì)算機(jī)，內(nèi)存在256M以上，硬盤(pán)在1GB，都可以滿足系統(tǒng)的開(kāi)

42、發(fā)需要。當(dāng)然，硬件的配置越高，系統(tǒng)的開(kāi)發(fā)與運(yùn)行會(huì)更流暢?？紤]到如今的家用或商用電腦硬件的整體配置水平，系統(tǒng)在硬件方面是可行的。</p><p><b>　　2.2　算法分析</b></p><p>　　五子棋游戲的開(kāi)發(fā)在搜索算法方面，可以有多種選擇。通過(guò)從不同的角度分析各種搜索方法的效率，來(lái)考慮本系統(tǒng)的算法應(yīng)用。開(kāi)局時(shí)計(jì)算機(jī)每走一步的平均耗時(shí)(ms)，如表2.1所示。

43、</p><p>　　表2.1各種算法每走一步平均耗時(shí)(ms)</p><p>　　通過(guò)上表，可以看出使用置換表技術(shù)和歷史啟發(fā)技術(shù)可以增強(qiáng)搜索效率。綜合分析表中幾種算法的效率，本系統(tǒng)按照計(jì)算機(jī)下每一手棋所應(yīng)用的算法的大致順序，采用的主要算法有博弈樹(shù)、負(fù)極大值算法、Alpha-Beta剪枝算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。下面詳細(xì)地介紹一下這些算法。</p><p

44、><b>　　2.2.1　博弈樹(shù)</b></p><p>　　設(shè)想下五子棋的情形，兩人對(duì)弈，我們將其中一位叫做甲，另一位叫做乙。假定現(xiàn)在該甲下棋，甲可以有225種走法（不論好壞）；而對(duì)甲的任一走法，乙也可以有與之相對(duì)的若干種下法。然后又輪到甲走棋，對(duì)乙的下法甲又有若干種方法應(yīng)對(duì)。如此往復(fù)。顯然，我們可以依此構(gòu)建一棵博弈樹(shù)，將所有的走法羅列出來(lái)。在這棵樹(shù)的根部是棋局的初始局面。根的若干子

45、節(jié)點(diǎn)則是由甲的每一種可能走法所生成的局面，而這些節(jié)點(diǎn)的子節(jié)點(diǎn)則是由與之相對(duì)的乙的每一種可能走法所生成的局面。在這棵樹(shù)的末梢，是結(jié)束的棋局，甲勝或者乙勝或者是雙方都無(wú)法取勝的平局。如果我們令甲勝的局面值為WIN，乙勝的局面值為L(zhǎng)OST，而和局的值為DRAW。當(dāng)輪到甲走時(shí)，甲定會(huì)選擇子節(jié)點(diǎn)值為WIN或DRAW（如果沒(méi)有值為WIN的子節(jié)點(diǎn)的話）的下法；而輪到乙時(shí)，乙則會(huì)選擇子節(jié)點(diǎn)值為L(zhǎng)OST或DRAW（如果沒(méi)有值為L(zhǎng)OST的子節(jié)點(diǎn)的話）的下法

46、。對(duì)于中間節(jié)點(diǎn)的值可以有如下計(jì)算方法：如果該節(jié)點(diǎn)所對(duì)應(yīng)的局面輪到甲下棋，則該節(jié)點(diǎn)的值是其所有子節(jié)點(diǎn)中值最佳（對(duì)甲而言）的一個(gè)的值；如果該節(jié)點(diǎn)所對(duì)應(yīng)的局面輪到乙走棋，則該節(jié)點(diǎn)的值是其所有子節(jié)點(diǎn)中值最差（對(duì)甲而言）的一個(gè)的值。這樣看來(lái)從這</p><p>　　但是在五子棋游戲中，我們沒(méi)有建立完全搜索樹(shù)的可能。一方面是因?yàn)楹芏嗲樾胃揪偷竭_(dá)不了葉子節(jié)點(diǎn)。另一方面，這棵樹(shù)上的節(jié)點(diǎn)數(shù)量也已多到了無(wú)法處理的程度。所以我們需要

47、其它的算法來(lái)減少搜索的數(shù)量。</p><p>　　2.2.2　極大極小值算法（Minimax Algorithm）</p><p>　　在上面的博弈樹(shù)中，如果我們令甲勝的局面值為1，乙勝的局面值為-1，而和局的值為0。當(dāng)輪到甲下棋時(shí)，甲定會(huì)選擇子節(jié)點(diǎn)值最大的下法；而輪到乙時(shí)，乙則會(huì)選擇子節(jié)點(diǎn)值最小的下法。所以，對(duì)于中間節(jié)點(diǎn)的值可以有如下計(jì)算方法：如果該節(jié)點(diǎn)所對(duì)應(yīng)的局面輪到甲下棋，則該節(jié)點(diǎn)的

48、值是其所有子節(jié)點(diǎn)中值最大的一個(gè)的值。而如果該節(jié)點(diǎn)所對(duì)應(yīng)的局面輪到乙下棋，則該節(jié)點(diǎn)的值是其所有子節(jié)點(diǎn)中值最小的一個(gè)的值。</p><p>　　對(duì)博弈樹(shù)的這個(gè)變化僅僅是形式上的，本質(zhì)上絲毫未變，但是這個(gè)形式更容易推廣以運(yùn)用到一般實(shí)際的情形。</p><p>　　既然建立整棵的搜索樹(shù)不可能，那么，為當(dāng)前所面臨的局面找出一步好棋如何？也就是通過(guò)少量的搜索，為當(dāng)前局面選擇一步較好的走法。</p

49、><p>　　在通常的棋局當(dāng)中，一個(gè)局面的評(píng)估往往并不像輸、贏、平3種狀態(tài)這么簡(jiǎn)單，在分不出輸贏的局面中棋局也有優(yōu)劣之分。也就是說(shuō)，要用更細(xì)致的方法來(lái)刻畫(huà)局面的優(yōu)劣，而不是僅僅使用1、-1、0三個(gè)數(shù)字刻畫(huà)3種終了局面。假定我們有一個(gè)函數(shù)可以為每一局面的優(yōu)劣評(píng)分。例如甲勝為+∞；乙勝為-∞；和局為0；這樣我們可以建立一棵固定深度的搜索樹(shù)，其葉子節(jié)點(diǎn)不必是終了狀態(tài)，而只是固定深度的最深一層的節(jié)點(diǎn)，其值由上述函數(shù)評(píng)出；對(duì)于

50、中間節(jié)點(diǎn)，如同前面提到的那樣，甲方取子節(jié)點(diǎn)的最大值，乙方取子節(jié)點(diǎn)的最小值。這個(gè)評(píng)分的函數(shù)稱作靜態(tài)估值函數(shù)（Static Evaluation Function）。用以取代超出固定深度的搜索。顯然，我們無(wú)法擁有絕對(duì)精確的靜態(tài)估值函數(shù)。否則，只要這個(gè)靜態(tài)估值函數(shù)就可以解決所有的棋局了。估值函數(shù)給出的只是一個(gè)較粗略的評(píng)分，在此基礎(chǔ)上進(jìn)行的少量搜索的可靠性，理論上是不如前述的WIN，LOST，DRAW三種狀態(tài)的博弈樹(shù)的，但這個(gè)方法卻是可實(shí)現(xiàn)的。

51、利用具體的知識(shí)構(gòu)成評(píng)估函數(shù)的搜索叫做啟發(fā)式搜索（Heuristic Search）。估值函數(shù)在有些文獻(xiàn)中也稱為啟發(fā)函數(shù)（Heuristic Functio</p><p>　　在博弈樹(shù)搜索的文獻(xiàn)當(dāng)中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。MinMax算法是對(duì)弈的基礎(chǔ)思想。</p><p>　　2.2.3　負(fù)極大值算法（Negamax Algorithm）</

52、p><p>　　普通的極大極小值算法看起來(lái)有一點(diǎn)笨，既然一方試圖取極大值而另一方試圖取極小值——也就是說(shuō)——我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動(dòng)作。Knuth和Moore在1975年提出了負(fù)極大值（Negamax）方法，消除了兩方的差別，而且簡(jiǎn)潔優(yōu)雅。使用負(fù)極大值方法，博弈雙方都取極大值。</p><p>　　2.2.4　Alpha-Beta搜索</p>

53、<p>　　在極大極小搜索的過(guò)程中，存在著一定程度的數(shù)據(jù)冗余。舉一個(gè)最簡(jiǎn)單的例子：在象棋博弈的過(guò)程中，如果某一個(gè)節(jié)點(diǎn)輪到甲走棋，而甲向下搜索節(jié)點(diǎn)時(shí)發(fā)現(xiàn)第一個(gè)子節(jié)點(diǎn)就可以將死乙（節(jié)點(diǎn)值為最大值），則剩下的節(jié)點(diǎn)就無(wú)需再搜索了，甲的值就是第一個(gè)子節(jié)點(diǎn)的值。這個(gè)過(guò)程，就可以將大量冗余的（不影響結(jié)果的）節(jié)點(diǎn)拋棄。</p><p>　　圖2.2A lpha-Beta剪枝示例圖</p><p&

54、gt;　　將上述這個(gè)情形推廣一下，設(shè)想有如圖2.1左半部所示的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)下面數(shù)字為該節(jié)點(diǎn)的值，節(jié)點(diǎn)B的值為18，節(jié)點(diǎn)D的值為16，由此我們可以判斷節(jié)點(diǎn)C的值將小于等于16（取極小值）；而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Max（B,C），為18，也就是說(shuō)不再需要估算節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱為Alpha剪枝（alpha cutoff）。設(shè)想有如圖2-2右半部所示的一棵極大極小樹(shù)

55、的片斷，節(jié)點(diǎn)B的估值為8，節(jié)點(diǎn)D的估值為18，由此我們可以判斷節(jié)點(diǎn)C的值將大于等于18（取極大值）；而節(jié)點(diǎn)A的值為節(jié)點(diǎn)Min（B,C），為8。也就是說(shuō)不再需要求節(jié)點(diǎn)C的其他子節(jié)點(diǎn)如E、F的值就可以得出父節(jié)點(diǎn)A的值了。這樣將節(jié)點(diǎn)D的后繼兄弟節(jié)點(diǎn)減去稱為Beta剪枝（beta cutoff）。</p><p>　　2.2.5　置換表（Transposition Table）</p><p>　

56、　在極大極小搜索的過(guò)程中，改進(jìn)搜索算法的目標(biāo)在于將不必搜索的（冗余）分枝從搜索的過(guò)程中盡量剔除，以達(dá)到搜索盡量少的分枝來(lái)降低運(yùn)算量的目的。</p><p>　　在先前談到的幾種搜索算法中，我們看到可以通過(guò) Alpha-Beta剪枝來(lái)剪除兩種類型的冗余分枝/節(jié)點(diǎn)，但是已經(jīng)搜索過(guò)的節(jié)點(diǎn)不可以免于搜索。</p><p>　　從圖2-2的極大極小樹(shù)的片斷中，我們可以看出，該片斷從節(jié)點(diǎn)A開(kāi)始，有兩個(gè)

57、分B和C（為簡(jiǎn)化問(wèn)題，其他節(jié)點(diǎn)從略），B 有子節(jié)點(diǎn)D，C有子節(jié)點(diǎn)E，再往下D有子節(jié)點(diǎn)F，E有子節(jié)點(diǎn)G。讀者可以看到，在極大極小樹(shù)的不同分枝上，存在著完全相同的節(jié)點(diǎn)。在上圖中，節(jié)點(diǎn)F和G完全相同。對(duì)于節(jié)點(diǎn)F，在搜索分枝的時(shí)候，就可能已經(jīng)搜索過(guò)了。那么，在搜索節(jié)點(diǎn)G的子節(jié)點(diǎn)時(shí)，我們能不能直接利用已經(jīng)搜索過(guò)的節(jié)點(diǎn)F的結(jié)果，而不是重新搜索一遍節(jié)點(diǎn)G？</p><p>　　想法是可行的。如果要利用已經(jīng)搜索過(guò)的節(jié)點(diǎn)的結(jié)果，我

58、們就要用一張表把搜索過(guò)的節(jié)點(diǎn)記錄下來(lái)。然后在后續(xù)的搜索中，察看記錄在表中的這些結(jié)果，如果將要搜索的某個(gè)節(jié)點(diǎn)已有記錄，就直接利用記錄下來(lái)的結(jié)果。這種方法叫做置換表（Transposition Table，簡(jiǎn)稱TT）。</p><p>　　如果將Alpha-Beta搜索過(guò)程中每一節(jié)點(diǎn)的結(jié)果都記錄下來(lái)，則在任意節(jié)點(diǎn)向下搜索之前先查看這些紀(jì)錄，就可避免上述重復(fù)的操作。</p><p>　　但是這個(gè)

59、置換表如何實(shí)現(xiàn)的？困難集中在時(shí)間和空間復(fù)雜度上。</p><p>　　1．可能的節(jié)點(diǎn)可以認(rèn)為是無(wú)窮多，將其存入一張表中要占據(jù)多少存儲(chǔ)空間呢？</p><p>　　2．即使有無(wú)窮多內(nèi)存空間，一個(gè)節(jié)點(diǎn)要從表中找到自己對(duì)應(yīng)的一項(xiàng)，需要花費(fèi)多少時(shí)間？雖然有序表可用二分查找等快速的算法，但要維持表中內(nèi)容有序，又要進(jìn)行大量排序操作，會(huì)耗費(fèi)更多時(shí)間。如何解決？</p><p>　

60、　2.2.6　哈希表（Hash Table）</p><p>　　置換表的實(shí)現(xiàn)在時(shí)間和空間復(fù)雜度上的疑問(wèn)。實(shí)際上已經(jīng)明確了要實(shí)現(xiàn)置換表必須要滿足如下條件：</p><p>　　1．查找記錄中的節(jié)點(diǎn)數(shù)據(jù)時(shí)速度要非?？?，最好是類似于隨機(jī)存取。</p><p>　　2．將節(jié)點(diǎn)數(shù)據(jù)放入記錄的速度也要非?？?。這就意味著數(shù)據(jù)項(xiàng)插入的過(guò)程不可有數(shù)據(jù)移動(dòng)排序等操作。</p&g

61、t;<p>　　3．要能在有限的存儲(chǔ)空間內(nèi)進(jìn)行。</p><p>　　可以利用哈希表，哈希方法的思想為每一個(gè)學(xué)過(guò)數(shù)據(jù)結(jié)構(gòu)或算法課程的開(kāi)發(fā)人員所熟知。對(duì)棋類博弈來(lái)說(shuō)，定義一個(gè)巨大的數(shù)組，將每一局面記入其中，每一局面在數(shù)組中對(duì)應(yīng)惟一的位置。這樣，將數(shù)據(jù)記入和取出就類似于隨機(jī)讀寫(xiě)，不會(huì)有耗時(shí)的查找和插入過(guò)程。但是，以象棋而論，如果為每一局面在數(shù)組中對(duì)應(yīng)一個(gè)與其他局面不同的位置的話，則組合的結(jié)果是全世界所有

62、的計(jì)算機(jī)內(nèi)存加起來(lái)也不夠這樣一個(gè)數(shù)組用。</p><p>　　那么讓每一局面在數(shù)組中對(duì)應(yīng)惟一的位置，但并不保證數(shù)組中每一個(gè)數(shù)據(jù)項(xiàng)對(duì)應(yīng)惟一的局面如何呢？比如將所有的局面對(duì)應(yīng)在106單位的數(shù)組上。這樣，必然有一些局面對(duì)應(yīng)在相同的位置上；但是對(duì)一次搜索而言，這種情況發(fā)生的概率并不高。一旦某個(gè)搜索過(guò)的局面在該數(shù)組中未找到，我們不過(guò)是對(duì)它進(jìn)行Alpha-Beta搜索而已。不同的局面對(duì)應(yīng)在數(shù)組中同一存儲(chǔ)單元上的情形，叫做沖突

63、。</p><p>　　我們將利用哈希方法實(shí)現(xiàn)置換表的方法敘述如下。定義哈希數(shù)組如下：</p><p>　　structHASHITEM｛</p><p>　　int64 checksum；//64位哈希值，用以驗(yàn)證表中數(shù)據(jù)是否是要找的局面</p><p>　　int depth；//該表項(xiàng)求值時(shí)的搜索深度</p><p

64、>　　enum｛ exact，lower_bound，upper_bound ｝entry_type；//表項(xiàng)值的類型</p><p>　　double eval； //所代表的節(jié)點(diǎn)的值</p><p>　?。齢ashtable［HASH_TABLE_SIZE］；//定義大小為 HASH_TABLE_SIZE 的哈希數(shù)組</p><p>　　對(duì)要搜索的每一節(jié)點(diǎn)

65、，計(jì)算出它的一個(gè)哈希值（hashIndex，通常是一個(gè)32位數(shù)對(duì)哈希表大小取模）以確定此局面在哈希表中的位置。計(jì)算另一個(gè)64位的哈希值（Checksum）來(lái)校驗(yàn)表中的數(shù)據(jù)項(xiàng)是否是所要的那一項(xiàng)。</p><p>　　在對(duì)某一局面搜索之前，先查看哈希表項(xiàng) hashTable［hashIndex］，如果 hashTable［hashIn-dex］.checksum==Checksum并且hashTable［hashIn

66、dex］.depth 大于等于最大搜索深度減去當(dāng)前層數(shù)，就返回hashTable［hashIndex］.eval作為當(dāng)前局面的估值。</p><p>　　當(dāng)對(duì)一個(gè)局面的搜索完成之后，將Checksum、當(dāng)前層數(shù)和估值結(jié)果保存到 hashTable［hashIndex］當(dāng)中，以備后面的搜索使用。</p><p>　　2.2.7　歷史啟發(fā)（History Heuristic）</p>

67、;<p>　　在前面的章節(jié)我們?cè)?jīng)提到過(guò)，Alpha-Beta搜索的剪枝效率，幾乎完全取決于節(jié)點(diǎn)的排列順序。在節(jié)點(diǎn)排列順序處于理想狀態(tài)的情況下，Alpha-Beta搜索需遍歷的節(jié)點(diǎn)數(shù)僅為極大極小算法所需遍歷的節(jié)點(diǎn)數(shù)的平方根的兩倍左右。也就是說(shuō)對(duì)一棵極大極小樹(shù)來(lái)說(shuō)，如果極大極小搜索需遍歷106個(gè)節(jié)點(diǎn)求得結(jié)果，那么處于理想狀態(tài)的 Alpha-Beta搜索僅需遍歷約2000個(gè)節(jié)點(diǎn)就可求得結(jié)果。而在節(jié)點(diǎn)的排序最不理想的情況下，Al

68、pha-Beta搜索要遍歷的結(jié)點(diǎn)數(shù)同極大極小算法一樣多。如何調(diào)整待展開(kāi)的走法排列的順序，是提高搜索效率的關(guān)鍵。</p><p>　　根據(jù)部分已經(jīng)搜索的結(jié)果來(lái)調(diào)整將要進(jìn)行搜索的節(jié)點(diǎn)順序是一個(gè)可行的方向。通常一個(gè)局面經(jīng)搜索得知較好時(shí)，在其后繼節(jié)點(diǎn)當(dāng)中往往有一些相似的局面，比如僅有一些無(wú)關(guān)緊要的棋子位置不同等等。這些相似的局面往往也是較好的?？梢酝ㄟ^(guò)一些較復(fù)雜的判斷來(lái)找出這些相似的局面，率先搜索，從而提高剪枝效率。但這

69、一方法需要具體棋類相關(guān)的知識(shí)，并且往往判斷復(fù)雜而效果不彰。</p><p>　　J.Schaeffer提出了History Heuristic的方法，在基于Alpha-Beta的搜索當(dāng)中，一個(gè)好的走法可以定義如下：</p><p>　　1．由其產(chǎn)生的節(jié)點(diǎn)引發(fā)了剪枝。</p><p>　　2．未引發(fā)剪枝，但是其兄弟走法中的最佳者。</p><p&g

70、t;　　在搜索的過(guò)程中，每當(dāng)找到一個(gè)好的走法，就將與該走法相對(duì)應(yīng)的歷史得分作一個(gè)增量，一個(gè)多次被搜索并確認(rèn)為好的走法的歷史紀(jì)錄就會(huì)較高，當(dāng)搜索中間節(jié)點(diǎn)時(shí)，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。這比采用基于棋類知識(shí)而對(duì)節(jié)點(diǎn)排序的方法要容易得多。由于歷史得分表隨搜索而改變，對(duì)節(jié)點(diǎn)順序的排列也會(huì)隨之動(dòng)態(tài)改變。</p><p><b>　　2.3　本章小結(jié)</b></p>

71、<p>　　本系統(tǒng)的可行性研究，從市場(chǎng)可行性、技術(shù)可行性方面著手進(jìn)行考慮。市場(chǎng)可行性主要研究五子棋游戲的潛在市場(chǎng)；技術(shù)可行性主要研究系統(tǒng)開(kāi)發(fā)軟硬件條件。綜上考慮，本項(xiàng)目的開(kāi)發(fā)技術(shù)成熟、完備，運(yùn)行環(huán)境優(yōu)良，具有一定的開(kāi)發(fā)前景。</p><p>　　算法分析部分主要介紹了五子棋游戲開(kāi)發(fā)用到的算法。按照計(jì)算機(jī)下每一手棋時(shí)，應(yīng)用算法的大致順序，本系統(tǒng)使用的主要算法有極大極小值算法、負(fù)極大值算法、Alpha-B

72、eta算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。其中的極大極小值算法是對(duì)弈算法的基礎(chǔ)。哈希表技術(shù)的使用，是置換表技術(shù)能夠?qū)崿F(xiàn)的基礎(chǔ)。各種算法的綜合使用，得以提高算法的效率。</p><p><b>　　第3章　總體設(shè)計(jì)</b></p><p>　　3.1　總體設(shè)計(jì)過(guò)程</p><p>　　總體設(shè)計(jì)過(guò)程通常由四個(gè)主要階段組成：系統(tǒng)體系結(jié)構(gòu)設(shè)計(jì)，確

73、定系統(tǒng)的具體體系結(jié)構(gòu)實(shí)現(xiàn)方案；系統(tǒng)模塊設(shè)計(jì)，確定系統(tǒng)模塊層次；結(jié)構(gòu)算法設(shè)計(jì)，確定軟件結(jié)構(gòu)和典型算法；交互設(shè)計(jì)，確定系統(tǒng)的交互界面。總體設(shè)計(jì)的典型過(guò)程包括如下七個(gè)階段：</p><p>　?。?）選取合理的體系結(jié)構(gòu)方案</p><p><b>　　（2）推薦最佳方案</b></p><p><b>　?。?）系統(tǒng)模塊設(shè)計(jì)</b&g

74、t;</p><p>　?。?）數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)</p><p><b>　　（5）交互設(shè)計(jì)</b></p><p><b>　?。?）編寫(xiě)文檔</b></p><p><b>　?。?）審查和復(fù)審</b></p><p>　　由于本系統(tǒng)應(yīng)用到算法的設(shè)

75、計(jì)，下面詳細(xì)描述一下第四個(gè)階段。</p><p>　　高效率的程序基于良好的數(shù)據(jù)結(jié)構(gòu)與算法，一般來(lái)說(shuō)，數(shù)據(jù)結(jié)構(gòu)與算法就是一類數(shù)據(jù)的表示及其相關(guān)的操作。從數(shù)據(jù)表示的觀點(diǎn)來(lái)看，存儲(chǔ)在數(shù)組中的一個(gè)有序整數(shù)表也是一種數(shù)據(jù)結(jié)構(gòu)。算法是指對(duì)數(shù)據(jù)結(jié)構(gòu)施加的一些操作。一個(gè)算法如果能在所要求的資源限制范圍內(nèi)將問(wèn)題解決好，則稱這個(gè)算法是有效率的。一個(gè)算法如果比其他已知算法所需要的資源都少，這個(gè)算法也稱為是有效率的。算法的代價(jià)是指消耗

76、的資源量。一般來(lái)說(shuō)，代價(jià)是由一個(gè)關(guān)鍵資源，例如時(shí)間或空間來(lái)評(píng)估的。</p><p>　　3.2　系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)</p><p>　　3.2.1　系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)</p><p>　　本系統(tǒng)在開(kāi)發(fā)過(guò)程中，為了設(shè)計(jì)更合理的數(shù)據(jù)結(jié)構(gòu)，使用了用戶自定義數(shù)據(jù)類型結(jié)構(gòu)體和枚舉類型。</p><p>　　1．利用哈希表方法實(shí)現(xiàn)置換表，哈希表中元

77、素的結(jié)構(gòu)定義如下：</p><p>　　typedef struct HASHITEM</p><p><b>　　{</b></p><p>　　LONGLONG checksum; //哈希值，用以驗(yàn)證表中數(shù)據(jù)是否是要找的局面</p><p>　　EnterType enterType; // 數(shù)據(jù)類型&

78、lt;/p><p>　　short nPly; // 取到此值時(shí)的層次</p><p>　　short value; // 節(jié)點(diǎn)的值</p><p>　　} HashItem;</p><p>　　2．用以表示走法的結(jié)構(gòu)：</p><p>　　typedef struct ST

79、ONEMOVE </p><p><b>　　{</b></p><p>　　int x; // 棋子的橫坐標(biāo)</p><p>　　int y; // 棋子的縱坐標(biāo)</p><p>　　int score; // 此走法的分?jǐn)?shù)</p><p>　　}StoneMove;&l

80、t;/p><p><b>　　3．枚舉類型的使用</b></p><p>　　enum EnterType{exam,lower,uper};//搜索的精確值、下邊界、上邊界</p><p>　　enum { IDD = IDD_BEST };</p><p>　　enum { IDD = IDD_PENTE_DIALOG

81、};</p><p>　　3.2.2　系統(tǒng)的算法設(shè)計(jì)</p><p>　　本系統(tǒng)是通過(guò)多個(gè)算法的結(jié)合使用來(lái)增強(qiáng)算法的效率。應(yīng)用的主要算法有博弈樹(shù)、負(fù)極大值算法、Alpha-Beta剪枝算法、置換表、哈希表、歷史啟發(fā)等。其中的博弈樹(shù)算法是搜索算法的基礎(chǔ)，但是它的搜索量太大，在實(shí)現(xiàn)的過(guò)程中，我們不可能讓系統(tǒng)搜索所有的結(jié)點(diǎn)，于是使用極大極小值算法對(duì)博弈樹(shù)進(jìn)行了改進(jìn)。極大極小值算法是對(duì)弈算法的基礎(chǔ)

82、。普通的極大極小值算法看起來(lái)有一點(diǎn)笨，既然一方試圖取極大值而另一方試圖取極小值，也就是說(shuō)我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動(dòng)作。而負(fù)極大值方法，消除了兩方的差別，博弈雙方都取極大值。在極大極小搜索的過(guò)程中，存在著一定程度的數(shù)據(jù)冗余。這就需要Alpha-Beta算法的剪枝功能來(lái)消除冗余。在搜索過(guò)程中，利用置換表技術(shù)將 Alpha-Beta搜索過(guò)程中每一節(jié)點(diǎn)的結(jié)果都記錄下來(lái)，則在任意節(jié)點(diǎn)向下搜索之前先查看這些記錄

83、，就可避免重復(fù)搜索，以提高搜索效率。而置換表的實(shí)現(xiàn)則是依賴哈希表。這種算法之間的優(yōu)化組合，使得本系統(tǒng)能夠?qū)崿F(xiàn)它有效的搜索。</p><p>　　3.3　系統(tǒng)模塊設(shè)計(jì)</p><p>　　五子棋游戲是在系統(tǒng)地分析了游戲玩家的各項(xiàng)需求，以實(shí)際為基礎(chǔ)進(jìn)行設(shè)計(jì)的。本系統(tǒng)可以進(jìn)行人與計(jì)算機(jī)的對(duì)弈，還可以實(shí)現(xiàn)兩個(gè)人在同一臺(tái)計(jì)算機(jī)上對(duì)弈。本系統(tǒng)包括三大模塊：游戲模塊、設(shè)置模塊、幫助模塊。每個(gè)模塊包括的主

84、要內(nèi)容如下： </p><p>　　1．游戲模塊：新局、初級(jí)、中級(jí)、專家、英雄榜。</p><p>　　2．設(shè)置模塊：悔棋、提示、英文菜單、聲音效果。</p><p>　　3．幫助模塊：有關(guān)本系統(tǒng)的介紹</p><p><b>　　其中：</b></p><p>　　在新局對(duì)話框下，可以對(duì)本局游戲

85、進(jìn)行設(shè)置：</p><p>　　（1）對(duì)弈方式選擇：人與計(jì)算機(jī)對(duì)弈、人與人對(duì)弈</p><p>　　（2）先手選擇：玩家執(zhí)黑先下、計(jì)算機(jī)執(zhí)黑先下</p><p>　?。?）是否選擇聲音效果</p><p>　　本系統(tǒng)的功能模塊，如下圖3.1所示。</p><p>　　圖3.1系統(tǒng)功能模塊圖</p><

86、;p><b>　　3.4　本章小結(jié)</b></p><p>　　本系統(tǒng)按照總體設(shè)計(jì)典型過(guò)程的七個(gè)階段進(jìn)行，詳細(xì)介紹了系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)。本系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)主要采用了用戶自定義數(shù)據(jù)類型——結(jié)構(gòu)體和枚舉類型。算法設(shè)計(jì)是利用各種算法的優(yōu)化組合來(lái)提高算法的效率。本系統(tǒng)主要包括三大功能模塊——游戲模塊、選項(xiàng)模塊、功能模塊。每個(gè)功能模塊包括若干子功能。本系統(tǒng)以需求分析結(jié)論為基礎(chǔ)，考慮得比較全面

87、。 </p><p><b>　　第4章　詳細(xì)設(shè)計(jì)</b></p><p>　　4.1　系統(tǒng)運(yùn)行平臺(tái)設(shè)置</p><p>　　1．硬件環(huán)境：臺(tái)式計(jì)算機(jī)（PC）一臺(tái)，如表4.1所示。</p><p>　　表4.1　運(yùn)行環(huán)境硬件配置</p><p>　　2．軟件環(huán)境：Windows 2000 Prof

88、essional /Server or Windows XP操作系統(tǒng)。</p><p>　　4.2　系統(tǒng)的程序流程圖</p><p>　　1．程序流程圖的作用</p><p>　　程序流程圖是人們對(duì)解決問(wèn)題的方法、思路或算法的一種描述。</p><p><b>　　2．流程圖的優(yōu)點(diǎn)：</b></p><

89、;p>　?。?）采用簡(jiǎn)單規(guī)范的符號(hào)，畫(huà)法簡(jiǎn)單；</p><p>　?。?）結(jié)構(gòu)清晰，邏輯性強(qiáng)；</p><p>　?。?）便于描述，容易理解。</p><p>　　3．本系統(tǒng)的程序流程為玩家首先為新一局游戲的對(duì)弈模式、先手、游戲級(jí)別、是否有聲音效果、使用中/英文菜單等功能進(jìn)行設(shè)置，玩家確定設(shè)置完棋局以后，就進(jìn)入人與計(jì)算機(jī)或是人與人的對(duì)弈階段，在對(duì)弈的過(guò)程中，每

90、下一手棋，都會(huì)進(jìn)行本局游戲是否結(jié)束的判斷，結(jié)束的標(biāo)志是游戲的一方有五個(gè)棋子相連。如果本局游戲沒(méi)有結(jié)束，則玩家可以選擇使用悔棋或讓計(jì)算機(jī)向玩家提示兩項(xiàng)功能。如果本局游戲結(jié)束，判斷玩家的成績(jī)是否優(yōu)于英雄榜里的成績(jī)，如果是，就會(huì)出現(xiàn)喜登英雄榜界面（如圖4.8），玩家可以輸入自己的大名，之后就可以進(jìn)行新一局游戲的設(shè)置。本系統(tǒng)的程序流程，如圖4.1所示。</p><p>　　圖4.1系統(tǒng)的程序流程圖</p>

91、<p>　　4.3　系統(tǒng)主要功能的實(shí)現(xiàn)</p><p><b>　　4.3.1　新局</b></p><p><b>　　1．實(shí)現(xiàn)目標(biāo)</b></p><p>　　在主窗體菜單下，單擊新局菜單項(xiàng)，就會(huì)出現(xiàn)新一局的設(shè)置界面。在這個(gè)界面中，可以對(duì)本局游戲的對(duì)弈方式、先手和聲音效果進(jìn)行設(shè)置。在對(duì)弈方式方面，可以單擊單選

92、按鈕或是使用快捷鍵，選擇是與計(jì)算機(jī)對(duì)弈還是兩人在同一計(jì)算機(jī)上對(duì)弈，游戲默認(rèn)的選擇是與計(jì)算機(jī)對(duì)弈。在先手方面，可以選擇是玩家執(zhí)黑先下還是計(jì)算機(jī)執(zhí)黑先下，默認(rèn)的選擇是玩家執(zhí)黑先下。在聲音效果方面，可以單擊復(fù)選框，選擇是否在下棋的過(guò)程中有聲音效果，默認(rèn)選擇有聲音效果。在對(duì)這三項(xiàng)設(shè)置完成之后，單擊確定按鈕，則保存對(duì)本局游戲的設(shè)置，即初始化棋盤(pán)結(jié)束，進(jìn)入人與計(jì)算機(jī)或人與人的對(duì)弈階段。</p><p>　　本系統(tǒng)的新局設(shè)置，

93、如圖4.2所示。</p><p><b>　　圖4.2新局界面</b></p><p><b>　　2．實(shí)現(xiàn)過(guò)程</b></p><p>　　實(shí)現(xiàn)新局界面的流程，如圖4.3所示。</p><p>　　圖4.3新局界面流程圖</p><p>　　4.3.2　菜單及提示</

94、p><p><b>　　1．實(shí)現(xiàn)目標(biāo)</b></p><p>　　在主窗體的選項(xiàng)菜單下，可以選擇游戲過(guò)程中是使用中文菜單還是英文菜單。游戲默認(rèn)的選擇是中文菜單。如果你選擇了英文菜單，則在游戲過(guò)程中所有出現(xiàn)的界面都是用英文表示的。</p><p>　　在游戲過(guò)程中，可以使用主窗體的選項(xiàng)菜單下的提示功能。當(dāng)你對(duì)棋局感到不知所措的時(shí)候，可以讓計(jì)算機(jī)給你一

95、些提示。提示的方式是在棋盤(pán)上計(jì)算機(jī)覺(jué)得最佳的位置出現(xiàn)一個(gè)矩形框。你可以參考他的提示，這可能會(huì)對(duì)你下棋有些幫助。當(dāng)你在棋盤(pán)上一個(gè)棋子都沒(méi)有的時(shí)候，使用此功能，按照國(guó)際正規(guī)比賽的規(guī)則，計(jì)算機(jī)會(huì)提示你在天元的位置下第一個(gè)子。</p><p>　　菜單及提示功能的設(shè)置，如圖4.4、圖4.5、圖4.6所示。</p><p><b>　　圖4.4游戲菜單</b></p>

96、;<p><b>　　圖4.5選項(xiàng)菜單</b></p><p><b>　　圖4.6提示效果</b></p><p><b>　　2．實(shí)現(xiàn)過(guò)程</b></p><p>　　實(shí)現(xiàn)菜單及提示界面的流程，如圖4.7所示。</p><p>　　圖4.7菜單及提示界面流程圖

97、</p><p>　　4.3.3　游戲結(jié)束</p><p><b>　　1．實(shí)現(xiàn)目標(biāo)</b></p><p>　　當(dāng)每局游戲結(jié)束的時(shí)候，會(huì)出現(xiàn)一個(gè)對(duì)話框。在對(duì)話框上，會(huì)顯示本局游戲是黑棋勝還是白棋勝，雙方共下了多少手棋。如果玩家使用黑棋則顯示黑棋悔棋幾次，如果玩家使用白棋則顯示白棋悔棋幾次。如果在雙方共下了不到二十手棋就輸了的話，在對(duì)話框上就會(huì)

98、顯示：“哎，你也實(shí)在太差了，難道你不知道該好好學(xué)習(xí)嗎？”否則顯示：“哈哈，你輸了，去多學(xué)幾招兒吧”。</p><p>　　單擊確定按鈕之后，就可以對(duì)下一局游戲進(jìn)行設(shè)置。</p><p>　　每一局游戲結(jié)束界面，如圖4.8所示。</p><p>　　圖4.8游戲結(jié)束界面</p><p><b>　　2．實(shí)現(xiàn)過(guò)程</b>&l

99、t;/p><p>　　實(shí)現(xiàn)游戲結(jié)束界面的流程，如圖4.9所示。</p><p>　　圖4.9結(jié)束界面流程圖</p><p><b>　　4.3.4　英雄榜</b></p><p><b>　　1．實(shí)現(xiàn)目標(biāo)</b></p><p>　　英雄榜里按初級(jí)、中級(jí)、專家級(jí)三個(gè)級(jí)別記錄玩家的

100、姓名和成績(jī)。每一局游戲結(jié)束的時(shí)候，如果玩家獲勝，而且成績(jī)優(yōu)于英雄榜里的成績(jī)，系統(tǒng)就會(huì)彈出喜登英雄榜界面。在這個(gè)界面中，顯示著此局游戲所選的級(jí)別，可以輸入玩家的姓名，單擊確定按鈕之后，玩家的大名和此局游戲的成績(jī)就會(huì)出現(xiàn)在英雄榜的相應(yīng)級(jí)別的記錄里。單擊英雄榜界面的重置按鈕，則英雄榜里的記錄就恢復(fù)到初始默認(rèn)狀態(tài)。</p><p>　　喜登英雄榜的界面，如圖4.10所示。</p><p>　　圖4

101、.10喜登英雄榜界面</p><p>　　英雄榜的界面，如圖4.11所示。</p><p>　　圖4.11英雄榜界面</p><p><b>　　2．實(shí)現(xiàn)過(guò)程</b></p><p>　　實(shí)現(xiàn)英雄榜的流程，如圖4.12所示。</p><p>　　圖4.12英雄榜界面流程圖</p>&

102、lt;p><b>　　4.4　本章小結(jié)</b></p><p>　　本章主要介紹了系統(tǒng)將要運(yùn)行的軟硬件環(huán)境，系統(tǒng)程序開(kāi)發(fā)的總體流程，并根據(jù)此流程，完成了代碼的編寫(xiě)工作。依據(jù)本系統(tǒng)的總體設(shè)計(jì)，在這個(gè)階段實(shí)現(xiàn)了各個(gè)功能模塊的程序?qū)崿F(xiàn)工作。這里詳細(xì)介紹了新局界面、菜單及提示界面、游戲結(jié)束界面、英雄榜及喜登英雄榜界面的實(shí)現(xiàn)目標(biāo)和實(shí)現(xiàn)過(guò)程。每一個(gè)界面的實(shí)現(xiàn)過(guò)程都用程序流程圖描述出來(lái)，使得每一個(gè)功

103、能模塊的實(shí)現(xiàn)過(guò)程都更直觀易懂。</p><p><b>　　第5章　系統(tǒng)測(cè)試</b></p><p><b>　　5.1系統(tǒng)軟件測(cè)試</b></p><p>　　選擇游戲菜單下的人機(jī)對(duì)戰(zhàn)的初級(jí)選項(xiàng)，以下中白棋為電腦方,測(cè)試結(jié)果如圖5.1。</p><p>　　圖5.1初級(jí)測(cè)試結(jié)果</p>

104、<p>　　選中中級(jí)選項(xiàng)，測(cè)試結(jié)果如圖5.2。</p><p>　　圖5.2中級(jí)測(cè)試結(jié)果</p><p>　　選中專家選項(xiàng)，測(cè)試結(jié)果如圖5.3。</p><p>　　圖5.3專家測(cè)試結(jié)果</p><p>　　喜登英雄榜的測(cè)試，其結(jié)果如圖5.4。</p><p>　　圖5.4喜登英雄榜測(cè)試結(jié)果</p&

105、gt;<p>　　英雄榜測(cè)試結(jié)果如圖5.5。</p><p>　　圖5.5英雄榜測(cè)試結(jié)果</p><p>　　從測(cè)試結(jié)果可以看出，游戲模塊、設(shè)置模塊、幫助模塊中的主要內(nèi)容都實(shí)現(xiàn)了，達(dá)到了預(yù)期的設(shè)計(jì)要求，本次設(shè)計(jì)比較成功。</p><p><b>　　結(jié)論</b></p><p>　　隨著近幾十年來(lái)人工智能的

106、飛速發(fā)展，越來(lái)越多的具有智能的機(jī)器進(jìn)入了人類的生活，人工智能的重要性如今顯而易見(jiàn)。而五子棋人機(jī)對(duì)弈程序的設(shè)計(jì)與實(shí)現(xiàn)這個(gè)課題，正好提供了這樣一個(gè)研究的機(jī)會(huì)，通過(guò)對(duì)人工智能中博弈方面的研究（人機(jī)對(duì)弈），在簡(jiǎn)單的人機(jī)對(duì)弈全局設(shè)計(jì)方面，以及具體到相關(guān)的算法上，都有了深入的了解。</p><p>　　通過(guò)編寫(xiě)這個(gè)程序，體會(huì)最為深刻的一點(diǎn)是系統(tǒng)架構(gòu)和設(shè)計(jì)模式的重要性。即使是對(duì)于一個(gè)并不大的程序，代碼的組織都是非常重要的，因?yàn)?/p>

107、這關(guān)系到日后的維護(hù)以及擴(kuò)展。這個(gè)游戲之中，有關(guān)博弈樹(shù)算法的知識(shí)都可以直接從無(wú)所不包的Internet上獲取，甚至可以直接獲得一個(gè)完整的五子棋人機(jī)對(duì)弈算法的源代碼級(jí)模塊。但是對(duì)于系統(tǒng)的架構(gòu)，卻完全是自己的事情，成千上萬(wàn)行的代碼需要通過(guò)合適的方法組織起來(lái)，使程序員編寫(xiě)代碼更加有條理，更加符合軟件工程的標(biāo)準(zhǔn)，這才是最重要的。</p><p>　　本系統(tǒng)實(shí)現(xiàn)了五子棋游戲的設(shè)計(jì)，總結(jié)起來(lái)，主要完成了以下工作。</p&

108、gt;<p>　　首先，對(duì)五子棋游戲有了更加深刻的理解。五子棋游戲起源于中國(guó)古代，發(fā)展于日本，風(fēng)靡于歐洲，它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。五子棋不僅能增強(qiáng)人們的抽象思維能力、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。它既有簡(jiǎn)單易學(xué)的特點(diǎn)，為人民群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧；既能組織群眾性的比賽、活動(dòng)，又能舉辦高水平的國(guó)際性比賽。</p><p>

109、　　在可行性研究階段，確定了本系統(tǒng)要實(shí)現(xiàn)的目標(biāo)。作為一個(gè)悠閑的小游戲系統(tǒng)，首先應(yīng)該為用戶提供一套方便的操作方法，在游戲模式，用戶操作,反饋信息方面應(yīng)該有明確的說(shuō)明，能夠讓大多數(shù)玩家能快速上手。使該游戲看上去是一款悠閑的精品。</p><p>　　在需求分析階段，按需求的業(yè)務(wù)需求、用戶需求、功能需求三個(gè)層次來(lái)完成。其中的用戶需求就是市場(chǎng)的需求，它是需求分析階段最重要的工作。</p><p>

110、　　本系統(tǒng)在詳細(xì)設(shè)計(jì)階段實(shí)現(xiàn)了人與人在同一臺(tái)計(jì)算機(jī)上對(duì)弈，人與計(jì)算機(jī)對(duì)弈兩種對(duì)弈模式。實(shí)現(xiàn)了中英文兩種菜單，在游戲過(guò)程中有聲音效果，可以悔棋、計(jì)算機(jī)提示下棋位置，可以查詢英雄榜，設(shè)置游戲難度，先手等功能。</p><p>　　本系統(tǒng)主要應(yīng)用的算法有極大極小值算法、Alpha-Beta算法、置換表技術(shù)、哈希表技術(shù)、歷史啟發(fā)等。通過(guò)本系統(tǒng)的開(kāi)發(fā)，對(duì)這些算法有了深入的了解，并熟練地掌握其應(yīng)用。</p>&

111、lt;p>　　由于時(shí)間和個(gè)人能力有限，這個(gè)五子棋游戲還有幾處不完善的地方。</p><p>　　第一、沒(méi)有設(shè)置禁手規(guī)則。</p><p>　　第二、由于計(jì)算機(jī)在落子時(shí)選取的是得分最高的一步落子，所以如果玩家在開(kāi)局的時(shí)候不改變落子步驟，那么將會(huì)獲得從頭至尾相同的棋局。</p><p>　　第三、對(duì)于人機(jī)對(duì)弈的悔棋處理，由于這個(gè)算法的開(kāi)銷相當(dāng)大，每一步落子都會(huì)存在