《人工智能井子棋报告.docx》由会员分享，可在线阅读，更多相关《人工智能井子棋报告.docx（30页珍藏版）》请在三一办公上搜索。
1、 目 录第一章 系统需求分析与总体设计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 系统目标 (6)1.2.4 需求定义 (6)1.2.5 系统功能结构图 (7)1.2.6 性能要求与系统开发的重点与难点 (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、计与系统实现 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 模块功能调用关系及其示意图 (
3、22)第三章 系统测试 3.1程序运行结果截图(24)第四章 系统总结4.1 系统存在的问题(27)4.2 将要做的工作(27)4.3 总结和体会(27) 4.4 参考文献(28)第一章 系统需求分析与总体设计1.1 概述 五子棋是一种大众喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性，它不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征短、平、快，又有古典哲学的高深学问阴阳易理；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有场的概念，亦有点的连接。它是中西文化
4、的交流点，是古今哲理的结晶。近来随着计算机的快速发展，各种棋类游戏被纷纷请进了电脑，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。而且这类软件个个水平颇高，大有与人脑分庭抗礼之势。其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱；而我也做了一个“无比”简单的五子棋程序。总的来说（我们假定您熟悉五子棋的基本规则），要让电脑知道人下子之后该在哪一点下子，就要根据盘面的形势，为每一可能落子的点计算其重要程度，也就是当这子落下后会形成什么棋型（如：“冲四”、“活三” 等），然后总览全盘选出最重要的
5、一点，这便是最基本的算法的思想。1.1.1 五子棋背景介绍 五子棋是一种两人对弈的纯策略型棋类游戏，是起源于中国古代的传统黑白棋种之一。发展于日本，流行于欧美。五子棋，日文亦有“连五子、五子连、串珠、五目、五目碰、五格、五石、五法、五联、京棋”等多种称谓，英文则称之为“FIR (Five In A Row的缩写)、Gomoku(日语“五目”的罗马拼音)、Gobang、connect 5、mo-rphion”。捷克语piskvorky，韩语omok五子棋相传起源于四千多年前的尧帝时期，比围棋的历史还要悠久，可能早在“尧造围棋”之前，民间就已有五子棋游戏。有关早期五子棋的文史资料与围棋有相似之处，
6、因为古代五子棋的棋具与围棋是完全相同的。在上古的神话传说中有“女娲造人，伏羲做棋”一说，增山海经中记载：“休舆之山有石焉，名曰帝台之棋，五色而文状鹑卵。”李善注引三国魏邯郸淳艺经中曰：“棋局，纵横各十七道，合二百八十九道，白黑棋子，各一百五十枚”。可见，五子棋颇有渊源。亦有传说，五子棋最初流行于少数民族地区，以后渐渐演变成围棋并在炎黄子孙后代中遍及开来。在古代，五子棋棋具虽然与围棋相类同，但是下法却是完全不同的。正如辞海中所言，五子棋是“棋类游戏，棋具与围棋相同，两人对局，轮流下子，先将五子连成一行者为胜。”。古代五子棋棋盘与围棋棋盘是通用的，汉魏时为十七路（1717）棋盘，至南北朝时即已流行
7、十九路（1919）棋盘，直至1931年，才出现所谓五子棋专用棋盘，如图所示，为十五路（1515）棋盘，形状近于正方形，平面上画横竖各15条平行线，线路为黑色，构成225个交叉点，邻近两个交点的距离纵线约为2.5厘米，横线约为2.4厘米。棋盘正中一点为“天元”。棋盘两端的横线称端线，棋盘左右最外边的两条纵线称边线。从两条端线和两条边线向正中发展而纵横交叉在第四条线形成的四个点称为“星”。天元和星应在棋盘上用直径约为0.5厘米的实心小圆点标出。五子棋棋子亦称“棋石”，分黑、白两色，形状为扁圆形，有一面凸起或两面凸起等形状，厚度不超过0.8厘米，直径为2.02.3厘米；一副棋子总数为225枚，其中黑
8、子113枚，白子112枚。按质地的不同，可分为玻璃、陶瓷、塑料、智石、磁铁、蛤贝、烧料、水晶、玛瑙、玉石等棋子。1.1.2 相关术语1.1.2.1 对局相关术语黑方执黑棋一方的简称。白方执白棋一方的简称。胜局有一方获胜的对局。和局分不出胜负的对局。终局对局结束。复盘对局双方将本盘对局全过程的再现。1.1.2.2 行棋相关术语阳线即:直线，棋盘上可见的横纵直线。交叉点阳线垂直相交的点，简称“点”。阴线即:斜线，由交叉点构成的与阳线成45夹角的隐形斜线。落子棋子直接落于棋盘的空白交叉点上。轮走方即“行棋方”，有权利落子的黑方或白方。着在对局过程中，行棋方把棋子落在棋盘无子的点上，不论落子的手是否脱
9、离棋子，均被视为一着。回合双方各走一着，称为一个回合。开局在对局开始阶段形成的布局。连同色棋子在一条阳线或阴线上相邻成一排。长连五枚以上同色棋子在一条阳线或阴线上相邻成一排。五连只有五枚同色棋子在一条阳线或阴线上相邻成一排。成五含有五枚同色棋子所形成的连，包括五连和长连。四在一条阳线或阴线上连续相邻的5个点上只有四枚同色棋子的棋型。活四有两个点可以成五的四。冲四只有一个点可以成五的四。死四不能成五的四。三在一条阳线或阴线上连续相邻的5个点上只有三枚同色棋子的棋型。活三再走一着可以形成活四的三。连活三即连的活三(同色棋子在阳线或阴线上相邻成一排的活三)简称“连三”。跳活三中间隔有一个空点的活三。
10、简称“跳三”。眠三再走一着可以形成冲四的三。死三不能成五的三。二在一条阳线或阴线上连续相邻的5个点上只有两枚同色棋子的棋型。活二再走一着可以形成活三的二。连活二即连的活二(同色棋子在阳线或阴线上相邻成一排的活二)，简称“连二”。跳活二中间隔有一个空点的活二。简称“跳二”。大跳活二中间隔有两个空点的活二。简称“大跳二”。眠二再走一着可以形成眠三的二。死二不能成五的二。先手对方必须应答的着法，相对于先手而言，冲四称为“绝对先手”。三三一子落下同时形成两个活三。也称“双三”。四四一子落下同时形成两个冲四。也称“双四”。四三一子落下同时形成一个冲四和一个活三。1.2需求分析1.2.1选题与题目要求实习
11、题目：五子棋人机博弈游戏。内容要求：实现五子棋游戏的人机博弈。要求：友好的人机图形化界面、方便的操作方式；自动判断输、赢或平；可选择黑白；可悔棋；可以基于人工智能方面的知识进行设计，如：启发式搜索、搜索函数的设置、_算法、知识的表示及知识库，推理机等。1.2.2 系统总体分析程序主要涉及的是界面的制作，五子棋的核心算法以及其他方便使用的功能。程序采用VC 6.0软件环境实现。运行环境为Windows XP及其他系统。使用对话框的软件模式。主要提供的功能是游戏的开始，结束，悔棋操作；程序的提示信息的中英文；软件的配置信息，主要包括游戏的模式，分为人机对战和双人对转；AI智能的高低，分为简单，中级
12、，高级三种。AI智能使用的算法，主要有极大极小值算法，alpha-beta算法等。以及程序的托盘功能和托盘菜单等。1.2.3系统目标五子棋游戏系统开发主要包括界面的生成和显示刷新以及AI智能的生成和运行两个方面。对于前者要求友好的人机图形化界面、方便的操作方式；自动判断输、赢或平；可选择黑白；可悔棋。而对于后者则要求基于人工智能方面的知识进行设计，如：启发式搜索、搜索函数的设置、_算法、知识的表示及知识库，推理机等，使AI能够自动根据当前的棋盘局势自动下子。系统开发的总体任务是实现各操作和界面的便捷化，规范化，自动化以及AI智能的智能化，快速化，准确化。1.2.4 需求定义作为一个可视化的方便
13、快捷的五子棋游戏软件，此软件要求的功能有：1. 整洁，友好的操作界面：采用圆形按钮美化，采用位图背景，清晰明了，棋子分黑白红，其中红色用于显示赢棋是显示赢方的棋路。2. 方便快捷的用户操作的响应：准确性应鼠标和键盘的消息，准确完成下子及棋盘的显示和更新，游戏某一方赢棋时消息框提示并棋子红色显示。3. 详细准确的提示信息：当前操作不可行时候用消息框给用户足够准确的提示信息。4. 方便齐全的功能：包括五子棋的各种应有的悔棋，判输赢等功能。5. 纠错功能：用户操作错误能够进行纠正。6. 用户设置的保存和读取功能：ini文件保存游戏配置，语言设置。游戏开始时候从ini文件读取这些保存点信息。7. 使用
14、语言的选择功能：用户可以选择中文或者英文。8. AI响应的功能：AI能准确无误的给出当前局势的响应。9. 游戏设置功能，用户可以根据自己喜好选择是否先手，游戏方式，AI等级选择，AI算法选择等，设置之后游戏重新初始化。10. 游戏记录的显示和保存：显示游戏的英雄榜，记录可以重置。1.2.5系统功能结构图五子棋游戏系统 选择游戏的模式，AI等级，AI算法。是否先手。采用图形界面，用位图做背景。还可以使用美化工具进行美化。圆形按钮，中英文菜单。语言设置游戏设置主界面显示游戏可以托盘化，更加方便快捷。用户游戏和语言设置等以ini文件的形式保存。游戏开始读取配置。根据需要选择中英文托盘功能AI智能拓展
15、性配置信息界面方便拓展成网络五子棋的形式.AI智能自动下子，自动判断输赢。图 1-1 系统功能结构图1.2.6 性能要求与系统开发的重点与难点正确性，可靠性，高效率，软件完整性，操作易使用性，软件可维护性，软件可测试行，可复用性，易理解性，软件可移植性。系统出现了一些技术难点大致如下：1.游戏界面的制作和及时响应用户要求及游戏行进中截面的更新。游戏的内部状态和界面显示的转换。2.游戏AI智能的实现，对不同棋盘局势实现不同的响应，平衡AI智能在游戏中进攻和防守的选择。1.3 可行性分析1.3.1技术可行性 此次信息系统开发是大学专业知识的一次综合应用与提高。首先就开发硬件基础设施而言，本次课程设
16、计安排在学校314机房进行，该机房计算机配置肯定能满足系统开发的要求。此外我可以利用课余时间在自己的电脑上进行程序的设计。其次就软件环境而言，本人选择微软的软件开发环境VC 6.0。此环境人性化的操作界面和便捷的程序编辑方式，使程序的设计方便快捷。再者，就技术力量来说，我可以顺利完成此次开发工作。大学的学习，使我已经学习了C，C+等程序设计语言，对图形界面的设计也比较熟悉，VC的使用经验也比较充足。开发过程中也会出现许多的问题，有我预想之中的，也有一些没有我预想到，但我有信心克服一切困难。因此从经济角度考虑，此信息系统开发可行。1.3.2经济可行性目标系统开发需求比较低，加上具有成熟的软硬件环
17、境，所以在软硬件的支出上十分有限。而且，目标系统并不是十分的复杂，开发的周期较短，人员经济支出有限。 当系统开发完成实际付诸使用后，在为使用者带来便利的同时，也为软件的进一步推广创造了条件。这带来的经济回报将远超过支出，并且最重要的一点是该软件的开发可以给我们对系统的开发有个全面的认识。因此从经济角度考虑，此信息系统开发可行。1.3.3 操作可行性软件设计完成后，运行在Windows系统上，可以响应鼠标和键盘的操作，均为用户熟悉的使用环境。软件界面整洁漂亮，不会引发任何歧义。因此从操作角度考虑，此信息系统开发可行。1.3.4法律可行性整个系统由于是自行开发，自行使用，所以系统本身不存在法律上的
18、版权争议。在软件使用方面，使用的是正版VC 6.0软件，不存在软件的使用纠纷。因此从法律角度考虑，此信息系统开发可行。1.3.5社会可行性五子棋简单易学，容易上手，深受广大玩家的喜爱。本软件功能齐全，界面清晰，操作方便，会深受玩家的欢迎。从社会角度考虑，此信息系统开发可行。1.3.6结论根据以上的可行性研究，我认为开发此系统的条件已经具备，可以开始进行开发。第二章 详细设计与系统实现2.1 游戏主要功能模块程序的主要功能模块主功能界面模块，五子棋游戏类模块，游戏模式设置模块，游戏语言设置模块，链表使用功能模块，游戏记录模块，获得游戏者姓名模块，关闭对话框方式模块，圆形按钮实现模块。下面一一介绍
19、：2.1.1 主功能界面模块类名: CmyFiveChessDlg.主要实现功能：实现界面的现实，游戏中棋盘棋子的显示。其他各功能模块的其中调度。用户功能的选择途径等。主要变量及注释如下:CLanguageDlg m_Lan_dlg; /语言设置对话框对象，调用语言设置对话框int m_Lan_Model; /从ini文件读取保存的语言设置 0-中文 ，1 -英语CAIModelDlg m_Option_dlg; /模式设置对话框，调用配置对话框int m_Ai_Model; /AI等级 ，0-简单，1-中级，2-高级int m_Game_Model; /0-双人，1-人机int m_ai_k
20、ind; /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; /要发送的信息的内容CString m_AllMessage; /全部要显示的内容CPaintDC *m_Show_DC; /CFive的显示
21、的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; /英语菜单CMenu m_Chinese_Menu; /中文菜单enumC,
22、Em_Current_Menu; /标记当前菜单选择，枚举主要函数及其功能：CMyFiveChessDlg（）； /构造函数，获得ini文件的路径，构造CFive类对象，初始化游戏设置对话框和语言选择对话框。OnInitDialog()；/对话框的初始化，菜单的选择，界面的现实，初始化游戏记录文件和关闭方式设置对话框，Init_Close_Info() /读取ini文件，初始化关闭方式设置对话框Init_Record_Info()；/读取ini文件，初始化游戏记录对话框的信息Init_Model_Info()； /读取ini文件，初始化游戏设置对话框的信息Init_Language_Info(
23、)；/读取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)/读ini文件OnLButtonDown(UINT nFlags, CPo
24、int point) /响应鼠标左键消息，游戏的主要控制OnGameRecord()/游戏记录菜单OnCreate(LPCREATESTRUCT lpCreateStruct)/响应Create消息，产生托盘WindowProc(UINT message, WPARAM wParam, LPARAM lParam)/主要截获处理托盘的消息2.1.2五子棋游戏类模块类名： CFive主要实现功能：游戏的构造，棋盘棋子的现实，游戏下子。游戏内部记录及AI智能的响应。主要宏定义：#define GRID_NUM 15 /棋盘表格的大小#define GRID_COUNT 225 /棋盘表格的总数目#
25、define BLACK 0 /黑子#define WHITE 1 /白子#define NOSTONE 0xFF /没有棋子，初始状态为空/获胜的五个棋子的走向#define WIN_ROW 1 /横#define WIN_COL 2 /纵#define WIN_LEFTUP_RIGHTDOWN 3 /左上到右下#define WIN_LEFTDOWN_RIGHTUP 4 /左下到右上主要数据结构:struct WININFO /保存游戏获胜信息int winner; /-1 没有获胜 0 黑 1 白int Start_X; /五连的起始坐标和结束坐标int Start_Y;int End_
26、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 /五子;主要的变量和相应的注释：bool m_isGameStart; /游戏是否开始，bo
27、ol 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; /对战模式 0-双人对战 ，1 -人机对战int m_Kind; /Ai算法种类int m_ChessBoardGRID_NUMGRID_NUM; /棋盘数组，记录棋盘下子int m_Last_x,m_Last_y; /上次行棋的位置x和yint m_Che
28、ss_Down_Num; /当前已经下的棋子数目WININFO m_Win; /获胜信息SeqList m_Record; /下棋记录的顺序表信息CSeqList list; /主要是链表的操作函数主要函数及其功能:CFive(int aitype,int model,bool AiFirst,int AiKind); /构造函数，界面类调用void Show(CPaintDC * dc); /显示棋盘棋子 显示黑白棋子；显示最近行棋位置；if(m_isWin) 显示赢棋的信息； 显示棋盘;void NewGame(); /新游戏清空棋盘；如果机器现行则在天元位置下棋void Clear();
29、 /全部清空，相当于初始化void CheckGameOver(int X,int Y,int Color); /检查是否游戏结束,m_isGameOver表示结果分别从0度，90度，135度，45度方向检查是否某一方胜利；检查某一个方向就是以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); /机器自动下子boo
30、l 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算法实现int alpha_beta(int level, int turn, int alpha, int beta, int x, int y); /alpha_beta算法int compute(int turn, int level, int &x,int &y
31、); /计算获得下一个最佳位置int GetPointWeight(int turn, int x, int y); /棋盘位置评分/极大极小值算法算法实现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度，
32、90度，135度，45度方向给该点评分；将所有分数累加得到该点的评分；2.1.2.1 博弈算法简介机器博弈是人工智能一个传统的研究领域。机器博弈的研究广泛而深入。早在上世纪五十年代，就有人设想利用机器智能来实现机器与人的对弈。国内外许多知名学者和知名科研机构都曾经涉足这方面的研究，历经半个多世纪，到目前为止已经取得了许多惊人的成就。1997年IBM的“深蓝”战胜了国际象棋世界冠军卡斯帕罗夫，惊动了世界。除此之外，加拿大阿尔伯塔大学的奥赛罗程序Logistello和西洋跳棋程序Chinook也相继成为确定的、二人、零和、完备信息游戏世界冠军 ，而西洋双陆棋这样的存在非确定因素的棋类也有了美国卡内
33、基梅隆大学的西洋双陆琪程序BKG这样的世界冠军。对围棋、中国象棋、桥牌、扑克等许多种其它种类游戏博弈的研究也正在进行中。机器博弈的核心技术是博弈搜索算法，这也是机器博弈研究的热点。机器博弈的核心思想并不复杂，实际上就是对博弈树节点的估值过程和对博弈树搜索过程的结合。在博弈的任何一个中间阶段，站在博弈双方其中一方的立场上，可以构想一个博弈树。这个博弈树的根节点是当前时刻的棋局，它的儿子节点是假设再行棋一步以后的各种棋局，孙子节点是从儿子节点的棋局再行棋一步的各种棋局，以此类推，构造整棵博弈树，直到可以分出胜负的棋局。整棵的博弈树非常庞大，且不同的棋类有所不同，分支因子大的如围棋的博弈树显然要比分
34、支因子小的如国际象棋的博弈树要大得多。博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行棋。对博弈树进行极大极小搜索，可以达到这一目的。极大极小搜索，是因为博弈双方所要达到的目的相反，一方要寻找的利益恰是一方失去的利益，所以博弈的一方总是希望下一走是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程。博弈搜索的基本思想已经提出半个多世纪，目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。也就是说，没有随机因素的博弈在两个人之间进行，在任何一个时刻，一方失去的利益即为另一方得到的利益，不会出现“双赢”的局面，而且在任何时刻，博弈的双方都明确的知道每一个棋子是否存在和存在于什
35、么位置。二人、零和、完备信息的博弈搜索理论已经非常系统。极大极小算法是所有搜索算法的基础。在这个基础上，目前在这一领域的算法主要有两类，一类是作为主流的深度优先的alpha-beta搜索及其系列增强算法，另一类是最佳优先的系列算法。2.1.2.2 极大极小值算法极大极小值算法的基本思想是始终站在博弈一方的立场上给棋局估值，有利于这一方的棋局给予一个较高的价值分数，不利于这一方（有利于另一方）的给予一个较低的价值分数，双方优劣不明显的局面给予一个中间价值分数。在这一方行棋的时候，选择价值极大的儿子节点走步，另一方下棋则选择价值极小的儿子节点走步。这就是一个极大极小过程。将博弈的双方分别命名为MA
36、X和MIN。而搜索的任务是为MAX找出最佳的移动。假设MAX先移动(此时暂时不考虑五子棋的禁手规则)，然后2个博弈者轮流移动。因此，深度为偶数的节点，对应于MAX下一步移动的位置，称为MAX节点；深度为奇数的节点对应于MIN下一步移动的位置，称为MIN节点(博弈树的顶节点深度为0)。k层包括深度为2k和2k+1的节点。通常用层数来表示博弈树的搜索深度。他可以表示出向前预测的MAX和MIN交替运动的回合数。对于复杂的博弈，博弈者必须认识到由于博弈树的复杂程度所以搜索到终点是不可能的(除了在博弈快结束时)。所以，常采用在有限范围搜索方法，确定下一个要考察的节点，在确定节点时只要能充分利用与问题有关
37、的信息，估计出节点的重要性，就能在搜索时选择重要性较高的节点，以利于博弈者以较快的速度求出最佳的下子位置。假设轮到MAX从搜索树的叶节点中选取，他肯定选择拥有最大值的节点。因此，MIN叶节点的一个MAX节点双亲的倒推值就等于叶节点的分数评估值中的最大值。另一方面，MIN从叶节点中选取时，必然选取最小的节点(即最负的值)。既然如此，MAX叶节点的MIN双亲节点被分配一个倒推值，它等于叶节点分数评估值的最小值。在所有叶节点的父节点被赋予倒推值后，开始倒推另一层，假定MAX将选择有最大倒推值的MIN的后继节点，而MIN会选择有最小倒推值的MAX后继节点。继续逐层对节点评估，直到最后开始节点的后继者被
38、赋予倒推值。MAX将选择有最大倒推值的节点作为他的首步。整个过程的有效性基于这样的假设。设想当前棋局S为轮到计算机方下棋(用方框表示)，任选一空点作为计算机方的下棋位置(可有若干种选择)，接着考虑在此情况下游戏者一方下棋的棋局(用圆圈表示)；从某一个圆圈棋局出发，任选一空点作为游戏者一方的下子处(又有若干种选择)。再次形成计算机方下棋的方框棋局；依此类推，这样可形成一棵以S为根结点的博弈树，该树以圆圈棋局为第2层子结点，以方框棋局为第3层子结点等等。如果继续向前搜索，可形成多层子结点，现在以向前搜索3层子结点为例来说明极大极小值的过程。对第3层子结点的某一棋局n，求出其估计值h(n)，假设有一
39、博弈树已形成，如下图所示，h(n)的值由各结点旁的数值给出。根节点S30-40-30最佳第二层节点第三层节点3040603060-4050-308050 图2-1 极大极小值算法示意图根据极小极大化分析法，先计算第3层子结点h(n)值，然后第2层子结点的估计值取他的各个后继子结点的极小值，根结点的估计值取他的各子结点的极大值。这个取得最大估计值的子结点即为从S出发的计算机方的最佳下子方案。2.1.2.3 alpha-beta算法在极大极小搜索的过程中，存在着一定程度的数据冗余，如图 2-2所示左半部的一棵极大极小树的片断，节点下面为该节点的值，设A 为极大值节点，节点B的值为18，节点D 的值
40、为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剪枝示意图同样道理在图 2-3右半部一棵极大极小树的片段中，设A为极小值节点，节点B的估值为8，节点D的估值为l8，由此可以判断节点C的值将大于等于18(取极大值)；而节点A 的值为Min(B，c)，是8。也就是说不再需要求节点C的其他子节点如E、F值就可以得出父节点A 的值了。这样将节点D的后继兄弟节点剪去称为Beta剪枝(剪枝)。ABCDEFA取最小值818Beta剪枝(剪枝)
