人工智能课程设计

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坐标。由于本课程设计是基

3、于Java语言开发的，在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,

4、 weight = 7; / 搜索的深度以及广度 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

5、int y_max = 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

6、=0;/走了几步了， 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

7、= 0) return evaluate(); int rt = getBests(1 - sbw); for (int i = 0; i < rt.length; i+) int x = rti0; int y = rti1; if (getType(x, y, 1 - sbw) = 1) /电脑可取胜 return 100 * ( getMark(1) + step*1000 ); isChessOnxy = 1 - sbw; / 预存当前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; resetMaxMin(x,y)

8、; int t = findMin(max, beta, step - 1); isChessOnxy = 2; / 还原预设边界值 x_min=temp1; x_max=temp2; y_min=temp3; y_max=temp4; if (t > max) max = t; /beta 剪枝 if (max >= beta) return max; return max; /-搜索当前搜索状态极小值-/ /alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝 /beta 祖先节点得到的当前最大最小值，用于beta 剪枝 /step 还要搜索的步数 /return 当

9、前搜索子树极小值。 protected int findMin(int alpha, int beta, int step) int min = beta; 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 ); / 预存当

10、前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; isChessOnxy = sbw; resetMaxMin(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; /-选取局

11、部最优的几个落子点作为下一次扩展的节点-/ /bwf 棋色 0：黑棋 1：白棋 /return 选出来的节点坐标 private int getBests(int bwf) int 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) * (

12、j_max-j_min)3; for ( int i = i_min; i < i_max; i+) for (int j = j_min; j < j_max; j+) if (isChessOnij = 2) type_1 = getType(i, j, bwf); type_2 = getType(i, j, 1 - bwf); if(able_flag && bwf=0 && (type_1 = 20 | type_1 = 21 | type_1 = 22) / 禁手棋位置,不记录 continue; rtn0 = i; rtn1 = j;

13、rtn2 = getMark(type_1) + getMark(type_2); n+; / 对二维数组排序 Arrays.sort(rt, new ArrComparator(); int size = weight > n? n:weight; int bests = new intsize3; System.arraycopy(rt, 0, bests, 0, size); return bests; 程序开始2、 程序流程图显示界面,绘制棋盘Haveai=true?Y N 与电脑博弈与人博弈 玩家下子（黑）玩家下子音乐控制悔棋重新开始音乐控制悔棋重新开始判断胜负，是否禁手玩家下子（白）电脑下棋游戏结束3、 程序执行结果初始界面人机博弈人人博弈禁手选择4、 个人总结、看法本程序是