FiveChess1.5.rar_五子棋java剪枝_剪枝

package com.control; import com.view.FiveChessFrame; import java.awt.*; import java.util.Arrays; import java.util.Random; public class AI { public int isChessOn [][]; //棋局 protected boolean win = false; // 是否已经分出胜负 protected int win_bw; // 胜利棋色 protected int deep =4, weight = 7; // 搜索的深度以及广度 int chess_num = 0; // 总落子数目 public int playerCol = 0; //玩家棋色黑色0，白色1 public int nowCol = 0; // 当前应该下的棋色 0：黑色(默认)， 1：白色 // 边界值,用于速度优化 protected int x_max = 19, x_min = 0; protected int y_max = 19, y_min = 0; public int bestX; public int bestY; public static void main(String[] args) { // TODO Auto-generated method stub AI panel = new AI(); panel.putOne(1); } /** * 电脑下棋 * @param bwf */ public void putOne(int bwf ) { //bwf 棋色 0:黑色 1：白色 isChessOn = FiveChessFrame.chessTable; int x, y, mx = -100000000; x = y = -1; // 搜索最优下棋点 int[][] bests = getBests( bwf ); for (int k = 0; k < bests.length; k++) { int i = bests[k][0]; int j = bests[k][1]; // 有成5,则直接下子,并退出循环..没有,则思考对方情况 if (getType(i, j, bwf) == 1) { x = i; y = j; break; } if (getType(i, j,1 - bwf) == 1) { x = i; y = j; break; } // 预存当前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; // 预设己方下棋,并更新边界值 isChessOn[i][j] = bwf; resetMaxMin(i,j); // 预测未来 int t = findMin(-100000000, 100000000, deep); // 还原预设下棋位置以及边界值 isChessOn[i][j] = 2; x_min=temp1; x_max=temp2; y_min=temp3; y_max=temp4; // 差距小于1000，50%概率随机选取 //System.out.println("外 :" + i + "," + j + " mx:" + mx + " t:" + t); if (t - mx > 1000 || Math.abs(t - mx)<1000 && randomTest(3)) { x = i; y = j; mx = t; //System.out.println(i + "," + j + " mx:" + mx + " t:" + t); } } bestX=x; bestY = y; System.out.println("x="+x+",y="+y); /* int step=0; step++; System.out.println("step "+step+":-----------------------------------------------"); for(int i=0;i<15;i++,System.out.print("\n")) for(int j=0;j<15;j++) { if(isChessOn[j][i]!=2)System.out.print(isChessOn[j][i]); else System.out.print(isChessOn[j][i]); } */ } /** * 搜索当前搜索状态极大值 * @param alpha祖先节点得到的当前最小最大值，用于alpha 剪枝 * @param beta祖先节点得到的当前最大最小值，用于beta 剪枝。 * @param step 还要搜索的步数 * @return 当前搜索子树极大值 */ protected int findMax(int alpha, int beta, int step) { int max = alpha; if (step == 0) { return evaluate(); } int[][] rt = getBests(1 - playerCol); for (int i = 0; i < rt.length; i++) { int x = rt[i][0]; int y = rt[i][1]; if (getType(x, y, 1 - playerCol) == 1) //电脑可取胜 return 100 * ( getMark(1) + step*1000 ); isChessOn[x][y] = 1 - playerCol; // 预存当前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; resetMaxMin(x,y); int t = findMin(max, beta, step - 1); isChessOn[x][y] = 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; } /** * 搜索当前搜索状态极小 * @param alpha祖先节点得到的当前最小最大值，用于alpha 剪枝 * @param beta祖先节点得到的当前最大最小值，用于beta 剪枝 * @param step还要搜索的步数 * @return当前搜索子树极小值 */ protected int findMin(int alpha, int beta, int step) { int min = beta; if (step == 0) { return evaluate(); } int[][] rt = getBests(playerCol); for (int i = 0; i < rt.length; i++) { int x = rt[i][0]; int y = rt[i][1]; int type = getType(x, y, playerCol); if (type == 1) //玩家成5 return -100 * ( getMark(1) + step*1000 ); // 预存当前边界值 int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max; isChessOn[x][y] = playerCol; resetMaxMin(x,y); int t = findMax( alpha, min, step - 1 ); isChessOn[x][y] = 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; } /** * 选取局部最优的几个落子点作为下一次扩展的节点 * @param 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==19 ? x_max:x_max+1); int j_max=(y_max==19 ? 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 < j_max; j++) if (isChessOn[i][j] == 2) { type_1 = getType(i, j, bwf); type_2 = getType(i, j, 1 - bwf); rt[n][0] = i; rt[n][1] = j; rt[n][2] = getMark(type_1) + getMark(type_2); n++; } // 对二维数组排序 Arrays.sort(rt, new ArrComparator()); int size = weight > n? n:weight; int[][] bests = new int[size][3]; System.arraycopy(rt, 0, bests, 0, size); return bests; } /** * 计算指定方位上的棋型 * @param x x,y 方向线基准一点。 * @param y * @param ex ex,ey 指定方向步进向量。 * @param ey * @param bwf 棋子颜色 * @return */ private int[] count(int x, int y, int ex, int ey, int bwf) { // 正方向 以及 反方向棋子个数 int rt_1 = 1,rt_2 = 1; // 总棋子个数 int rt = 1; // 正方向 以及 反方向连子的活度 int ok_1 = 0,ok_2 =0; // 总活度 int ok = 0; // 连子中间有无空格 boolean flag_mid1 =false,flag_mid2 = false; // 连子中间空格的位置 int flag_i1 = 1,flag_i2 = 1; if (isChessOn[x][y] != 2) { throw new IllegalArgumentException("position x,y must be empty!.."); } int i; // 往正方向搜索 for (i = 1; x + i * ex < 19 && x + i * ex >= 0 && y + i * ey < 19 && y + i * ey >= 0; i++) { if (isChessOn[x + i * ex][y + i * ey] == bwf) rt_1++; // 位置为空,若中空标志为false,则记为中空并继续搜索 否则,break else if(isChessOn[x + i * ex][y + i * ey] == 2) { if(!flag_mid1) { flag_mid1 = true; flag_i1 = i; } else break; } // 位置为对方棋子 else break; } // 计算正方向活度,, // 最后一个位置不超过边界 if (x + i * ex < 19 && x + i * ex >= 0 && y + i * ey < 19 && y + i * ey >= 0) { /