Word版可编辑-基于VisualC的五子棋设计与实现精心整理.doc

太原科技大学太原科技大学 毕毕 业业 设设 计 论计 论 文 文 设计设计 论文论文 题目 题目 基于 Visual C 的五子棋设计与实现 姓姓 名名 陈磊陈磊 学院 系 学院 系 电子信息工程系电子信息工程系 专专 业业 通信工程通信工程 年年 级级 通信通信 082201H 082201H 指导教师指导教师 司秉楠司秉楠 20122012 年年 6 6 月月 1414 日日 太原科技大学毕业设计 论文 任务书太原科技大学毕业设计 论文 任务书 学院 直属系 电子信息工程系 时间 2012 年 1 月 14 日 学 生 姓 名陈磊指 导 教 师司秉楠 设计 论文 题目基于 Visual C 的五子棋设计与实现 主要研 究内容 学习 C 编程语言 在 Visual C 6 0 环境中实现五子棋的设计 研究方法 通过 Visual C 6 0 编写程序和编译程序 并成功运行五子棋游 戏 实现五子棋的相关功能 主要技术 指标 或研 究目标 1 掌握 Visual C 6 0 的应用 并进行程序的编译和运行 2 编写五子棋的相关程序 以实现五子棋的走棋 悔棋 判断输赢 英雄榜记录等功能 教研室 意见 教研室主任 专业负责人 签字 年 月 日 说明 一式两份 一份装订入学生毕业设计 论文 内 一份交学院 直属系 太原科技大学华科学院毕业设计 论文 目录 摘要 ABSTRACT 第 1 章 绪论 1 1 1 课题背景 1 1 2 五子棋介绍 1 1 3 目的和意义 2 1 4 系统设计思想 3 1 5 开发工具简介 3 第 2 章 可行性研究与算法分析 5 2 1 本系统的可行性研究 5 2 2 算法分析 6 2 2 1 博弈树 6 2 2 2 极大极小值算法 7 2 2 3 负极大值算法 8 2 2 4 ALPHA BETA 搜索 8 2 2 5 置换表 9 2 2 6 哈希表 10 2 2 7 历史启发 11 2 3 本章小结 12 第 3 章 总体设计 13 3 1 总体设计过程 13 3 2 系统的数据结构设计 13 3 2 1 系统的数据结构设计 13 3 2 2 系统的算法设计 14 3 3 系统模型设计 15 3 4 本章小结 16 第 4 章 详细设计 17 太原科技大学华科学院毕业设计 论文 4 1 系统运行平台设计 17 4 2 系统的程序流程图 17 4 3 系统主要功能的实现 18 4 3 1 新局 18 4 3 2 菜单及提示 20 4 3 3 游戏结束 23 4 3 4 英雄榜 24 4 4 本章小结 26 第 5 章 系统测试 27 5 1 系统软件测试 27 结论 30 致谢 32 参考文献 33 附录 34 太原科技大学华科学院毕业设计 论文 摘要 自从计算机作为游戏对战平台以来 各种棋类游戏如雨后春笋般纷纷冒出 使得那 些喜爱下棋 又常常苦于没有对手的棋迷们能随时过足棋瘾 而五子棋游戏由于其规则 简单 变化多端 深受大众喜爱 五子棋不仅能增强人们的抽象思维能力 逻辑推理能力 空间想象力 提高人们的 记忆力 心算能力等 而且深含哲理 有助于修身养性 它既有简单易学的特点 为人 民群众所喜闻乐见 又有深奥的技巧 既能组织群众性的比赛 活动 又能举办高水平 的国际性比赛 基于五子棋游戏以上的优点 开发五子棋是一个非常有价值的课题 本系统具有功 能齐全 简单易学 既动手又动脑的特点 尤其是游戏的同时 还有声音效果的配合 使游戏更加富有趣味性和消遣性 本系统基于 Visual C 6 0 软件 主要应用估值函数 负极大值搜索算法 Alpha Beta 剪枝等算法来完成人机对弈功能的实现 本系统的成功 开发 能够使人们的日常娱乐生活更加丰富多彩 关键词 五子棋 国际性比赛 人机对弈 Visual C 6 0 太原科技大学华科学院毕业设计 论文 太原科技大学华科学院毕业设计 论文 Abstract Since the computer as a game platform various board games have mushroomed out Makes those who love chess and often do not have the Jimi opponents will be able to keep a full game addiction Gobang game and its rules are simple making love by the public Gobang can not only enhance people s ability to abstract thinking logical reasoning spatial imagination and enhancing people s memory mental arithmetic ability but also with deep philosophical self help and support It has easy to learn the characteristics of the eye and ear other esoteric skills Can organize the masses of competitions activities but also organized a high level of international competition Gobang game based on the merits of the above the development of Gobang is a very valuable subject The system is fully functional easy to learn hands and both mental and physical characteristics Especially games at the same time there are sound effects with them to games more interesting and full of fun Application of this system is mainly valuation function the negative Maxima search algorithm such as Alpha Beta search algorithm to complete the function of the realization of human chessboard The successful development of the system will enable people s daily life more colorful entertainment Key words Gobang International Competition Human Chessboard Visual C 6 0 太原科技大学华科学院毕业设计 论文 太原科技大学华科学院毕业设计 论文 1 基于 Visual C 的五子棋设计与实现 第 1 章 绪论 1 1 课题背景 计算机技术的发展 使得计算机在现代企业 家庭中得以普及 应用计算 机成为现代人生活中非常重要的一部分 大到政府办公 教育事业 商业活动 小到生活中的每一个细节 随着社会进步的节奏越来越快 人们的生活压力也 越来越大 每天奔波于不同的目的地 忙得没有时间和朋友见面 忙得想找个 释放压力的机会都没有 这个时候 你是不是非常希望有个游戏 能够陪你轻 松愉快度过周末 自从计算机作为游戏对战平台以来 各种棋类游戏如雨后春 笋般纷纷冒出 使得那些喜爱下棋 又常常苦于没有对手的棋迷们能随时过足 棋瘾 而且这类软件大都水平颇高 大有与人脑分庭抗礼之势 其中战胜过国 际象棋世界冠军 卡斯帕罗夫的 深蓝 便是最具说服力的代表 五子棋是一种 受大众广泛喜爱的游戏 其规则简单 变化多端 非常富有趣味性和消遣性 同时具有简单易学 既动手又动脑的特点 1 2 五子棋介绍 五子棋是起源于中国古代的传统黑白棋种之一 现代五子棋日文称之为 连珠 英译为 Renju 英文称之为 Gobang 或 FIR Five In a Row 的 缩写 亦有 连五子 五子连 串珠 五目 五目碰 五格 等多 种称谓 相传早在尧造围棋之前 五子棋游戏在民间已经相当盛行了 据 增 山海经 中记载 休舆之山有石焉 名曰帝台之棋 五色而文状鹑卵 辞 海 中亦言 五子棋中棋类游戏 棋具与围棋相同 两人对局 轮流下子 先将五子连成一行者为胜 唐时由高丽使者带到高丽 后来辗转反复 流传到 日本 起先是在日本皇宫内盛行的游戏 只限于王室成员 贵族阶层之间的对 弈 后来据说被出入皇宫的挑夫看见 由此便流行民间 五子棋起源于古代中国 发展于日本 风靡于欧洲 对于它与围棋的关系 太原科技大学华科学院毕业设计 论文 2 有两种说法 一种说法是早于围棋 早在 尧造围棋 之前 民间就已有五子 棋游戏 另一说法是源于围棋 是围棋发展的一个分支 在中国的文化里 倍 受人们的青睐 古代的五子棋的棋具与围棋相同 纵横各十七道 五子棋大约 随围棋一起在我国南北朝时先后传入朝鲜 日本等地 据日本史料文献介绍 中国古代的五子棋是经由高丽 朝鲜 于 1688 年至 1704 年的日本元禄时代传 到日本的 到日本明治 32 年 公元 1899 年 经过公开征名 连珠 这一名称 才被正式确定下来 取意于 日月如合壁 五星如连珠 从此 连珠活动经过 了不断的改良 主要是规则的变化 即对执黑棋一方的限制 例如 1899 年规 定 禁止黑白双方走 双三 1903 年规定 只禁止黑方走 双三 1912 年规定 黑方被迫走 双三 亦算输 1916 年规定 黑方不许走 长连 1918 年规定 黑方不许走 四 三 三 1931 年规定 黑方不许走 双 四 并规定将 19 19 的围棋盘改为 15 15 的连珠专用棋盘 本世纪初五子棋传入欧洲并迅速风靡全欧 通过一系列的变化 使五子棋 这一简单的游戏复杂化 规范化 而最终成为今天的职业连珠五子棋 同时也 成为一种国际比赛棋 现代五子棋 连珠 的基本下法是 先由执黑棋一方将一枚棋子落在天元 点上 为了尊重对方和出于礼貌 持白棋的一方通常将盘面的第二手棋布在天 元下方周围 1 3 目的和意义 五子棋游戏不仅能增强人们的抽象思维能力 逻辑推理能力 空间想象力 提高人们的记忆力 心算能力等 而且深含哲理 有助于修身养性 五子棋既 有现代休闲方式所特有的特征 短 平 快 又有中国古典哲学所包含的高 深学问 阴阳易理 它既有简单易学的特点 为人民群众所喜闻乐见 又有 深奥的技巧 既能组织举办群众性的比赛 活动 又能组织举办高水平的国际 性比赛 它的棋文化源渊流长 具有东方的神秘和西方的直观 它是中西方文 化的交融点 也是中西方文化交流的一个平台 五子棋的根在中国 在这个国境里 他有着广泛的群众基础 但与世界先 进的五子棋技术相比 我们的棋艺水平还要继续提高 所以我们要推广五子棋 太原科技大学华科学院毕业设计 论文 3 宣传五子棋 争取在较短的时间内赶上和超过世界五子棋坛的先进水平 在这 种环境下 开发一个易学实用的五子棋游戏软件是很有必要的 中国作为五子棋的发源国 要对五子棋在下个世纪的发展起到世界性的推 动作用 五子棋的发展在中国出现方兴未艾 星火燎原之势 同时还有一大批 的中生代棋手和充满希望的 明日之星 相信 中国棋手攀登五子棋巅峰的日 子会早日来到 1 4 系统设计思想 一个优秀的游戏软件 必须有一个正确的设计思想 通过合理地选择数据 结构 操作系统以及开发环境 构成一个完善的体系结构 才能充分发挥计算 机应用的优势 根据游戏玩家的实际需求 本系统的设计按照下述原则进行 1 实用性 系统以用户需求为目标 以方便用户为原则 同时融入先进 的设计思想 根据用户实际的需求情况 量身制作一个功能齐全 操作简单 实用性强的游戏软件 充分满足游戏玩家的需求 真正成为为玩家提供轻松 娱乐 休闲的工具 2 先进性 本软件将充分应用现有成熟的计算机技术 软件开发技术 为用户提供高性能的系统 可以方便的实现玩家的需要 3 高可靠性 一个实用的系统同时必须是可靠的 本系统通过合理而先 进的结构设计以及软 硬件的优化选型 可保证系统的可靠性与容错性 4 可维护性 系统的设计要求方便维护 包括硬件的维护 软件的维护 更改 升级等 5 可扩展性及灵活性 系统的设计以方便未来业务的扩展和系统扩充为 目标 系统要求能够方便的升级 充分保护系统的投资 玩家可以根据自己的 需要 灵活设置自己的游戏 6 智能性 智能化是这个游戏软件的一大特色 系统在设计时 充分考 虑系统运行的智能性 如果有充足的时间改进 计算机就可以实现更高的 AI 在游戏中走的每一步就会考虑得更周密 1 5 开发工具简介 Visual C 6 0 是 Microsoft 公司开发的基于 C C 的面向对象的可视化集成 太原科技大学华科学院毕业设计 论文 4 开发工具 它是 Visual Studio 中功能最为强大 代码效率最高的开发工具 Visual C 6 0 与以前的版本相比有了多方面的改进 它的编译器 调试器 连 接器 编辑器 资源编辑器都有所加强 在编辑器中还提供了自动语句生成功 能 编辑器会像 Visual Basic 一样自动提示函数的参数 对象的成员 另外 Visual C 6 0 还提供了很多向导 MFC 提供了一些新的类 提供了更强大的 数据访问功能 用户可利用 Visual C 6 0 以两种方式编写 Win32 应用程序 一种方式是基于 Windows API 的 C 编程方式 另一种是基于 MFC 的 C 编程 方式 Visual C 6 0 的主要特点如下 Visual C 6 0 的最大特色就是提供面向对象技术的支持 它利用类把大 部分与用户界面设计有关的 Windows API 函数封装起来 通过 MFC Microsoft Foundation Class 类库的方式提供给开发人员使用 大大提高了程序代码的重 用性 Visual C 6 0 提供一个功能强大的应用程序生成向导 AppWizard 这 也是其得意之处 有了 AppWizard 用户将不会为创建繁琐的初始化代码而苦 恼 AppWizard 将帮助 MFC 类库的用户自动生成一个运行程序框架 一个空 的不能做任何事情的应用程序 而用户只需要在该框架的适当部分添加扩充代 码就可以得到一个满意的应用程序 Visual C 6 0 的另一个强大工具就是 Class Wizard 用户通过它能够方便 而有效地使用和管理 MFC 类库 以前 继承和派生一个类是一件很麻烦的事 而现在简单了 只需在 Class Wizard 中指定一些必要信息 Visual C 6 0 将自 动为你生成类的框架和代码 Visual C 6 0 利用 所见即所得 的方式完成程序界面的设计 大大减轻了 程序设计人员的劳动强度 提高了开发效率 Visual C 6 0 的功能强大 用途广泛 不仅可以编写普通的应用程序 还 能很好的进行系统及通信软件的开发 太原科技大学华科学院毕业设计 论文 5 第 2 章 可行性研究与算法分析 2 1 本系统的可行性研究 本系统要实现的目标 作为一个悠闲的小游戏软件 首先应该为用户提供 一套方便的操作方法 在游戏模式 用户操作 反馈信息方面应该有明确的说 明 能够让大多数玩家能快速上手 使该游戏看上去是一款悠闲的精品 本系统的流程图描述如下 玩家在新开局后 可以设置本局游戏 包括对 弈模式 游戏级别 中英文菜单 声音效果等进行设置 即初始化棋盘 初始 化棋盘完成后 玩家和计算机就可以在分析了当前棋局以后下棋 即对弈阶段 在玩家和计算机每下了一手棋以后 都会进行胜负的判断 如有胜负 则结束 此局游戏 如果此局玩家的成绩比英雄榜里的成绩更好 则把玩家的姓名和成 绩记录到英雄榜中 覆盖原来的玩家名和成绩 本游戏软件的系统流程图 如图 2 1 所示 新新 开开 局局 初初始始化化棋棋盘盘 对对 弈弈 胜胜 负负 判判 断断 英英 雄雄 榜榜 图 2 1 系统流程图 本系统是一款休闲的小游戏 是人们日常生活娱乐的工具 只要针对大众 的喜好 使系统功能齐全 操作简单 界面美观大方 就一定会有市场潜力 太原科技大学华科学院毕业设计 论文 6 根据该系统目标来衡量所需的技术是否具备 一般可从软硬件的性能要求 环 境条件 操作人员水平和数量等方面去考虑和分析 考虑到系统实施的可行性 在软件方面选择了性能稳定的 VC 6 0 开发环 境 C 语言来进行开发 VC 是非常成熟的开发工具 因此无论在安全性 可用性及可靠性等方面都毫无置疑 因此软件方面是可行的 在硬件方面 则选择空间较大 只要是 Pentium III 系列及以上的计算机 内存在 256M 以上 硬盘在 1GB 都可以满足系统的开发需要 当然 硬件的 配置越高 系统的开发与运行会更流畅 考虑到如今的家用或商用电脑硬件的 整体配置水平 系统在硬件方面是可行的 2 2 算法分析 五子棋游戏的开发在搜索算法方面 可以有多种选择 通过从不同的角度 分析各种搜索方法的效率 来考虑本系统的算法应用 开局时计算机每走一步 的平均耗时 ms 如表 2 1 所示 表 2 1 各种算法每走一步平均耗时 ms 通过上表 可以看出使用置换表技术和历史启发技术可以增强搜索效率 综合分析表中几种算法的效率 本系统按照计算机下每一手棋所应用的算法的 大致顺序 采用的主要算法有博弈树 负极大值算法 Alpha Beta 剪枝算法 置换表技术 哈希表技术 历史启发等 下面详细地介绍一下这些算法 太原科技大学华科学院毕业设计 论文 7 2 2 1 博弈树 设想下五子棋的情形 两人对弈 我们将其中一位叫做甲 另一位叫做乙 假定现在该甲下棋 甲可以有 225 种走法 不论好坏 而对甲的任一走法 乙 也可以有与之相对的若干种下法 然后又轮到甲走棋 对乙的下法甲又有若干 种方法应对 如此往复 显然 我们可以依此构建一棵博弈树 将所有的走法 罗列出来 在这棵树的根部是棋局的初始局面 根的若干子节点则是由甲的每 一种可能走法所生成的局面 而这些节点的子节点则是由与之相对的乙的每一 种可能走法所生成的局面 在这棵树的末梢 是结束的棋局 甲胜或者乙胜或 者是双方都无法取胜的平局 如果我们令甲胜的局面值为 WIN 乙胜的局面值 为 LOST 而和局的值为 DRAW 当轮到甲走时 甲定会选择子节点值为 WIN 或 DRAW 如果没有值为 WIN 的子节点的话 的下法 而轮到乙时 乙则会 选择子节点值为 LOST 或 DRAW 如果没有值为 LOST 的子节点的话 的下法 对于中间节点的值可以有如下计算方法 如果该节点所对应的局面轮到甲下棋 则该节点的值是其所有子节点中值最佳 对甲而言 的一个的值 如果该节点 所对应的局面轮到乙走棋 则该节点的值是其所有子节点中值最差 对甲而言 的一个的值 这样看来从这棵树的叶子节点倒推向根部 就可以得出所有节点 的值 双方就可以从其所面临的棋局中选择一步好棋 然后一步步走向胜利 博弈树是从根部向下递归产生的一棵包含所有可能的对弈过程的搜索树 这里 称为完全搜索树 Neill Graham 形容此过程类似于在一个状态图中寻求从初始 状态通向终了状态的过程 只是状态图搜索仅有一个主体参加 仅是单方面做 出的路径选择 而博弈树的搜索则有对立的双方参加 一方只能做出一半选择 而这一半选择的目的是使对方远离其竭力靠近的目标 也就是说状态图搜索是 纯粹的或树 OR tree 而博弈树搜索是与或树 AND OR tree 但是在五子棋游戏中 我们没有建立完全搜索树的可能 一方面是因为很 多情形根本就到达不了叶子节点 另一方面 这棵树上的节点数量也已多到了 无法处理的程度 所以我们需要其它的算法来减少搜索的数量 2 2 2 极大极小值算法 Minimax Algorithm 在上面的博弈树中 如果我们令甲胜的局面值为 1 乙胜的局面值为 1 而 和局的值为 0 当轮到甲下棋时 甲定会选择子节点值最大的下法 而轮到乙 太原科技大学华科学院毕业设计 论文 8 时 乙则会选择子节点值最小的下法 所以 对于中间节点的值可以有如下计 算方法 如果该节点所对应的局面轮到甲下棋 则该节点的值是其所有子节点 中值最大的一个的值 而如果该节点所对应的局面轮到乙下棋 则该节点的值 是其所有子节点中值最小的一个的值 对博弈树的这个变化仅仅是形式上的 本质上丝毫未变 但是这个形式更 容易推广以运用到一般实际的情形 既然建立整棵的搜索树不可能 那么 为当前所面临的局面找出一步好棋 如何 也就是通过少量的搜索 为当前局面选择一步较好的走法 在通常的棋局当中 一个局面的评估往往并不像输 赢 平 3 种状态这么 简单 在分不出输赢的局面中棋局也有优劣之分 也就是说 要用更细致的方 法来刻画局面的优劣 而不是仅仅使用 1 1 0 三个数字刻画 3 种终了局面 假定我们有一个函数可以为每一局面的优劣评分 例如甲胜为 乙胜为 和局为 0 这样我们可以建立一棵固定深度的搜索树 其叶子节点不必是终了 状态 而只是固定深度的最深一层的节点 其值由上述函数评出 对于中间节 点 如同前面提到的那样 甲方取子节点的最大值 乙方取子节点的最小值 这个评分的函数称作静态估值函数 Static Evaluation Function 用以取代超出 固定深度的搜索 显然 我们无法拥有绝对精确的静态估值函数 否则 只要 这个静态估值函数就可以解决所有的棋局了 估值函数给出的只是一个较粗略 的评分 在此基础上进行的少量搜索的可靠性 理论上是不如前述的 WIN LOST DRAW 三种状态的博弈树的 但这个方法却是可实现的 利用 具体的知识构成评估函数的搜索叫做启发式搜索 Heuristic Search 估值函数 在有些文献中也称为启发函数 Heuristic Function 在博弈树搜索的文献当中 极大极小方法往往指的是基于静态估值函数的 有限深度的极大极小搜索 MinMax 算法是对弈的基础思想 2 2 3 负极大值算法 Negamax Algorithm 普通的极大极小值算法看起来有一点笨 既然一方试图取极大值而另一方 试图取极小值 也就是说 我们总要检查哪一方要取极大值而哪一方又要 取极小值 以执行不同的动作 Knuth 和 Moore 在 1975 年提出了负极大值 Negamax 方法 消除了两方的差别 而且简洁优雅 使用负极大值方法 太原科技大学华科学院毕业设计 论文 9 博弈双方都取极大值 2 2 4 Alpha Beta 搜索 在极大极小搜索的过程中 存在着一定程度的数据冗余 举一个最简单的 例子 在象棋博弈的过程中 如果某一个节点轮到甲走棋 而甲向下搜索节点 时发现第一个子节点就可以将死乙 节点值为最大值 则剩下的节点就无需再 搜索了 甲的值就是第一个子节点的值 这个过程 就可以将大量冗余的 不 影响结果的 节点抛弃 A BC FED A C DE B F 18 18 8 16 alpha剪剪枝枝示示例例 beta剪剪枝枝示示例例 取取极极小小值值的的节节点点取取极极大大值值的的节节点点 图 2 2A lpha Beta 剪枝示例图 将上述这个情形推广一下 设想有如图 2 1 左半部所示的一棵极大极小树 的片断 节点下面数字为该节点的值 节点 B 的值为 18 节点 D 的值为 16 由此我们可以判断节点 C 的值将小于等于 16 取极小值 而节点 A 的值为节 点 Max B C 为 18 也就是说不再需要估算节点 C 的其他子节点如 E F 的 值就可以得出父节点 A 的值了 这样将节点 D 的后继兄弟节点减去称为 Alpha 剪枝 alpha cutoff 设想有如图 2 2 右半部所示的一棵极大极小树的片断 节 点 B 的估值为 8 节点 D 的估值为 18 由此我们可以判断节点 C 的值将大于等 于 18 取极大值 而节点 A 的值为节点 Min B C 为 8 也就是说不再需 要求节点 C 的其他子节点如 E F 的值就可以得出父节点 A 的值了 这样将节 点 D 的后继兄弟节点减去称为 Beta 剪枝 beta cutoff 2 2 5 置换表 Transposition Table 在极大极小搜索的过程中 改进搜索算法的目标在于将不必搜索的 冗余 分枝从搜索的过程中尽量剔除 以达到搜索尽量少的分枝来降低运算量的目的 在先前谈到的几种搜索算法中 我们看到可以通过 Alpha Beta 剪枝来剪除 太原科技大学华科学院毕业设计 论文 10 两种类型的冗余分枝 节点 但是已经搜索过的节点不可以免于搜索 从图 2 2 的极大极小树的片断中 我们可以看出 该片断从节点 A 开始 有两个分 B 和 C 为简化问题 其他节点从略 B 有子节点 D C 有子节点 E 再往下 D 有子节点 F E 有子节点 G 读者可以看到 在极大极小树的不同 分枝上 存在着完全相同的节点 在上图中 节点 F 和 G 完全相同 对于节点 F 在搜索分枝的时候 就可能已经搜索过了 那么 在搜索节点 G 的子节点 时 我们能不能直接利用已经搜索过的节点 F 的结果 而不是重新搜索一遍节 点 G 想法是可行的 如果要利用已经搜索过的节点的结果 我们就要用一张表 把搜索过的节点记录下来 然后在后续的搜索中 察看记录在表中的这些结果 如果将要搜索的某个节点已有记录 就直接利用记录下来的结果 这种方法叫 做置换表 Transposition Table 简称 TT 如果将 Alpha Beta 搜索过程中每一节点的结果都记录下来 则在任意节点 向下搜索之前先查看这些纪录 就可避免上述重复的操作 但是这个置换表如何实现的 困难集中在时间和空间复杂度上 1 可能的节点可以认为是无穷多 将其存入一张表中要占据多少存储空间 呢 2 即使有无穷多内存空间 一个节点要从表中找到自己对应的一项 需要 花费多少时间 虽然有序表可用二分查找等快速的算法 但要维持表中内容有 序 又要进行大量排序操作 会耗费更多时间 如何解决 2 2 6 哈希表 Hash Table 置换表的实现在时间和空间复杂度上的疑问 实际上已经明确了要实现置 换表必须要满足如下条件 1 查找记录中的节点数据时速度要非常快 最好是类似于随机存取 2 将节点数据放入记录的速度也要非常快 这就意味着数据项插入的过程 不可有数据移动排序等操作 3 要能在有限的存储空间内进行 可以利用哈希表 哈希方法的思想为每一个学过数据结构或算法课程的开 发人员所熟知 对棋类博弈来说 定义一个巨大的数组 将每一局面记入其中 太原科技大学华科学院毕业设计 论文 11 每一局面在数组中对应惟一的位置 这样 将数据记入和取出就类似于随机读 写 不会有耗时的查找和插入过程 但是 以象棋而论 如果为每一局面在数 组中对应一个与其他局面不同的位置的话 则组合的结果是全世界所有的计算 机内存加起来也不够这样一个数组用 那么让每一局面在数组中对应惟一的位置 但并不保证数组中每一个数据 项对应惟一的局面如何呢 比如将所有的局面对应在 106 单位的数组上 这样 必然有一些局面对应在相同的位置上 但是对一次搜索而言 这种情况发生的 概率并不高 一旦某个搜索过的局面在该数组中未找到 我们不过是对它进行 Alpha Beta 搜索而已 不同的局面对应在数组中同一存储单元上的情形 叫做 冲突 我们将利用哈希方法实现置换表的方法叙述如下 定义哈希数组如下 structHASHITEM int64 checksum 64 位哈希值 用以验证表中数据是否是要找的局面 int depth 该表项求值时的搜索深度 enum exact lower bound upper bound entry type 表项值的类型 double eval 所代表的节点的值 hashtable HASH TABLE SIZE 定义大小为 HASH TABLE SIZE 的哈希数组 对要搜索的每一节点 计算出它的一个哈希值 hashIndex 通常是一个 32 位数对哈希表大小取模 以确定此局面在哈希表中的位置 计算另一个 64 位的 哈希值 Checksum 来校验表中的数据项是否是所要的那一项 在对某一局面搜索之前 先查看哈希表项 hashTable hashIndex 如果 hashTable hashIn dex checksum Checksum 并且 hashTable hashIndex depth 大于等于最大搜索深度减去当前层数 就返回 hashTable hashIndex eval 作为当前局面的估值 当对一个局面的搜索完成之后 将 Checksum 当前层数和估值结果保存到 hashTable hashIndex 当中 以备后面的搜索使用 2 2 7 历史启发 History Heuristic 在前面的章节我们曾经提到过 Alpha Beta 搜索的剪枝效率 几乎完全取 太原科技大学华科学院毕业设计 论文 12 决于节点的排列顺序 在节点排列顺序处于理想状态的情况下 Alpha Beta 搜 索需遍历的节点数仅为极大极小算法所需遍历的节点数的平方根的两倍左右 也就是说对一棵极大极小树来说 如果极大极小搜索需遍历 106 个节点求得结 果 那么处于理想状态的 Alpha Beta 搜索仅需遍历约 2000 个节点就可求得结 果 而在节点的排序最不理想的情况下 Alpha Beta 搜索要遍历的结点数同极 大极小算法一样多 如何调整待展开的走法排列的顺序 是提高搜索效率的关 键 根据部分已经搜索的结果来调整将要进行搜索的节点顺序是一个可行的方 向 通常一个局面经搜索得知较好时 在其后继节点当中往往有一些相似的局 面 比如仅有一些无关紧要的棋子位置不同等等 这些相似的局面往往也是较 好的 可以通过一些较复杂的判断来找出这些相似的局面 率先搜索 从而提 高剪枝效率 但这一方法需要具体棋类相关的知识 并且往往判断复杂而效果 不彰 J Schaeffer 提出了 History Heuristic 的方法 在基于 Alpha Beta 的搜索当中 一个好的走法可以定义如下 1 由其产生的节点引发了剪枝 2 未引发剪枝 但是其兄弟走法中的最佳者 在搜索的过程中 每当找到一个好的走法 就将与该走法相对应的历史得 分作一个增量 一个多次被搜索并确认为好的走法的历史纪录就会较高 当搜 索中间节点时 将走法根据其历史得分排列顺序 以获得较佳的排列顺序 这 比采用基于棋类知识而对节点排序的方法要容易得多 由于历史得分表随搜索 而改变 对节点顺序的排列也会随之动态改变 2 3 本章小结 本系统的可行性研究 从市场可行性 技术可行性方面着手进行考虑 市 场可行性主要研究五子棋游戏的潜在市场 技术可行性主要研究系统开发软硬 件条件 综上考虑 本项目的开发技术成熟 完备 运行环境优良 具有一定 的开发前景 算法分析部分主要介绍了五子棋游戏开发用到的算法 按照计算机下每一 太原科技大学华科学院毕业设计 论文 13 手棋时 应用算法的大致顺序 本系统使用的主要算法有极大极小值算法 负 极大值算法 Alpha Beta 算法 置换表技术 哈希表技术 历史启发等 其中 的极大极小值算法是对弈算法的基础 哈希表技术的使用 是置换表技术能够 实现的基础 各种算法的综合使用 得以提高算法的效率 第 3 章 总体设计 3 1 总体设计过程 总体设计过程通常由四个主要阶段组成 系统体系结构设计 确定系统的 具体体系结构实现方案 系统模块设计 确定系统模块层次 结构算法设计 确定软件结构和典型算法 交互设计 确定系统的交互界面 总体设计的典型 过程包括如下七个阶段 1 选取合理的体系结构方案 2 推荐最佳方案 3 系统模块设计 4 数据结构和算法设计 5 交互设计 6 编写文档 7 审查和复审 由于本系统应用到算法的设计 下面详细描述一下第四个阶段 高效率的程序基于良好的数据结构与算法 一般来说 数据结构与算法就 是一类数据的表示及其相关的操作 从数据表示的观点来看 存储在数组中的 一个有序整数表也是一种数据结构 算法是指对数据结构施加的一些操作 一 个算法如果能在所要求的资源限制范围内将问题解决好 则称这个算法是有效 率的 一个算法如果比其他已知算法所需要的资源都少 这个算法也称为是有 效率的 算法的代价是指消耗的资源量 一般来说 代价是由一个关键资源 例如时间或空间来评估的 太原科技大学华科学院毕业设计 论文 14 3 2 系统的数据结构和算法设计 3 2 1 系统的数据结构设计 本系统在开发过程中 为了设计更合理的数据结构 使用了用户自定义数 据类型结构体和枚举类型 1 利用哈希表方法实现置换表 哈希表中元素的结构定义如下 typedef struct HASHITEM LONGLONG checksum 哈希值 用以验证表中数据是否是要找的局面 EnterType enterType 数据类型 short nPly 取到此值时的层次 short value 节点的值 HashItem 2 用以表示走法的结构 typedef struct STONEMOVE int x 棋子的横坐标 int y 棋子的纵坐标 int score 此走法的分数 StoneMove 3 枚举类型的使用 enum EnterType exam lower uper 搜索的精确值 下边界 上边界 enum IDD IDD BEST enum IDD IDD PENTE DIALOG 3 2 2 系统的算法设计 本系统是通过多个算法的结合使用来增强算法的效率 应用的主要算法有 博弈树 负极大值算法 Alpha Beta 剪枝算法 置换表 哈希表 历史启发等 其中的博弈树算法是搜索算法的基础 但是它的搜索量太大 在实现的过程中 我们不可能让系统搜索所有的结点 于是使用极大极小值算法对博弈树进行了 太原科技大学华科学院毕业设计 论文 15 改进 极大极小值算法是对弈算法的基础 普通的极大极小值算法看起来有一 点笨 既然一方试图取极大值而另一方试图取极小值 也就是说我们总要检查 哪一方要取极大值而哪一方又要取极小值 以执行不同的动作 而负极大值方 法 消除了两方的差别 博弈双方都取极大值 在极大极小搜索的过程中 存 在着一定程度的数据冗余 这就需要 Alpha Beta 算法的剪枝功能来消除冗余 在搜索过程中 利用置换表技术将 Alpha Beta 搜索过程中每一节点的结果都记 录下来 则在任意节点向下搜索之前先查看这些记录 就可避免重复搜索 以 提高搜索效率 而置换表的实现则是依赖哈希表 这种算法之间的优化组合 使得本系统能够实现它有效的搜索 3 3 系统模块设计 五子棋游戏是在系统地分析了游戏玩家的各项需求 以实际为基础进行设 计的 本系统可以进行人与计算机的对弈 还可以实现两个人在同一台计算机 上对弈 本系统包括三大模块 游戏模块 设置模块 帮助模块 每个模块包 括的主要内容如下 1 游戏模块 新局 初级 中级 专家 英雄榜 2 设置模块 悔棋 提示 英文菜单 声音效果 3 帮助模块 有关本系统的介绍 其中 在新局对话框下 可以对本局游戏进行设置 1 对弈方式选择 人与计算机对弈 人与人对弈 2 先手选择 玩家执黑先下 计算机执黑先下 3 是否选择声音效果 本系统的功能模块 如下图 3 1 所示 太原科技大学华科学院毕业设计 论文 16 五五子子棋棋游游戏戏 英英 文文 菜菜 单单 人人 与与 人人 先先 手手 对对 弈弈 方方 式式 新新 局局 英英 雄雄 榜榜 专专 家家 提提 示示 悔悔 棋棋 声声 音音 效效 果果 中中 级级 初初 级级 选选 项项 游游 戏戏 计计 算算 机机 先先 下下 玩玩 家家 先先 下下 人人 与与 计计 算算 机机 图 3 1 系统功能模块图 3 4 本章小结 本系统按照总体设计典型过程的七个阶段进行 详细介绍了系统的数据结 构和算法设计 本系统的数据结构主要采用了用户自定义数据类型 结构体 和枚举类型 算法设计是利用各种算法的优化组合来提高算法的效率 本系统 主要包括三大功能模块 游戏模块 选项模块 功能模块 每个功能模块包 括若干子功能 本系统以需求分析结论为基础 考虑得比较全面 太原科技大学华科学院毕业设计 论文 17 第 4 章 详细设计 4 1 系统运行平台设置 1 硬件环境 台式计算机 PC 一台 如表 4 1 所示 表 4 1 运行环境硬件配置 硬件配置 处理器Pentium III800 以上 内存256M 以上 硬盘空间1G 以上 2 软件环境 Windows 2000 Professional Server or Windows XP 操作系统 4 2 系统的程序流程图 1 程序流程图的作用 程序流程图是人们对解决问题的方法 思路或算法的一种描述 2 流程图的优点 1 采用简单规范的符号 画法简单 2 结构清晰 逻辑性强 3 便于描述 容易理解 3 本系统的程序流程为玩家首先为新一局游戏的对弈模式 先手 游戏级 别 是否有声音效果 使用中 英文菜单等功能进行设置 玩家确定设置完棋局 以后 就进入人与计算机或是人与人的对弈阶段 在对弈的过程中 每下一手 棋 都会进行本局游戏是否结束的判断 结束的标志是游戏的一方有五个棋子 相连 如果本局游戏没有结束 则玩家可以选择使用悔棋或让计算机向玩家提 示两项功能 如果本局游戏结束 判断玩家的成绩是否优于英雄榜里的成绩 如果是 就会出现喜登英雄榜界面 如图 4 8 玩家可以输入自己的大名 之 后就可以进行新一局游戏的设置 本系统的程序流程 如图 4 1 所示 太原科技大学华科学院毕业设计 论文 18 开开 始始 新新 开开 局局 设设置置完完棋棋 局局了了吗吗 悔悔棋棋 提提示示 荣荣登登英英雄雄榜榜 对对 弈弈 本本局局结结束束了了吗吗 成成绩绩优优于于 英英雄雄榜榜吗吗 结结 束束 Y Y N Y Y 退退出出游游戏戏吗吗 Y N N 悔悔棋棋 提提示示吗吗 N N 图 4 1 系统的程序流程图 4 3 系统主要功能的实现 4 3 1 新局 1 实现目标 在主窗体菜单下 单击新局菜单项 就会出现新一局的设置界面 在这个 界面中 可以对本局游戏的对弈方式 先手和声音效果进行设置 在对弈方式 方面 可以单击单选按钮或是使用快捷键 选择是与计算机对弈还是两人在同 太原科技大学华科学院毕业设计 论文 19 一计算机上对弈 游戏默认的选择是与计算机对弈 在先手方面 可以选择是 玩家执黑先下还是计算机执黑先下 默认的选择是玩家执黑先下 在声音效果 方面 可以单击复选框 选择是否在下棋的过程中有声音效果 默认选择有声 音效果 在对这三项设置完成之后 单击确定按钮 则保存对本局游戏的设置 即初始化棋盘结束 进入人与计算机或人与人的对弈阶段 本系统的新局设置 如图 4 2 所示 图 4 2 新局界面 2 实现过程 实现新局界面的流程 如图 4 3 所示 太原科技大学华科学院毕业设计 论文 20 开开 始始 人人机机对对弈弈吗吗 确确定定设设置置吗吗 有有声声音音效效果果吗吗 玩玩家家先先下下吗吗 游游戏戏中中无无声声音音效效果果游游戏戏中中有有声声音音效效果果 玩玩家家执执黑黑先先下下计计算算机机执执黑黑先先下下 人人机机对对弈弈人人与与人人对对弈弈 完完成成新新局局的的设设置置重重新新设设置置 结结 束束 新新 局局 Y N Y N Y N Y N 图 4 3 新局界面流程图 4 3 2 菜单及提示 1 实现目标 在主窗体的选项菜单下 可以选择游戏过程中是使用中文菜单还是英文菜 单 游戏默认的选择是中文菜单 如果你选择了英文菜单 则在游戏过程中所 有出现的界面都是用英文表示的 太原科技大学华科学院毕业设计 论文 21 在游戏过程中 可以使用主窗体的选项菜单下的提示功能 当你对棋局感 到不知所措的时候 可以让计算机给你一些提示 提示的方式是在棋盘上计算 机觉得最佳的位置出现一个矩形框 你可以参考他的提示 这可能会对你下棋 有些帮助 当你在棋盘上一个棋子都没有的时候 使用此功能 按照国际正规 比赛的规则 计算机会提示你在天元的位置下第一个子 菜单及提示功能的设置 如图 4 4 图 4 5 图 4 6 所示 图 4 4 游戏菜单 太原科技大学华科学院毕业设计 论文 22 图 4 5 选项菜单 图 4 6 提示效果 2 实现过程 太原科技大学华科学院毕业设计 论文 23 实现菜单及提示界面的流程 如图 4 7 所示 开开 始始 使使用用中中文文 菜菜单单吗吗 需需要要提提示示吗吗 本本局局结结束束了了吗吗 对对 弈弈 显显示示中中文文菜菜单单显显示示英英文文菜菜单单 提提示示 结结 束束 游游戏戏设设置置 Y N Y 棋棋局局设设置置 N Y N 图 4 7 菜单及提示界面流程图 4 3 3 游戏结束 1 实现目标 当每局游戏结束的时候 会出现一个对话框 在对话框上 会显示本局游 戏是黑棋胜还是白棋胜 双方共下了多少手棋 如果玩家使用黑棋则显示黑棋 悔棋几次 如果玩家使用白棋则显示白棋悔棋几次 如果在双方共下了不到二 十手棋就输了的话 在对话框上就会显示 哎 你也实在太差了 难道你不 知道该好好学习吗 否则显示 哈哈 你输了 去多学几招儿吧 单击确定按钮之后 就可以对下一局游戏进行设置 每一局游戏结束界面 如图 4 8 所示 太原科技大学华科学院毕业设计 论文 24 图 4 8 游戏结束界面 2 实现过程 实现游戏结束界面的流程 如图 4 9 所示 开开 始始 是是黑黑棋棋赢赢了了吗吗 此此局局棋棋子子数数 大大于于20吗吗 玩玩家家使使用用 黑黑棋棋吗吗 输输出出字字符符串串2输输出出字字符符串串1 显显示示黑黑棋棋悔悔棋棋次次数数显显示示白白棋棋悔悔棋棋次次数数 显显示示黑黑棋棋赢赢显显示示白白棋棋赢赢 结结 束束 对对 弈弈 Y N Y N Y N 本本局局结结束束了了吗吗 N Y 图 4 9 结束界面流程图 4 3 4 英雄榜 1 实现目标 太原科技大学华科学院毕业设计 论文 25 英雄榜里按初级 中级 专家级三个级别记录玩家的姓名和成绩 每一局 游戏结束的时候 如果玩家获胜 而且成绩优于英雄榜里的成绩 系统就会弹 出喜登英雄榜界面 在这个界面中 显示着此局游戏所选的级别 可以输入玩 家的姓名 单击确定按钮之后 玩家的大名和此局游戏的成绩就会出现在英雄 榜的相应级别的记录里 单击英雄榜界面的重置按钮 则英雄榜里的记录就恢 复到初始默认状态 喜登英雄榜的界面 如图 4 10 所示 图 4 10 喜登英雄榜界面 英雄榜的界面 如图 4 11 所示 图 4 11 英雄榜界面 太原科技大学华科学院毕业设计 论文 26 2 实现过程 实现英雄榜的流程 如图 4 12 所示 开开 始始 玩玩家家输输入入 姓姓名名吗吗 输输入入玩玩家