一. 问题定义 :. 能按照五子棋的规则 ( 规则附文后 ) 进行人机对战, 并能顺利结束棋局机器思考步骤最好不要超过 30 秒考虑先手禁手的规则 : 黑方不能以双活 3 或双 4 取胜, 其中活 3 有连 3 和跳 3,4 有活 4 和冲 4; 一旦出现禁手, 对方指出, 则判负 ; 若同时

Size: px

Start display at page:

Download "一. 问题定义 :. 能按照五子棋的规则 ( 规则附文后 ) 进行人机对战, 并能顺利结束棋局机器思考步骤最好不要超过 30 秒考虑先手禁手的规则 : 黑方不能以双活 3 或双 4 取胜, 其中活 3 有连 3 和跳 3,4 有活 4 和冲 4; 一旦出现禁手, 对方指出, 则判负 ; 若同时"

托衡于
7 years ago
Views:

1 五子棋游戏设计与实现翟晓华目录五子棋游戏设计与实现翟晓华... 1 一. 问题定义 :... 2 二. 模块设计整理描述功能描述棋子类棋盘类规则分析类游戏类... 6 三. 算法描述 AI 算法设计输赢判断算法设计禁手判断算法设计四. 程序说明五. 使用说明... 12

2 一. 问题定义 :. 能按照五子棋的规则 ( 规则附文后 ) 进行人机对战, 并能顺利结束棋局机器思考步骤最好不要超过 30 秒考虑先手禁手的规则 : 黑方不能以双活 3 或双 4 取胜, 其中活 3 有连 3 和跳 3,4 有活 4 和冲 4; 一旦出现禁手, 对方指出, 则判负 ; 若同时出现禁手和成 5, 则先 5 为胜. 二. 模块设计 2.1 整理描述本游戏设计有三个模块 : 人机交互界面规则分析部分棋盘棋子部分程序整体结构及模块之间的联系如下图所示 : 调用棋盘棋子模块新建棋盘对象用户根据自己需求调用人机交互模块选择等级以及白棋或黑棋根据用户选择, 获取机器先或玩家先以及游戏难度, 将结果传给规则分析模块开始游戏用户或者计算机走步, 如果轮到计算机走步, 调用规则分析模块根据当前棋局给出一个计算机走步位置否则通过人机交互模块获得玩家输入的位置调用规则分析模块, 首先判断当前这步是否是黑子, 是则继续调用规则分析模块判断是否是禁手, 若是则提示结束游戏, 用户可重新开局判断当前是否有一方已经构成五子, 若是, 则提示该方胜利, 结束游戏若不是则等待另一方走步

3 2.2 功能描述棋子类 Chess 类 : 属性 : 棋子位置, 颜色提供的主要方法 : a) public void initial(int x, int y): 用于初始化棋子 ; 棋盘类 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 achess 待放的棋子 0 成功, 非禁手 * 放置失败 : * -1 棋盘该处已经有子 * 1 长连禁手 * 2 三三禁手 * 3 四四禁手 c) public boolean pickup( chess achess ) * 在当前棋盘上拿起棋子 achess achess 棋子

4 d) public boolean back () * 悔棋 true : 悔棋成功 * false: 悔棋失败 * 规则分析类 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;// 存放总分值

5 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) 判断禁手 aboard 待判断的棋盘类 x 将要放的棋子的 x 坐标 y 将要放的棋子的 y 坐标 0 非禁手 * 1 长连禁手 * 2 三三禁手 * 3 四四禁手 b) public static boolean IsFourCheck(int x,int y,int adjsame,int direction,int color,chessboard aboard) * 判断在 (x,y) 落子后是否成活四 ( 即判断是否为活三 ), 黑棋需递归判断关键点是否禁手, 白棋不需要 x 将要放的棋子的 x 坐标 y 将要放的棋子的 y 坐标 adjsame 与 (x,y) 相邻连续黑色棋子数 direction 方向 color 棋子颜色 aboard 棋盘对象 c) public static void updatascore(string[]mode, chessboard aboard); * 更新 score 数组每个位置的权值

6 * 分为 score1,score2,score3,score4 四个方向 mode 模式, 分黑棋模式与白棋模式 aboard 棋盘类 d) public static int[]max(chessboard aboard, int turn); * 通过传入棋盘与电脑该走白棋还是黑棋, 给出当前最好的一步棋 (x,y) aboard 棋盘 turn 0 电脑该走白棋 * 1 电脑该走黑棋 Max 数组 :Max[0] = score * Max[1] = i * Max[2] = j e) public static boolean iswin ( chessboard aboard, chess achess ); * 根据当前棋盘与最近放的一步棋判断是否胜利 aboard 当前棋盘 achess 最近放的棋子 true: 赢了 * false: 未赢游戏类 game 类 :

7 完成人机交互功能 : 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 四个方向 mode 模式, 分黑棋模式与白棋模式 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] 分别如下 :

8 " ", " ",{0,1,5,6}, {20,80,80,20} 对应的含义见下图 : 在相应位置落下一个黑子所得到的权值 scorelist[i]: 空白的相对偏移量 rel_add[i]: 当前的模式 mode_black[i]: 对应的棋局 : {20,80 80,20} {0, 1 5, 6} 用这种方法, 预置了 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] 存放这四个方向所得到的权值总合

9 score4 方向 score2 方向 score3 方向 score1 方向 3) 从 Score_White[15][15] 与 Score_Black [15][15] 分别选出一个最大值 (i,j) 与 (i1,j1), 则表示下一步白子放于 (i,j) 价值最大, 黑子放于 (i1,j1) 价值最大根据当前自己的颜色, 将对手颜色的最大权值置为负, 因为对手权值越大, 对自己威胁越大此时若自己的最大权值大过对手权值, 表示对手的威胁不及自己的优势, 将自己的棋放于自己的最大权值点若自己的最大权值小于对手权值, 表示对手的威胁大过自己的优势, 将自己的棋放于对手的最大权值点其作用也就是不让对手放在那儿 4) 主要算法实现 : 此处为源代码中的 analyse.max(); 算法调用过程流程图

10 创建棋盘类 chessboard 对棋盘进行初始化等待用户下棋扫描棋盘, 调用 Max( 棋盘 ) 函数进行计算, 得到一个具有最高权值的位置放下从用户的选择读入机器先还是人先, 难度是几否否棋局结束是机器先是在棋盘中心下一个黑子提示结果 Max 算法流程图 Max 函数开始将 15*15 的棋盘分为下一个方向的 n 个字符串 N 扫描这两个数组, 得到两个最大值根据当前下棋方分别乘以一个预定系数用计算机点的估值减去对方点的估值, 是否大于一个预定的阈值是否对于棋盘上的每一个位置, 根据预定的模式以及这 n 个字符串得到该位置的权值, 填入 score[i][j] 4 个方向已扫描完? Y 将 4 个 score 相加得到总体的权值, 存入 score_black 与 score_white 数组防守, 返回对方权值最大的那一点结束进攻, 返回自己最高权值那一点 3.2 输赢判断算法设计应为每次导致输赢的只会是当前放置的棋子, 输赢算法中只需从当前点开始扫描判断是否已经形成五子对于这个子的八个方向判断是否已经形成五子如果有, 则说明有一方胜利, 如果没有则继续搜索, 直到有一方胜利或者搜索完整个棋盘

11 3.3 禁手判断算法设计对于当前棋子位中心的四个方向, 分别得到每个方向该子左边五个字和右边五个子的情况, 如果是黑子, 以 1 表示 ; 如果是白子或者超出棋盘边界, 以 2 表示 ; 如果没有子, 以 0 表示如 : 基础结构 : 从当前将放置的黑棋向外围 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

12 若 ((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) 模式数量以及权值是根据自己的经验以及若干次测试后选择的, 所以有待改进 ; 五. 使用说明打开程序, 首先选择难度, 系统默认选择普通再点菜单上的开始 : 任意选择一个就可以开始游戏注意 : 在点击开始之前点击棋盘是没有响应的

13 这里选择了电脑先 : 电脑先落子, 直接点击棋盘便可以下棋若走错了, 可以点击右侧悔棋按钮悔棋 :

14 在有一方胜利或者平局, 会弹出提示 : 此时点击棋盘或者悔棋都没有相应不过可以通过开始菜单重新开始一盘

图形学 Project 2 要求任意两个多边形, 求出其相交的区域使用说明例 1 第一步, 与 Project 1 画多边形的方法相同, 画一个多边形 ; 第二步, 单击 INTERSECT WITH, 随后画出第二个多边形 ; 第三步, 单击 FILL 进行填充

图形学 Project 2 要求任意两个多边形, 求出其相交的区域使用说明例 1 第一步, 与 Project 1 画多边形的方法相同, 画一个多边形 ; 第二步, 单击 INTERSECT WITH, 随后画出第二个多边形 ; 第三步, 单击 FILL 进行填充图形学 Project 2 要求任意两个多边形, 求出其相交的区域使用说明例 1 第一步, 与 Project 1 画多边形的方法相同, 画一个多边形 ; 第二步, 单击 INTERSECT WITH, 随后画出第二个多边形 ; 第三步, 单击 FILL 进行填充例 2 单击 CLEAR, 重新回到初始状态, 下面让我们看一下自交多边形的情况当单击数次后, 出现左图的情况, 之后我们单击