1、 可修改 歡送下載 精品 Word 可修改 歡送下載 精品 Word 可修改 歡送下載 精品 Word 目 錄 系統(xtng)需求分析與總體設計概述(i sh)(3)1.1.1 五子棋背景(bijng)介紹(3)1.1.2相關(xinggun)術語(4)1.1.2.1對局相關(xinggun)術語(4)1.1.2.2行棋相關術語(4)1.2 需求分析(6)1.2.1 選題與題目要求 (6)總體(zngt)分析 (6)系統(xtng)目標 (6)需求(xqi)定義 (6)系統(xtng)功能結構圖 (7)性能(xngnng)要求與系統開發的重點與難點 (7)1.3可行性分析(8)1.3.1 技

2、術可行性(8)1.3.2 經濟可行性(8)1.3.3 操作可行性(8)1.3.4 法律可行性(8)1.3.5 社會可行性(9)1.3.6 結論 (9) 詳細設計與系統實現 2.1 游戲主要功能模塊 (10)2.1.1 主功能界面模塊 (10)2.1.2 五子棋游戲類模塊 (11) 2.1.2.1博弈算法簡介 (15)2.1.2.2極大極小值算法 (16)2.1.2.3 alpha-beta值算法 (17)2.1.3 游戲模式設置模塊 (19)2.1.4 游戲語言設置模塊 (19)2.1.5 鏈表使用功能模塊 (20)2.1.6游戲記錄模塊 (20)2.1.7 獲得游戲者姓名模塊 (21)2.1

3、.8 關閉對話框方式及托盤功能模塊 (21)2.1.9 圓形按鈕模塊(m kui) (21)2.1.10 配置文件的讀取和保存(bocn)(22)2.2 模塊功能(gngnng)調用關系及其示意圖 (22)第三章 系統(xtng)測試 3.1程序運行結果(ji gu)截圖(24)第四章 系統總結4.1 系統存在的問題(27)4.2 將要做的工作(27)4.3 總結和體會(27) 4.4 參考文獻(28)第一章 系統需求分析與總體設計1.1 概述 五子棋是一種群眾喜愛的游戲，其規那么簡單，變化多端，非常富有趣味性和消遣性，它不僅能增強思維能力，提高智力，而且富含哲理，有助于修身養性。五子棋既有現

4、代休閑的明顯特征短、平、快，又有古典哲學的高深學問陰陽易理；它既有簡單易學的特性，為人民群眾所喜聞樂見，又有深奧的技巧和高水平的國際性比賽；它的棋文化源淵流長，具有東方的神秘和西方的直觀；既有場的概念，亦有點的連接。它是中西文化的交流點，是古今哲理的結晶。近來隨著計算機的快速開展，各種棋類游戲被紛紛請進了電腦，使得那些喜愛下棋，又常常苦于沒有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大有與人腦分庭抗禮之勢。其中戰勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍便是最具說服力的代表；其它像圍棋的“手淡、象棋的“將族等也以其優秀的人工智能深受棋迷喜愛；而我也做了一個“無比簡單的五子棋程序。總的

5、來說我們(w men)假定您熟悉五子棋的根本(gnbn)規那么(n me)，要讓電腦知道人下子之后該在哪一點下子，就要根據(gnj)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這子落下后會形成什么棋型如：“沖四、“活三 等，然后總覽全盤選出最重要的一點(y din)，這便是最根本的算法的思想。1.1.1 五子棋背景介紹 五子棋是一種兩人 HYPERLINK :/baike.baidu /view/17808.htm t _blank 對弈的純 HYPERLINK :/baike.baidu /view/117922.htm t _blank 策略型 HYPERLINK :/baike

6、.baidu /view/667148.htm t _blank 棋類 HYPERLINK :/baike.baidu /view/2468.htm t _blank 游戲，是起源于中國古代的傳統黑白棋種之一。開展于日本，流行于歐美。五子棋，日文亦有“連五子、五子連、串珠、五目、五目碰、五格、五石、五法、五聯、京棋等多種稱謂，英文那么稱之為“FIR (Five In A Row的縮寫)、Gomoku(日語“五目的羅馬拼音)、Gobang、connect 5、mo-rphion。捷克語piskvorky，韓語omok五子棋相傳起源于四千多年前的堯帝時期，比圍棋的歷史還要悠久，可能早在“堯造圍棋之

7、前，民間就已有五子棋游戲。有關早期五子棋的文史資料與圍棋有相似之處，因為古代五子棋的棋具與圍棋是完全相同的。在上古的神話傳說中有“女媧造人，伏羲做棋一說，?增山海經?中記載：“休輿之山有石焉，名曰帝臺之棋，五色而文狀鶉卵。李善注引三國魏邯鄲淳?藝經?中曰：“棋局，縱橫各十七道，合二百八十九道，白黑棋子，各一百五十枚。可見，五子棋頗有淵源。亦有傳說，五子棋最初流行于少數民族地區，以后漸漸演變成圍棋并在炎黃子孫后代中普及開來。在古代，五子棋棋具雖然與圍棋相類同，但是下法卻是完全不同的。正如?辭海?中所言，五子棋是“棋類游戲，棋具與圍棋相同，兩人對局，輪流下子，先將五子連成一行者為勝。古代五子棋棋盤

8、與圍棋棋盤是通用的，漢魏時為十七路1717棋盤，至南北朝時即已流行十九路1919棋盤，直至1931年，才出現所謂五子棋專用棋盤，如下圖，為十五路1515棋盤，形狀近于正方形，平面上畫橫豎各15條平行線，線路為黑色，構成225個交叉點，鄰近兩個交點的距離縱線約為2.5厘米，橫線約為2.4厘米。棋盤正中一點為“ HYPERLINK :/baike.baidu /view/365548.htm t _blank 天元。棋盤兩端的橫線稱端線，棋盤左右最外邊的兩條縱線稱邊線。從兩條端線和兩條邊線向正中開展而縱橫交叉在第四條線形成的四個點稱為“星。天元和星應在棋盤上用直徑約為0.5厘米的實心小圓點標出。五

9、子棋棋子(qz)亦稱“棋石，分黑、白兩色，形狀為扁圓形，有一面凸起或兩面凸起等形狀，厚度不超過0.8厘米，直徑為2.02.3厘米；一副棋子總數為225枚，其中黑子113枚，白子112枚。按質地的不同，可分為玻璃、陶瓷(toc)、塑料、智石、磁鐵、蛤貝、燒料、水晶、瑪瑙、玉石等棋子。1.1.2 相關(xinggun)術語1.1.2.1 對局相關(xinggun)術語黑方執黑棋一方(y fn)的簡稱。白方執白棋一方的簡稱。勝局有一方獲勝的對局。和局分不出勝負的對局。終局對局結束。復盤對局雙方將本盤對局全過程的再現。1.1.2.2 行棋相關術語陽線即:直線，棋盤上可見的橫縱直線。交叉點陽線 HYPE

10、RLINK :/baike.baidu /view/919948.htm t _blank 垂直 HYPERLINK :/baike.baidu /view/568883.htm t _blank 相交的點，簡稱“點。陰線即:斜線，由交叉點構成的與陽線成45夾角的隱形斜線。落子棋子直接落于棋盤的空白交叉點上。輪走方即“行棋方，有權利落子的黑方或白方。著在對局過程中，行棋方把棋子落在棋盤無子的點上，不管落子的手是否脫離棋子，均被視為一著。回合雙方各走一著，稱為一個回合。開局在對局開始階段形成的布局。連同色棋子在一條陽線或陰線上相鄰成一排。長連五枚以上同色棋子在一條陽線或陰線上相鄰成一排。五連只有

11、五枚同色棋子在一條陽線或陰線上相鄰成一排。成五含有五枚同色棋子(qz)所形成的連，包括五連和長連。四在一條陽線或陰線上連續相鄰(xin ln)的5個點上只有四枚同色棋子的棋型。活四有兩個(lin )點可以成五的四。沖四只有(zhyu)一個點可以成五的四。死四不能成五的四。三在一條陽線或陰線(yn xin)上連續相鄰的5個點上只有三枚同色棋子的棋型。活三再走一著可以形成活四的三。連活三即連的活三(同色棋子在陽線或陰線上相鄰成一排的活三)簡稱“連三。跳活三中間隔有一個空點的活三。簡稱“跳三。眠三再走一著可以形成沖四的三。死三不能成五的三。二在一條陽線或陰線上連續相鄰的5個點上只有兩枚同色棋子的棋型

12、。活二再走一著可以形成活三的二。連活二即連的活二(同色棋子在陽線或陰線上相鄰成一排的活二)，簡稱“連二。跳活二中間隔有一個空點的活二。簡稱“跳二。大跳活二中間隔有兩個空點的活二。簡稱“大跳二。眠二再走一著可以形成眠三的二。死二不能成五的二。先手對方必須應答的著法，相對于先手而言，沖四稱為“絕對先手。三三一子落下同時形成兩個活三。也稱“雙三。四四一子落下同時形成兩個沖四。也稱“雙四。四三一子落下同時形成一個沖四和一個活三。1.2需求分析1.2.1選題與題目要求實習題目：五子棋人機博弈游戲。內容(nirng)要求：實現五子棋游戲的人機博弈。要求：友好的人機圖形化界面、方便(fngbin)的操作方式

13、；自動判斷輸、贏或平；可選擇黑白；可悔棋；可以基于人工智能方面的知識進行設計，如：啟發式搜索、搜索函數的設置、_算法、知識(zh shi)的表示及知識庫，推理機等。1.2.2 系統總體(zngt)分析程序主要涉及的是界面的制作，五子棋的核心算法以及其他(qt)方便使用的功能。程序采用VC 6.0軟件環境實現。運行環境為Windows XP及其他系統。使用對話框的軟件模式。主要提供的功能是游戲的開始，結束，悔棋操作；程序的提示信息的中英文；軟件的配置信息，主要包括游戲的模式，分為人機對戰和雙人對轉；AI智能的上下，分為簡單，中級，高級三種。AI智能使用的算法，主要有極大極小值算法，alpha-b

14、eta算法等。以及程序的托盤功能和托盤菜單等。1.2.3系統目標五子棋游戲系統開發主要包括界面的生成和顯示刷新以及AI智能的生成和運行兩個方面。對于前者要求友好的人機圖形化界面、方便的操作方式；自動判斷輸、贏或平；可選擇黑白；可悔棋。而對于后者那么要求基于人工智能方面的知識進行設計，如：啟發式搜索、搜索函數的設置、_算法、知識的表示及知識庫，推理機等，使AI能夠自動根據當前的棋盤局勢自動下子。系統開發的總體任務是實現各操作和界面的便捷化，標準化，自動化以及AI智能的智能化，快速化，準確化。1.2.4 需求定義作為一個可視化的方便快捷的五子棋游戲軟件，此軟件要求的功能有：整潔，友好的操作界面：采

15、用圓形按鈕美化，采用位圖背景，清晰明了，棋子分黑白紅，其中紅色用于顯示贏棋是顯示贏方的棋路。方便快捷的用戶操作的響應：準確性應鼠標和鍵盤的消息(xio xi)，準確完成下子及棋盤的顯示和更新，游戲某一方贏棋時消息框提示并棋子紅色顯示。詳細準確的提示信息：當前(dngqin)操作不可行時候用消息框給用戶足夠準確的提示信息。方便齊全的功能：包括五子棋的各種應有(yn yu)的悔棋，判輸贏等功能。糾錯功能：用戶操作錯誤能夠進行(jnxng)糾正。用戶設置的保存和讀取功能：ini文件保存游戲配置，語言設置。游戲開始時候從ini文件讀取這些(zhxi)保存點信息。使用語言的選擇功能：用戶可以選擇中文或者

16、英文。AI響應的功能：AI能準確無誤的給出當前局勢的響應。游戲設置功能，用戶可以根據自己喜好選擇是否先手，游戲方式，AI等級選擇，AI算法選擇等，設置之后游戲重新初始化。游戲記錄的顯示和保存：顯示游戲的英雄榜，記錄可以重置。1.2.5系統功能結構圖五子棋游戲系統 選擇游戲的模式，AI等級，AI算法。是否先手。采用圖形界面，用位圖做背景。還可以使用美化工具進行美化。圓形按鈕，中英文菜單。語言設置游戲設置主界面顯示游戲可以托盤化，更加方便快捷。用戶游戲和語言設置等以ini文件的形式保存。游戲開始讀取配置。根據需要選擇中英文托盤功能AI智能拓展性配置信息界面方便拓展成網絡五子棋的形式.AI智能自動下

17、子，自動判斷輸贏。圖 1-1 系統功能結構圖1.2.6 性能(xngnng)要求與系統開發的重點(zhngdin)與難點正確性，可靠性，高效率，軟件完整性，操作易使用性，軟件可維護性，軟件可測試(csh)行，可復用性，易理解性，軟件可移植性。系統出現了一些技術難點大致(dzh)如下：1.游戲界面(jimin)的制作和及時響應用戶要求及游戲行進中截面的更新。游戲的內部狀態和界面顯示的轉換。2.游戲AI智能的實現，對不同棋盤局勢實現不同的響應，平衡AI智能在游戲中進攻和防守的選擇。1.3 可行性分析1.3.1技術可行性 此次信息系統開發是大學專業知識的一次綜合應用與提高。首先就開發硬件根底設施而言

18、，本次課程設計安排在學校314機房進行，該機房計算機配置肯定能滿足系統開發的要求。此外我可以利用課余時間在自己的電腦上進行程序的設計。其次就軟件環境而言，本人選擇微軟的軟件開發環境VC 6.0。此環境人性化的操作界面和便捷的程序編輯方式，使程序的設計方便快捷。再者，就技術力量來說，我可以順利完成此次開發工作。大學的學習，使我已經學習了C，C+等程序設計語言，對圖形界面的設計也比擬熟悉，VC的使用經驗也比擬充足。開發過程中也會出現許多的問題，有我預想之中的，也有一些沒有我預想到，但我有信心克服一切困難。因此從經濟角度考慮，此信息系統開發可行。1.3.2經濟可行性目標系統開發需求比擬低，加上具有成

19、熟的軟硬件環境，所以在軟硬件的支出上十分有限。而且，目標系統并不是十分的復雜，開發的周期較短，人員經濟支出有限。 當系統開發完成實際付諸使用后，在為使用者帶來便利的同時，也為軟件的進一步推廣創造了條件。這帶來的經濟回報將遠超過支出，并且最重要的一點是該軟件的開發可以給我們對系統的開發有個全面的認識。因此從經濟角度考慮，此信息系統開發可行。1.3.3 操作(cozu)可行性軟件(run jin)設計完成后，運行在Windows系統上，可以響應鼠標和鍵盤的操作，均為用戶熟悉的使用環境。軟件界面整潔漂亮，不會引發任何歧義。因此(ync)從操作角度(jiod)考慮，此信息系統開發(kif)可行。1.3

20、.4法律可行性整個系統由于是自行開發，自行使用，所以系統本身不存在法律上的版權爭議。在軟件使用方面，使用的是正版VC 6.0軟件，不存在軟件的使用糾紛。因此從法律角度考慮，此信息系統開發可行。1.3.5社會可行性五子棋簡單易學，容易上手，深受廣闊玩家的喜愛。本軟件功能齊全，界面清晰，操作方便，會深受玩家的歡送。從社會角度考慮，此信息系統開發可行。1.3.6結論根據以上的可行性研究，我認為開發此系統的條件已經具備，可以開始進行開發。第二章 詳細設計與系統實現2.1 游戲(yux)主要功能模塊程序(chngx)的主要功能模塊主功能界面模塊，五子棋游戲類模塊，游戲模式設置模塊，游戲語言設置模塊，鏈表

21、使用功能模塊，游戲記錄模塊，獲得游戲者姓名模塊，關閉對話框方式(fngsh)模塊，圓形按鈕實現模塊。下面一一介紹：2.1.1 主功能界面(jimin)模塊類名(li mn): CmyFiveChessDlg.主要實現功能：實現界面的現實，游戲中棋盤棋子的顯示。其他各功能模塊的其中調度。用戶功能的選擇途徑等。主要變量及注釋如下:CLanguageDlg m_Lan_dlg; /語言設置對話框對象，調用語言設置對話框int m_Lan_Model; /從ini文件讀取保存的語言設置 0-中文 ，1 -英語CAIModelDlg m_Option_dlg; /模式設置對話框，調用配置對話框int m

22、_Ai_Model; /AI等級 ，0-簡單，1-中級，2-高級int m_Game_Model; /0-雙人，1-人機int m_ai_kind; /Ai的種類 0 - 極大極小算法 1-alpha_bata算法bool b_AiFirst; /是否電腦先行 1-是 0- 否CString runpath; /ini文件的路徑，用于讀取和寫ini文件CString m_Info_Url; /五子棋網絡信息 urlCOLORREF m_Message_Color; /顯示發送信息的顏色CFont m_Message_Font; /顯示發送信息的字體CString m_NewMessage; /

23、要發送的信息的內容CString m_AllMessage; /全部要顯示的內容CPaintDC *m_Show_DC; /CFive的顯示的DC，用于顯示棋盤CFive *m_Five; /CFive對象CFive(int aitype,int model,bool AiFirst)CGameRecord m_Record; /游戲玩家記錄對話框，用于顯示記錄對話框int m_jun_record, m_mid_record, m_sen_record; /游戲的各個等級的記錄CNameDlg m_NameDlg; /記錄玩家姓名對話框CCloseSelectDlg m_CloseDlg;

24、/關閉方式選擇對話框CMenu m_English_Menu; /英語(yn y)菜單CMenu m_Chinese_Menu; /中文(zhngwn)菜單enumC,Em_Current_Menu; /標記(bioj)當前菜單項選擇(xunz)擇，枚舉(mi j)主要函數及其功能：CMyFiveChessDlg； /構造函數，獲得ini文件的路徑，構造CFive類對象，初始化游戲設置對話框和語言選擇對話框。OnInitDialog()；/對話框的初始化，菜單的選擇，界面的現實，初始化游戲記錄文件和關閉方式設置對話框，Init_Close_Info() /讀取ini文件，初始化關閉方式設置對話

25、框Init_Record_Info()；/讀取ini文件，初始化游戲記錄對話框的信息Init_Model_Info()； /讀取ini文件，初始化游戲設置對話框的信息Init_Language_Info()；/讀取ini文件,初始化語言對話框的信息OnPaint(); /畫游戲界面OnEndGame()；/結束游戲按鈕OnBack()；/悔棋功能按鈕OnLanguage()；/語言選擇按鈕OnModel()/游戲設置按鈕OnNewGame()/新游戲按鈕Setini(CString filename,CString keyS ,CString AppS ,CString StrS)/寫ini文

26、件Getini(CString filename,CString keyS ,CString AppS, CString def)/讀ini文件OnLButtonDown(UINT nFlags, CPoint point) /響應鼠標左鍵消息，游戲的主要控制OnGameRecord()/游戲記錄菜單OnCreate(LPCREATESTRUCT lpCreateStruct)/響應Create消息，產生托盤WindowProc(UINT message, WPARAM wParam, LPARAM lParam)/主要截獲處理托盤的消息2.1.2五子棋游戲類模塊類名： CFive主要實現功能

27、：游戲的構造，棋盤棋子的現實，游戲下子。游戲內部記錄及AI智能的響應。主要(zhyo)宏定義：#define GRID_NUM 15 /棋盤表格(biog)的大小#define GRID_COUNT 225 /棋盤(qpn)表格的總數目#define BLACK 0 /黑子(hiz)#define WHITE 1 /白子#define NOSTONE 0 xFF /沒有(mi yu)棋子，初始狀態為空/獲勝的五個棋子的走向#define WIN_ROW 1 /橫#define WIN_COL 2 /縱#define WIN_LEFTUP_RIGHTDOWN 3 /左上到右下#define WI

28、N_LEFTDOWN_RIGHTUP 4 /左下到右上主要數據結構:struct WININFO /保存游戲獲勝信息int winner; /-1 沒有獲勝 0 黑 1 白int Start_X; /五連的起始坐標和結束坐標int Start_Y;int End_X;int End_Y;int win_way; /五子連接方向 ，1，2，3，4四個方向;struct tagPoint /點int x, y;Enum /枚舉，棋盤局勢的種類和相應的評分RUSH1 = 1, /沖一LIVE1, /活一RUSH2, /沖二RUSH3 = 6, /沖三LIVE2 = 10, /活二LIVE3 = 10

29、0, /活三RUSH4, /沖四LIVE3_3 = 1000, /雙活三LIVE4, /活四LIVE3_4, /活三四(sn s)LIVE4_4, /雙活四FIVE = 100000 /五子;主要的變量和相應(xingyng)的注釋：bool m_isGameStart; /游戲是否(sh fu)開始，bool m_isGameOver; /游戲是否(sh fu)結束bool m_isWin; / /是否(sh fu)某一方勝利int m_Cur_Turn; /當前輪到誰下子 BLACK-黑子 WHITE-白子bool m_isAiFirst; /是否電腦先行 1-是 0-否int m_AIt

30、ype; /ai等級 ，0-簡單，1-中級，2-高級int m_Model; /對戰模式 0-雙人對戰 ，1 -人機對戰int m_Kind; /Ai算法種類int m_ChessBoardGRID_NUMGRID_NUM; /棋盤數組，記錄棋盤下子int m_Last_x,m_Last_y; /上次行棋的位置x和yint m_Chess_Down_Num; /當前已經下的棋子數目WININFO m_Win; /獲勝信息SeqList m_Record; /下棋記錄的順序表信息CSeqList list; /主要是鏈表的操作函數主要函數及其功能:CFive(int aitype,int mod

31、el,bool AiFirst,int AiKind); /構造函數，界面類調用void Show(CPaintDC * dc); /顯示棋盤(qpn)棋子 顯示黑白棋子；顯示最近(zujn)行棋位置；if(m_isWin) 顯示(xinsh)贏棋的信息； 顯示(xinsh)棋盤;void NewGame(); /新游戲(yux)清空棋盤；如果機器現行那么在天元位置下棋void Clear(); /全部清空，相當于初始化void CheckGameOver(int X,int Y,int Color); /檢查是否游戲結束,m_isGameOver表示結果分別從0度，90度，135度，45度方

32、向檢查是否某一方勝利；檢查某一個方向就是以int X,int Y為中心的該方向周圍相同顏色棋子的數目；void NextPos(int &x,int &y); /根據當前的人的下子獲得機器的下一步根據當前算法種類和AI智能選擇函數獲得最正確位置存放在xy里。void Play(int X,int Y); /x,y處下子void AutoPlay(int &x,int &y); /機器自動下子bool IsValidPos(int X,int Y); /判斷一個位置是否為有效位置bool CanBack(); /能否悔棋void Back(); /悔棋void SaveWinInfo(int X

33、1,int Y1,int X2,int Y2,int Color,int wonway); /保存獲勝信息/ alpha_beta算法實現int alpha_beta(int level, int turn, int alpha, int beta, int x, int y); /alpha_beta算法(sun f)int compute(int turn, int level, int &x,int &y); /計算(j sun)獲得下一個最正確(zhngqu)位置(wi zhi)int GetPointWeight(int turn, int x, int y); /棋盤(qpn)位置

34、評分/極大極小值算法算法實現void ComputerPlay(int *m,int *n); /計算獲得下一個最正確位置給棋盤的每個空白點評分；選擇分數最大的或最小的位置下棋；int NumToScoreMax(int num); /極大點分數int NumToScoreMin(int num); /極小點分數int GiveScore(bool max,int chess,int row,int col); / int row,int col位置點的評分分別從0度，90度，135度，45度方向給該點評分；將所有分數累加得到該點的評分；2.1.2.1 博弈算法簡介機器博弈是人工智能一個傳統的

35、研究領域。機器博弈的研究廣泛而深入。早在上世紀五十年代，就有人設想利用機器智能來實現機器與人的對弈。國內外許多知名學者和知名科研機構都曾經涉足這方面的研究，歷經半個多世紀，到目前為止已經取得了許多驚人的成就。1997年IBM的“深藍戰勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。除此之外，加拿大阿爾伯塔大學的奧賽羅程序Logistello和西洋跳棋程序Chinook也相繼成為確定的、二人、零和、完備信息游戲世界冠軍 ，而西洋雙陸棋這樣的存在非確定因素的棋類也有了美國卡內基梅隆大學的西洋雙陸琪程序BKG這樣的世界冠軍。對圍棋、中國象棋、橋牌、撲克等許多種其它種類游戲博弈的研究也正在進行中。機器博弈

36、的核心技術是博弈搜索算法，這也是機器博弈研究的熱點。機器博弈的核心思想并不復雜，實際上就是對博弈樹節點的估值過程和對博弈樹搜索過程的結合。在博弈的任何一個中間階段，站在博弈雙方其中一方的立場上，可以設想一個博弈樹。這個博弈樹的根節點是當前時刻的棋局，它的兒子節點是假設再行棋一步以后的各種棋局，孫子節點是從兒子節點的棋局再行棋一步的各種棋局，以此類推，構造整棵博弈樹，直到可以分出勝負的棋局。整棵的博弈樹非常龐大，且不同的棋類有所不同，分支因子大的如圍棋的博弈樹顯然要比分支因子小的如國際象棋的博弈樹要大得多。博弈程序的任務就是對博弈樹進行搜索找出當前最優的一步行棋。對博弈樹進行極大極小(j xio

37、)搜索，可以到達(dod)這一目的。極大極小搜索(su su)，是因為博弈雙方所要到達(dod)的目的相反，一方要尋找的利益恰是一方失去的利益，所以博弈的一方總是希望下一走是兒子(r zi)節點中取值最大者，而另一方恰恰相反。這便形成了極大極小過程。博弈搜索的根本思想已經提出半個多世紀，目前廣泛研究的是確定的、二人、零和、完備信息的博弈搜索。也就是說，沒有隨機因素的博弈在兩個人之間進行，在任何一個時刻，一方失去的利益即為另一方得到的利益，不會出現“雙贏的局面，而且在任何時刻，博弈的雙方都明確的知道每一個棋子是否存在和存在于什么位置。二人、零和、完備信息的博弈搜索理論已經非常系統。極大極小算法是

38、所有搜索算法的根底。在這個根底上，目前在這一領域的算法主要有兩類，一類是作為主流的深度優先的alpha-beta搜索及其系列增強算法，另一類是最正確優先的系列算法。2.1.2.2 極大極小值算法極大極小值算法的根本思想是始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分數，不利于這一方有利于另一方的給予一個較低的價值分數，雙方優劣不明顯的局面給予一個中間價值分數。在這一方行棋的時候，選擇價值極大的兒子節點走步，另一方下棋那么選擇價值極小的兒子節點走步。這就是一個極大極小過程。將博弈的雙方分別命名為MAX和MIN。而搜索的任務是為MAX找出最正確的移動。假設MAX先移動(

39、此時暫時不考慮五子棋的禁手規那么)，然后2個博弈者輪流移動。因此，深度為偶數的節點，對應于MAX下一步移動的位置，稱為MAX節點；深度為奇數的節點對應于MIN下一步移動的位置，稱為MIN節點(博弈樹的頂節點深度為0)。k層包括深度為2k和2k+1的節點。通常用層數來表示博弈樹的搜索深度。他可以表示出向前預測的MAX和MIN交替運動的回合數。對于復雜的博弈，博弈者必須認識到由于博弈樹的復雜程度所以搜索到終點是不可能的(除了在博弈快結束時)。所以，常采用在有限范圍搜索方法，確定下一個要考察的節點，在確定節點時只要能充分利用與問題有關的信息，估計出節點的重要性，就能在搜索時選擇重要性較高的節點，以利

40、于博弈者以較快的速度求出最正確的下子位置。假設輪到MAX從搜索樹的葉節點中選取，他肯定選擇擁有最大值的節點。因此，MIN葉節點的一個MAX節點雙親的倒推值就等于葉節點的分數評估值中的最大值。另一方面，MIN從葉節點中選取時，必然選取最小的節點(即最負的值)。既然如此，MAX葉節點的MIN雙親節點被分配一個倒推值，它等于葉節點分數評估值的最小值。在所有葉節點的父節點被賦予倒推值后，開始倒推另一層，假定MAX將選擇有最大倒推值的MIN的后繼節點，而MIN會選擇有最小倒推值的MAX后繼節點。繼續逐層對節點評估，直到最后開始節點的后繼者被賦予倒推值。MAX將選擇有最大倒推值的節點作為他的首步。整個(z

41、hngg)過程的有效性基于這樣的假設。設想當前棋局S為輪到計算機方下棋(xi q)(用方框表示)，任選一空點作為計算機方的下棋位置(可有假設(jish)干種選擇)，接著考慮在此情況下游戲者一方下棋的棋局(q j)(用圓圈表示)；從某一個圓圈棋局出發，任選一空點作為游戲者一方的下子處(又有假設(jish)干種選擇)。再次形成計算機方下棋的方框棋局；依此類推，這樣可形成一棵以S為根結點的博弈樹，該樹以圓圈棋局為第2層子結點，以方框棋局為第3層子結點等等。如果繼續向前搜索，可形成多層子結點，現在以向前搜索3層子結點為例來說明極大極小值的過程。對第3層子結點的某一棋局n，求出其估計值h(n)，假設有一

42、博弈樹已形成，如下列圖所示，h(n)的值由各結點旁的數值給出。根節點S30-40-30最正確第二層節點第三層節點3040603060-4050-308050 圖2-1 極大(j d)極小值算法示意圖根據極小(j xio)極大化分析法，先計算第3層子結點h(n)值，然后第2層子結點的估計值取他的各個后繼子結點(ji din)的極小值，根結點的估計值取他的各子結點的極大值。這個取得最大估計值的子結點即為從S出發的計算機方的最正確(zhngqu)下子方案(fng n)。2.1.2.3 alpha-beta算法在極大極小搜索的過程中，存在著一定程度的數據冗余，如圖 2-2所示左半部的一棵極大極小樹的片

43、斷，節點下面為該節點的值，設A 為極大值節點，節點B的值為18，節點D 的值為16，由此可以判斷節點C的值將小于等于16(取極小值)；而節點A的值為節點Max(B，C)，是18，也就是說不再需要估計節點C的其他子節點如E、F的值就可以得出父節點A 的值了。剔除這些冗余數據，是減小搜索空間的必然做法，所采用的方法就是1975年Monroe Newborn提出的alpha-beta剪枝，如圖2-2 所示將節點D的后繼兄弟節點剪去稱為Alpha剪枝(剪枝)。ABCDEFA取最大值1816Alpha剪枝(剪枝)圖 2-2 Alpha剪枝(jin zh)示意圖同樣(tngyng)道理在圖 2-3右半部一

44、棵極大極小樹的片段中，設A為極小值節點，節點B的估值為8，節點D的估值為l8，由此可以判斷節點C的值將大于等于18(取極大值)；而節點A 的值為Min(B，c)，是8。也就是說不再需要求節點C的其他(qt)子節點如E、F值就可以得出父節點A 的值了。這樣將節點D的后繼兄弟節點剪去稱為Beta剪枝(剪枝(jin zh)。ABCDEFA取最小值818Beta剪枝(剪枝) 圖 2-3 Beta剪枝(jin zh)示意圖把alpha-beta剪枝應用到極大極小搜索中，就形成了alpha-beta搜索。alpha-beta搜索由于過程簡單、容易理解、且占用空間小等優良特點被廣泛應用，成為現在主流的搜索算

45、法的根底。但是它也有缺點，即它對于節點的排列非常敏感。如果節點的排列順序不是從最差到最好，就有可能使剪枝一直無法進行，從而實際上搜索了整棵的博弈樹。大多數alpha-beta剪枝算法都采用深度優先的搜索策略(cl)，是因為深度優先搜索較之寬度優先搜索節省存儲空間，只需保存根節點到當前搜索節點的路徑上的節點信息即可。針對(zhndu)alpha-beta剪枝算法的改良(giling)算法(sun f)很多，比方(b fng)，渴望搜索Aspiration Search，極小窗口搜索Minimal Window Search，置換表Transposition Table，遍歷深化Iterative

46、 Deepening，歷史啟發搜索History Heuristic，殺手啟發搜索(Killer Heuristic)， MTD(f)算法等。2.1.3 游戲模式設置模塊類名：CAIModelDlg主要實現功能：游戲者對當前游戲的設置，設置游戲的對戰模式，包括雙人對戰和人機對戰。設置游戲AI智能等級，設置AI智能的算法，設置游戲的先手。主要變量及其相應的注釋：Int m_Cur_Ai_model; /機器等級，0-簡單，1-中級，2-高級int m_Game_Model; /游戲模式 0-雙人對戰 1-人機對戰int m_Ai_Kind; /Ai算法的種類 0-極大極小 1-alpha_bet

47、a算法BOOL m_beAiFirst; /1-機器先行 ，0-人先行主要函數及其功能：int Get_Ai_Model(); /獲得當前的AI等級void Set_Ai_Model(int model); /設置AI等級int Get_Game_Model(); /獲得當前的游戲模式void Set_Game_model(int model); /設置當前的游戲模式int Get_Ai_Kind(); /獲得當前的AI類型void Set_Ai_Kind(int kind); /設置當前的AI類型2.1.4 游戲語言設置模塊類名：CLanguageDlg主要實現功能：游戲者對當前游戲的語言設

48、置。主要變量(binling)及其相應的注釋：int m_Current_Language_Mode; /當前(dngqin)語言選擇，0表示漢語，1表示英語CComboBoxm_Lan_Com; /用于選擇(xunz)語言的下拉列表框主要函數(hnsh)及其功能：void Set_Lan_Model(int model); /設置(shzh)當前語言int Get_Lan_Model(); /獲得當前的語言類型2.1.5鏈表使用功能模塊主要實現功能：記錄當前游戲的下子以到達悔棋的功能。因為每次悔棋的時候只涉及到最后一個或兩個棋子，所以選擇順序表，相當于只在表尾操作。每個游戲中用一個順序表來記

49、錄下子的情況，那么悔棋的實現就是順序表的操作。#define MAXSIZE 225 /最大記錄個數struct Node /下棋記錄的節點信息int Pos_X; /位置int Pos_Y;int Color; /顏色， 0-黑色 1-白色;struct SeqList /行棋記錄Node listMAXSIZE;int size; /當前記錄個數;類名：CSeqList主要函數及其功能：Void ListInitiate(SeqList *L); /鏈表初始化int ListLength(SeqList *L); /獲得鏈表的長度int ListInsert(SeqList *L,/*in

50、t pos,*/Node element); /鏈表的插入操作int ListDelete(SeqList *L/*,int pos*/,Node *element); /鏈表的刪除操作int ListGet(SeqList L,/*int pos,*/Node *element); /獲得鏈表某一個(y )元素2.1.6 游戲(yux)記錄模塊類名(li mn)：CGameRecord主要實現功能：游戲的玩家記錄(jl)，以下子的個數最少為最優。主要變量及響應(xingyng)注釋：CString m_path; /路徑名CStringm_Jun_Name; /各個游戲等級的游戲記錄CStr

51、ingm_Mid_Name;CStringm_Sen_Name;CStringm_Junior;CStringm_Mid;CStringm_Senior;主要函數及其功能：void SetRecord(CString name,int range , int chessnum); /設置游戲記錄void OnRecordReset(); /游戲記錄重置2.1.7獲得游戲者姓名模塊類名：CNameDlg主要實現功能：游戲玩家破記錄時候記錄玩家的名字。主要變量及響應注釋：CStringm_HeroName; /記錄玩家的姓名2.1.8 關閉對話框方式及托盤顯示模塊類名：CCloseSelectDl

52、g主要功能：實現用戶關閉程序時候根據需要選擇是直接關閉還是最小化到托盤，并設置下次是否繼續提示。托盤功能主要實現游戲的托盤化及托盤的右鍵彈出菜單的消息響應。int m_CloseSelected; /選擇的方式 0-關閉 1-托盤 CString m_path; /路徑名BOOLm_NoTip;/是否(sh fu)繼續提示 1-不再提示 0-提示主要(zhyo)函數：:Shell_NotifyIcon(NIM_ADD,&m_tnid); /用于實現程序(chngx)的托盤功能2.1.9圓形按鈕模塊(m kui)類名(li mn)：CRoundButton主要功能：將界面的按鈕畫成圓形以到達美化

53、的效果。主要變量及函數：CRgn m_rgn; /畫的區域CPoint m_ptCentre; /圓的圓心點int m_nRadius; /圓的半徑virtual void DrawItem(LPDRAWITEMSTRUCT lpDrawItemStruct); /重畫virtual void PreSubclassWindow(); /重新定位此類使用時先給要重繪的按鈕關聯一個變量，再將CButton類型改成CRoundButton就可以。2.1.10 配置文件的讀取和保存主要的功能：實現游戲配置的保存以及游戲配置文件的讀取來初始化游戲。主要函數：bool WritePrivateProfi

54、leString(LPCTSTR lpAppName,LPCTSTR lpKeyName,LPCTSTR lpString,LPCTSTR lpFileName); /ini文件的寫操作DWORD GetPrivateProfileString(LPCTSTR lpAppName,LPCTSTR lpKeyName,LPCTSTR lpDefaut,LPSTR lpReturnedString,DWORD nSize,LPCTSTR lpFileName); /讀ini文件2.2模塊功能調用關系及其示意圖程序運行的功能模塊調用主要過程大致如下： 程序運行，主界面模塊生成對象，在構造函數中構造首

55、先從配置文件中讀取配置信息，獲取用戶設置的游戲模式，AI智能等級(dngj)和AI博弈函數，是否先手，語言種類等信息，利用這些信息構造CFive類對象，在對話框的初始化函數(hnsh)中根據配置加載菜單，初始化游戲記錄信息(xnx)和關閉設置信息，畫游戲的棋盤，初始化按鈕使它是否可用，生成并顯示程序托盤，加載托盤菜單。游戲(yux)進入，此時可以響應玩家對游戲的設置，語言的設置，用戶選擇開始游戲后，如果(rgu)是設置AI先行，那么電腦現在棋盤天元位置下棋，然后響應用戶的鼠標左鍵消息下棋，如果玩家先行的話響應鼠標左鍵消息等待玩家輸入，然后AI智能根據當前棋盤的局勢作出反響獲得最正確位置，并在該

56、處下子。然后繼續響應玩家的輸入。游戲中如果玩家更改游戲配置信息，那么CFive類先析構，再根據新的配置信息重新構造，并且將新的配置信息寫入配置文件。用戶可以根據需要進行悔棋和終止游戲。可以更改游戲的語言，并將新的語言配置信息寫入ini文件，可以根據游戲記錄的配置信息查看游戲記錄的信息和重置游戲信息，重置時候重寫記錄配置信息。當用戶關閉軟件時候，獲取當前的設置是否繼續提示，如果提示從配置信息中獲取當前是選擇關閉還是選擇托盤化，并將玩家的設置寫入配置文件。用戶選擇about對話框可以查看自己當前機器的某些硬件信息，可以聯網查看五子棋游戲的介紹。其功能調度概要示意圖如下：是否開始游戲初始化主界面對話

57、框，初始化游戲記錄信息和關閉設置信息。畫界面。初始按鈕可以性，生成托盤和托盤菜單加載。根據配置信息構造CFive類對象從ini文件讀取語言的配置信息從ini文件初始化游戲配置游戲軟件生成 重新設置游戲信息，語言信息，重置游戲記錄信息。重置游戲類，寫ini文件記錄配置信息。再初始化盤面是否結束是根據配置玩家先或電腦先，然后響應鼠標左鍵消息，AI智能根據當前局勢獲得下一最正確位置。顯示棋盤，更新結束游戲和悔棋按鈕。 否 是否破記錄。是玩家刷新了記錄，輸入姓名。是 圖 2-4 功能(gngnng)調度示意圖系統(xtng)測試3.1 系統(xtng)測試截圖至此，軟件的設計大致完成(wn chng)，下面是一些軟件功能實現的截圖，以測試軟件的性能