人工智能课程设计(共9页).docx

《人工智能课程设计(共9页).docx》由会员分享，可在线阅读，更多相关《人工智能课程设计(共9页).docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上人工智能 技术报告简介本课程设计是基于alpha-beta剪枝算法的五子棋的博弈游戏，具有悔棋，可选择禁手，支持人机对战，人人对战等功能。整个设计基于Java语言开发，界面美观大方。 alpha-beta剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：(1) 对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不必再扩展

2、该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为剪枝。(2) 对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为剪枝。1、 数据结构定义本文定义15*15的五子棋棋盘，实现算法，在算法中采用的数据结构包括：int isChessOn描述当前棋盘，0表示黑子，1表示白字，2表示无子；int pre记录棋点的x，y坐标。由于本课程设计是基于Java语言开发的，

3、在Java中只能用类表示并实现所定义的数据结构。所以下面将用类来描述相应的数据结构及算法：public class ChessPanelprivate ImageIcon map; /棋盘背景位图 private ImageIcon blackchess;/黑子位图 private ImageIcon whitechess;/白子位图 public int isChessOn ;/棋局 protected boolean win = false; / 是否已经分出胜负 protected int win_bw; / 胜利棋色 protected int deep = 3, weight = 7

4、; / 搜索的深度以及广度 public int drawn_num = 110; / 和棋步数 int chess_num = 0; / 总落子数目 public int pre = new intdrawn_num + 12; / 记录下棋点的x,y坐标 最多 (drawn_num + 1) 个 public int sbw = 0; /玩家棋色黑色0，白色1 public int bw = 0; / 当前应该下的棋色 0：黑色(默认)， 1：白色 protected int x_max = 15, x_min = 0; / 边界值,用于速度优化 protected int y_max =

5、 15, y_min = 0; / 边界值,用于速度优化 protected boolean able_flag = true; / 是否选择禁手标志 0:无禁手 1:有禁手(默认 private int h;/棋子长 private int w;/棋子宽 private int insx;/插入棋子的位置 private int insy; private Point mousePoint;/鼠标当前位置 private int winer;/获胜方 private boolean humanhuman=false; /是否是人人对弈 private int plast=0;/走了几步了，

6、public int BLACK_ONE;/0表黑子 public int WHITE_ONE;/1表白子 public int NONE_ONE;/2表无子public int N;/棋盘边长/-搜索当前搜索状态极大值-/ /alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝 /beta 祖先节点得到的当前最大最小值，用于beta 剪枝。 /step 还要搜索的步数 /return 当前搜索子树极大值 protected int findMax(int alpha, int beta, int step) int max = alpha; if (step = 0) return

7、 evaluate(); int rt = getBests(1 - sbw); for (int i = 0; i max) max = t; /beta 剪枝 if (max = beta) return max; return max; /-搜索当前搜索状态极小值-/ /alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝 /beta 祖先节点得到的当前最大最小值，用于beta 剪枝 /step 还要搜索的步数 /return 当前搜索子树极小值。 protected int findMin(int alpha, int beta, int step) int min = be

8、ta; if (step = 0) return evaluate(); int rt = getBests(sbw); for (int i = 0; i rt.length; i+) int x = rti0; int y = rti1; int type = getType(x, y, sbw); if (type = 1) /玩家成5 return -100 * ( getMark(1) + step*1000 ); / 预存当前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; isChessOnxy = sbw; res

9、etMaxMin(x,y); int t = findMax( alpha, min, step - 1 ); isChessOnxy = 2; / 还原预设边界值 x_min=temp1; x_max=temp2; y_min=temp3; y_max=temp4; if (t min) min = t; /alpha 剪枝 if (min = alpha) return min; return min; /-选取局部最优的几个落子点作为下一次扩展的节点-/ /bwf 棋色 0：黑棋 1：白棋 /return 选出来的节点坐标 private int getBests(int bwf) in

10、t i_min=(x_min=0 ? x_min:x_min-1); int j_min=(y_min=0 ? y_min:y_min-1); int i_max=(x_max=15 ? x_max:x_max+1); int j_max=(y_max=15 ? y_max:y_max+1); int n = 0; int type_1,type_2; int rt = new int(i_max-i_min) * (j_max-j_min)3; for ( int i = i_min; i i_max; i+) for (int j = j_min; j n? n:weight; int b

11、ests = new intsize3; System.arraycopy(rt, 0, bests, 0, size); return bests; 程序开始2、 程序流程图显示界面,绘制棋盘Haveai=true?Y N 与电脑博弈与人博弈 玩家下子（黑）玩家下子音乐控制悔棋重新开始音乐控制悔棋重新开始判断胜负，是否禁手玩家下子（白）电脑下棋游戏结束3、 程序执行结果初始界面人机博弈人人博弈禁手选择4、 个人总结、看法本程序是使用Alpha-Beta搜索的算法完成的一个简单的五子棋博弈游戏。虽然Alpha-Beta已经尽力做到细致、全面，但由于Alpha-Beta搜索存在博弈树算法中普遍存在的一个缺点一随着搜索层数的增加，算法的效率大大下降。所以该搜索的效率还是不怎么理想，五子棋程序的“智力”也不高。因此可以在上述程序的基础上，针对五子棋本身的特点和规律对Alpha-Beta搜索算法进行优化与修正，比如用启发式搜索。专心-专注-专业