五子棋概要设计说明书

作者 : 马秉尧 张谦 秦永彬

目录 1 引言 1 1.1 编写说明 1 1.2 背景 1 1.3 定义 1 1.4 参考文献 1 2 总体设计 1 2.1 需求规定 1 2.2 运行环境 2 2.3 基本设计概念和处理流程 2 2.4 结构 3 2.5 功能需求与程序的关系 4 2.6 尚未解决的问题 4 3 接口设计 5 3.1 用户接口 5 3.2 外部接口 5 3.3 内部接口 5 4 系统数据结构设计 5 4.1 逻辑结构和物理结构设计要点 5 4.1.1 基本类型定义 5 4.1.2 估值核心的棋盘数据结构设计 6 4.1.3 搜索引擎的走法数据结构设计 6 4.2 数据结构与程序的关系 7 4.2.1 估值核心数据结构和程序的关系 7 4.2.2 搜索引擎数据结构和程序的关系 7 5 系统出错处理设计 7

1 引言 1.1 编写说明本说明书提供了五子棋各个模块的概要设计说明, 以供软件工程师和编码人员进行详细 设计与具体实现 1.2 背景软件名称 : 五子棋 开发人员所在原校 : 济南大学信息学院 开发人员列表 : 马秉尧 衣明志 王久元 张谦 王旻煜 秦永彬 预定完成日期 :2003 年 5 月 1.3 定义禁守 : 对局中禁止使用的战术或被判负的行棋手段 长连 : 相同颜色相连的六子或六子以上 搜索 : 通过对博弈树进行完全遍历或者部分遍历找出一个最好或者较好落子点的过程 估值 : 通过既有的棋类知识来评估一个局面优劣的过程 委托 : 一种组合方法, 它使组合具有与继承同样的复用能力, 在委托方式下, 有两个对象参与处理一个请求, 接受请求的对象将操作委托给它的代理者 聚合 : 一个对象拥有另一个对象或对另一个对象负责, 一般我们称一个对象包含另一个对象或者是另一个对象的一部分 1.4 参考文献 [1] 王小春. PC 游戏编程 ( 人机对弈 ). 重庆 : 重庆大学出版社,2002.5 [2] 那威, 张照元. 连珠五子棋提高捷径 : 入段升级必读. 北京 : 北京体育大学出版社, 1998.1 [3] Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. 设计模式 : 可复用面 向对象软件的基础北京 : 机械工业出版社,2000.9 [4] Donald E. Knuth. The Art of Computer Programming. Addison-Wesley,1998 2 总体设计 2.1 需求规定 棋盘采用 19 19 标准围棋棋盘 游戏采用人机对弈模式, 可以选择任何一方执黑先行 游戏中没有禁守规则和其他走子限制 只有当连五以后才判为获胜, 长连也算获胜 - 1 -

软件禁止采用模式匹配的设计方法 ( 即不允许在软件中存有大量已有的棋谱和算法 ) 电脑走一步棋所花费的时间尽量控制在 20 秒之内 棋盘颜色与棋子颜色要对比分明, 便于其他程序识别 游戏中可以显示游戏状态的信息, 但是不能有弹出对话框之类的窗口挡住棋盘 允许悔棋, 认输, 结束并重新开始游戏 2.2 运行环境硬件配置 ( 推荐 ): CPU:P4 1GHZ 或更高 内存 :128M 或更多 显示器分辨率 :800x600 或更高 运行本软件的系统平台 : Windows 9x Windows Me Windows 2000 Windows XP Windows 2003 开发工具 : Delphi 7 2.3 基本设计概念和处理流程本软件采用面向对象的设计方案, 通过把对弈接口组件化, 来实现界面设计与算法设计 的完全分离 游戏界面只与对弈接 口进行相互通讯, 与使 用的博弈算法无关 搜索算法引擎通过递 归调用估值算法核心 来找出最佳落子点 游戏 对弈 搜索 估值 程序 接口 算法 算法 界面 组件 引擎 核心 对弈接口组件将具体 的博弈算法封装成可 以与界面交互的接口 图 1 总体处理流程图 - 2 -

2.4 结构 TBestMove BestMove GobangAI TGobangAI Board [X, Y] SearchEngine TSearchEngine Board [X, Y] Evaluator Move[Index] Move[Index] Score[Index] Score[Index] CurMove CurMove TGobangForm GobangAI StoneColor Level Winner IsGameOver IsStart GetBestMove(Depth) AddStone(X, Y) GiveUp TEvaluator GoBack Board [X, Y] Start IsDraw Stop GetScore(StoneColor) 图 2 总体设计结构图 表 1 类模块列表 类标识符 类名 功能 TGobangForm 五子棋 它是程序界面设计部分的实现, 它主要负责界面的绘制, 而真正 主程序 的人机对弈操作委托 GobangAI 来完成 窗体类 TGobangAI 五子棋对弈接口类 它定义了完成人机对弈的操作接口, 这样主窗体类可以通过这些操作接口来完成人机对弈的过程 而实际这些操作的实现是通过桥接的方式委托搜索引擎 SearchEngine 来完成的 TBestMove 最佳走法的线程类 它是通过委托 TGobangAI 实例中的 SearchEngine 对象的 GetBestMove 操作来找出当前电脑的最佳走法 而它本身却是在 TGobangAI 中被实例化并被调用的 TSearchEngine 搜索引擎类 在它当中定义了搜索算法所需要的数据结构和操作, 而搜索算法中的核心操作是委托估值核心 Evaluator 来完成的 TEvaluator 估值核 心类 在它当中定义了估值核心所需要的数据结构和操作, 并实现了估 值核心 属性操作标识符所属类 表 2 各个类中的属性和操作列表 功能 Board TGobangAI 返回指定位置落子状态, 委托 SearchEngine 实现 Move TGobangAI 返回所指定的步数的走法, 委托 SearchEngine 实现 Score TGobangAI 返回所指定步数的走法得分, 委托 SearchEngine 实现 CurMove TGobangAI 返回当前走法索引, 委托 SearchEngine 实现 StoneColor TGobangAI 设定或返回电脑的棋色 - 3 -

Level TGobangAI 设定或返回电脑的棋力水平值 IsStart TGobangAI 返回游戏是否开始 AddStone TGobangAI 玩家下子, 如果玩家未赢, 则紧跟着电脑下子 GiveUp TGobangAI 玩家认输 GoBack TGobangAI 玩家悔棋, 棋局退回到玩家下最后一颗子之前的状态 Start TGobangAI 开始游戏, 开局后, 棋色和棋力属性将不能再改变 Stop TGobangAI 结束游戏, 游戏结束后, 棋色和棋力属性可以改变 Board Move Score CurMove Winner IsGameOver GetBestMove TSearchEngine 返回或设定指定位置落子状态, 委托 Evaluator 实现 TSearchEngine 返回所指定的步数的走法 TSearchEngine 返回所指定的步数的走法得分 TSearchEngine 返回当前走法索引 TSearchEngine 返回获胜者 TSearchEngine 返回游戏是否结束 TSearchEngine 返回最佳走法 Board TEvaluator 返回或设定指定位置落子状态 IsDraw TEvaluator 返回是否平局 GetScore TEvaluator 返回棋局估值 上面所列出的属性和操作仅为 public 的属性和操作,private 的变量 属性和操作这里没有给出定义, 它们将在接口设计和系统数据结构设计中进行讨论 另外 TGobangAI 是一个组件类, 其中定义了三个比较特殊的事件属性, 通过这三个事件, 可以使界面设计更加灵活方便, 这三个事件的功能在下表中给出 : 表 3 TGobangAI 组件中的事件定义列表 事件 OnGameStart OnChange OnGameOver 描述 游戏开始事件 游戏中棋盘状态改变所触发的事件 游戏结束事件 2.5 功能需求与程序的关系 TGobangForm TGobangAI TSearchEngine TEvaluator 界面 界面算法接口 算法 2.6 尚未解决的问题因为博弈算法中搜索引擎的改进是影响整个游戏智能化程度的关键, 但是搜索算法有很多, 现在还不能确定哪种搜索算法更适合于本游戏, 这些算法的测试将在详细设计和编码调试时再进行 - 4 -

3 接口设计 3.1 用户接口用户的所有操作全部通过鼠标或者热键来完成 开始游戏 悔棋 认输和结束游戏这些 操作通过点击按钮 右键菜单或使用热键来完成 棋色和水平选择通过点击单选框或右键菜 单来完成 游戏中棋子状态将直接反映在棋盘上, 其他反馈信息 ( 比如棋盘当前局面 走棋 时间 棋谱等信息 ) 将在单独的反馈信息栏中显示 3. 2 外部接口本程序与其他比赛程序通过裁判程序 ( 有比赛裁判委员会给出 ) 来进行相互通讯, 棋盘上落子通过鼠标事件的触发来完成, 裁判程序将模拟这一鼠标事件 裁判程序对棋盘状态的获取将直接根据棋盘颜色变化来检测 3. 3 内部接口 TGobangAI 组件定义了界面和算法的接口,TGobangAI 中聚合了 TSearchEngine 类的实例 FSearchEngine, 而 TSearchEngine 中聚合了 TEvaluator 的实例 FEvaluator 通过这种设计, 提高了系统的松散耦合性 4 系统数据结构设计 4.1 逻辑结构和物理结构设计要点 4.1.1 基本类型定义 : // 棋色类型 TStoneColor = (scblack, // 黑棋 scwhite); // 白棋 // 落子点状态类型 TPointState = (psblack, pswhite, psnone, // 有黑棋 // 有白棋 // 没有棋 psinvalid); // 无效位置 // 落子点组合类型 TPointCombi = (pcstwo, pcsthree, // 眠二 // 眠三 pcsfour, // 眠四 ( 冲四 ) pctwo, pcthree, pcfour, pcfive); // 活二 // 活三 // 活四 // 连五 // 棋盘上的扫描线类型 TScanLine = array of TPointState; - 5 -

// 棋子间状态描述类型 TStonesState = array[tstonecolor] of array[tpointcombi] of Integer; 4. 1.2 估值核心的棋盘数据结构设计 : FScanLines: array[0..95] of TScanLine; // 棋盘扫描线 FIsValidLine: array[0..95] of Boolean; // 扫描线有效标志 FLinesState: array[0..95] of TStonesState; // 每根扫描线上的棋子间状态 FBoardState: TStonesState; // 整个棋盘上的棋子间状态 FValidLineCount: Integer; // 棋盘上有效扫描线的数量对于估值核心棋盘的表示, 重点要考虑的是估值的速度, 因此本棋盘采用将 19 19 的棋盘上的横纵斜行都转化为横行的方式来储存, 除去斜行上不足 5 个落子点的行, 横纵斜行共有 96 行, 每一行上的棋子数目不同, 因此采用动态数组 FScanLines 来存储 虽然使用动态数组, 但是只是在估值核心被初始化时才会分配动态数组的内存, 其他情况下不改变此动态数组的内存分配, 因此存取效率同静态数组几乎没有差别 另外为了表示每一行上面的棋子组合状态 ( 比如活三 冲四 连五等状态 ), 又定义了 96 行的数组 FLinesState 来存贮这些状态, 而 FboardState 汇总了整个棋盘上的棋子组合状态 为了进一步提高棋局判断是否平局的效率, 定义了 96 行的数组 FIsValidLine 和变量 FvalidLineCount 4. 1.3 搜索引擎的走法数据结构设计 FBestMove: TPoint; // 记录最好的落子点 FEvaluator: TEvaluator; // 估值核心 FMove: array[0..360] of TPoint; // 走法数组 FScore: array[0..360] of Integer; // 走法得分数组 FHScore: array[0..360] of Integer; // 历史得分数组 FLTPoint: array[0..361] of TPoint; // 左上边界数组 FRBPoint: array[0..361] of TPoint; // 右下边界数组 FCurMove: Integer; // 当前走法索引值搜索引擎中棋盘的表示主要是靠调用估值核心 FEvaluator 的中的棋盘属性来实现的, 搜索引擎中更关注的是走法的表示,19 19 的棋盘上共有 361 个点, 因此采用有 361 个元算的点类型数组来存贮走法是一种比较直观的方法, 采用这种方法的好处是, 这个数组被看作一个栈,FCurMove 为栈指针, 下标小于栈指针的点表示已经走过的点, 它们按照所走棋谱的顺序储存, 悔棋只需要按照顺序从棋盘上移去, 并将 FCurMove 的值减小即可 而大于等于 FCurMove 的点表示还未落子和待落子的点, 它们将按照历史得分数组 FHScore 中的历史分数值从大到小进行排列, 因为大部分搜索算法都是通过对搜索树进行剪枝来提高搜索速度的, 而这种剪枝的效率同搜索节点的排列顺序是有很大关系的, 通过历史启发方式来调整搜索节点顺序可以大大的提高搜索最佳落子点 FbestMove 的命中速度 但是 19 19 的棋盘毕竟还是很大, 仅通过调整节点顺序来进行剪枝还是很慢, 所以根据五子棋的特点, 将搜索范围限制在当前棋盘上所有棋子的最边界再向外延伸两个落子点的范围内就很有必要, 因为根据五子棋的特点, 超出这个范围, 便不会有好的落子点, 因此可以不再搜索 通过增加 FLTPoint 和 FBRPoint 这两个数组便实现了这一范围的限制 走法得分数组 Fscore 仅用于返回更有效的反馈信息, 对于搜索效率没有提高的作用 - 6 -

4.2 数据结构与程序的关系 4.2.1 估值核心数据结构和程序的关系为了提高估值核心的效率, 估值的计算不是通过一次操作来完成的, 而是分散到估值核心的多个操作中来完成的 每次落子或悔棋时, 都会重新分析落子点或提子点所影响的那四行 ( 横行 纵行和两个斜行 ) 上的棋子组合状态, 然后更改整个棋盘的棋子组合状态, 这样做就不必到返回估值时在对整个棋盘进行全部扫描, 因此极大的提高了估值核心的效率 4. 2.2 搜索引擎数据结构和程序的关系根据历史得分调整节点顺序是通过排序过程完成的, 因为排序也需要时间, 所以不宜把排序放到搜索算法中去, 但是这样调整节点顺序的机会就少了很多, 为了能够更好的调整节点顺序, 采用迭代深化是一个好的方法, 它将仅进行一次 n 层搜索转化为从 1 层到 n 层渐进的进行 n 次搜索, 每次搜索前都根据上一次搜索得到的历史得分来调整节点顺序以便进行更深一层的搜索 这样表面上看是进行了更多的搜索, 而实际情况却是深层搜索比浅层搜索的节点多的多, 多进行的那些浅层搜索对于深层的搜索可以忽略不计, 而浅层搜索得到的历史得分更好的调整了节点的顺序, 使得深层搜索的剪枝效率大大提高, 因此实际搜索的节点数大大地减少了, 搜索的速度也就提高了 5 系统出错处理设计 因为本软件设计比较精巧, 在与用户的交互上不需要用户通过键盘键入信息, 因此出错机会几乎为零, 因为病毒或者操作系统重要文件损坏等所造成的错误不应归咎于本软件, 本软件也没有义务去处理这些错误, 因此本软件没有设计出错信息提示和出错处理 - 7 -