人工智能井子棋報告

1、 目 錄第一章 系統(tǒng)需求分析與總體設計1.1 概述(3)1.1.1 五子棋背景介紹(3)1.1.2相關術語(4)1.1.2.1對局相關術語(4)1.1.2.2行棋相關術語(4)1.2 需求分析(6)1.2.1 選題與題目要求 (6)1.2.2 總體分析 (6)1.2.3 系統(tǒng)目標 (6)1.2.4 需求定義 (6)1.2.5 系統(tǒng)功能結構圖 (7)1.2.6 性能要求與系統(tǒng)開發(fā)的重點與難點 (7)1.3可行性分析(8)1.3.1 技術可行性(8)1.3.2 經濟可行性(8)1.3.3 操作可行性(8)1.3.4 法律可行性(8)1.3.5 社會可行性(9)1.3.6 結論 (9)第二章 詳細設

2、計與系統(tǒng)實現(xiàn)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.8 關閉對話框方式與托盤功能模塊 (21)2.1.9 圓形按鈕模塊 (21)2.1.10 配置文件的讀取和保存(22)2.2 模塊功能調用關系與其示意圖 (22)第

3、三章 系統(tǒng)測試3.1程序運行結果截圖(24)第四章 系統(tǒng)總結4.1 系統(tǒng)存在的問題(27)4.2 將要做的工作(27)4.3 總結和體會(27)4.4 參考文獻(28)第一章 系統(tǒng)需求分析與總體設計1.1 概述五子棋是一種大眾喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性和消遣性，它不僅能增強思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。五子棋既有現(xiàn)代休閑的明顯特征"短、平、快"，又有古典哲學的高深學問"陰陽易理"；它既有簡單易學的特性，為人民群眾所喜聞樂見，又有深奧的技巧和高水平的國際性比賽；它的棋文化源淵流長，具有的神秘和西方的直觀；既有&qu

4、ot;場"的概念，亦有"點"的連接。它是中西文化的交流點，是古今哲理的結晶。近來隨著計算機的快速發(fā)展，各種棋類游戲被紛紛請進了電腦，使得那些喜愛下棋，又常?？嘤跊]有對手的棋迷們能隨時過足棋癮。而且這類軟件個個水平頗高，大有與人腦分庭抗禮之勢。其中戰(zhàn)勝過國際象棋世界冠軍-卡斯帕羅夫的“深藍”便是最具說服力的代表；其它像圍棋的“手淡”、象棋的“將族”等也以其優(yōu)秀的人工智能深受棋迷喜愛；而我也做了一個“無比”簡單的五子棋程序。總的來說（我們假定您熟悉五子棋的基本規(guī)則），要讓電腦知道人下子之后該在哪一點下子，就要根據(jù)盤面的形勢，為每一可能落子的點計算其重要程度，也就是當這

5、子落下后會形成什么棋型（如：“沖四”、“活三” 等），然后總覽全盤選出最重要的一點，這便是最基本的算法的思想。1.1.1 五子棋背景介紹五子棋是一種兩人對弈的純策略型棋類游戲，是起源于中國古代的傳統(tǒng)黑白棋種之一。發(fā)展于日本，流行于歐美。五子棋，日文亦有“連五子、五子連、串珠、五目、五目碰、五格、五石、五法、五聯(lián)、京棋”等多種稱謂，英文則稱之為“FIR (Five In ARow的縮寫)、Gomoku(日語“五目”的羅馬拼音)、Gobang、connect 5、mo-rphion”。捷克語piskvorky，語omok五子棋相傳起源于四千多年前的堯帝時期，比圍棋的歷史還要悠久，可能早在“堯造圍棋

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

7、盤是通用的，漢時為十七路（17×17）棋盤，至南北朝時即已流行十九路（19×19）棋盤，直至1931年，才出現(xiàn)所謂五子棋專用棋盤，如圖所示，為十五路（15×15）棋盤，形狀近于正方形，平面上畫橫豎各15條平行線，線路為黑色，構成225個交叉點，鄰近兩個交點的距離縱線約為2.5厘米，橫線約為2.4厘米。棋盤正中一點為“天元”。棋盤兩端的橫線稱端線，棋盤左右最外邊的兩條縱線稱邊線。從兩條端線和兩條邊線向正中發(fā)展而縱橫交叉在第四條線形成的四個點稱為“星”。天元和星應在棋盤上用直徑約為0.5厘米的實心小圓點標出。五子棋棋子亦稱“棋石”，分黑、白兩色，形狀為扁圓形，有一面凸

8、起或兩面凸起等形狀，厚度不超過0.8厘米，直徑為2.02.3厘米；一副棋子總數(shù)為225枚，其中黑子113枚，白子112枚。按質地的不同，可分為玻璃、瓷、塑料、智石、磁鐵、蛤貝、燒料、水晶、瑪瑙、玉石等棋子。1.1.2 相關術語1.1.2.1 對局相關術語黑方執(zhí)黑棋一方的簡稱。白方執(zhí)白棋一方的簡稱。勝局有一方獲勝的對局。和局分不出勝負的對局。終局對局結束。復盤對局雙方將本盤對局全過程的再現(xiàn)。1.1.2.2行棋相關術語陽線即:直線，棋盤上可見的橫縱直線。交叉點陽線垂直相交的點，簡稱“點”。陰線即:斜線，由交叉點構成的與陽線成45°夾角的隱形斜線。落子棋子直接落于棋盤的空白交叉點上。輪走方

9、即“行棋方”，有權利落子的黑方或白方。著在對局過程中，行棋方把棋子落在棋盤無子的點上，不論落子的手是否脫離棋子，均被視為一著?；睾想p方各走一著，稱為一個回合。開局在對局開始階段形成的布局。連同色棋子在一條陽線或陰線上相鄰成一排。長連五枚以上同色棋子在一條陽線或陰線上相鄰成一排。五連只有五枚同色棋子在一條陽線或陰線上相鄰成一排。成五含有五枚同色棋子所形成的連，包括五連和長連。四在一條陽線或陰線上連續(xù)相鄰的5個點上只有四枚同色棋子的棋型。活四有兩個點可以成五的四。沖四只有一個點可以成五的四。死四不能成五的四。三在一條陽線或陰線上連續(xù)相鄰的5個點上只有三枚同色棋子的棋型。活三再走一著可以形成活四的三

10、。連活三即連的活三(同色棋子在陽線或陰線上相鄰成一排的活三)簡稱“連三”。跳活三中間隔有一個空點的活三。簡稱“跳三”。眠三再走一著可以形成沖四的三。死三不能成五的三。二在一條陽線或陰線上連續(xù)相鄰的5個點上只有兩枚同色棋子的棋型。活二再走一著可以形成活三的二。連活二即連的活二(同色棋子在陽線或陰線上相鄰成一排的活二)，簡稱“連二”。跳活二中間隔有一個空點的活二。簡稱“跳二”。大跳活二中間隔有兩個空點的活二。簡稱“大跳二”。眠二再走一著可以形成眠三的二。死二不能成五的二。先手對方必須應答的著法，相對于先手而言，沖四稱為“絕對先手”。三三一子落下同時形成兩個活三。也稱“雙三”。四四一子落下同時形成兩

11、個沖四。也稱“雙四”。四三一子落下同時形成一個沖四和一個活三。1.2需求分析1.2.1選題與題目要求實習題目：五子棋人機博弈游戲。容要求：實現(xiàn)五子棋游戲的人機博弈。要求：友好的人機圖形化界面、方便的操作方式；自動判斷輸、贏或平；可選擇黑白；可悔棋；可以基于人工智能方面的知識進行設計，如：啟發(fā)式搜索、搜索函數(shù)的設置、_算法、知識的表示與知識庫，推理機等。1.2.2 系統(tǒng)總體分析程序主要涉與的是界面的制作，五子棋的核心算法以與其他方便使用的功能。程序采用VC 6.0軟件環(huán)境實現(xiàn)。運行環(huán)境為Windows XP與其他系統(tǒng)。使用對話框的軟件模式。主要提供的功能是游戲的開始，結束，悔棋操作；程序的提示信

12、息的中英文；軟件的配置信息，主要包括游戲的模式，分為人機對戰(zhàn)和雙人對轉；AI智能的高低，分為簡單，中級，高級三種。AI智能使用的算法，主要有極大極小值算法，alpha-beta算法等。以與程序的托盤功能和托盤菜單等。1.2.3系統(tǒng)目標五子棋游戲系統(tǒng)開發(fā)主要包括界面的生成和顯示刷新以與AI智能的生成和運行兩個方面。對于前者要求友好的人機圖形化界面、方便的操作方式；自動判斷輸、贏或平；可選擇黑白；可悔棋。而對于后者則要求基于人工智能方面的知識進行設計，如：啟發(fā)式搜索、搜索函數(shù)的設置、_算法、知識的表示與知識庫，推理機等，使AI能夠自動根據(jù)當前的棋盤局勢自動下子。系統(tǒng)開發(fā)的總體任務是實現(xiàn)各操作和界面

13、的便捷化，規(guī)化，自動化以與AI智能的智能化，快速化，準確化。1.2.4需求定義作為一個可視化的方便快捷的五子棋游戲軟件，此軟件要求的功能有：1. 整潔，友好的操作界面：采用圓形按鈕美化，采用位圖背景，清晰明了，棋子分黑白紅，其中紅色用于顯示贏棋是顯示贏方的棋路。2. 方便快捷的用戶操作的響應：準確性應鼠標和鍵盤的消息，準確完成下子與棋盤的顯示和更新，游戲某一方贏棋時消息框提示并棋子紅色顯示。3. 詳細準確的提示信息：當前操作不可行時候用消息框給用戶足夠準確的提示信息。4. 方便齊全的功能：包括五子棋的各種應有的悔棋，判輸贏等功能。5. 糾錯功能：用戶操作錯誤能夠進行糾正。6. 用戶設置的保存和

14、讀取功能：ini文件保存游戲配置，語言設置。游戲開始時候從ini文件讀取這些保存點信息。7. 使用語言的選擇功能：用戶可以選擇中文或者英文。8. AI響應的功能：AI能準確無誤的給出當前局勢的響應。9. 游戲設置功能，用戶可以根據(jù)自己喜好選擇是否先手，游戲方式，AI等級選擇，AI算法選擇等，設置之后游戲重新初始化。10. 游戲記錄的顯示和保存：顯示游戲的英雄榜，記錄可以重置。1.2.5系統(tǒng)功能結構圖五子棋游戲系統(tǒng)選擇游戲的模式，AI等級，AI算法。是否先手。采用圖形界面，用位圖做背景。還可以使用美化工具進行美化。圓形按鈕，中英文菜單。語言設置游戲設置主界面顯示游戲可以托盤化，更加方便快捷。用戶

15、游戲和語言設置等以ini文件的形式保存。游戲開始讀取配置。根據(jù)需要選擇中英文托盤功能AI智能拓展性配置信息界面方便拓展成網(wǎng)絡五子棋的形式.AI智能自動下子，自動判斷輸贏。圖 1-1 系統(tǒng)功能結構圖1.2.6 性能要求與系統(tǒng)開發(fā)的重點與難點正確性，可靠性，高效率，軟件完整性，操作易使用性，軟件可維護性，軟件可測試行，可復用性，易理解性，軟件可移植性。系統(tǒng)出現(xiàn)了一些技術難點大致如下：1.游戲界面的制作和與時響應用戶要求與游戲行進中截面的更新。游戲的部狀態(tài)和界面顯示的轉換。2.游戲AI智能的實現(xiàn)，對不同棋盤局勢實現(xiàn)不同的響應，平衡AI智能在游戲中進攻和防守的選擇。1.3 可行性分析1.3.1技術可行

16、性此次信息系統(tǒng)開發(fā)是大學專業(yè)知識的一次綜合應用與提高。首先就開發(fā)硬件基礎設施而言，本次課程設計安排在學校314機房進行，該機房計算機配置肯定能滿足系統(tǒng)開發(fā)的要求。此外我可以利用課余時間在自己的電腦上進行程序的設計。其次就軟件環(huán)境而言，本人選擇微軟的軟件開發(fā)環(huán)境VC 6.0。此環(huán)境人性化的操作界面和便捷的程序編輯方式，使程序的設計方便快捷。再者，就技術力量來說，我可以順利完成此次開發(fā)工作。大學的學習，使我已經學習了C，C+等程序設計語言，對圖形界面的設計也比較熟悉，VC的使用經驗也比較充足。開發(fā)過程中也會出現(xiàn)許多的問題，有我預想之中的，也有一些沒有我預想到，但我有信心克服一切困難。因此從經濟角度

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

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

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

20、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; /五子棋網(wǎng)絡信息 urlCOLORREF m_Message_Color; /顯示發(fā)送信息的顏色CFont m_Message_Font; /顯示發(fā)送信息的字體CString m_NewMessage; /要發(fā)送的信息的容CString m_AllMessage

21、; /全部要顯示的容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; /關閉方式選擇對話框CMenu m_English_Menu; /英

22、語菜單CMenu m_Chinese_Menu; /中文菜單enumC,Em_Current_Menu; /標記當前菜單選擇，枚舉主要函數(shù)與其功能：CMyFiveChessDlg（）； /構造函數(shù)，獲得ini文件的路徑，構造CFive類對象，初始化游戲設置對話框和語言選擇對話框。OnInitDialog()；/對話框的初始化，菜單的選擇，界面的現(xiàn)實，初始化游戲記錄文件和關閉方式設置對話框，Init_Close_Info() /讀取ini文件，初始化關閉方式設置對話框Init_Record_Info()；/讀取ini文件，初始化游戲記錄對話框的信息Init_Model_Info()； /讀取in

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

24、讀ini文件OnLButtonDown(UINT nFlags, CPoint point) /響應鼠標左鍵消息，游戲的主要控制OnGameRecord()/游戲記錄菜單OnCreate(LPCREATESTRUCT lpCreateStruct)/響應Create消息，產生托盤WindowProc(UINT message, WPARAM wParam, LPARAM lParam)/主要截獲處理托盤的消息2.1.2五子棋游戲類模塊類名： CFive主要實現(xiàn)功能：游戲的構造，棋盤棋子的現(xiàn)實，游戲下子。游戲部記錄與AI智能的響應。主要宏定義：#define GRID_NUM 15 /棋盤表格的

25、大小#define GRID_COUNT 225 /棋盤表格的總數(shù)目#define BLACK 0 /黑子#define WHITE 1 /白子#define NOSTONE 0xFF /沒有棋子，初始狀態(tài)為空/獲勝的五個棋子的走向#define WIN_ROW 1 /橫#define WIN_COL 2 /縱#define WIN_LEFTUP_RIGHTDOWN 3 /左上到右下#define WIN_LEFTDOWN_RIGHTUP 4 /左下到右上主要數(shù)據(jù)結構:struct WININFO /保存游戲獲勝信息int winner; /-1 沒有獲勝 0 黑 1 白int Start_X

26、; /五連的起始坐標和結束坐標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 = 100, /活三RUSH4, /沖四LIVE3_3 = 1000, /雙活三LIVE4, /活四LIVE3_4, /活三四LIVE4_4, /雙活四FIVE = 100000 /五子;主要的變量和相

27、應的注釋：bool m_isGameStart; /游戲是否開始，bool m_isGameOver; /游戲是否結束bool m_isWin; / /是否某一方勝利int m_Cur_Turn; /當前輪到誰下子 BLACK-黑子 WHITE-白子bool m_isAiFirst; /是否電腦先行 1-是 0-否int m_AItype; /ai等級 ，0-簡單，1-中級，2-高級int m_Model; /對戰(zhàn)模式 0-雙人對戰(zhàn) ，1 -人機對戰(zhàn)int m_Kind; /Ai算法種類int m_ChessBoardGRID_NUMGRID_NUM; /棋盤數(shù)組，記錄棋盤下子int m_La

28、st_x,m_Last_y; /上次行棋的位置x和yint m_Chess_Down_Num; /當前已經下的棋子數(shù)目WININFO m_Win; /獲勝信息SeqList m_Record; /下棋記錄的順序表信息CSeqList list; /主要是鏈表的操作函數(shù)主要函數(shù)與其功能:CFive(int aitype,int model,bool AiFirst,int AiKind); /構造函數(shù)，界面類調用void Show(CPaintDC * dc); /顯示棋盤棋子 顯示黑白棋子；顯示最近行棋位置；if(m_isWin) 顯示贏棋的信息； 顯示棋盤;void NewGame(); /

29、新游戲清空棋盤；如果機器現(xiàn)行則在天元位置下棋void Clear(); /全部清空，相當于初始化void CheckGameOver(int X,int Y,int Color); /檢查是否游戲結束,m_isGameOver表示結果分別從0度，90度，135度，45度方向檢查是否某一方勝利；檢查某一個方向就是以int X,int Y為中心的該方向周圍一樣顏色棋子的數(shù)目；void NextPos(int &x,int &y); /根據(jù)當前的人的下子獲得機器的下一步根據(jù)當前算法種類和AI智能選擇函數(shù)獲得最佳位置存放在xy里。void Play(int X,int Y); /x,y

30、處下子void AutoPlay(int &x,int &y); /機器自動下子bool IsValidPos(int X,int Y); /判斷一個位置是否為有效位置bool CanBack(); /能否悔棋void Back(); /悔棋void SaveWinInfo(int X1,int Y1,int X2,int Y2,int Color,int wonway); /保存獲勝信息/ alpha_beta算法實現(xiàn)int alpha_beta(int level, int turn, int alpha, int beta, int x, int y); /alpha_b

31、eta算法int compute(int turn, int level, int &x,int &y); /計算獲得下一個最佳位置int GetPointWeight(int turn, int x, int y); /棋盤位置評分/極大極小值算法算法實現(xiàn)void ComputerPlay(int *m,int *n);/計算獲得下一個最佳位置給棋盤的每個空白點評分；選擇分數(shù)最大的或最小的位置下棋；int NumToScoreMax(int num); /極大點分數(shù)int NumToScoreMin(int num); /極小點分數(shù)int GiveScore(bool max

32、,int chess,int row,int col); / int row,int col位置點的評分分別從0度，90度，135度，45度方向給該點評分；將所有分數(shù)累加得到該點的評分；2.1.2.1 博弈算法簡介機器博弈是人工智能一個傳統(tǒng)的研究領域。機器博弈的研究廣泛而深入。早在上世紀五十年代，就有人設想利用機器智能來實現(xiàn)機器與人的對弈。國外許多知名學者和知名科研機構都曾經涉足這方面的研究，歷經半個多世紀，到目前為止已經取得了許多驚人的成就。1997年IBM的“深藍”戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。除此之外，加拿大阿爾伯塔大學的奧賽羅程序Logistello和西洋跳棋程序Chi

33、nook也相繼成為確定的、二人、零和、完備信息游戲世界冠軍，而西洋雙陸棋這樣的存在非確定因素的棋類也有了美國卡基梅隆大學的西洋雙陸琪程序BKG這樣的世界冠軍。對圍棋、中國象棋、橋牌、撲克等許多種其它種類游戲博弈的研究也正在進行中。機器博弈的核心技術是博弈搜索算法，這也是機器博弈研究的熱點。機器博弈的核心思想并不復雜，實際上就是對博弈樹節(jié)點的估值過程和對博弈樹搜索過程的結合。在博弈的任何一個中間階段，站在博弈雙方其中一方的立場上，可以構想一個博弈樹。這個博弈樹的根節(jié)點是當前時刻的棋局，它的兒子節(jié)點是假設再行棋一步以后的各種棋局，子節(jié)點是從兒子節(jié)點的棋局再行棋一步的各種棋局，以此類推，構造整棵博弈

34、樹，直到可以分出勝負的棋局。整棵的博弈樹非常龐大，且不同的棋類有所不同，分支因子大的如圍棋的博弈樹顯然要比分支因子小的如國際象棋的博弈樹要大得多。博弈程序的任務就是對博弈樹進行搜索找出當前最優(yōu)的一步行棋。對博弈樹進行極大極小搜索，可以達到這一目的。極大極小搜索，是因為博弈雙方所要達到的目的相反，一方要尋找的利益恰是一方失去的利益，所以博弈的一方總是希望下一走是兒子節(jié)點中取值最大者，而另一方恰恰相反。這便形成了極大極小過程。博弈搜索的基本思想已經提出半個多世紀，目前廣泛研究的是確定的、二人、零和、完備信息的博弈搜索。也就是說，沒有隨機因素的博弈在兩個人之間進行，在任何一個時刻，一方失去的利益即為

35、另一方得到的利益，不會出現(xiàn)“雙贏”的局面，而且在任何時刻，博弈的雙方都明確的知道每一個棋子是否存在和存在于什么位置。二人、零和、完備信息的博弈搜索理論已經非常系統(tǒng)。極大極小算法是所有搜索算法的基礎。在這個基礎上，目前在這一領域的算法主要有兩類，一類是作為主流的深度優(yōu)先的alpha-beta搜索與其系列增強算法，另一類是最佳優(yōu)先的系列算法。2.1.2.2 極大極小值算法極大極小值算法的基本思想是始終站在博弈一方的立場上給棋局估值，有利于這一方的棋局給予一個較高的價值分數(shù)，不利于這一方（有利于另一方）的給予一個較低的價值分數(shù)，雙方優(yōu)劣不明顯的局面給予一個中間價值分數(shù)。在這一方行棋的時候，選擇價值極

36、大的兒子節(jié)點走步，另一方下棋則選擇價值極小的兒子節(jié)點走步。這就是一個極大極小過程。將博弈的雙方分別命名為MAX和MIN。而搜索的任務是為MAX找出最佳的移動。假設MAX先移動(此時暫時不考慮五子棋的禁手規(guī)則)，然后2個博弈者輪流移動。因此，深度為偶數(shù)的節(jié)點，對應于MAX下一步移動的位置，稱為MAX節(jié)點；深度為奇數(shù)的節(jié)點對應于MIN下一步移動的位置，稱為MIN節(jié)點(博弈樹的頂節(jié)點深度為0)。k層包括深度為2k和2k+1的節(jié)點。通常用層數(shù)來表示博弈樹的搜索深度。他可以表示出向前預測的MAX和MIN交替運動的回合數(shù)。對于復雜的博弈，博弈者必須認識到由于博弈樹的復雜程度所以搜索到終點是不可能的(除了在

37、博弈快結束時)。所以，常采用在有限圍搜索方法，確定下一個要考察的節(jié)點，在確定節(jié)點時只要能充分利用與問題有關的信息，估計出節(jié)點的重要性，就能在搜索時選擇重要性較高的節(jié)點，以利于博弈者以較快的速度求出最佳的下子位置。假設輪到MAX從搜索樹的葉節(jié)點中選取，他肯定選擇擁有最大值的節(jié)點。因此，MIN葉節(jié)點的一個MAX節(jié)點雙親的倒推值就等于葉節(jié)點的分數(shù)評估值中的最大值。另一方面，MIN從葉節(jié)點中選取時，必然選取最小的節(jié)點(即最負的值)。既然如此，MAX葉節(jié)點的MIN雙親節(jié)點被分配一個倒推值，它等于葉節(jié)點分數(shù)評估值的最小值。在所有葉節(jié)點的父節(jié)點被賦予倒推值后，開始倒推另一層，假定MAX將選擇有最大倒推值的M

38、IN的后繼節(jié)點，而MIN會選擇有最小倒推值的MAX后繼節(jié)點。繼續(xù)逐層對節(jié)點評估，直到最后開始節(jié)點的后繼者被賦予倒推值。MAX將選擇有最大倒推值的節(jié)點作為他的首步。整個過程的有效性基于這樣的假設。設想當前棋局S為輪到計算機方下棋(用方框表示)，任選一空點作為計算機方的下棋位置(可有若干種選擇)，接著考慮在此情況下游戲者一方下棋的棋局(用圓圈表示)；從某一個圓圈棋局出發(fā)，任選一空點作為游戲者一方的下子處(又有若干種選擇)。再次形成計算機方下棋的方框棋局；依此類推，這樣可形成一棵以S為根結點的博弈樹，該樹以圓圈棋局為第2層子結點，以方框棋局為第3層子結點等等。如果繼續(xù)向前搜索，可形成多層子結點，現(xiàn)在

39、以向前搜索3層子結點為例來說明極大極小值的過程。對第3層子結點的某一棋局n，求出其估計值h(n)，假設有一博弈樹已形成，如下圖所示，h(n)的值由各結點旁的數(shù)值給出。根節(jié)點S30-40-30最佳第二層節(jié)點第三層節(jié)點3040603060-4050-308050 圖2-1 極大極小值算法示意圖根據(jù)極小極大化分析法，先計算第3層子結點h(n)值，然后第2層子結點的估計值取他的各個后繼子結點的極小值，根結點的估計值取他的各子結點的極大值。這個取得最大估計值的子結點即為從S出發(fā)的計算機方的最佳下子方案。2.1.2.3 alpha-beta算法在極大極小搜索的過程中，存在著一定程度的數(shù)據(jù)冗余，如圖 2-2

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

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

42、排列非常敏感。如果節(jié)點的排列順序不是從最差到最好，就有可能使剪枝一直無法進行，從而實際上搜索了整棵的博弈樹。大多數(shù)alpha-beta剪枝算法都采用深度優(yōu)先的搜索策略，是因為深度優(yōu)先搜索較之寬度優(yōu)先搜索節(jié)省存儲空間，只需保存根節(jié)點到當前搜索節(jié)點的路徑上的節(jié)點信息即可。針對alpha-beta剪枝算法的改進算法很多，比如，渴望搜索（Aspiration Search），極小窗口搜索（Minimal Window Search），置換表（Transposition Table），遍歷深化（Iterative Deepening），歷史啟發(fā)搜索（History Heuristic），殺手啟發(fā)搜索(K

43、iller Heuristic)， MTD(f)算法等。2.1.3 游戲模式設置模塊類名：CAIModelDlg主要實現(xiàn)功能：游戲者對當前游戲的設置，設置游戲的對戰(zhàn)模式，包括雙人對戰(zhàn)和人機對戰(zhàn)。設置游戲AI智能等級，設置AI智能的算法，設置游戲的先手。主要變量與其相應的注釋：Int m_Cur_Ai_model; /機器等級，0-簡單，1-中級，2-高級int m_Game_Model; /游戲模式 0-雙人對戰(zhàn) 1-人機對戰(zhàn)int m_Ai_Kind; /Ai算法的種類 0-極大極小 1-alpha_beta算法BOOL m_beAiFirst; /1-機器先行 ，0-人先行主要函數(shù)與其功能

44、：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主要實現(xiàn)功能：游戲者對當前游戲的語言設置。主要變量與其相應的注釋：int m_Current_Language_Mode;

45、/當前語言選擇，0表示漢語，1表示英語CComboBoxm_Lan_Com; /用于選擇語言的下拉列表框主要函數(shù)與其功能：void Set_Lan_Model(int model); /設置當前語言int Get_Lan_Model(); /獲得當前的語言類型2.1.5鏈表使用功能模塊主要實現(xiàn)功能：記錄當前游戲的下子以達到悔棋的功能。因為每次悔棋的時候只涉與到最后一個或兩個棋子，所以選擇順序表，相當于只在表尾操作。每個游戲中用一個順序表來記錄下子的情況，則悔棋的實現(xiàn)就是順序表的操作。#define MAXSIZE 225 /最大記錄個數(shù)struct Node /下棋記錄的節(jié)點信息int Pos

46、_X; /位置int Pos_Y;int Color; /顏色， 0-黑色 1-白色;struct SeqList /行棋記錄Node listMAXSIZE;int size; /當前記錄個數(shù);類名：CSeqList主要函數(shù)與其功能：Void ListInitiate(SeqList *L); /鏈表初始化int ListLength(SeqList *L); /獲得鏈表的長度int ListInsert(SeqList *L,/*int pos,*/Node element); /鏈表的插入操作int ListDelete(SeqList *L/*,int pos*/,Node *elem

47、ent); /鏈表的刪除操作int ListGet(SeqList L,/*int pos,*/Node *element); /獲得鏈表某一個元素2.1.6 游戲記錄模塊類名：CGameRecord主要實現(xiàn)功能：游戲的玩家記錄，以下子的個數(shù)最少為最優(yōu)。主要變量與響應注釋：CString m_path; /路徑名CStringm_Jun_Name; /各個游戲等級的游戲記錄CStringm_Mid_Name;CStringm_Sen_Name;CStringm_Junior;CStringm_Mid;CStringm_Senior;主要函數(shù)與其功能：void SetRecord(CString

48、 name,int range , int chessnum); /設置游戲記錄void OnRecordReset(); /游戲記錄重置2.1.7獲得游戲者模塊類名：CNameDlg主要實現(xiàn)功能：游戲玩家破記錄時候記錄玩家的名字。主要變量與響應注釋：CStringm_HeroName; /記錄玩家的2.1.8 關閉對話框方式與托盤顯示模塊類名：CCloseSelectDlg主要功能：實現(xiàn)用戶關閉程序時候根據(jù)需要選擇是直接關閉還是最小化到托盤，并設置下次是否繼續(xù)提示。托盤功能主要實現(xiàn)游戲的托盤化與托盤的右鍵彈出菜單的消息響應。int m_CloseSelected; /選擇的方式 0-關閉 1

49、-托盤 CString m_path; /路徑名BOOLm_NoTip;/是否繼續(xù)提示 1-不再提示 0-提示主要函數(shù)：:Shell_NotifyIcon(NIM_ADD,&m_tnid); /用于實現(xiàn)程序的托盤功能2.1.9圓形按鈕模塊類名：CRoundButton主要功能：將界面的按鈕畫成圓形以達到美化的效果。主要變量與函數(shù)：CRgn m_rgn; /畫的區(qū)域CPoint m_ptCentre; /圓的圓心點int m_nRadius; /圓的半徑virtual void DrawItem(LPDRAWITEMSTRUCT lpDrawItemStruct); /重畫virtual

50、 void PreSubclassWindow(); /重新定位此類使用時先給要重繪的按鈕關聯(lián)一個變量，再將CButton類型改成CRoundButton就可以。2.1.10 配置文件的讀取和保存主要的功能：實現(xiàn)游戲配置的保存以與游戲配置文件的讀取來初始化游戲。主要函數(shù)：bool WritePrivateProfileString(LPCTSTR lpAppName,LPCTSTR lpKeyName,LPCTSTR lpString,LPCTSTR lpFileName); /ini文件的寫操作DWORD GetPrivateProfileString(LPCTSTR lpAppName,LPCTS