java是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台(即JavaEE, JavaME, JavaSE)的总称。本站提供基于Java框架struts,spring,hibernate等的桌面应用、web交互及移动终端的开发技巧与资料

保持永久学习的心态,将成就一个优秀的你,来 继续搞起java知识。

前言

改了又改,查了又查,想了又想,我真的不知道怎样让它再聪明了,大多时候走的都是正确的,但偶尔会蹦出那么一步臭棋,全盘皆输。希望有相关经验的道友看到后可以指出原因和不足。

效果图

按钮什么的还未完成,只是能实现正常的下棋了。

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走法搜索部分 --

1import 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

1/**
 * 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部分

1import 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

1/**
 * 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();
    }
}

五子棋javaAIalphabeta

因为水平有限,难免有疏忽或者不准确的地方,希望大家能够直接指出来,我会及时改正。一切为了知识的分享。

后续会有更多的精彩的内容分享给大家。