前言
改了又改，查了又查，想了又想，我真的不知道怎样让它再聪明了，大多时候走的都是正确的，但偶尔会蹦出那么一步臭棋，全盘皆输。希望有相关经验的道友看到后可以指出原因和不足。
效果图
按钮什么的还未完成，只是能实现正常的下棋了。
完成过程
UI部分
本来准备找张棋盘图片做背景，想了下我们还有人机界面课呢，权当复习一下java GUI了，事实上过程比我想象中简单许多。现在界面部分输出游戏结果和按钮什么的还没来得及弄，只是凑合可以玩了，闲了再加上，先贴出来，找点动力再说。
棋盘部分 －－ 实现落子，撤子，判断是否成五子(游戏结束)。对局面的评估函数(这个很重要，下面专门会解释)
AI部分(这个更重要了) ， 主要功能就是得出AI的下一步走法。
alpha_beta剪枝搜索
未了解过此算法的可先去看
最大最小搜索
Alpha-Beta剪枝
上面两文解释的很清楚了，在此就不再赘述。
估值函数
判断是否能成5, 如果是机器方的话给予100000分，如果是人方的话给予－100000 分；
判断是否能成活4或者是双死4或者是死4活3，如果是机器方的话给予10000分，如果是人方的话给予－10000分；
判断是否已成双活3，如果是机器方的话给予5000分，如果是人方的话给予－5000 分；
判断是否成死3活3，如果是机器方的话给予1000分，如果是人方的话给予－1000 分；
判断是否能成死4，如果是机器方的话给予500分，如果是人方的话给予－500分；
判断是否能成单活3，如果是机器方的话给予200分，如果是人方的话给予－200分；
判断是否已成双活2，如果是机器方的话给予100分，如果是人方的话给予－100分；
判断是否能成死3，如果是机器方的话给予50分，如果是人方的话给予－50分；
判断是否能成双活2，如果是机器方的话给予10分，如果是人方的话给予－10分；
判断是否能成活2，如果是机器方的话给予5分，如果是人方的话给予－5分；
判断是否能成死2，如果是机器方的话给予3分，如果是人方的话给予－3分。
存在的问题以及未完成的地方
最主要的问题就是偶尔会走臭棋。反复调试找原因，甚至把搜索方法又重新写了一遍，还是无果。觉得问题出现在估值函数上，但又想不出如何解决。
未完成的地方当然是提高搜索的效率了，每次估值都是要全盘进行估值，这样造成的时间影响是很大的，还可以用位棋盘来保存局面的情况，每走一步进行更新，每次回溯时再恢复，这样估值时之用考虑最近的一步，而不是全局了。这个等日后有时间再好好改进一下吧。
对于输赢的判断已经有了，但是还少了UI部分的显示，只是仅仅输出提示在命令行上。
代码
AI走法搜索部分 －－
import java.util.Random;
/**
* Created by shiyi on 16/3/14.
*/
public class Robot {
private static ChessBoard chess = ChessBoard.getInstance();
private Robot() {}
private static int depth = 1;
private static int robotColor = chess.BLACK;
private static Robot robot = new Robot();
public static Robot getRobot() {
return robot;
}
/* alpha_beta剪枝搜索 */
public int alpha_betaFind(int depth, int alpha, int beta, int color, int prex, int prey) {
if(depth >= Robot.depth || 0 != chess.isEnd(prex, prey, color%2+1)) {
int ans = chess.reckon(robotColor) - chess.reckon(robotColor%2 + 1);
if(depth % 2 == 0)
ans = -ans;
return ans;
}
for(int x=1; x<=chess.N; x++) {
for(int y=1; y<=chess.N; y++) {
if(!chess.isEmpty(x, y))
continue;
chess.makeMove(x, y, color);
int val = -alpha_betaFind(depth+1, -beta, -alpha, color%2+1, x, y);
chess.unMove(x, y);
if(val >= beta)
return beta;
if(val > alpha)
alpha = val;
}
}
return alpha;
}
/* 返回AI走法 */
public int[] getNext(int color) {
int rel[] = new int[2];
int ans = -100000000;
Random random = new Random();
for(int x=1; x<=chess.N; x++) {
for(int y=1; y<=chess.N; y++) {
if(!chess.isEmpty(x, y))
continue;
chess.makeMove(x, y, color);
int val = -alpha_betaFind(0, -100000000, 100000000, color%2 + 1, x, y);
int ra = random.nextInt(100);
if(val > ans || val == ans && ra >= 50) {
ans = val;
rel[0] = x;
rel[1] = y;
}
chess.unMove(x, y);
}
}
return rel;
}
}落子撤子以及估值 －－ChessBoard
/**
* Created by shiyi on 16/3/14.
*/
public class ChessBoard {
public final int N = 15;
public final int EMPTY = 0;
public final int BLACK = 1;
public final int WHITE = 2;
public int[][] board = new int[N+1][N+1];
private ChessBoard() {}
private static final ChessBoard chess = new ChessBoard();
/* 返回类单例 */
public static ChessBoard getInstance() {
return chess;
}
/* 判断该位置是否无子 */
public boolean isEmpty(int x, int y) {
return board[x][y] == EMPTY;
}
/* 落子 */
public void makeMove(int x, int y, int color) {
board[x][y] = color;
}
/* 撤子 */
public void unMove(int x, int y) {
board[x][y] = EMPTY;
}
public int reckon(int color) {
int dx[] = {1, 0, 1, 1};
int dy[] = {0, 1, 1, -1};
int ans = 0;
for(int x=1; x<=N; x++) {
for (int y = 1; y <= N; y++) {
if (board[x][y] != color)
continue;
int num[][] = new int[2][100];
for (int i = 0; i < 4; i++) {
int sum = 1;
int flag1 = 0, flag2 = 0;
int tx = x + dx[i];
int ty = y + dy[i];
while (tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == color) {
tx += dx[i];
ty += dy[i];
++sum;
}
if(tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == EMPTY)
flag1 = 1;
tx = x - dx[i];
ty = y - dy[i];
while (tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == color) {
tx -= dx[i];
ty -= dy[i];
++sum;
}
if(tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == EMPTY)
flag2 = 1;
if(flag1 + flag2 > 0)
++num[flag1 + flag2 - 1][sum];
}
//成5
if(num[0][5] + num[1][5] > 0)
ans = Math.max(ans, 100000);
//活4 | 双死四 | 死4活3
else if(num[1][4] > 0
|| num[0][4] > 1
|| (num[0][4] > 0 && num[1][3] > 0))
ans = Math.max(ans, 10000);
//双活3
else if(num[1][3] > 1)
ans = Math.max(ans, 5000);
//死3活3
else if(num[1][3] > 0 && num[0][3] > 0)
ans = Math.max(ans, 1000);
//死4
else if(num[0][4] > 0)
ans = Math.max(ans, 500);
//单活3
else if(num[1][3] > 0)
ans = Math.max(ans, 200);
//双活2
else if(num[1][2] > 1)
ans = Math.max(ans, 100);
//死3
else if(num[0][3] > 0)
ans = Math.max(ans, 50);
//双活2
else if(num[1][2] > 1)
ans = Math.max(ans, 10);
//单活2
else if(num[1][2] > 0)
ans = Math.max(ans, 5);
//死2
else if(num[0][2] > 0)
ans = Math.max(ans, 1);
}
}
return ans;
}
/* 判断局面是否结束 0未结束 1WHITE赢 2BLACK赢 */
public int isEnd(int x, int y, int color) {
int dx[] = {1, 0, 1, 1};
int dy[] = {0, 1, 1, -1};
for (int i = 0; i < 4; i++) {
int sum = 1;
int tx = x + dx[i];
int ty = y + dy[i];
while (tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == color) {
tx += dx[i];
ty += dy[i];
++sum;
}
tx = x - dx[i];
ty = y - dy[i];
while (tx > 0 && tx <= N
&& ty > 0 && ty <= N
&& board[tx][ty] == color) {
tx -= dx[i];
ty -= dy[i];
++sum;
}
if(sum >= 5)
return color;
}
return 0;
}
}
UI部分
import java.awt.*;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.util.Random;
/**
* Created by shiyi on 16/3/15.
*/
public class UI {
private ChessBoard chess = ChessBoard.getInstance();
private int userColor = chess.WHITE;
private int robotColor = chess.BLACK;
private Frame frame = new Frame("绘制棋盘");
private MyChess drawArea = new MyChess();
private Robot robot = Robot.getRobot();
public void init(){
Panel p = new Panel();
//机器执先
chess.makeMove(chess.N/2+1, chess.N/2+1, chess.BLACK);
drawArea.setPreferredSize(new Dimension(720, 720));
drawArea.addMouseListener(new MouseListener() {
@Override
public void mouseClicked(MouseEvent e) {
int x = e.getX();
int y = e.getY();
int i = (x-60)/40+1;
int j = (y-60)/40+1;
System.out.println(i+"---"+j);
if(chess.isEmpty(i, j)) {
chess.makeMove(i, j, userColor);
int rel = chess.isEnd(i, j, userColor);
if(rel != 0) {
System.out.println("玩家胜利");
return;
}
drawArea.repaint();
int rob[] = robot.getNext(robotColor);
chess.makeMove(rob[0], rob[1], robotColor);
rel = chess.isEnd(rob[0], rob[1], robotColor);
if(rel != 0) {
System.out.println("机器胜利");
return;
}
drawArea.repaint();
}
}
@Override
public void mousePressed(MouseEvent e) {
}
@Override
public void mouseReleased(MouseEvent e) {
}
@Override
public void mouseEntered(MouseEvent e) {
}
@Override
public void mouseExited(MouseEvent e) {
}
});
frame.add(drawArea);
frame.setSize(900, 720);
frame.setVisible(true);
}
}
class MyChess extends Canvas {
private ChessBoard chess = ChessBoard.getInstance();
private final int N = chess.N + 2;
private final int square = 40;
private final int stx = square;
private final int sty = square;
private final int length = (N-1)*square;
public void drawPiece(int color, int x, int y, Graphics g) {
if (color == chess.BLACK) {
g.setColor(new Color(0, 0, 0));
g.fillArc(stx + x * square - 19, sty + y * square - 19, 38, 38, 0, 360);
} else if (color == chess.WHITE) {
g.setColor(new Color(255, 255, 255));
g.fillArc(stx + x * square - 19, sty + y * square - 19, 38, 38, 0, 360);
}
}
public void paint(Graphics g) {
g.setColor(new Color(0, 0, 0));
g.fillRect(stx-8, sty-8, stx+(N-2)*square+15, sty+(N-2)*square+15);
g.setColor(new Color(139, 255, 71));
g.fillRect(stx-4, sty-4, stx+(N-2)*square+7, sty+(N-2)*square+7);
g.setColor(new Color(0, 0, 0));
g.fillArc(stx+8*square-6, sty+8*square-6, 12, 12, 0, 360);
g.fillArc(stx+4*square-6, sty+4*square-6, 12, 12, 0, 360);
g.fillArc(stx+4*square-6, sty+12*square-6, 12, 12, 0, 360);
g.fillArc(stx+12*square-6, sty+4*square-6, 12, 12, 0, 360);
g.fillArc(stx+12*square-6, sty+12*square-6, 12, 12, 0, 360);
for(int i = 0; i < N; i++) {
g.drawLine(stx+i*square, sty, stx+i*square, sty+length);
g.drawLine(stx, sty+i*square, stx+length, sty+i*square);
}
for(int i=1; i<=chess.N; i++) {
for(int j=1; j<=chess.N; j++) {
drawPiece(chess.board[i][j], i, j, g);
}
}
}
}Main
/**
* Created by shiyi on 16/3/14.
*/
public class Main {
public static void main(String[] args) {
System.out.println("游戏开始");
UI ui = new UI();
ui.init();
}
}