五子棋游戏(双人对战版)软件设计.doc

2012-2013学年第1学期“软件工程”课程设计报告学院系信息工程学院计算机科学系专业计算机科学与技术班级项目名称五子棋游戏（双人对战版）软件设计组长小组成员主要负责完成软件的测试模块主要负责完成界面设计以及源代码的编写与调试主要负责完成数据结构设计以及源代码的编写与调试主要负责完成的功能设计以及源代码的编写与调试主要负责完成软件的问题描述和算法分析部分以及报告的整合主要负责完成软件的需求分析模块目录第一章 五子棋双人对战版软件问题描述31.1 五子棋的相关介绍31.1.1 五子棋的简介31.1.2 五子棋规则31.2 五子棋双人对战版软件41.2.1 软件设计思想4第二章 五子棋双人对战实现的算法分析42.1传统五子棋算法介绍及初步实现42.1.1 估值函数42.1.2 AlphaBeta 搜索52.1.3 胜负判断72.2 五子棋算法的优化72.2.1 减少搜索范围72.2.2 设置下棋风格82.2.3 增大搜索层数82.2.4 使用置换表82.2.5 启发式搜索8第三章 需求分析报告93.1 介绍93.1.1 目的93.1.2 文档约定93.1.3 面向的读者和阅读建议93.1.4 参考文献103.2 整体描述103.2.1 功能需求103.2.2 性能需求113.2.3 数据流图123.3 系统特点123.3.1 系统特点123.3.2 系统功能123.4 外部接口需求133.4.1 用户界面133.4.2 硬件接口133.4.3 软件界面133.5 其他非功能需求133.5.1 系统交付日期133.5.2 系统需求133.6 软件总流程图14第四章 设计与实现154.1 基本设计概念和处理流程154.2 结构154.3 功能设计164.3.1 软件的基本功能设计164.3.2 软件的附加功能设计164.4 接口设计164.4.1 用户接口164.4.2 外部接口174.4.3 内部接口174.5 界面设计174.5.1 界面设计运用的主要方法174.6 系统数据结构设计194.6.1 逻辑结构和物理结构设计要点194.6.2 数据结构与程序的关系214.7 系统出错处理设计224.8 软件运行结果22第五章 测试255.1 黑盒测试25第一章 五子棋双人对战版软件问题描述1.1 五子棋的相关介绍1.1.1 五子棋的简介 五子棋是一种两人对弈的纯策略型棋类游戏，棋具与围棋通用，是起源于中国古代的传统黑白棋种之一。发展于日本，流行于欧美。容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。1.1.2 五子棋规则无禁手玩法：黑先白后，谁先连五谁胜。禁手玩法：黑先行棋，黑棋只能走冲四活三胜，黑双活三禁手 双冲四禁手 四三三禁手 四四三禁手 六连长连禁手；白后手，白棋无任何禁手，还可以抓黑棋的禁手点取胜。 职业规则玩法：三手交换五手两打，黑棋有禁手，意思是下到第三手棋执白方有权选择交换下黑棋或者继续行棋，下到第五手时执黑方给出两个打点让执白方选择去掉一个打点下剩下的打点。1.2 五子棋双人对战版软件1.2.1 软件设计思想人对人游戏，其实只是对游戏规则的实现，我们只是利用五子棋游戏的规则以及五子棋的经典算法来编程，这些规则和算法，我们将用相应的函数来实现。一个优秀的游戏软件必须有一个正确的设计思想通过合理地选择数据结构、操作系统以及开发环境构成一个完善的体系结构才能充分发挥计算机应用的优势。根据游戏玩家的实际需求本系统的设计按照下述原则进行：实用性、先进性、高可靠性、可维护性、可扩展性及灵活性、智能性。第二章 五子棋双人对战实现的算法分析2.1传统五子棋算法介绍及初步实现2.1.1 估值函数不同的棋型，其优先级不同。例如，四个棋子连成一线且还能继续落子的棋型（活四）显然要比只有三个棋子连成一线（活三或死三）好。要使计算机正确地做出这种判断，就要把第一种棋型的估值设高。事实上，对于每一种特定的棋型，都需要相应的估值来反映其优劣情况。另外，由于搜索模块频繁地调用估值函数，为了尽可能地加快搜索速度，估值函数应设计的越仔细越好。估值时，需要从四个方向上来考虑所下棋子对当前盘面的影响。这个方向分别是以该棋子为出发点，水平、竖直和两条为45 度角和135 度角的线。为方便分析棋盘上的格局，本文中约定以“A”代表黑子，“B”代表白子，“？”代表棋盘上空位。算法中关于棋子死活的规定如下：一方落子后，它的落子连成的一条线有两条不损伤的出路，则称该棋型是活的。否则称该棋型是死的。比如关于活三的定义：不论对手如何落子，仍然至少有一种方法可以冲四。因此，B?AAA? B 中的三个A，不能算是活三；B?AAA?B 中的三A，也不是活三，尽管它有可能成为活四。这样，棋型的估值设计才能比较细致。本文算法对特定棋型的估值如表1 所示。表一：特定棋型的估值2.1.2 AlphaBeta 搜索在博弈问题中，每一个格局可供选择的行动方案都有很多，因此会生成十分庞大的博弈树。一般地只生成一定深度的博弈树，然后进行极小极大搜索。极大极小搜索是指：在一棵博弈树中，当轮到甲走时，甲定会选择子节点值最大的走法；而轮到乙走时，乙则会选择子节点值最小的走法3。使用估值函数对博弈树的每一个局面进行估值后，就可以通过极大极小搜索在博弈树中寻找最佳的合法走法。在极大极小搜索的过程中，存在着一定程度的数据冗余。如图1 左半部所示的一棵极大极小树的片断。其中节点下方数字为该节点的值，方形框节点代表计算机走，圆形框节点代表人走。A 节点表示计算机走，由于A 是极大值点，根据极小极大搜索原理它要从B 和C 当中选最大的值。假设目前已经通过估值得出B 为18，当搜索C 节点时，因为C 是该人走，所以根据极小极大搜索原理要从D、E、F 中选取最小的值。此时如果估出D 为16，那么C 的值必小于或等于16。又因为已经得出B 的值为18，说明节点A 的值为Max（B，C）=18，也就是说无须求出节点C 的其他子节点如E、F 的值就可以得出父节点A 的值。这种将节点D的后继兄弟节点剪去的方法称为Alpha 剪枝。同理，在图1右半部一棵极大极小树的片段中，将节点D 的后继兄弟节点剪去称为Beta 剪枝。图1 Alpha-Beta 剪枝将Alpha 剪枝和Beta 剪枝加入极大极小搜索，就得到Alpha-Beta 搜索算法，该算法描述如下：int AlphaBeta(int depth, int alpha, int beta)if depth 为0，说明当前节点是叶子节点then返回对当前棋局的估值elsewhile 还存在可能的走法走一步棋，从对手角度进行-AlphaBeta(depth-1,-beta，-alpha)的递归搜索，记录返回值为val撤消刚才走的一步若 val 大于等于beta，则返回beta 的值若 val 大于alpha，则修改alpha 的值为valend whileend if返回 alpha其中depth 记录搜索的深度，alpha 记录搜索到的最好的值，beta 记录对于对手来说最坏的值。如果INFINITY 表示无穷大，则AlphaBeta(3, -INFINITY, INFINITY)表示完成一次3层的搜索。2.1.3 胜负判断在棋局的胜负是根据最后一个落子的情况来判断的。此时需要查看四个方向，即以该棋子为出发点的水平，竖直和两条分别为45 度角和135 度角的线，看在这四个方向上的其它棋子是否能和最后落子构成连续五个棋子，如果能的话，则表示这盘棋局已经分出胜负。实际上，我们可以提前若干步预判当前棋局的胜负情况。本文算法采用了如下的规则对胜负进行预判，提高了算法的智能。在甲和乙对弈的棋局中，某个时刻轮到甲下棋时几种可能获胜的情况：甲已有任意组活四，或者甲已有任意组死四：一步获胜甲已有任意组活三，或者甲已有多于一组的死三：两步获胜甲已有一组死三和任意组的活二：三步获胜2.2 五子棋算法的优化 到目前为止，我们使用传统的Alpha-Beta 搜索结合估值函数的五子棋算法完成一个简单的五子棋对弈程序。虽然估值尽力做到细致、全面，但由于Alpha-Beta 搜索存在博弈树算法中普遍存在的一个缺点随着搜索层数的增加，算法的效率大大下降。所以搜索的效率还是不理想，五子棋程序的“智力”也不高。 因此，在上述基础上，我们继续研究，通过对Alpha-Beta搜索算法的优化与修正，针对五子棋本身的特点和规律，提出采取以下优化措施，显著地提高了五子棋程序对弈的水平和能力。2.2.1 减少搜索范围五子棋棋盘大小为1515，传统算法中计算机每走一步都要遍历整个棋盘，对于棋面上所有空位都进行试探性下子并估值，这样大大影响算法的效率。其实在某个时刻，棋盘上很多的位置都是可以不用去考虑的。2.2.2 设置下棋风格对一个落子估值的时候，首先在己方的角度对其进行评估，获得一个返估值Value_Me；随后在对手的角度再进行一次评估，获得一个估值Value_Enemy；通过Value = K1 *Value_Me + K2 * Value_Enemy 而获得最终的估值结果。其中K1 和K2 是一对关键系数，当K1 / K2 越大的时候，就表示计算机落子的攻击性更强，反之则表示计算机落子考虑较多的是阻断对方的落子，防守性更强些。K1、K2 的值可以由玩家设定，也可以由计算机根据当前棋面自己决定。与传统算法相比，这样得到的五子棋程序更加智能。2.2.3 增大搜索层数理想状态下，为了尽可能提高计算机下棋的“智力”，搜索层数应该越大越好。实际上，由于博弈树异常庞大，搜索层数的增加将会导致算法的效率大大下降。搜索层数。根据已有的资源条件，最有效地进行搜索。2.2.4 使用置换表在Alpha-Beta 搜索过程中，为了避免重复搜索已经搜索过的节点，加快搜索速度，可以使用一张表格记录每一节点的搜索结果，对任意节点向下搜索之前先察看记录在表中的这些结果。如果将要搜索的某个节点在表中已有记录，就直接利用记录下来的结果。我们称这种方法为置换表（Transposition Table,简称TT）。2.2.5 启发式搜索五子棋游戏开局阶段有很多“定式”。将“定式”的格局及其走法当成棋谱保存在数据库中，若发现当前格局存在于棋谱中，则我们不需要搜索，直接按照棋谱下棋，即利用棋谱进行启发式搜索，这样便加快了搜索的速度。该方法的关键是棋谱的模糊匹配以及棋谱的存储结构。第三章 需求分析报告3.1 介绍3.1.1 目的软件需求分析是软件开发周期的第一个阶段，也是关系到软件开发成败的关键一步。对于任何一个软件而言，需求分析工作都是至关重要的一步。只有通过软件需求分析，才能把软件的功能和性能由总体的概念性描述转化为具体的规格说明，进而建立软件开发的基础。实践表明，需求分析工作进行得好坏，在很大程度上决定了软件开发的成败。软件需求分析的任务是：让用户和开发者共同明确将要开发的是一个什么样的软件。具体而言，就是通过对问题及其环境的理解、分析和综合，建立逻辑模型，完成新软件的逻辑方案设计。用户及其开发人员，管理人员通过阅读这份需求分析规格说明书能够了解本系统的开发目的，开发方法以及目前的硬件和软件的情况和开发所需资金和设备，概要设计说明书和完成后续设计与开发工作将在此基础上进一步提出。3.1.2 文档约定 此文档的书写大标题是二号加粗宋体，小标题是四号加粗宋体，正文是小四宋体，1.5倍行距。画图为Visio画图。3.1.3 面向的读者和阅读建议预期的读者相关开发人员，项目经理，营销人员，用户，测试人员，管理人员等。建议序列读取文件,开始的概述部分，然后继续阅读每一类读者相关的部分或者关注的部分。3.1.4 参考文献3.2 整体描述该课程设计在设计与实验过程中需要在windows XP系统/windows 2000以上系统中进行，程序设计要求在visual C+6.0平台中进行，完成代码的编写、编译、调试、测试等工作。本游戏对计算机硬件和操作系统要求极低，所以在这里只是把自己的电脑硬件参数和系统参数列下：操作系统：windows xp软件环境：安装VC+6.03.2.1 功能需求游戏说明：游戏开始时，由红子开局，将一枚棋子落在棋盘一坐标上，然后由黑子落子，如此轮流下子，直到某一方首先在棋盘的竖、横或斜三方向上的五子连成线，则该方该局获胜；选择是否继续下一盘游戏，若继续则重复以上操作，若否则游戏结束。1、功能列表如下：a) 输出棋盘；b) 显示用户行程；c) 判断每局游戏输赢。d) 判断是否进行下一局。e) 退出游戏。用例图 2、功能描述（1）棋盘是19*19的方格棋盘。（2）红子先下，黑子后下，两者交替下子。（3）出现五子相连时则该用户赢。3.2.2 性能需求1、技术可行性运用Windows2000/XP以上的操作系统，SQL SERVER2000的数据库技术，开发以Windows XP为用户的操作平台，界面友善、功能齐全的五子棋双人对战小游戏。2、经济可行性一方面，新系统中棋盘界面和更强劲的功能支持，不仅增加了游戏的趣味性，而且使游戏者更尽兴；另一方面系统开发成本低，现有PC机即可提供该系统开发工作需要的所有硬件设备环境。3、操作可行性操作上是键盘的使用，主要凭借输入坐标确定棋子落子位置，方便简单。使用前只要看明白游戏规则及其方法即可。3.2.3 数据流图 顶层数据流图 2-13.3 系统特点3.3.1 系统特点系统必须满足条件1、红子下完之后黑子才能下。 2、棋子下完后须立即判断是否出现五子相连的情况。 3.3.2 系统功能 该五子棋程序基本上实现了五子棋的游戏功能，有双方下棋的界面及最终判定结果的界面。同时该游戏明了易懂，方便玩家在游戏过程中的基本操作，使游戏更加简便。在细节方面，该系统提供实时存储功能，随时记录为完成的游戏，使用户可以很好的处理意外中断的情况。该游戏基本实现了游戏的一些要求和特征。在游戏的源程序及文档方面，我们也严格遵守软件工程思想，立足实验要求，确定任务，需求分析，设计和编码，每个步骤力求清晰易懂。原代码注释详尽，各功能模块功能分明，可移植性强。3.4 外部接口需求3.4.1 用户界面界面的设计应本着简洁、漂亮、通俗易懂，操作简单，并具有一定的灵活性；尽可能采用开发工具构造界面，使需求定义和设计、编码相衔接；参考、比较成熟的软件的界面的风格，提取有用的设计方法。3.4.2 硬件接口 采用标准的键盘、鼠标控制接口。3.4.3 软件界面 软件组件包括操作系统、数据库、工具、库和集成的商业组建之间的连接，以及应用程序编程接口协议。 这里主要考虑软件与操作系统、数据库管理系统的接口以及局域网和互联网软件之间的数据交换。考虑到文档处理时有可能需要较常用的办公软件。例如Microsoft的Office系列所以应尽量实现它们之间的数据格式的自动转换。3.5 其他非功能需求3.5.1 系统交付日期 人人对战的DEMO必须在十二月十七号交付。3.5.2 系统需求 给游戏引入段位制;输入秘技获得额外的收获等。3.6 软件总流程图否是否否否无有开始棋盘已满红方选择位置判断该位置是否有棋另外找位置红方下一个位置判断红方是否获胜棋盘已满无有黑方选择位置判断该位置是否有棋黑方下一个位置判断黑方是否获胜另外找位置是输出红方获胜是是输出平局输出平局输出黑方获胜结束第四章 设计与实现4.1 基本设计概念和处理流程本软件采用面向对象的设计方案，通过把对弈接口组件化，来实现界面设计与算法设计的完全分离。图1 总处理流程图4.2 结构图2 总体设计结构图4.3 功能设计4.3.1 软件的基本功能设计1.显示一个十九行十九列的五子棋棋盘。2.用鼠标点击棋盘上的交叉点处,则会准确地在该位置显示出棋子。 3.玩家为红方先下棋,可下在任意的地方。 4.可以自动判断游戏是否结束，是否黑方或者是红方已经胜利，并且跳出对话框来提示玩家。 5.在游戏棋盘上方会有一个游戏信息，这个游戏信息是用来提示当前是黑白双方的哪一方下子,玩家可以根据这个提示来下棋，而不会导致不清楚轮到哪一方下棋。 6.可以重新开始游戏，并且有悔棋功能，当某一玩家点击悔棋时会自动跳转到上一个状态，重新落子。4.3.2 软件的附加功能设计1.给软件设计更换棋盘大小的功能，用户可自由选择。2.给软件设计一个更换棋盘背景的功能。3.给软件设计播放背景音乐的功能。4.给软件设计排行榜的功能。4.4 接口设计4.4.1 用户接口用户的所有操作全部通过鼠标或者热键来完成。开始游戏、悔棋、认输和结束游戏这些操作通过点击按钮、右键菜单或使用热键来完成。棋色和水平选择通过点击单选框或右键菜单来完成。游戏中棋子状态将直接反映在棋盘上，其他反馈信息（比如棋盘当前局面、走棋时间、棋谱等信息）将在单独的反馈信息栏中显示。4.4.2 外部接口本程序与其他比赛程序通过裁判程序（有比赛裁判委员会给出）来进行相互通讯，棋盘上落子通过鼠标事件的触发来完成，裁判程序将模拟这一鼠标事件。裁判程序对棋盘状态的获取将直接根据棋盘颜色变化来检测。4.4.3 内部接口TGobangAI组件定义了界面和算法的接口，TGobangAI中聚合了TSearchEngine类的实例FSearchEngine，而TSearchEngine中聚合了TEvaluator的实例FEvaluator。通过这种设计，提高了系统的松散耦合性。4.5 界面设计4.5.1 界面设计运用的主要方法首先用MFC新建的单文档工程，然后用CClientDC画的。进入界面：初始化界面：双发对弈界面：4.6 系统数据结构设计4.6.1 逻辑结构和物理结构设计要点4.6.1.1 基本类型定义/棋色类型TStoneColor = (scRed, /红棋 scBlack); /黑棋/落子点状态类型TPointState = (psRed, /有红棋 psBlack, /有黑棋 psNone, /没有棋 psInvalid); /无效位置/落子点组合类型TPointCombi = (pcSTwo, /眠二 pcSThree, /眠三 pcSFour, /眠四（冲四） pcTwo, /活二 pcThree, /活三 pcFour, /活四 pcFive); /连五/棋盘上的扫描线类型TScanLine = array of TPointState;/棋子间状态描述类型TStonesState = arrayTStoneColor of arrayTPointCombi of Integer;4.6.1.2 估值核心的棋盘数据结构设计FScanLines: array0.95 of TScanLine; /棋盘扫描线FIsValidLine: array0.95 of Boolean; /扫描线有效标志FLinesState: array0.95 of TStonesState; /每根扫描线上的棋子间状态FBoardState: TStonesState; /整个棋盘上的棋子间状态FValidLineCount: Integer; /棋盘上有效扫描线的数量对于估值核心棋盘的表示，重点要考虑的是估值的速度，因此本棋盘采用将1919的棋盘上的横纵斜行都转化为横行的方式来储存，除去斜行上不足5个落子点的行，横纵斜行共有96行，每一行上的棋子数目不同，因此采用动态数组FScanLines来存储。虽然使用动态数组，但是只是在估值核心被初始化时才会分配动态数组的内存，其他情况下不改变此动态数组的内存分配，因此存取效率同静态数组几乎没有差别。另外为了表示每一行上面的棋子组合状态（比如活三、冲四、连五等状态），又定义了96行的数组FLinesState来存贮这些状态，而FboardState汇总了整个棋盘上的棋子组合状态。为了进一步提高棋局判断是否平局的效率，定义了96行的数组FIsValidLine和变量FvalidLineCount。4.6.1.3 搜索引擎的走法数据结构设计FBestMove: TPoint; /记录最好的落子点FEvaluator: TEvaluator; /估值核心FMove: array0.360 of TPoint; /走法数组FScore: array0.360 of Integer; /走法得分数组FHScore: array0.360 of Integer; /历史得分数组FLTPoint: array0.361 of TPoint; /左上边界数组FRBPoint: array0.361 of TPoint; /右下边界数组FCurMove: Integer; /当前走法索引值搜索引擎中棋盘的表示主要是靠调用估值核心FEvaluator的中的棋盘属性来实现的，搜索引擎中更关注的是走法的表示，1919的棋盘上共有361个点，因此采用有361个元算的点类型数组来存贮走法是一种比较直观的方法，采用这种方法的好处是，这个数组被看作一个栈，FCurMove为栈指针，下标小于栈指针的点表示已经走过的点，它们按照所走棋谱的顺序储存，悔棋只需要按照顺序从棋盘上移去，并将FCurMove的值减小即可。而大于等于FCurMove的点表示还未落子和待落子的点，它们将按照历史得分数组FHScore中的历史分数值从大到小进行排列，因为大部分搜索算法都是通过对搜索树进行剪枝来提高搜索速度的，而这种剪枝的效率同搜索节点的排列顺序是有很大关系的，通过历史启发方式来调整搜索节点顺序可以大大的提高搜索最佳落子点FbestMove的命中速度。但是1919的棋盘毕竟还是很大，仅通过调整节点顺序来进行剪枝还是很慢，所以根据五子棋的特点，将搜索范围限制在当前棋盘上所有棋子的最边界再向外延伸两个落子点的范围内就很有必要，因为根据五子棋的特点，超出这个范围，便不会有好的落子点，因此可以不再搜索。通过增加FLTPoint和FBRPoint这两个数组便实现了这一范围的限制。走法得分数组Fscore仅用于返回更有效的反馈信息，对于搜索效率没有提高的作用。4.6.2 数据结构与程序的关系4.6.2.1 估值核心数据结构和程序的关系为了提高估值核心的效率，估值的计算不是通过一次操作来完成的，而是分散到估值核心的多个操作中来完成的。每次落子或悔棋时，都会重新分析落子点或提子点所影响的那四行（横行、纵行和两个斜行）上的棋子组合状态，然后更改整个棋盘的棋子组合状态，这样做就不必到返回估值时在对整个棋盘进行全部扫描，因此极大的提高了估值核心的效率。4.6.2.2 搜索引擎数据结构和程序的关系根据历史得分调整节点顺序是通过排序过程完成的，因为排序也需要时间，所以不宜把排序放到搜索算法中去，但是这样调整节点顺序的机会就少了很多，为了能够更好的调整节点顺序，采用迭代深化是一个好的方法，它将仅进行一次n层搜索转化为从1层到n层渐进的进行n次搜索，每次搜索前