基于J2ME的蓝牙中国象棋游戏的设计与实现.doc

基于J2ME的蓝牙中国象棋游戏的设计与实现 基于J2ME的蓝牙中国象棋游戏的设计与实现论文= beta) /裁剪 return beta; if (val alpha) /保留最大值 alpha = val; return alpha; 3.5 历史启发及走法排序(搜索辅助) Alpha-Beta 搜索算法在最小-最大的基础上引入树的裁剪的思想以期提 19 高效率,它的效率在很大程度上取决于树的结构如果搜索了没多久就发现可以 裁剪了,那么需要分析的工作量将大大减少,效率自然也就大大提高;而如果 直至分析了所有的可能性之后才能裁剪,那此时裁剪也已经失去了它原有的 价值.因而,要想保证 Alpha-Beta 搜索算法的效率就需要调整树的结构,即调整待 搜索的结点的顺序,使得裁剪可以尽可能早地发生. 根据部分已经搜索的结果来调整将要进行搜索的节点顺序是一个可行的方向. 通常当一个局面经过搜索被认为较好时,其子结点中往往有一些与它相似的局面也 是较好的.由 J.Schaeffer 所提出的历史启发 (History Heuristic)就是建立 在这样一种观点之上的.在搜索的过程中,每当发现一个好的走法,就给该走法累 加一个增量以记录其 历史得分 一个多次被搜索并认为是好的走法的 , 历史得分 就会较高.对于即将搜索的结点,按照历史得分的高低对它们进行排序,保证 较好的走法( 历史得分高的走法)排在前面,这样 Alpha-Beta 搜索就可以尽可 能早地进行裁剪 ,从而保证了搜索的效率. 对于走法的排序可以使用各种排序算法,在程序中采用了归并排序.归并排序 的空间复杂度为 O(n),时间复杂度为 O(nlog2n),具有较高的效率. 3.6 局面评估 局面评估是评估一个局面优劣的过程.如果说搜索算法是心脏,那么局面评估 就是大脑.搜索算法负责驱动整个程序,而局面评估则负责对搜索的内容进行判断 和评价. 在中国象棋中所要考虑的最基本的几个因素包括如下三点: (1)棋子的价值评估 棋子的价值评估,简单的说就是评估双方都有哪些棋子在棋盘上.例如,可以 让一个车价值为 500,一个马价值为 300,一个兵价值为 100, 将的价值为无限大 (通常用一个远大于其他棋子的数)等等.一方的棋子总值就是棋盘上存活的该方 棋子乘以棋子价值的和.用一个式子表达: SideValue=Sum(PieceNumber*PieceValue) 其中 PieceNumber 是某种棋子的数量,PieceValue 是该种棋子的价值,Sum 是对各 种棋子的总价值求和.如果红色的棋子价值总和大于黑色的棋子价值总和,通常意 味着红方的局势优于黑方.红黑双方的 SideValue 之差越大,优势也就越大. 20 (2)棋子的灵活性与棋盘控制 棋子的灵活性是指棋子的活动范围,通常是越大越好.一匹不能动的马很难在 棋局中发挥重要作用;同样,一个蹲在角落里的车也是价值不高的.评估棋子的灵 活性较为简单,将一个棋子的所有合法走法罗列出来,乘上该种棋子每一可走步的 价值就行了.也可用一个式子表达: Mobility=Sum(MoveNumber*MoveValue) 其中,MoveNumber 是某种棋子的合法走法数量,MoveValue 是该种棋子每一走法的 价值,Sum 是对所有棋子的灵活性价值求和.Mobility 就是所有棋子的灵活性分数. 还可以评估博弈双方对棋盘上位置的控制能力.在象棋中,如果某一位置落在 某方棋子的合法走步上,就可以认为被该方控制.如果某一位置同时落在双方的合 法走步上,我们可以根据双方控制该位置的棋子数量及棋子价值来决定孰优孰劣. (3)棋子关系的评估 棋子间的关系也是估值的重要内容之一,我们可以将某个棋子被对方棋子威胁 看成是一个不利的因素.例如红车的位置在黑马的合法走步当中,此时我们可以把 红车的价值减去一个值.而如果红马在黑车的合法走步之中,红马同时也在红卒的 合法走步之中,我们可以认为红马置于红卒的保护之下,没有受到威胁,价值不变. 棋子关系的评估应考虑到该谁走棋的问题.如果某个红马落在黑炮的合法走步 之内,但此时轮到红方走棋,应认为红马受到的威胁较轻.而如果此时轮到黑方走 棋,就应认为红马受到的威胁很大,应减去一个相对较大的值了.如果将被对 方威胁,且轮到对方走棋,那么无论有何种棋子可以走到将位都没有意义,将 等于失去了.此时应结束估值返回失败的估值(通常是极大或极小值) . 4. J2ME 蓝牙中国象棋的设计与实现 本章将详细讨论蓝牙联网游戏中国象棋的具体设计与开发流程,包括系统 总体设计和系统详细设计,并演示了系统的运行结果,给出了关键代码. 4.1 系统总体设计 4.1.1 系统目标 中国象棋是一款家喻户晓的游戏,不仅能丰富文化生活,陶冶情操,更有助于 开发智力,启迪思维,锻炼辨证分析能力和培养顽强的意志. 本文要实现以下功能: (1)实现人机对弈,包括正常下棋,悔棋,认输等. (2)实现游戏存档,读档功能. (3)实现双人联网对弈,也包括正常下棋,悔棋,认输等. (4)实现联网游戏过程中的聊天功能. (5)实现游戏音效的播放.4.1.2 系统结构 系统结构图如图 4-1 所示: 图 4-1 系统结构图 界面模块:负责与用户交互,包括显示和对用户输入的响应. 22 象棋引擎模块:负责生成人工智能的象棋走法. 蓝牙通信模块:负责双人游戏过程中的所有消息传递. 存储模块:负责存储游戏设置和单人游戏时的游戏存档. 音效模块:负责根据游戏设置播放背景音效和下棋音效. 辅助模块:用于显示一些提示信息. 系统主要流程图如图 4-2 所示: 图 4-2 系统主要流程图 4.1.3 系统用例 玩家进入游戏后要么进行单机游戏要么进行双人联网对弈.如图 4-3 所示: 图 4-3 系统顶层用例图 4.1.3.1 人机对弈用例图 图 4-4 人机对弈用例图 玩家进入单机游戏后可以与人工智能的象棋引擎进行对弈.对弈过程中根据需 要可以进行存档,读档,悔棋,认输,重新开局,和声音播放等操作. 以下是用例描述: 表 4-1 人机对弈用例描述 用例名称 参与者 前置条件 后置条件 主事件流 人机对弈 玩家 玩家进入游戏界面 继续下棋 玩家选择要走的棋和棋要走到的位置 系统判断走棋合法性 24 其他事件流 A1:走棋不合法 系统显示玩家走棋后的棋盘 系统判断未分出胜负 A2:已分出胜负 系统产生走法 系统显示系统走棋后的棋盘 系统判断未分出胜负 A3:已分出胜负 用例结束 A1:走棋不合法 玩家继续选择要走的棋和棋要走到的位置 系统判断走棋直到合法 进入人机对弈主事件流第 3 步 A2,A3:已分出胜负 系统提示游戏结束,显示游戏胜负结果 进入人机对弈主事件流第 8 步 表 4-2 存档用例描述 用例名称 参与者 前置条件 后置条件 主事件流 存档 玩家 玩家开始游戏,还未分出胜负,轮到玩家回合 保存成功 玩家选择存档命令 系统保存当前棋盘信息 系统提示存档成功 用例结束 读档 玩家 玩家进入单机游戏界面 系统显示存档时的棋盘状态 玩家选择读档命令 系统显示存档时的棋盘状态 用例结束 其他事件流 用例名称 参与者 前置条件 后置条件 主事件流 其他事件流 表 4-4 读档用例描述 用例名称 参与者 前置条件 后置条件 读档 玩家 玩家进入单机游戏界面 系统显示存档时的棋盘状态 25 主事件流 玩家选择读档命令 系统显示存档时的棋盘状态 用例结束 其他事件流表 4-4 悔棋用例描述 用例名称 参与者 前置条件 后置条件 主事件流 悔棋 玩家 玩家进入游戏,还未分出胜负,轮到玩家回合 系统恢复玩家操作的上一步 玩家选择悔棋 系统恢复玩家操作的上一步 用例结束 其他事件流表 4-5 认输用例描述 用例名称 参与者 前置条件 后置条件 主事件流 认输 玩家 玩家进入游戏,还未分出胜负,轮到玩家回合 系统显示游戏结果 玩家选择认输 系统显示游戏结束 用例结束 其他事件流 表 4-6 重新开局用例描述 用例名称 参与者 前置条件 后置条件 主事件流 重新开局 玩家 玩家进入游戏,分出胜负 开始新棋局 玩家选择重新开局命令 系统显示初始棋局,交换双方棋子颜色 用例结束 其他事件流 4.1.3.2 双人对弈用例图 图 4-5 双人对弈用例图 游戏双方在联网后可以进行双人对弈,在对弈过程中可根据需要进行悔棋,认 输,重新开局等操作,另外可以随时发送聊天信息. 以下是用例描述: 表 4-7 双人对弈用例描述 用例名称 参与者 前置条件 后置条件 主事件流 其他事件流 双人对弈 玩家 进入双人游戏界面 继续下棋 玩家选择要走的棋子和棋子要走到的位置 系统判断走法合法 A1:走棋不合法 系统改变棋盘内容 系统判断未分出胜负 A2:已分出胜负 系统发送走棋信息到对方端 系统收到对方发来的走棋信息 系统改变棋盘内容 系统判断未分出胜负 A3:已分出胜负 用例结束 A1:走棋不合法 玩家继续选择要走的棋和棋要走到的位置 系统判断直到走棋合法 进入双人对弈主事件流第 3 步 27 A2,A3:已分出胜负 系统提示游戏结束,显示胜负结果 系统发送走棋信息到对方端 进入双人对弈主事件流第 9 步 表 4-8 悔棋用例描述 用例名称 参与者 前置条件 后置条件 主事件流 其他事件流 悔棋 玩家 进入游戏界面,游戏未分出胜负,玩家回合 继续游戏 玩家选择悔棋命令 系统发送悔棋命令到对方端 系统收到对方同意消息 A1:系统收到对方不同意消息 系统恢复玩家操作的上一步 继续下棋 A1:系统收到对方不同意消息 系统提示对方不同意 进入对战悔棋主事件流第 5 步 表 4-9 认输用例描述 用例名称 参与者 前置条件 后置条件 主事件流 认输 玩家 进入游戏,未分出胜负,玩家回合 游戏结束 玩家选择认输命令 系统提示游戏结束 系统显示游戏战果 系统发送认输消息到对方端 用例结束 其他事件流 表 4-10 重新开局用例描述 用例名称 参与者 前置条件 后置条件 主事件流 重新开局 主机端玩家 主机端与客户端已建立连接或游戏已分胜负 开始新棋局,交换双方棋子颜色 主机端玩家选择开始新棋局命令 系统发送开始命令到客户端 客户端返回确认消息 28 系统显示游戏界面 用例结束 其他事件流 表 4-11 聊天用例描述 用例名称 参与者 前置条件 后置条件 主事件流 其他事件流 聊天 玩家 进入游戏界面 继续游戏 玩家选择聊天 系统显示信息输入界面 玩家编辑信息并选择发送命令 A1:玩家选择取消发送 系统发送信息 系统回到游戏界面 A1:玩家选择取消发送 (1)进入发送信