計(jì)算機(jī)畢業(yè)論文---五子棋游戲軟件的設(shè)計(jì)與實(shí)現(xiàn)

1、<p>　　2014年4月30日</p><p>　論文題目:五子棋游戲軟件的設(shè)計(jì)與實(shí)現(xiàn)</p><p><b>　　摘要</b></p><p>　　C++語(yǔ)言是一種面向?qū)ο蟮恼Z(yǔ)言，盡管在當(dāng)前，可視化語(yǔ)言發(fā)展迅速，普及很快，但C++語(yǔ)言作為一種基礎(chǔ)的語(yǔ)言，它的有時(shí)依然存在，甚至有時(shí)它是不可替代的，特別是和硬件接口技術(shù)相聯(lián)系的軟件。&

2、lt;/p><p>　　五子棋游戲是一種簡(jiǎn)單大眾的游戲，自從計(jì)算機(jī)實(shí)現(xiàn)以來(lái)，深受廣大電腦玩家的喜愛(ài)，現(xiàn)在流行的五子棋游戲軟件大多缺乏美觀(guān)的界面，和容易的操作方法，電腦的AI值也不是很高。本文通過(guò)C++語(yǔ)言在計(jì)算機(jī)圖形方面的編程，設(shè)計(jì)了五子棋游戲軟件，使該軟件具有美觀(guān)友好的截面，在人機(jī)對(duì)弈時(shí)，使電腦具有較高的智商。本游戲是以C++語(yǔ)言作為開(kāi)發(fā)工具，采用搜索算法設(shè)計(jì)最優(yōu)落子點(diǎn)開(kāi)發(fā)的游戲軟件。本文詳細(xì)地介紹了五子棋游戲軟件

3、設(shè)計(jì)的全過(guò)程，描述了該軟件的詳細(xì)功能。</p><p>　　關(guān)鍵詞：C++語(yǔ)言； 面向?qū)ο笳Z(yǔ)言； 算法</p><p><b>　　Abstract</b></p><p>　　The C++ language is an Object-oriented language, although in the current visualiza

4、tion language rapidly, and spread quickly, but the C++ language as a basis for language, its advantages still exist, and sometimes it is irreplaceable, particularly hardware and software interfaces are linked. </p>

5、<p>　　Gobang game is a simple and popular game, since the computer to achieve, by the love of computer players, but now most popular game soft gobang lack aesthetic interface, and easy method of operation, the val

6、ue of the computer AI is not high. The adoption of the C++ programming language in computer graphics, designed gobang game software to enable the software with a beautiful and friendly interface in both game, the compute

7、r has a higher IQ. The game is based on C++ language, using searching alg</p><p>　　Key word：C++ language； Object-oriented language； algorithm</p><p><b>　　目錄</b></p><p>&

8、lt;b>　　摘要I</b></p><p>　　AbstractII</p><p><b>　　1引言1</b></p><p>　　1.1五子棋的介紹1</p><p>　　1.2系統(tǒng)設(shè)計(jì)思想2</p><p>　　1.3開(kāi)發(fā)工具簡(jiǎn)介3</p>

9、;<p>　　1.4關(guān)于MFC簡(jiǎn)介3</p><p>　　1.5論文結(jié)構(gòu)4</p><p><b>　　2需求分析5</b></p><p>　　2.1需求分析的編寫(xiě)目的5</p><p>　　2.2可行性研究5</p><p>　　2.2.1技術(shù)可行性5&l

10、t;/p><p>　　2.2.2法律可行性5</p><p>　　2.2.3經(jīng)濟(jì)可行性5</p><p>　　2.2.4可行性結(jié)論5</p><p>　　2.3五子棋游戲規(guī)則5</p><p>　　2.3.1無(wú)禁手規(guī)則5</p><p>　　2.3.2禁手規(guī)則6</p&

11、gt;<p>　　2.3.3禁手的解釋6</p><p>　　2.4任務(wù)概述7</p><p>　　2.4.1目標(biāo)7</p><p>　　2.4.2處理對(duì)象7</p><p>　　2.4.3安全性和完整性7</p><p>　　2.5功能模塊分類(lèi)7</p><p

12、><b>　　3總體設(shè)計(jì)9</b></p><p>　　3.1系統(tǒng)環(huán)境要求9</p><p>　　3.2總體設(shè)計(jì)過(guò)程9</p><p>　　3.3系統(tǒng)的算法設(shè)計(jì)9</p><p>　　3.3.1博弈樹(shù)9</p><p>　　3.3.2極大極小值算法（Minimax Al

13、gorithm）10</p><p>　　3.3.3負(fù)極大值算法（Negamax Algorithm）11</p><p>　　3.3.4Alpha-Beta搜索11</p><p>　　3.3.5置換表（Transposition Table）12</p><p>　　3.3.6哈希表（Hash Table）13<

14、/p><p>　　3.3.7歷史啟發(fā)（History Heuristic）14</p><p><b>　　4詳細(xì)設(shè)計(jì)16</b></p><p>　　4.1系統(tǒng)程序流程圖16</p><p>　　4.2系統(tǒng)運(yùn)行平臺(tái)設(shè)置17</p><p>　　4.3系統(tǒng)主要功能的實(shí)現(xiàn)17<

15、/p><p>　　4.3.1程序系統(tǒng)結(jié)構(gòu)17</p><p>　　4.3.2初始化棋盤(pán)17</p><p>　　4.3.3下棋操作18</p><p>　　4.3.4判斷輸贏20</p><p>　　4.3.5AI算法21</p><p>　　5系統(tǒng)的實(shí)驗(yàn)與測(cè)試24</

16、p><p>　　5.1系統(tǒng)主要功能的實(shí)現(xiàn)24</p><p>　　5.1.1初始化棋盤(pán)24</p><p>　　5.1.2人機(jī)對(duì)戰(zhàn)24</p><p>　　5.1.3人人對(duì)戰(zhàn)25</p><p>　　5.1.4認(rèn)輸功能25</p><p>　　5.1.5游戲規(guī)則26</

17、p><p><b>　　5.2測(cè)試26</b></p><p>　　5.2.1測(cè)試的任務(wù)26</p><p>　　5.2.2測(cè)試的目標(biāo)26</p><p>　　5.2.3軟件測(cè)試的方法26</p><p><b>　　6結(jié)論28</b></p>

18、<p><b>　　致謝29</b></p><p><b>　　參考文獻(xiàn)30</b></p><p><b>　　引言</b></p><p>　　計(jì)算機(jī)技術(shù)的發(fā)展，使得計(jì)算機(jī)在現(xiàn)代企業(yè)、家庭中得以普及，應(yīng)用計(jì)算機(jī)成為現(xiàn)代人生活中非常重要的一部分。大到政府辦公、教育事業(yè)、商業(yè)活動(dòng)，小到

19、生活中的每一個(gè)細(xì)節(jié)。隨著社會(huì)進(jìn)步的節(jié)奏越來(lái)越快，人們的生活壓力也越來(lái)越大。每天奔波于不同的目的地，忙得沒(méi)有時(shí)間和朋友見(jiàn)面，忙得想找個(gè)釋放壓力的機(jī)會(huì)都沒(méi)有。這個(gè)時(shí)候，你是不是非常希望有個(gè)游戲，能夠陪你輕松愉快度過(guò)周末。自從計(jì)算機(jī)作為游戲?qū)?zhàn)平臺(tái)以來(lái)，各種棋類(lèi)游戲如雨后春筍般紛紛冒出。使得那些喜愛(ài)下棋，又常?？嘤跊](méi)有對(duì)手的棋迷們能隨時(shí)過(guò)足棋癮，而且這類(lèi)軟件大都水平頗高，大有與人腦分庭抗禮之勢(shì)。</p><p>　　五

20、子棋是一種受大眾廣泛喜愛(ài)的游戲，其規(guī)則簡(jiǎn)單，變化多端，非常富有趣味性和消遣性。同時(shí)具有簡(jiǎn)單易學(xué)、既動(dòng)手又動(dòng)腦的特點(diǎn)。五子棋游戲不僅能增強(qiáng)人們的抽象思維能力、邏輯推理能力、空間想象力，提高人們的記憶力、心算能力等，而且深含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑方式所特有的特征“短、平、快” ，又有中國(guó)古典哲學(xué)所包含的高深學(xué)問(wèn)“陰陽(yáng)易理”；它既有簡(jiǎn)單易學(xué)的特點(diǎn)，為人民群眾所喜聞樂(lè)見(jiàn)，又有深?yuàn)W的技巧；既能組織舉辦群眾性的比賽、活動(dòng)，又能組織

21、舉辦高水平的國(guó)際性比賽；它的棋文化源淵流長(zhǎng)，具有東方的神秘和西方的直觀(guān)，它是中西方文化的交融點(diǎn)，也是中西方文化交流的一個(gè)平臺(tái)。</p><p>　　五子棋的根在中國(guó)，在這個(gè)國(guó)境里，他有著廣泛的群眾基礎(chǔ)。但與世界先進(jìn)的五子棋技術(shù)相比，我們的棋藝水平還要繼續(xù)提高，所以我們要推廣五子棋，宣傳五子棋，爭(zhēng)取在較短的時(shí)間內(nèi)趕上和超過(guò)世界五子棋壇的先進(jìn)水平。在這種環(huán)境下，開(kāi)發(fā)一個(gè)易學(xué)實(shí)用的五子棋游戲軟件是很有必要的。</

22、p><p><b>　　五子棋的介紹</b></p><p>　　五子棋是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一?，F(xiàn)代五子棋日文稱(chēng)之為“連珠”，英譯為“Renju”，英文稱(chēng)之為“Gobang”或“FIR”(Five In a Row的縮寫(xiě))，亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱(chēng)謂。相傳早在堯造圍棋之前，五子棋游戲在民間已經(jīng)相當(dāng)盛行了。據(jù)《

23、增山海經(jīng)》中記載：“休輿之山有石焉，名曰帝臺(tái)之棋，五色而文狀鶉卵?！薄掇o海》中亦言：“五子棋中棋類(lèi)游戲，棋具與圍棋相同，兩人對(duì)局，輪流下子，先將五子連成一行者為勝。”唐時(shí)由高麗使者帶到高麗，后來(lái)輾轉(zhuǎn)反復(fù)，流傳到日本。起先是在日本皇宮內(nèi)盛行的游戲，只限于王室成員、貴族階層之間的對(duì)弈，后來(lái)?yè)?jù)說(shuō)被出入皇宮的挑夫看見(jiàn)，由此便流行民間。</p><p>　　五子棋起源于古代中國(guó)，發(fā)展于日本，風(fēng)靡于歐洲。對(duì)于它與圍棋的關(guān)系有

24、兩種說(shuō)法，一種說(shuō)法是早于圍棋，早在“堯造圍棋”之前，民間就已有五子棋游戲；另一說(shuō)法是源于圍棋，是圍棋發(fā)展的一個(gè)分支。在中國(guó)的文化里，倍受人們的青睞。古代的五子棋的棋具與圍棋相同，縱橫各十七道。五子棋大約隨圍棋一起在我國(guó)南北朝時(shí)先后傳入朝鮮、日本等地。據(jù)日本史料文獻(xiàn)介紹，中國(guó)古代的五子棋是經(jīng)由高麗(朝鮮)，于1688年至1704年的日本元祿時(shí)代傳到日本的。到日本明治32年(公元1899年)，經(jīng)過(guò)公開(kāi)征名，“連珠”這一名稱(chēng)才被正式確定下來(lái)，

25、取意于“日月如合壁，五星如連珠”。從此，連珠活動(dòng)經(jīng)過(guò)了不斷的改良，主要是規(guī)則的變化(即對(duì)執(zhí)黑棋一方的限制)。例如，1899年規(guī)定，禁止黑白雙方走“雙三” ；1903年規(guī)定，只禁止黑方走“雙三” ；1912年規(guī)定，黑方被迫走“雙三”亦算輸；1916年規(guī)定，黑方不許走“長(zhǎng)連” ；1918年規(guī)定，黑方不許走“四、三、三” ；1931年規(guī)定，黑方不許走“雙四” ，并規(guī)定將19×19的圍棋盤(pán)改為15×15的連珠專(zhuān)用棋盤(pán)。<

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

27、;　　系統(tǒng)設(shè)計(jì)思想</b></p><p>　　一個(gè)優(yōu)秀的游戲軟件，必須有一個(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>　　（1）實(shí)用性：系統(tǒng)以用戶(hù)需求為目標(biāo)，以方便用戶(hù)為原則，同時(shí)融入先進(jìn)的設(shè)計(jì)思想。根據(jù)用戶(hù)實(shí)際的需求情況，量身制作

28、一個(gè)功能齊全、操作簡(jiǎn)單、實(shí)用性強(qiáng)的游戲軟件。充分滿(mǎn)足游戲玩家的需求，真正成為為玩家提供輕松、娛樂(lè)、休閑的工具。</p><p>　?。?）先進(jìn)性：本軟件將充分應(yīng)用現(xiàn)有成熟的計(jì)算機(jī)技術(shù)、軟件開(kāi)發(fā)技術(shù)，為用戶(hù)提供高性能的系統(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)的可靠性與

29、容錯(cuò)性。</p><p>　　（4）可維護(hù)性：系統(tǒng)的設(shè)計(jì)要求方便維護(hù)，包括硬件的維護(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>　?。?）智能性：智能化是這個(gè)游戲軟件的一大特色。系統(tǒng)

30、在設(shè)計(jì)時(shí)，充分考慮系統(tǒng)運(yùn)行的智能性，如果有充足的時(shí)間改進(jìn)，計(jì)算機(jī)就可以實(shí)現(xiàn)更高的AI，在游戲中走的每一步就會(huì)考慮得更周密。</p><p><b>　　開(kāi)發(fā)工具簡(jiǎn)介</b></p><p>　　Visual Studio是微軟公司推出的開(kāi)發(fā)環(huán)境。是目前最流行的Windows平臺(tái)應(yīng)用程序開(kāi)發(fā)環(huán)境。Visual Studio 2010版本于2010年4月12日上市，其集成

31、開(kāi)發(fā)環(huán)境（IDE）的界面被重新設(shè)計(jì)和組織，變得更加簡(jiǎn)單明了。Visual Studio 2010同時(shí)帶來(lái)了 NET Framework 4.0、Microsoft Visual Studio 2010 CTP( Community Technology Preview--CTP)，并且支持開(kāi)發(fā)面向Windows 7的應(yīng)用程序。除了Microsoft SQL Server，它還支持 IBM DB2和Oracle數(shù)據(jù)庫(kù) 。</p>

32、;<p>　　Visual Studio 2010特點(diǎn)：支持Windows Azure，微軟云計(jì)算架構(gòu)邁入重要里程碑；助力移動(dòng)與嵌入式裝置開(kāi)發(fā)，三屏一云商機(jī)無(wú)限；實(shí)踐當(dāng)前最熱門(mén)的 Agile/Scrum 開(kāi)發(fā)方法，強(qiáng)化團(tuán)隊(duì)競(jìng)爭(zhēng)力；升級(jí)的軟件測(cè)試功能及工具，為軟件質(zhì)量嚴(yán)格把關(guān)；搭配Windows 7，Silverlight4 與 Office，發(fā)揮多核并行運(yùn)算威力；創(chuàng)建美感與效能并重的新一代軟件；支持最新C++標(biāo)準(zhǔn)，增強(qiáng)ID

33、E，切實(shí)提高程序員開(kāi)發(fā)效率。</p><p><b>　　關(guān)于MFC簡(jiǎn)介</b></p><p>　　MFC(Microsoft Foundation Classes)，是一個(gè)微軟公司提供的類(lèi)庫(kù)（class libraries），以C++類(lèi)的形式封裝了Windows的API，并且包含一個(gè)應(yīng)用程序框架，以減少應(yīng)用程序開(kāi)發(fā)人員的工作量。其中包含的類(lèi)包含大量Windows句

34、柄封裝類(lèi)和很多Windows的內(nèi)建控件和組件的封裝類(lèi)。 </p><p>　　MFC：微軟基礎(chǔ)類(lèi)(Microsoft Foundation Classes)，同VCL類(lèi)似，是一種應(yīng)用程序框架，隨微軟Visual C++開(kāi)發(fā)工具發(fā)布。目前最新版本為10.0（截止2011年3月），并且發(fā)布了中文版。該類(lèi)庫(kù)提供一組通用的可重用的類(lèi)庫(kù)供開(kāi)發(fā)人員使用，大部分類(lèi)均從CObject 直接或間接派生，只有少部分類(lèi)例外。[1]&l

35、t;/p><p>　　MFC應(yīng)用程序的總體結(jié)構(gòu)通常由開(kāi)發(fā)人員從MFC類(lèi)派生的幾個(gè)類(lèi)和一個(gè)CWinApp類(lèi)對(duì)象（應(yīng)用程序?qū)ο螅┙M成。MFC 提供了MFC AppWizard 自動(dòng)生成框架。</p><p>　　Windows 應(yīng)用程序中，MFC 的主包含文件為"Afxwin.h"。</p><p>　　此外MFC的部分類(lèi)為MFC/ATL 通用，可以在W

36、in32 應(yīng)用程序中單獨(dú)包含并使用這些類(lèi)。</p><p>　　由于它的易用性，初學(xué)者常誤認(rèn)為VC++開(kāi)發(fā)必須使用MFC，這種想法是錯(cuò)誤的。作為Application Framework，MFC的使用只能提高某些情況下的開(kāi)發(fā)效率，只起到輔助作用，而不能替代整個(gè)Win32 程序設(shè)計(jì)。</p><p><b>　　論文結(jié)構(gòu)</b></p><p>

37、　　本論文共分5章，文章的結(jié)構(gòu)安排如下：</p><p>　　第1章緒論。闡明了本課題研究的背景以及有關(guān)本課題的介紹、本課題系統(tǒng)設(shè)計(jì)思想和簡(jiǎn)單介紹開(kāi)發(fā)工具。</p><p>　　第2章用戶(hù)需求分析。詳細(xì)描述本系統(tǒng)的編寫(xiě)目的，任務(wù)概述，進(jìn)行功能模塊分類(lèi)，表明對(duì)系統(tǒng)的要求，為系統(tǒng)設(shè)計(jì)做好準(zhǔn)備。</p><p>　　第3章總體設(shè)計(jì)。提出對(duì)系統(tǒng)環(huán)境的要求，描述本系統(tǒng)的總體設(shè)

38、計(jì)過(guò)程以及系統(tǒng)算法設(shè)計(jì)。</p><p>　　第4章詳細(xì)設(shè)計(jì)。給出了系統(tǒng)程序流程圖，提出了系統(tǒng)運(yùn)行平臺(tái)的設(shè)置以及描述了系統(tǒng)主要功能的實(shí)現(xiàn)。</p><p>　　第5章系統(tǒng)的實(shí)現(xiàn)和測(cè)試。主要是給出系統(tǒng)主要功能的實(shí)現(xiàn)的截圖。</p><p><b>　　需求分析</b></p><p><b>　　需求分析的編寫(xiě)目

39、的</b></p><p>　　本需求分析報(bào)告的目的是規(guī)范化本軟件的編寫(xiě)，旨在為五子棋游戲軟件的開(kāi)發(fā)做前期調(diào)查，進(jìn)行全面細(xì)致的用戶(hù)需求分析，明確所要開(kāi)發(fā)的軟件應(yīng)具有的功能、性能和界面，提高系統(tǒng)開(kāi)發(fā)過(guò)程中的能見(jiàn)度，便于對(duì)系統(tǒng)開(kāi)發(fā)過(guò)程中的控制與管理，同時(shí)提出了本系統(tǒng)的軟件開(kāi)發(fā)過(guò)程，作為工作成果的原始依據(jù)，同時(shí)也表明了本系統(tǒng)的共性，以期能夠獲得更大范圍的應(yīng)用。</p><p><

40、;b>　　可行性研究</b></p><p><b>　　技術(shù)可行性</b></p><p>　　系統(tǒng)現(xiàn)階段的發(fā)展過(guò)程中，利用現(xiàn)有人力和物力是完全具備的能力開(kāi)發(fā)出來(lái)的，本系統(tǒng)的實(shí)現(xiàn)方法步驟簡(jiǎn)單容易，所以本系統(tǒng)的技術(shù)上是完全可行的。 </p><p>　?。?）在當(dāng)前的限制條件下，該系統(tǒng)的功能目標(biāo)能達(dá)到； &

41、lt;/p><p>　?。?）利用現(xiàn)有的技術(shù)，該系統(tǒng)的功能能實(shí)現(xiàn)； </p><p>　　（3）對(duì)開(kāi)發(fā)人員的數(shù)量和質(zhì)量的要求并說(shuō)明這些要求應(yīng)該能滿(mǎn)足； </p><p>　?。?）在規(guī)定的期限內(nèi)，本系統(tǒng)的開(kāi)發(fā)能完成。 </p><p><b>　　法律可行性 </b></p>

42、;<p>　　本系統(tǒng)只用于個(gè)人消遣娛樂(lè)，無(wú)廣告，不收取任何費(fèi)用，不透露任何私人信息，在法律 方面是完全可行的。 </p><p><b>　　經(jīng)濟(jì)可行性</b></p><p>　　本系統(tǒng)開(kāi)發(fā)成本低，不需要過(guò)多人員、金錢(qián)和特殊要求。</p><p><b>　　可行性結(jié)論 </b>

43、;</p><p>　　綜上所述，本工程的技術(shù)相當(dāng)成熟，完備也比較完善，測(cè)試手段可靠，具有良好的市場(chǎng) 拓展，技術(shù)上可行，經(jīng)濟(jì)上可行，操作上可行，因此本工程可立即開(kāi)始。</p><p><b>　　五子棋游戲規(guī)則</b></p><p><b>　　無(wú)禁手規(guī)則 </b></p><p>　　

44、黑白雙方依次落子，由黑先下，當(dāng)棋盤(pán)上有三個(gè)子時(shí)(兩黑一白),如果此時(shí)白方覺(jué)得開(kāi)的局不利于自已可以提出交換,黑方無(wú)條件接受!也可以不交換,主動(dòng)權(quán)在白方!然后繼續(xù)下棋,任一方先在棋盤(pán)上形成橫向、豎向、斜向的連續(xù)的相同顏色的五個(gè)(含五個(gè)以上)棋子的一方為勝。 </p><p><b>　　禁手規(guī)則</b></p><p>　　禁手是針對(duì)黑棋而言的，禁手是指一手黑棋棋形成：雙

45、活三，雙四，長(zhǎng)連(五子以上)為輸!這種方法限制了黑棋先行的優(yōu)勢(shì)！禁手對(duì)白棋無(wú)效！</p><p><b>　　禁手的解釋</b></p><p>　　圖2.1至圖2.8的x點(diǎn)為黑棋的禁手點(diǎn)</p><p>　　圖2.1三三禁手-示例1 圖2.2三三禁手-示例2</p><p>　　圖2.3四四禁手-示

46、例1 圖2.4四四禁手-示例2</p><p>　　圖2.5四四禁手-示例3</p><p>　　圖2.6四四禁手(扁擔(dān)陣)示例</p><p>　　圖2.7四三三禁手示例 圖2.8長(zhǎng)連禁手示例</p><p><b>　　任務(wù)概述</b></p><p&

47、gt;<b>　　目標(biāo)</b></p><p>　　本系統(tǒng)要實(shí)現(xiàn)的目標(biāo)：作為一個(gè)悠閑的小游戲軟件，首先應(yīng)該為用戶(hù)提供一套方便的操作方法，在游戲模式、用戶(hù)操作、反饋信息方面應(yīng)該有明確的說(shuō)明，能夠讓大多數(shù)玩家能快速上手，使該游戲看上去是一款悠閑的精品。</p><p>　　本系統(tǒng)能夠?qū)崿F(xiàn)以下功能：</p><p>　?。?）有人機(jī)對(duì)戰(zhàn)和人人對(duì)戰(zhàn)兩種

48、模式供玩家選擇；</p><p>　　（2）在開(kāi)局和退出以及下棋錯(cuò)誤的情況下都有提示音；</p><p><b>　　（3）悔棋；</b></p><p><b>　　（4）認(rèn)輸；</b></p><p><b>　　處理對(duì)象</b></p><p>　

49、　五子棋棋盤(pán)為15*15：棋盤(pán)正中一點(diǎn)為“天元”。棋盤(pán)兩端的橫線(xiàn)稱(chēng)端線(xiàn)。棋盤(pán)左右最外邊的兩條縱線(xiàn)稱(chēng)邊線(xiàn)。從兩條端線(xiàn)和兩條邊線(xiàn)向正中發(fā)展而縱橫交叉在第四條線(xiàn)形成的四個(gè)點(diǎn)稱(chēng)為“星”。</p><p><b>　　安全性和完整性</b></p><p>　　考慮到系統(tǒng)實(shí)施的可行性，在軟件方面選擇了性能穩(wěn)定的VS2010開(kāi)發(fā)環(huán)境、C++語(yǔ)言來(lái)進(jìn)行開(kāi)發(fā)。VS2010是非常成熟的

50、開(kāi)發(fā)工具，因此無(wú)論在安全性、可用性及可靠性等方面都毫無(wú)置疑，因此軟件方面是可行的。</p><p>　　在硬件方面，則選擇空間較大，只要是Pentium III系列及以上的計(jì)算機(jī)，內(nèi)存在256M以上，硬盤(pán)在1GB，都可以滿(mǎn)足系統(tǒng)的開(kāi)發(fā)需要。當(dāng)然，硬件的配置越高，系統(tǒng)的開(kāi)發(fā)與運(yùn)行會(huì)更流暢?？紤]到如今的家用或商用電腦硬件的整體配置水平，系統(tǒng)在硬件方面是可行的。</p><p><b>

51、;　　功能模塊分類(lèi)</b></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)包括三大模塊：游戲模塊、選項(xiàng)模塊、幫助模塊。每個(gè)模塊包括的主要內(nèi)容如下：</p><p>　　游戲模塊：新游戲、人人對(duì)戰(zhàn)、人機(jī)對(duì)戰(zhàn)、退出。</p><p>　　選

52、項(xiàng)模塊：悔棋、認(rèn)輸。</p><p>　　幫助模塊；游戲規(guī)則、有關(guān)本軟件的介紹。</p><p>　　本系統(tǒng)的主要功能模塊，如下圖2.9所示</p><p>　　圖2.9系統(tǒng)主要功能模塊圖</p><p><b>　　總體設(shè)計(jì)</b></p><p><b>　　系統(tǒng)環(huán)境要求</b

53、></p><p>　　服務(wù)器：要求處理器為Pentium III 兼容處理器或更高速度的處理器，處理器速度最低要求：600 MHz，推薦使用：1 GHz 或更高，80GB或以上可使用硬盤(pán)空間內(nèi)存最低要求：512 MB，推薦使用：1 GB 或更大，最大：操作系統(tǒng)最大內(nèi)存。</p><p>　　客戶(hù)機(jī)：要求處理器為Pentium III 兼容處理器或更高速度的處理器，處理器速度最低要求

54、：600 MHz，推薦使用：1 GHz 或更高，內(nèi)存最低要求：512 MB，推薦使用：1 GB 或更大，最大：操作系統(tǒng)最大內(nèi)存。</p><p><b>　　總體設(shè)計(jì)過(guò)程</b></p><p>　　總體設(shè)計(jì)過(guò)程通常由四個(gè)主要階段組成：系統(tǒng)體系結(jié)構(gòu)設(shè)計(jì)，確定系統(tǒng)的具體體系結(jié)構(gòu)實(shí)現(xiàn)方案；系統(tǒng)模塊設(shè)計(jì)，確定系統(tǒng)模塊層次；結(jié)構(gòu)算法設(shè)計(jì)，確定軟件結(jié)構(gòu)和典型算法；交互設(shè)計(jì)，確定

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

56、說(shuō)，代價(jià)是由一個(gè)關(guān)鍵資源，例如時(shí)間或空間來(lái)評(píng)估的。</p><p><b>　　系統(tǒng)的算法設(shè)計(jì)</b></p><p>　　五子棋游戲的開(kāi)發(fā)在搜索算法方面，可以有多種選擇。通過(guò)從不同的角度分析各種搜索方法的效率，來(lái)考慮本系統(tǒng)的算法應(yīng)用。</p><p>　　下面詳細(xì)地介紹一些算法：</p><p><b>　　

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

58、而這些節(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)的話(huà)）的下法；而輪到乙時(shí)，乙則會(huì)選擇子節(jié)點(diǎn)值為L(zhǎng)OST或DRAW（如果沒(méi)有值為L(zhǎng)OST的子節(jié)點(diǎn)的話(huà)）的下法。對(duì)于中間節(jié)點(diǎn)的值可以有如下計(jì)算方法：如果

59、該節(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ú)法處理的程度。所以我們需要其它的算法來(lái)減少搜索的數(shù)量。</p&

60、gt;<p>　　極大極小值算法（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)的值是其所有子節(jié)點(diǎn)中值最大的一個(gè)的值。而如果該節(jié)點(diǎn)所對(duì)應(yīng)

61、的局面輪到乙下棋，則該節(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><p>　　在通常的棋局當(dāng)中，一

62、個(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ì)于中間節(jié)點(diǎn)，如同前面提到的那樣，甲方取子節(jié)點(diǎn)的最大值，乙

63、方取子節(jié)點(diǎn)的最小值。這個(gè)評(píng)分的函數(shù)稱(chēng)作靜態(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)的。利用具體的知識(shí)構(gòu)成評(píng)估函數(shù)的搜索叫做啟發(fā)式搜索（Heu

64、ristic Search）。估值函數(shù)在有些文獻(xiàn)中也稱(chēng)為啟發(fā)函數(shù)（Heuristic Functio</p><p>　　在博弈樹(shù)搜索的文獻(xiàn)當(dāng)中，極大極小方法往往指的是基于靜態(tài)估值函數(shù)的有限深度的極大極小搜索。MinMax算法是對(duì)弈的基礎(chǔ)思想。</p><p>　　負(fù)極大值算法（Negamax Algorithm）</p><p>　　普通的極大極小值算法看起來(lái)有

65、一點(diǎn)笨，既然一方試圖取極大值而另一方試圖取極小值——也就是說(shuō)——我們總要檢查哪一方要取極大值而哪一方又要取極小值，以執(zhí)行不同的動(dòng)作。Knuth和Moore在1975年提出了負(fù)極大值（Negamax）方法，消除了兩方的差別，而且簡(jiǎn)潔優(yōu)雅。使用負(fù)極大值方法，博弈雙方都取極大值。</p><p>　　Alpha-Beta搜索</p><p>　　在極大極小搜索的過(guò)程中，存在著一定程度的數(shù)據(jù)冗余。

66、舉一個(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>　　將上述這個(gè)情形推廣一下，設(shè)想有如圖3.1左半部所示的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)下面數(shù)字為該節(jié)點(diǎn)的值，節(jié)點(diǎn)B的值為18，節(jié)點(diǎn)D的值為16，由此我們可以判斷

67、節(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)減去稱(chēng)為Alpha剪枝（alpha cutoff）。</p><p>　　圖3.1 Alpha-Beta剪枝示例圖</p><p>　　設(shè)想有如圖3.1右半部所示的一棵極大極小樹(shù)的片斷，節(jié)點(diǎn)B的估值為8，節(jié)點(diǎn)

68、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)減去稱(chēng)為Beta剪枝（beta cutoff）。</p><p>　　置換表（Transposition Table）</p><p>　　在極大極小搜索的過(guò)程中，改進(jìn)搜索算法的目

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

70、，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é)果，我們就要用一張表把搜索過(guò)的節(jié)點(diǎn)記錄下來(lái)。然后在后續(xù)的搜

71、索中，察看記錄在表中的這些結(jié)果，如果將要搜索的某個(gè)節(jié)點(diǎn)已有記錄，就直接利用記錄下來(lái)的結(jié)果。這種方法叫做置換表（Transposition Table，簡(jiǎn)稱(chēng)TT）。</p><p>　　如果將Alpha-Beta搜索過(guò)程中每一節(jié)點(diǎn)的結(jié)果都記錄下來(lái)，則在任意節(jié)點(diǎn)向下搜索之前先查看這些紀(jì)錄，就可避免上述重復(fù)的操作。</p><p>　　但是這個(gè)置換表如何實(shí)現(xiàn)的？困難集中在時(shí)間和空間復(fù)雜度上。&l

72、t;/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>　　哈希表（Hash Table）</p>

73、<p>　　置換表的實(shí)現(xiàn)在時(shí)間和空間復(fù)雜度上的疑問(wèn)。實(shí)際上已經(jīng)明確了要實(shí)現(xiàn)置換表必須要滿(mǎn)足如下條件：</p><p>　　1．查找記錄中的節(jié)點(diǎn)數(shù)據(jù)時(shí)速度要非?？欤詈檬穷?lèi)似于隨機(jī)存取。</p><p>　　2．將節(jié)點(diǎn)數(shù)據(jù)放入記錄的速度也要非?？?。這就意味著數(shù)據(jù)項(xiàng)插入的過(guò)程不可有數(shù)據(jù)移動(dòng)排序等操作。</p><p>　　3．要能在有限的存儲(chǔ)空間內(nèi)進(jìn)行。&

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

75、<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ǔ)單元上的情形，叫做沖突。</p><p>　　我們將利用哈希方

76、法實(shí)現(xiàn)置換表的方法敘述如下。定義哈希數(shù)組如表3.1所示：</p><p>　　表3.1定義哈希數(shù)組</p><p>　　對(duì)要搜索的每一節(jié)點(diǎn)，計(jì)算出它的一個(gè)哈希值（hashIndex，通常是一個(gè)32位數(shù)對(duì)哈希表大小取模）以確定此局面在哈希表中的位置。計(jì)算另一個(gè)64位的哈希值（Checksum）來(lái)校驗(yàn)表中的數(shù)據(jù)項(xiàng)是否是所要的那一項(xiàng)。</p><p>　　在對(duì)某一局面搜索

77、之前，先查看哈希表項(xiàng) hashTable［hashIndex］，如果 hashTable［hashIn-dex］.checksum==Checksum并且hashTable［hashIndex］.depth 大于等于最大搜索深度減去當(dāng)前層數(shù)，就返回hashTable［hashIndex］.eval作為當(dāng)前局面的估值。</p><p>　　當(dāng)對(duì)一個(gè)局面的搜索完成之后，將Checksum、當(dāng)前層數(shù)和估值結(jié)果保存到 h

78、ashTable［hashIndex］當(dāng)中，以備后面的搜索使用。</p><p>　　歷史啟發(fā)（History Heuristic）</p><p>　　在前面我們?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ù)

79、來(lái)說(shuō)，如果極大極小搜索需遍歷106個(gè)節(jié)點(diǎn)求得結(jié)果，那么處于理想狀態(tài)的 Alpha-Beta搜索僅需遍歷約2000個(gè)節(jié)點(diǎn)就可求得結(jié)果。而在節(jié)點(diǎn)的排序最不理想的情況下，Alpha-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)中往

80、往有一些相似的局面，僅有一些無(wú)關(guān)緊要的棋子位置不同等等。這些相似的局面往往也是較好的。可以通過(guò)一些較復(fù)雜的判斷來(lái)找出這些相似的局面，率先搜索從而提高剪枝效率。但這一方法需要具體棋類(lèi)相關(guān)的知識(shí)，并且往往判斷復(fù)雜而效果不彰。</p><p>　　J.Schaeffer提出了History Heuristic的方法，在基于Alpha-Beta的搜索當(dāng)中，一個(gè)好的走法可以定義如下：</p><p>

81、;　　1．由其產(chǎn)生的節(jié)點(diǎn)引發(fā)了剪枝。</p><p>　　2．未引發(fā)剪枝，但是其兄弟走法中的最佳者。</p><p>　　在搜索的過(guò)程中，每當(dāng)找到一個(gè)好的走法，就將與該走法相對(duì)應(yīng)的歷史得分作一個(gè)增量，一個(gè)多次被搜索并確認(rèn)為好的走法的歷史紀(jì)錄就會(huì)較高，當(dāng)搜索中間節(jié)點(diǎn)時(shí)，將走法根據(jù)其歷史得分排列順序，以獲得較佳的排列順序。這比采用基于棋類(lèi)知識(shí)而對(duì)節(jié)點(diǎn)排序的方法要容易得多。由于歷史得分表隨搜索而

82、改變，對(duì)節(jié)點(diǎn)順序的排列也會(huì)隨之動(dòng)態(tài)改變。</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　系統(tǒng)程序流程圖</b></p><p>　　1．程序流程圖的作用</p><p>　　程序流程圖是人們對(duì)解決問(wèn)題的方法、思路或算法的一種描述。</p><p>

83、<b>　　2．流程圖的優(yōu)點(diǎn)：</b></p><p>　?。?）采用簡(jiǎn)單規(guī)范的符號(hào)，畫(huà)法簡(jiǎn)單；</p><p>　?。?）結(jié)構(gòu)清晰，邏輯性強(qiáng)；</p><p>　?。?）便于描述，容易理解；</p><p>　　3．本系統(tǒng)的程序流程為玩家進(jìn)入游戲后，默認(rèn)為人機(jī)對(duì)弈，如果玩家是兩個(gè)人，可以在游戲菜單中，選擇人人對(duì)戰(zhàn)模式，

84、接下來(lái)就是對(duì)弈過(guò)程，每下一步棋，都會(huì)進(jìn)行本局游戲是否結(jié)束的判斷，結(jié)束的標(biāo)志是游戲的一方有五個(gè)棋子相連。如果本局游戲沒(méi)有結(jié)束，則玩家可以通過(guò)選項(xiàng)菜單中的悔棋和認(rèn)輸來(lái)實(shí)現(xiàn)悔一步棋和主動(dòng)認(rèn)輸?shù)墓δ?。如果本局游戲結(jié)束，則會(huì)彈出哪方獲得了勝利。本系統(tǒng)的程序流程，如圖4.1所示。</p><p>　　圖4.1系統(tǒng)的程序流程</p><p><b>　　系統(tǒng)運(yùn)行平臺(tái)設(shè)置</b>&l

85、t;/p><p>　　硬件環(huán)境：臺(tái)式計(jì)算機(jī)（PC）一臺(tái)。</p><p><b>　　系統(tǒng)主要功能的實(shí)現(xiàn)</b></p><p><b>　　程序系統(tǒng)結(jié)構(gòu)</b></p><p>　　程序系統(tǒng)結(jié)構(gòu)如圖4.2所示</p><p>　　圖4.2程序系統(tǒng)結(jié)構(gòu)</p>&l

86、t;p><b>　　初始化棋盤(pán)</b></p><p>　　由于游戲的棋盤(pán)大小是一定的，不能改變大小的，是應(yīng)該符合要求的。所以首先需要設(shè)置窗口的大小。設(shè)置的對(duì)話(huà)框的長(zhǎng)為530，寬為490，并且對(duì)話(huà)框在屏幕的中央顯示，代碼如表4.1所示。</p><p>　　表4.1設(shè)置窗口大小和位置</p><p>　　然后在OnPaint函數(shù)中畫(huà)棋盤(pán)、

87、背景、天元和星以及黑棋和白棋，RGB(210,180,140)代表棋盤(pán)背景為棕褐色，棋盤(pán)是15*15的標(biāo)準(zhǔn)棋盤(pán)，每一個(gè)間隔距離是30，天元和星是以邊長(zhǎng)為10的正方形表示的，填充顏色為黑色。并且以半徑為15的圓分別填充黑白兩色來(lái)代表黑白棋，代碼如表4.2所示。</p><p>　　表4.2初始化棋盤(pán)的各種對(duì)象</p><p><b>　　下棋操作</b></p&g

88、t;<p>　　首先聲明變量m_flag來(lái)判斷是否要捕捉鼠標(biāo)消息.m_flag=1時(shí),捕捉消息,m_flag=0時(shí),不要捕捉消息，接下來(lái)聲明變量m_mode定義游戲模式(人人對(duì)戰(zhàn)或者人機(jī)對(duì)戰(zhàn)).m_mode=0時(shí),為人機(jī)對(duì)戰(zhàn)（默認(rèn)）,m_mode=1時(shí),為人人對(duì)戰(zhàn)。最后聲明m_color來(lái)判斷當(dāng)前誰(shuí)走棋（m_color=-1時(shí)，白棋走；m_color=1時(shí)，黑棋走），具體代碼如表4.3所示、流程圖如圖4.3所示。</

89、p><p>　　圖4.3下棋操作流程圖</p><p><b>　　表4.3下棋操作</b></p><p><b>　　判斷輸贏</b></p><p>　　接著是用一個(gè)IsOver（）函數(shù)判斷是否結(jié)束，是則結(jié)束并重新開(kāi)始；否則，接著把鼠標(biāo)變成對(duì)方棋子，表示對(duì)方下棋。</p><p

90、>　　此函數(shù)是利用剛下棋的位置為中心，檢查它各個(gè)方向上的連續(xù)五個(gè)棋子是否同色，是則結(jié)束并重新開(kāi)始。</p><p>　　然而，判斷一個(gè)方向上的五個(gè)棋子的是否同色就涉及到聲明棋盤(pán)數(shù)組wzq[SIZE][SIZE]，初始情況每一項(xiàng)為0；若黑棋按下，該項(xiàng)值為1；若白棋按下，該項(xiàng)值為-1，這樣就可以利用連續(xù)五個(gè)棋子的值相加，如果它們的值的絕對(duì)值等于5，則說(shuō)明是同色，具體代碼如表4.4所示、流程圖如圖4.4所示。&l

91、t;/p><p><b>　　圖4.4判斷輸贏</b></p><p><b>　　表4.4判斷輸贏</b></p><p><b>　　AI算法</b></p><p>　　所謂人機(jī)對(duì)戰(zhàn)就是人和計(jì)算機(jī)的博弈，計(jì)算機(jī)如何下棋就需要程序的設(shè)計(jì)與實(shí)現(xiàn)。然而，計(jì)算機(jī)不能隨便在棋盤(pán)上面放一

92、顆棋子。計(jì)算機(jī)要下的那個(gè)位置，必定是它認(rèn)為最好的！當(dāng)然，這里的最好是程序員給予計(jì)算機(jī)的，是計(jì)算機(jī)算法的體現(xiàn)，下面主要介紹一下本文的AI博弈算法。</p><p>　　在上文中聲明了wzq棋盤(pán)數(shù)組，賦值為1和-1，五個(gè)連續(xù)的棋子的值相加絕對(duì)值為5，則判斷為勝， 然而，它的功能不止于此，它幾乎關(guān)系到本程序的全部算法，當(dāng)絕對(duì)值為4時(shí)，表示五個(gè)棋子中有一個(gè)空位置和四個(gè)同色的棋子；絕對(duì)值為3時(shí)，表示五個(gè)棋子中有兩個(gè)空位置和

93、三個(gè)同色的棋子，也表示五個(gè)棋子中有四個(gè)同色棋子和一個(gè)異色棋子；絕對(duì)值為2時(shí)，表示五個(gè)棋子中有三個(gè)空位置和兩個(gè)同色棋子，也表示五個(gè)棋子中一個(gè)空位置和三個(gè)同色棋子和一個(gè)異色棋子；當(dāng)絕對(duì)值為0或1時(shí)，由于出現(xiàn)1和0的機(jī)會(huì)太少不必多加考慮，具體代碼如表4.5所示。</p><p><b>　　表4.5 AI算法</b></p><p><b>　　系統(tǒng)的實(shí)驗(yàn)與測(cè)試&

94、lt;/b></p><p><b>　　系統(tǒng)主要功能的實(shí)現(xiàn)</b></p><p><b>　　初始化棋盤(pán)</b></p><p>　　初始化棋盤(pán)界面如圖5.1所示，在實(shí)際操作中玩家可以在外圍的四個(gè)黑點(diǎn)的區(qū)域內(nèi)下棋，玩家可以選擇黑棋或者白棋。</p><p><b>　　圖5.1棋

95、盤(pán)的實(shí)現(xiàn)</b></p><p><b>　　人機(jī)對(duì)戰(zhàn)</b></p><p>　　人機(jī)對(duì)戰(zhàn)界面如圖5.2所示，在實(shí)際操作中人機(jī)對(duì)戰(zhàn)時(shí)當(dāng)一方取得勝利后，系統(tǒng)會(huì)自動(dòng)提示勝利的一方，然后點(diǎn)擊確定，開(kāi)始下一局。</p><p>　　圖5.2人機(jī)對(duì)戰(zhàn)的實(shí)現(xiàn)</p><p><b>　　人人對(duì)戰(zhàn)</b&

96、gt;</p><p>　　人人對(duì)戰(zhàn)如圖5.3所示，在實(shí)際操作中玩家對(duì)戰(zhàn)時(shí)，當(dāng)一方獲得勝利后，系統(tǒng)會(huì)自動(dòng)提示勝利的一方，點(diǎn)擊確定，雙方可以開(kāi)始下一局的對(duì)決。</p><p>　　圖5.3人人對(duì)戰(zhàn)的實(shí)現(xiàn)</p><p><b>　　認(rèn)輸功能</b></p><p>　　認(rèn)輸界面如圖5.4所示，在實(shí)際操作中如果對(duì)戰(zhàn)一方，覺(jué)得

97、此局沒(méi)有勝利的可能了也可以選擇投降認(rèn)輸，這樣可以節(jié)省游戲的時(shí)間。</p><p>　　圖5.4認(rèn)輸功能的實(shí)現(xiàn)</p><p><b>　　游戲規(guī)則</b></p><p>　　游戲規(guī)則如圖5.5所示，在實(shí)際操作中玩家點(diǎn)擊左上角幫助可以查看關(guān)于游戲的規(guī)則。</p><p><b>　　圖5.5游戲規(guī)則</b

98、></p><p><b>　　測(cè)試</b></p><p><b>　　測(cè)試的任務(wù)</b></p><p>　　在軟件完成之前，盡可能多地發(fā)現(xiàn)軟件中的錯(cuò)誤。</p><p><b>　　測(cè)試的目標(biāo)</b></p><p>　　測(cè)試的目的是為了發(fā)現(xiàn)

99、程序中的錯(cuò)誤而執(zhí)行程序的過(guò)程。</p><p>　　好的測(cè)試方案是極可能發(fā)現(xiàn)迄今為止尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試方案。</p><p>　　成功的測(cè)試是發(fā)現(xiàn)了到今為止尚未發(fā)現(xiàn)的錯(cuò)誤的測(cè)試。</p><p><b>　　軟件測(cè)試的方法</b></p><p>　　軟件測(cè)試有兩種方法：白盒法和黑盒法</p><p

100、>　　如果知道了產(chǎn)品應(yīng)該具有的功能，可以通過(guò)測(cè)試來(lái)檢測(cè)是否每個(gè)功能都能實(shí)現(xiàn)，這種測(cè)試方法叫作黑盒測(cè)試法；如果知道產(chǎn)品的內(nèi)部工作過(guò)程，可以通過(guò)測(cè)試來(lái)檢驗(yàn)是否按照規(guī)格說(shuō)明說(shuō)的規(guī)定正常運(yùn)行，這個(gè)方法叫白盒測(cè)試法。對(duì)于軟件而言，黑盒測(cè)試法是把程序看成一個(gè)黑盒子，完全不考慮程序的內(nèi)部結(jié)構(gòu)和處理過(guò)程。也就是說(shuō)黑盒測(cè)試是在程序的接口進(jìn)行測(cè)試，它只檢查程序的功能是否按照規(guī)格說(shuō)明說(shuō)的說(shuō)明正常運(yùn)行，程序是否能恰當(dāng)?shù)慕邮茌斎霐?shù)據(jù)，產(chǎn)生正確的輸出信息，并

101、且保持外部信息的完整性。黑盒測(cè)試又稱(chēng)為功能測(cè)試。與黑盒測(cè)試法相反，白盒測(cè)試法是把程序看成是裝在一個(gè)透明的白盒子里。也就是完全了解程序的結(jié)構(gòu)和處理過(guò)程，這種方法按照程序內(nèi)部的邏輯測(cè)試程序，檢驗(yàn)程序中的每條通路是否能按預(yù)定的要求正確工作，白盒測(cè)試又稱(chēng)為結(jié)構(gòu)測(cè)試。</p><p>　　粗看起來(lái)，不論采用上述那種測(cè)試方法，只要對(duì)每一種可能的情況都進(jìn)行測(cè)試，就可以得到完全正確的程序。包含所有可能情況的測(cè)試成為窮盡測(cè)試，對(duì)于

102、實(shí)際程序而言，窮盡測(cè)試通常是不可能做到的。使用黑盒測(cè)試法為了做到窮盡測(cè)試，至少對(duì)所有輸入數(shù)據(jù)的各種可能值的排列組合都進(jìn)行測(cè)試，但是，由此得到的應(yīng)該測(cè)試的情況，數(shù)字往往達(dá)到實(shí)際上根本無(wú)法測(cè)試的程度。實(shí)踐表明，用無(wú)效的輸入數(shù)據(jù)比有效的輸入數(shù)據(jù)進(jìn)行測(cè)試往往能發(fā)現(xiàn)更多的錯(cuò)誤。使用白盒測(cè)試法和使用黑盒測(cè)試法一樣也不可能做到窮盡測(cè)試。</p><p>　　因?yàn)椴荒茏龅礁F盡測(cè)試，所以軟件測(cè)試不可能發(fā)現(xiàn)程序中的所有錯(cuò)誤。也就是所

103、通過(guò)測(cè)試并不能證明程序是完全正確的。但是，目的是要通過(guò)測(cè)試保證軟件愛(ài)你的可靠性，因此，必須仔細(xì)設(shè)計(jì)測(cè)試方案，力爭(zhēng)用盡可能少的測(cè)試發(fā)現(xiàn)盡可能多的錯(cuò)誤。</p><p>　　考慮到各種因素和條件的限制，決定采用黑盒測(cè)試方案。黑盒測(cè)試注重于測(cè)試軟件的功能性需求，也就是說(shuō)黑盒測(cè)試要求軟件工程師列出程序所有功能需求的輸入條件。通過(guò)黑盒測(cè)試，我們能發(fā)現(xiàn)一些平時(shí)不能發(fā)現(xiàn)的細(xì)節(jié)性錯(cuò)誤。五子棋游戲功能測(cè)試用例如表5.1所示。<

104、;/p><p><b>　　表5.1測(cè)試用例</b></p><p><b>　　結(jié)論</b></p><p>　　以上就是設(shè)計(jì)這個(gè)游戲的全部過(guò)程，這款由C++軟件設(shè)計(jì)的五子棋游戲，從其圖形界面到游戲的風(fēng)格都能很好的滿(mǎn)足廣大玩家的需求，而且從規(guī)矩上也繼承了傳統(tǒng)游戲的精髓，不論是人機(jī)對(duì)戰(zhàn)，還是人人對(duì)戰(zhàn)都可以靈活運(yùn)用，所以肯定會(huì)廣

105、受玩家的喜愛(ài)。</p><p>　　五子棋在我國(guó)的很多大、中城市發(fā)展很快，尤其是首都北京，曾多次舉辦了五子棋的各種比賽，中央電視臺(tái)體育頻道也長(zhǎng)期播放著五子棋的講座，還有，一些大型企業(yè)和單位也曾舉辦過(guò)五子棋的比賽。預(yù)計(jì)在幾年后，五子棋將成為國(guó)內(nèi)最受歡迎的項(xiàng)目之一。 </p><p>　　中國(guó)作為五子棋的發(fā)源國(guó)，要對(duì)五子棋在下個(gè)世紀(jì)的發(fā)展起到世界性的推動(dòng)作用。五子棋的發(fā)展在中國(guó)出現(xiàn)方

106、興未艾、星火燎原之勢(shì)。同時(shí)還有一大批的中生代棋手和充滿(mǎn)希望的“明日之星”。相信，中國(guó)棋手攀登五子棋巔峰的日子會(huì)早日來(lái)到。</p><p><b>　　致謝</b></p><p>　　為期一個(gè)學(xué)期的畢業(yè)設(shè)計(jì)即將結(jié)束，在此期間，在方老師和同學(xué)的幫助下，我順利地完成了本次設(shè)計(jì)任務(wù)。通過(guò)此次設(shè)計(jì)，我在軟件研發(fā)與測(cè)試方面有很大收獲。我要感謝所有幫助過(guò)我的人。</p>

107、;<p>　　首先由衷地感謝我的指導(dǎo)老師*老師。能由*老師指導(dǎo)做畢業(yè)設(shè)計(jì)是我的榮幸，她的認(rèn)真負(fù)責(zé)給了我很大的觸動(dòng)，畢業(yè)設(shè)計(jì)的整個(gè)時(shí)間安排他都為我們規(guī)劃得很詳細(xì)，并定期檢查驗(yàn)收，論文初稿的審核連標(biāo)點(diǎn)符號(hào)都會(huì)指出來(lái)。在項(xiàng)目開(kāi)發(fā)過(guò)程中，劉老師在學(xué)習(xí)和生活上給了我很大的關(guān)懷和照顧，與她的每次交流，她的思維方式、她的經(jīng)驗(yàn)教訓(xùn)，都使我受益匪淺。</p><p>　　其次感謝我的父母還有家人，給了我無(wú)私的關(guān)懷，支

108、持著我的學(xué)業(yè)。希望他們永遠(yuǎn)健康幸福。</p><p>　　再次感謝我計(jì)算機(jī)專(zhuān)業(yè)的同學(xué)們，兩年半的時(shí)光我們一起度過(guò)、一起成長(zhǎng)，有歡笑、有淚水，但不論苦與樂(lè)，都將成為我腦海中揮之不去的記憶。</p><p>　　還要感謝培養(yǎng)了我的學(xué)院！感謝學(xué)院老師的教誨與培養(yǎng)，從他們的課程中我學(xué)到了很多知識(shí)，并運(yùn)用到了本次畢業(yè)設(shè)計(jì)中。</p><p>　　雖然我在畢業(yè)設(shè)計(jì)過(guò)程中投入了大

109、量精力，但由于自己學(xué)識(shí)、水平的限制，在理論的深度和博弈算法的理解等方面還有著很多的不足之處，懇請(qǐng)各位師長(zhǎng)批評(píng)指正!</p><p><b>　　參考文獻(xiàn)</b></p><p>　　王小春．PC游戲編程（人機(jī)博弈）[M]．重慶大學(xué)出版社，2008：18-27．102-152.</p><p>　　Bruce Eckel著．C++編程思想[M]．

110、劉宗田，邢紅等譯．機(jī)械工業(yè)出版社，2009：165-182.</p><p>　　Jesse Liberty著．21天學(xué)通C++[M]．康博創(chuàng)作室譯．人民郵電出版社，2012.</p><p>　　Noel Llopis．C++游戲編程[M]．李鵬，賈傳俊譯．清華大學(xué)出版社，2004.</p><p>　　Nicolai M.Josuttis著．C++標(biāo)準(zhǔn)程序庫(kù)[M

111、]．侯捷，孟巖譯．華中科技大學(xué)出版社，2003.</p><p>　　李紅．博弈樹(shù)搜索算法．長(zhǎng)春工程學(xué)院學(xué)報(bào)[J]．2007.</p><p>　　顧德裕．極大極小值算法．蘇州絲綢工學(xué)院學(xué)報(bào)[J]．2011.</p><p>　　侯俊杰著．深入淺出MFC[M]．第2版．華中科技大學(xué)出版社，2008.</p><p>　　林舒揚(yáng)．五子棋入門(mén)與提