五子棋游戏设计与实现 051221134 翟晓华 目录 五子棋游戏设计与实现... 1 051221134 翟晓华... 1 一. 问题定义 :... 2 二. 模块设计... 2 2.1 整理描述... 2 2.2 功能描述... 3 2.2.1 棋子类... 3 2.2.2 棋盘类... 3 2.2.3 规则分析类... 4 2.2.4 游戏类... 6 三. 算法描述... 7 3.1AI 算法设计... 7 3.2 输赢判断算法设计... 10 3.3 禁手判断算法设计... 11 四. 程序说明... 12 五. 使用说明... 12
一. 问题定义 :. 能按照五子棋的规则 ( 规则附文后 ) 进行人机对战, 并能顺利结束棋局 机器思考步骤最好不要超过 30 秒 考虑先手禁手的规则 : 黑方不能以双活 3 或双 4 取胜, 其中活 3 有连 3 和跳 3,4 有活 4 和冲 4; 一旦出现禁手, 对 方指出, 则判负 ; 若同时出现禁手和成 5, 则先 5 为胜. 二. 模块设计 2.1 整理描述本游戏设计有三个模块 : 人机交互界面 规则分析部分 棋盘棋子部分 程序整体结构及模块之间的联系如下图所示 : 调用棋盘棋子模块新建棋盘对象 用户根据自己需求调用人机交互模块选择等级以及白棋或黑棋 根据用户选择, 获取机器先或玩家先以及游戏难度, 将结果传给规则分析模块 开始游戏 用户或者计算机走步, 如果轮到计算机走步, 调用规则分析模块根据当前棋局给出一个计算机走步位置 否则通过人机交互模块获得玩家输入的位置 调用规则分析模块, 首先判断当前这步是否是黑子, 是则继续调用规则分析模块判断是否是禁手, 若是则提示结束游戏, 用户可重新开局判断当前是否有一方已经构成五子, 若是, 则提示该方胜利, 结束游戏 若不是则等待另一方走步
2.2 功能描述 2.2.1 棋子类 Chess 类 : 属性 : 棋子位置, 颜色 提供的主要方法 : a) public void initial(int x, int y): 用于初始化棋子 ; 2.2.2 棋盘类 chessboard 类 : 属性 : a) private int arraysize; // 棋盘大小 b) public chess[] steps; // 记录下每一步走过的棋 c) public int current; // 指向 steps 数组中当前走 的棋, 通过修改它来实现悔棋 d) public int[][] board; // 棋盘大小, 用二维数组表示,0 表无棋,1 表黑棋,2 表白棋 提供的主要方法 : a) public void initial(): 用于初始化棋盘 ; b) public int putdown( chess achess ): * 在当前棋盘上放下棋子 achess * @param achess 待放的棋子 * @return 0 成功, 非禁手 * 放置失败 : * -1 棋盘该处已经有子 * 1 长连禁手 * 2 三三禁手 * 3 四四禁手 c) public boolean pickup( chess achess ) * 在当前棋盘上拿起棋子 achess * @param achess 棋子 * @return
d) public boolean back () * 悔棋 * @return true : 悔棋成功 * false: 悔棋失败 * 2.2.3 规则分析类 analyse 类 : 完成以下 3 个主要功能 : a) isforbidden: 输入棋盘与待放棋子 (x,y) 判断禁手 棋 (x,y) b) Max : 通过传入棋盘与电脑该走白棋还是黑棋, 给出当前最好的一步 c) iswin : 根据当前棋盘与最近放的一步棋判断是否胜利 属性 a) public static int level = 2; // 游戏难度, 默认为 2 普通 b) public static final int modenum = 50; // 用于匹配的棋盘模式数目 c) //----------------------------------------------------- //score[i][j] 用于存放在棋盘 (i,j) 处放置一个棋子所得分数 //----------------------------------------------------- static int[][] score1;// 存放所得分值 - static int[][] score2;// 存放所得分值 static int[][] score3;// 存放所得分值 / static int[][] score4;// 存放所得分值 \ static int[][] Score_White;// 存放总分值
static int[][] Score_Black;// 存放总分值 d) static String[]mode_black;static String[]mode_white; 预先定义好的 modenum 种模式, 机器算法中就是匹配这 modenum 种模式, 匹配到了赋一个相应的权值 e) static int[][] rel_add; //modenum 种模式中空白区域对应的相对坐标 f) static int[][] scorelist; // 每个点相应的权值 提供的主要方法 : a) public static int isforbidden(chessboard aboard, int x, int y); * 输入棋盘与待放棋子 (x,y) 判断禁手 * @param aboard 待判断的棋盘类 * @param x 将要放的棋子的 x 坐标 * @param y 将要放的棋子的 y 坐标 * @return 0 非禁手 * 1 长连禁手 * 2 三三禁手 * 3 四四禁手 b) public static boolean IsFourCheck(int x,int y,int adjsame,int direction,int color,chessboard aboard) * 判断在 (x,y) 落子后是否成活四 ( 即判断是否为活三 ), 黑棋需递归判断关键点是否禁手, 白棋不需要 * @param x 将要放的棋子的 x 坐标 * @param y 将要放的棋子的 y 坐标 * @param adjsame 与 (x,y) 相邻连续黑色棋子数 * @param direction 方向 * @param color 棋子颜色 * @param aboard 棋盘对象 * @return c) public static void updatascore(string[]mode, chessboard aboard); * 更新 score 数组每个位置的权值
* 分为 score1,score2,score3,score4 四个方向 * @param mode 模式, 分黑棋模式与白棋模式 * @param aboard 棋盘类 d) public static int[]max(chessboard aboard, int turn); * 通过传入棋盘与电脑该走白棋还是黑棋, 给出当前最好的 一步棋 (x,y) * @param aboard 棋盘 * @param turn 0 电脑该走白棋 * 1 电脑该走黑棋 * @return Max 数组 :Max[0] = score * Max[1] = i * Max[2] = j e) public static boolean iswin ( chessboard aboard, chess achess ); * 根据当前棋盘与最近放的一步棋判断是否胜利 * @param aboard 当前棋盘 * @param achess 最近放的棋子 * @return true: 赢了 * false: 未赢 2.2.4 游戏类 game 类 :
完成人机交互功能 : a) Menu : 获得用户所选择难度以及谁先信息 b) paintcomponent : 画棋盘 c) mouseclicked : 响应鼠标点击事件 属性 a) 菜单 Menu ( 开始 ; 难度 ) b) Panel ( 悔棋 ; 结束 ) 提供的主要方法 : a) protected void paintcomponent( Graphics g ); 根据当前棋盘对象画出棋盘 b) public void mouseclicked(mouseevent e) 检测鼠标点击位置, 在棋盘上放下 (x,y) 这步棋, 并调用机器算法让电脑走下一步棋 c) public static void updatascore(string[]mode, chessboard aboard); * 更新 score 数组每个位置的权值 * 分为 score1,score2,score3,score4 四个方向 * @param mode 模式, 分黑棋模式与白棋模式 * @param aboard 棋盘类 d) 菜单以及按键的相应相应函数 由于不是重点这里不详述 三. 算法描述 3.1AI 算法设计 1) 首先初始化模式变量 mode_black[],mode_white[] 以及相对坐标数组 rel_add[] 和权值信息数组 scorelist[] 数据存放格式的解释 : 例如, 对于 i=6, mode_black[i],mode_white[i], rel_add[i],scorelist[i] 分别如下 :
"0011100", "0022200",{0,1,5,6}, {20,80,80,20} 对应的含义见下图 : 在相应位置落下一个黑子所 得到的权值 scorelist[i]: 空白的相对偏移量 rel_add[i]: 当前的模式 mode_black[i]: 对应的棋局 : {20,80 80,20} {0, 1 5, 6} 0 0 1 1 1 0 0 用这种方法, 预置了 50 个模式并且赋了相应的权值 2) 如图所示, 因为从不同的方向看 (i,j) 这一点所得到的权值是不同的 所以用四个数组 score1[15][15],score2[15][15],score3[15][15],score4[15][15] 分别存储当棋子放在 (i,j) 位置, 从 score1,score2,score3,score4 方向看分别所能够得到的权值 若放的是白子, 则 Score_White[15][15] 存放这四个方向所得到的权值总合若放的是黑子, 则 Score_Black [15][15] 存放这四个方向所得到的权值总合
score4 方向 score2 方向 score3 方向 score1 方向 3) 从 Score_White[15][15] 与 Score_Black [15][15] 分别选出一个最大值 (i,j) 与 (i1,j1), 则表示下一步白子放于 (i,j) 价值最大, 黑子放于 (i1,j1) 价值最大 根据当前自己的颜色, 将对手颜色的最大权值置为负, 因为对手权值越大, 对自己威胁越大 此时若自己的最大权值大过对手权值, 表示对手的威胁不及自己的优势, 将自己的棋放于自己的最大权值点 若自己的最大权值小于对手权值, 表示对手的威胁大过自己的优势, 将自己的棋放于对手的最大权值点 其作用也就是不让对手放在那儿 4) 主要算法实现 : 此处为源代码中的 analyse.max(); 算法调用过程流程图
创建棋盘类 chessboard 对棋盘进行初始化 等待用户下棋 扫描棋盘, 调用 Max( 棋盘 ) 函数进行计算, 得到一个具有最高权值的位置 放下 从用户的选择读入机器先还是人先, 难度是几 否 否 棋局结束 是 机器先 是 在棋盘中心下一个黑子 提示结果 Max 算法流程图 Max 函数开始 将 15*15 的棋盘分为下一个方向的 n 个字符串 N 扫描这两个数组, 得到两个最大值 根据当前下棋方分别乘以一个预定系数 用计算机点的估值减去对方点的估值, 是否大于一个预定的阈值 是 否 对于棋盘上的每一个位置, 根据预定的模式以及这 n 个字符串得到该位置的权值, 填入 score[i][j] 4 个方向已扫描完? Y 将 4 个 score 相加得到总体的权值, 存入 score_black 与 score_white 数组 防守, 返回对方权值最大的那一点 结束 进攻, 返回自己最高权值那一点 3.2 输赢判断算法设计 应为每次导致输赢的只会是当前放置的棋子, 输赢算法中只需从当前点开始扫描判断是否已经形 成五子 对于这个子的八个方向判断是否已经形成五子 如果有, 则说明有一方胜利, 如果没有 则继续搜索, 直到有一方胜利或者搜索完整个棋盘
3.3 禁手判断算法设计对于当前棋子位中心的四个方向, 分别得到每个方向该子 左边 五个字和 右边 五个子的情况, 如果是黑子, 以 1 表示 ; 如果是白子或者超出棋盘边界, 以 2 表示 ; 如果没有子, 以 0 表示 如 :2 2 2 0 1 1 1 1 1 1 2 基础结构 : 从当前将放置的黑棋向外围 8 个方向扫描, 对于任意一个方向 i, 扫描连续黑棋的个数并存于 adjsame[i], 直至扫描到了颜色不为黑棋处, 扫描空白个数存于 adjempty[i], 直至扫描到了不为空白处, 接着扫描连续黑子个数存于 jumpsame[i] 如此得到了三个数组, 分别表示从这一点向 i 方向看时, 有 (adjsame[i] 个黑子 + adjempty[i] 个空格 + jumpsame[i] 个黑子 ) 以这种结构为基础判断禁手 判断方法 ( 伪代码 ): 增加棋盘中冲四或跳四的计数器 fcount 与活三或跳三的计数器 tcount 1. 若 adjsame[i]+adjsame[i+4] == 4 表示 i 当前点周围 ( 不算本身 ) 有 4 个以上 ( 包括 4 个 ) 的点, 五子连线 2. 若 adjsame[i]+adjsame[i+4] >= 5 长连禁手 3. 若 adjsame[i]+adjsame[i+4] == 3 / 活四或连冲四不会成双?+0000??0000+? 若 ((adjempty[i]==1&&jumpsame[i]==0 adjempty[i]>1) (adjempty[i+4]==1&&jumpsame[i+4]==0 adjempty[i+4]>1)) fcount 增 1 4. 若 adjsame[i]+adjsame[i+4] < 3 若 (adjsame[i]+adjsame[i]+ jumpsame[i] == 3&&adjempty[i]==1) fcount 增 1 若 (adjsame[i]+adjsame[i+4]+ jumpsame[i]==3&&adjempty[i+4]==1) fcount 增 1 若 ((adjsame[i]+adjsame[i+4]==2 &&adjempty[i]>1 adjsame[i]+adjsame[i]+ jumpsame[i] ==2 &&adjempty[i]==1)&&adjempty[i+4]>0 &&IsFourCheck(x,y,adjsame[i],i,1,aboard)) tcount 增 1
若 ((same==2&&adjempty[i+4]>1 ysame==2 &&adjempty[i+4]==1)&&adjempty[i]>0 &&IsFourCheck(x,y,adjsame[i+4],i+4,1,aboard)) tcount 增 1 5. if(tcount>1) 三三禁手 if(fcount>1) 四四禁手 四. 程序说明 a) 难度之间的差别在于 modenum 的不同, 即能够识别的模式的数量不同 b) 模式数量以及权值是根据自己的经验以及若干次测试后选择的, 所以有待改进 ; 五. 使用说明 打开程序, 首先选择难度, 系统默认选择普通 再点菜单上的开始 : 任意选择一个就可以开始游戏 注意 : 在点击开始之前点击棋盘是没有响应的
这里选择了电脑先 : 电脑先落子, 直接点击棋盘便可以下棋 若走错了, 可以点击右侧悔棋按钮悔棋 :
在有一方胜利或者平局, 会弹出提示 : 此时点击棋盘或者悔棋都没有相应 不过可以通过开始菜单重新开始一盘