基于Minmax算法与Alpha-Beta剪枝的五子棋对战AI的Java代码实现

引言

五子棋 (GoBang) 是一种典型的博弈游戏，而“博弈”一词的定义在《人工智能-一种现代方法》一书中的第五章《对抗搜索》中给出

有完备信息的，确定性的，轮流行动的，两个游戏者的零和游戏.

这种游戏可以通过生成博弈树来对下一步的最优行动进行预测，这也是构建五子棋对战AI的原理，而这种思路是通过 极小化极大算法(Minimax) 来实现的，接下来将介绍其原理与代码实现。^[1]

极小化极大算法^[2]

将五子棋的每个行动按后续双方可能的行动展开，可得到一个庞大的搜索树，如图所示

若以AI玩家的某一次落子前的棋盘状态为根节点，第一层(depth==1)子节点即为AI玩家落子后的可能棋盘状态，
第二层(depth==2)子节点即为人类玩家下一步落子后的可能棋盘状态……对每个子节点来说，其值(data)即为相对于AI玩家的棋盘状态评分。

当从根节点开始搜索时，默认两玩家都发挥最佳水平，则需要遵从“AI玩家尽可能选择评分最大的路径，人类玩家尽可能选择评分最小的路径”，这样才能保证下一步的策略更加合理。
这就需要对两种层进行区分，在图上，标为MAX的正方形节点意味着要从其子节点中选择评分最大的一个，标MIN的圆形节点要从其子节点选择评分最小的一个。

对于这种问题，就可以利用深度优先搜索 (DPS) 的思路来逐步构筑代码：初始条件 (递归到最深层节点) 直接返回该节点评分值，当前节点为MAX节点返回子节点最大值，当前节点为MIN节点返回节点最小值，直到回溯至根节点结束。

伪代码实现：

int minimax(int depth, bool is_max) {
    int res;
  if (!son_num[depth]) return val(curState); // 搜索到无子节点返回当前评分
  if (is_max) { // 当前为MAX节点，返回子节点最大值
    for (int i = 0; i < son_num[depth]; ++i) {
      res = max(res, minimax(depth + 1, is_max ^ 1));
    }
    return res;
  } else { // 当前为MIN节点，返回子节点最小值
    for (int i = 0; i < son_num[depth]; ++i) {
      res = min(res, minimax(depth + 1, is_max ^ 1));
    }
    return res;
  }
}

然而从上面的代码可以看出来，我们需要解决几个问题：

• 子节点状态sonState的生成
• 节点状态的评估函数evaluate()的实现
• 搜索过于庞大，假设每层节点有10个子节点，当搜索深度为4时就会搜索 $10^4 = 10000$次，每次都要建立一个新的$15 \times 15$大小的二维数组，这个算法的空间复杂度将会达到 $O(2^n)$ ，因此适当的优化(即剪去不必要的分枝)是亟需的

生成函数generate()的实现

进行搜索前必须生成每一个节点的棋盘状态，即下一步每一个可能的走法，对于五子棋我们倾向于开局落子在中心位置，且距离棋盘上已有棋子位置的过远处(5个位置以外)的落子并没有太大价值，根据此便可构建generate()方法，伪代码实现如下：

int[][] generate() {
  if (isEmpty(board)) {
    return {{7,7}}
  }
  int[][] res;
  for (int i = 0; i < ROW; i++) {
    for (int j = 0; j < COL; j++>) {
      if (isChessNear) {
        res.add({i, j})
      }
     }
  }
  return res
}

评估函数evaluate()的实现

对DFS的优化——Alpha-Beta剪枝算法^[4]

当搜索树过于复杂且包含极值约束时，可以用Alpha-Beta算法剪去不可能的路径上的分支，现在结合某一局势解释其原理：

$\alpha$, $\beta$ 分别作为搜索过程中结果的最大下界和最小上界的记录值，若已知某节点的部分子节点的分数，虽然不能算出该节点的分数，但可以算出该节点的分数的取值范围。同时，利用该节点的分数的取值范围，在搜索其子节点时，如果已经确定没有更好的走法，就不必再搜索剩余的子节点了。在具体实现时，即 $\alpha \beta$ 说明该节点可以剪枝。

初始时 $\alpha = - \infty, \beta = + \infty$ ,当搜索至根节点时，由于其父节点为MIN类型，故更新 $\beta = 3$，同时A节点值返回为3。

继续向上返回时，由于父节点变为MAX类型，更新 $\alpha = 3$, 向下搜索至C节点。

这时根节点最小值为2，更新 $\beta = 2$, 发现 $\beta < \alpha$，说明节点C不会有更好的走法，故不再搜索其子节点并直接返回结果为2。

将Alpha-beta剪枝加入Minimax搜索中，伪代码实现如下：

int alpha_beta(int u, int alph, int beta, bool is_max) {
  if (!son_num[u]) return val[u];
  if (is_max) {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      alph = max(alph, alpha_beta(d, alph, beta, is_max ^ 1));
      if (alph >= beta) break;
    }
    return alph;
  } else {
    for (int i = 0; i < son_num[u]; ++i) {
      int d = son[u][i];
      beta = min(beta, alpha_beta(d, alph, beta, is_max ^ 1));
      if (alph >= beta) break;
    }
    return beta;
  }
}

附

最后贴上我的Java源码

▶

Board.java

import java.util.LinkedList;
import java.util.List;
import java.util.ArrayList;

public class Board {
// 通过name和id来创建一个棋盘
    public String name;
    public int id;
    public Board(String name, int id){
        this.name = name;
        this.id = id;
    }
    // 设置黑棋为1，白棋为2，空为0
    public static final int BLACK = 1;
    public static final int WHITE = 2;
    public static final int EMPTY = 0;
    public static final int INROW = 5;

    // 设置棋盘
    private int[][] board = new int[15][15];
    // 通过一个二维数组来创建一个棋盘
    public Board(int[][] initBoard){
        copyBoard(initBoard, board);
    }
    
    // 初始化状态队列
    private Deque status = new Deque();
    // 状态加入队尾
    public void pushStatus(int[][] board){
        int [][] copy = new int[15][15];
        copyBoard(board, copy);
        status.pushRear(copy);
    }
    // 状态出队尾
    public int[][] popStatus(){
        return status.popRear();
    }

    // 获取棋盘
    public int[][] getBoard(){
        return board;
    }
    // 判断并进行落子
    public boolean putChess(int x, int y, int color){
        if (x >=0 && x < board[0].length && y >= 0 && y < board.length && board[x][y] == EMPTY){
            if (color == 1){
                board[x][y] = BLACK;
            }
            else if (color == 2){
                board[x][y] = WHITE;
            }
            return true;
        }
        else{
            return false;
        }
    }

    // 移除指定位置的棋子
    public void removeChess(int x, int y){
        board[x][y] = EMPTY;
    }

    // 获取指定位置的棋子
    public String getChess(int x, int y) throws Exception{
        if (board[x][y] == BLACK){
            return "BLACK";
        }
        else if (board[x][y] == WHITE){
            return "WHITE";
        }
        else{
            return "EMPTY";
        }
    }

    // 判断棋盘是否已满
    public boolean isFull(){
        for (int i = 0; i < 15; i++){
            for (int j = 0; j < 15; j++){
                if (board[i][j] == EMPTY){
                    return false;
                }
            }
        }
        return true;
    }

    // 根据棋面判断是否有一方胜利
    public boolean isWin(int color){
        for (int i = 0; i < 15; i++){
            for (int j = 0; j < 15; j++){
                if (board[i][j] == color){
                    if (this.judgeWin(i, j) != 0){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    // 根据最后一步判断是否有一方胜利, 1为黑棋胜利，2为白棋胜利，0为未分胜负
    public int judgeWin(int x, int y){
        if (this.judgeRow(x, y) || this.judgeCol(x, y) || this.judgeLeftDiagonal(x, y) || this.judgeRightDiagonal(x, y)){
            if (board[x][y] == BLACK){
                return BLACK;
            }
            else if (board[x][y] == WHITE){
                return WHITE;
            }
        }
        return EMPTY;
    }
    /*
    *判断当前列内是否有五子相连
    @param x 当前横坐标
    @param y 当前纵坐标
    @return boolean
     */
    public boolean judgeCol(int x, int y){
        int count = 1;
        int color = board[x][y];
        for (int i = x - 1; i >= 0; i--){
            if (board[i][y] == color){
                count++;
            }
            else{
                break;
            }
        }
        for (int i = x + 1; i < 15; i++){
            if (board[i][y] == color){
                count++;
            }
            else{
                break;
            }
        }
        if (count >= INROW){
            return true;
        }
        else{
            return false;
        }
    }
    /*
    *判断当前行内是否有五子相连
    * @param x 当前横坐标
    * @param y 当前纵坐标
    * @return boolean
     */
    public boolean judgeRow(int x, int y) {
        int count = 1;
        int color = board[x][y];
        for (int i = y - 1; i >= 0; i--) {
            if (board[x][i] == color) {
                count++;
            } else {
                break;
            }
        }
        for (int i = y + 1; i < 15; i++) {
            if (board[x][i] == color) {
                count++;
            } else {
                break;
            }
        }
        if (count >= INROW) {
            return true;
        } else {
            return false;
        }
    }
        /*
        *判断当前左斜对角线内是否有五子相连
        * @param x 当前横坐标
        * @param y 当前纵坐标
        * @return boolean
         */
        public boolean judgeLeftDiagonal(int x, int y) {
            int count = 1;
            int color = board[x][y];
            for (int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--) {
                if (board[i][j] == color) {
                    count++;
                } else {
                    break;
                }
            }
            for (int i = x + 1, j = y + 1; i < 15 && j < 15; i++, j++) {
                if (board[i][j] == color) {
                    count++;
                } else {
                    break;
                }
            }
            if (count >= INROW) {
                return true;
            } else {
                return false;
            }
        }
        /*
        *判断当前右斜对角线内是否有五子相连
        * @param x 当前横坐标
        * @param y 当前纵坐标
        * @return boolean
         */
    public boolean judgeRightDiagonal(int x, int y) {
        int count = 1;
        int color = board[x][y];
        for (int i = x - 1, j = y + 1; i >= 0 && j < 15; i--, j++) {
            if (board[i][j] == color) {
                count++;
            } else {
                break;
            }
        }
        for (int i = x + 1, j = y - 1; i < 15 && j >= 0; i++, j--) {
            if (board[i][j] == color) {
                count++;
            } else {
                break;
            }
        }
        if (count >= INROW) {
            return true;
        } else {
            return false;
        }
    }

    // 继承LinkedList类，实现双端队列，储存棋盘状态
    class Deque extends LinkedList<int[][]>{
        public void pushRear(int[][] board) {
            addLast(board);
        }
        public int[][] popRear() {
            return removeLast();
        }
        public void pushFront(int[][] board) {
            addFirst(board);
        }
        public int[][] popFront() {
            return removeFirst();
        }
    }

    // 复制棋盘防止引用传递
    public static void copyBoard(int[][] srcboard, int[][] dstBoard) {
        for (int i = 0; i < srcboard.length; i++) {
            for (int j = 0; j < srcboard[i].length; j++) {
                dstBoard[i][j] = srcboard[i][j];
            }
        }
    }

    // 得到当前棋盘的所有合法走法
    public static List<int[]> getValidMoves(int[][] board){
        List<int[]> resList = new ArrayList<int[]>();
        for (int i = 0; i < 15; i++){
            for (int j = 0; j < 15; j++){
                if (board[i][j] == EMPTY && isAround(board, i, j)){
                    resList.add(new int[]{i, j});
                }
            }
        }
        return resList;
    }

    // 搜索指定点位距离为5范围内是否有棋子
    public static boolean isAround(int[][] board, int x, int y){
        for (int i = x - 3; i <= x + 3; i++){
            for (int j = y - 3; j <= y + 3; j++){
                if (i >= 0 && i < 15 && j >= 0 && j < 15 && board[i][j] != EMPTY){
                    return true;
                }
            }
        }
        return false;
    }
}

▶

CompeteAI.java

import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.util.ArrayList;
import java.util.List;


public class CompeteAI {
    private static int ROW = 15;
    private static int COL = 15;
    static final int MAX_NODE = 2;
    static final int MIN_NODE = 1;
    
    // 定义best数组各对象的索引偏移量
    private static int bestScore = 0;
    private static int bestX = 1;
    private static int bestY = 2;

    public static int[] miniMaxSearch(int curDepth, int depth, int[][] board, int alpha, int beta, int role) { //role == 1 执白棋 || role == 0 执黑棋

        /*
        * 初始化最佳数组，储存最佳的落子位置与分数
        * 0 -> bestScore, 1 -> bestX, 2 -> bestY 
        */ 
        int[] best = new int[3];

        /*
         * 初始化Board类，用于调用isWin函数
         */
        Board Board = new Board(board);

        /*
         * 初始化三个ArrayList，分别用于存储当前局面的所有可能走法(int[][])、走法数组(int[])评估值(int)
         */
        List<int[][]> childBoardList = new ArrayList<int[][]>();
        List<int[]> dirList = new ArrayList<int[]>();
        List<Integer> scoreList = new ArrayList<Integer>();

        /*
         * 调用generateStep方法，返回该步所有可能的走法
         */
        for (int[] step : Board.getValidMoves(Board.getBoard())) {
            Board childBoard = new Board(board);
            dirList.add(step);
            childBoard.putChess(step[0], step[1], role + 1);
            childBoardList.add(childBoard.getBoard());
        }

        /*
         * 当搜索到叶子节点或有一方胜利时，返回评估值
         * 评估值为当前局面的分数
         * 当正在执行搜索且子节点未被剪枝时，进行Func递归
         * curDepth++表示向下层搜索，childBoard表示以该子
         * 节点棋盘状态重新迭代，role ^ 1 表示棋色反转
         * 同时alpha、beta值向下传递以更新
         */
        if (curDepth == depth || Board.isWin((role ^ 1) + 1)) {
            best[0] = evaluate(board, role ^ 1);
            return best;
        } else {

            // 当前节点为MAX节点时
            if (curDepth % 2 == 0) {
                for (int[][] childBoard : childBoardList) {
                    int[] res = miniMaxSearch(curDepth + 1, depth, childBoard, alpha, beta, role ^ 1);
                    scoreList.add(res[bestScore]);
                    alpha = Math.max(alpha, res[bestScore]);
                    if (alpha >= beta) {
                        break;
                    }
                }
                /*
                 * 若深度为0，搜索该最值对应的走法数组
                 */
                if (curDepth == 0) {
                    int bestIndex = scoreList.indexOf(alpha);
                    best[bestX] = dirList.get(bestIndex)[0];
                    best[bestY] = dirList.get(bestIndex)[1];
                }
                best[bestScore] = alpha;
                return best;

                // 当前节点为MIN节点时
            } else {
                for (int[][] childBoard : childBoardList) {
                    int[] res = miniMaxSearch(curDepth + 1, depth, childBoard, alpha, beta, role ^ 1);
                    scoreList.add(res[bestScore]);
                    beta = Math.min(beta, res[bestScore]);
                    if (alpha >= beta) {
                        break;
                    }
                }
                best[bestScore] = beta;
                return best;
            }
        }
    }


    /**
     * @description: 基于role评估该棋面的得分
     * @param {int[][]} board
     * @param {int} role
     * @return {*}
     */    
    public static int evaluate(int[][] board, int role) {
        int value = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                if (board[i][j] != 0) {
                    value += evaluatePoint(board, i, j, role);
                }
            }
        }
        return value;
    }

    /*
     * 生成字符串匹配模式
     * FIVE为五连，FOUR为活四，RUSH_FOUR为冲四，DEAD_FOUR为死四，THREE为活三，RUSH_THREE为冲三，DEAD_THREE为死三，TWO为活二，DEAD_TWO为死二
     */
    private static final Pattern FIVE_BLACK = Pattern.compile("1{5}");
    private static final Pattern FOUR_BLACK = Pattern.compile("011110");
    private static final Pattern RUSH_FOUR_BLACK = Pattern.compile("1(101|011|110)1");
    private static final Pattern DEAD_FOUR_BLACK = Pattern.compile("01111(2|3)|(2|3)11110");
    private static final Pattern THREE_BLACK = Pattern.compile("0(1011|1101)0");
    private static final Pattern RUSH_THREE_BLACK = Pattern.compile("1(100|010|001)1");
    private static final Pattern DEAD_THREE_BLACK = Pattern.compile("0(1011|1101)(2|3)|(2|3)(1011|1101)0");
    private static final Pattern TWO_BLACK = Pattern.compile("01010");
    private static final Pattern DEAD_TWO_BLACK = Pattern.compile("0101(2|3)|(2|3)1010");

    private static final Pattern[] mBlack = { FIVE_BLACK, FOUR_BLACK, RUSH_FOUR_BLACK, DEAD_FOUR_BLACK, THREE_BLACK,
            RUSH_THREE_BLACK, DEAD_THREE_BLACK, TWO_BLACK, DEAD_TWO_BLACK };

    private static final Pattern FIVE_WHITE = Pattern.compile("2{5}");
    private static final Pattern FOUR_WHITE = Pattern.compile("022220");
    private static final Pattern RUSH_FOUR_WHITE = Pattern.compile("2(202|022|220)2");
    private static final Pattern DEAD_FOUR_WHITE = Pattern.compile("02222(1|3)|(1|3)22220");
    private static final Pattern THREE_WHITE = Pattern.compile("0(2022|2202)0");
    private static final Pattern RUSH_THREE_WHITE = Pattern.compile("2(200|020|002)2");
    private static final Pattern DEAD_THREE_WHITE = Pattern.compile("0(2022|2202)(1|3)|(1|3)(2022|2202)0");
    private static final Pattern TWO_WHITE = Pattern.compile("02020");
    private static final Pattern DEAD_TWO_WHITE = Pattern.compile("0202(1|3)|(1|3)2020");

    private static final Pattern[] mWhite = { FIVE_WHITE, FOUR_WHITE, RUSH_FOUR_WHITE, DEAD_FOUR_WHITE, THREE_WHITE,
            RUSH_THREE_WHITE, DEAD_THREE_WHITE, TWO_WHITE, DEAD_TWO_WHITE };

    // 将匹配模式转化为分数
    public static int pattern2point(Pattern pattern) {
        switch (pattern.toString()) {
            case "1{5}":
                return 100000;
            case "011110":
                return 10000;
            case "1(101|011|110)1":
                return 1000;
            case "01111(2|3)|(2|3)11110":
                return 100;
            case "0(1011|1101)0":
                return 100;
            case "1(100|010|001)1":
                return 10;
            case "0(1011|1101)(2|3)|(2|3)(1011|1101)0":
                return 5;
            case "01010":
                return 5;
            case "0101(2|3)|(2|3)1010":
                return 1;
            
            case "2{5}":
                return - Integer.MAX_VALUE;
            case "022220":
                return -100000;
            case "2(202|022|220)2":
                return -1000;
            case "02222(1|3)|(1|3)22220":
                return -100;
            case "0(2022|2202)0":
                return -100;
            case "2(200|020|002)2":
                return -10;
            case "0(2022|2202)(1|3)|(1|3)(2022|2202)0":
                return -5;
            case "02020":
                return -5;
            case "0202(1|3)|(1|3)2020":
                return -1;
            
            default:
                return 0;
        }
    }

    public static int evaluatePoint(int[][] board, int x, int y, int role) {
        int value = 0;
        Board Board = new Board(board);

        // 以当前棋色放置棋子
        Board.putChess(x, y, role + 1);
        
        /*
         * 搜索以四个方向两端延伸5个位置的棋子(到边界停止)并转化储存为字符串dirROW,dirCOL,dirLeftDiagonal,dirRightDiagonal(1为黑棋，2为白棋，0为空)
         */
        String dirROW = "";
        String dirCOL = "";
        String dirLeftDiagonal = "";
        String dirRightDiagonal = "";

        // 搜索横向
        for (int i = x - 5; i < x + 5; i++) {
            if (i >= 0 && i < ROW) {
                dirROW += board[x][i];
            }
            else{
                dirROW += "3";
            }
        }

        // 搜索纵向
        for (int i = y - 5; i < y + 5; i++) {
            if (i >= 0 && i < COL) {
                dirCOL += board[i][y];
            }
            else{
                dirCOL += "3";
            }
        }

        // 搜索左斜对角线
        for (int i = x - 5, j = y - 5; i < x + 5 && j < y + 5; i++, j++) {
            if (i >= 0 && i < ROW && j >= 0 && j < COL) {
                dirLeftDiagonal += board[i][j];
            }
            else{
                dirLeftDiagonal += "3";
            }
        }

        // 搜索右斜对角线
        for (int i = x - 5, j = y + 5; i < x + 5 && j > y - 5; i++, j--) {
            if (i >= 0 && i < ROW && j >= 0 && j < COL) {
                dirRightDiagonal += board[i][j];
            }
            else{
                dirRightDiagonal += "3";
            }
        }
        
        // 创建棋子字符串数组方便遍历
        String[] dirs = { dirROW, dirCOL, dirLeftDiagonal, dirRightDiagonal };

        /*
         * 对每一个方向的棋子进行匹配，若匹配成功则返回对应的分数
         * 角色相同则返回正分，角色不同则返回负分
         * 五连为int最大值，活四为10000，冲四为1000，死四为100，活三为100，冲三为10，死三为5，活二为5，死二为1
         */
        for (String dir : dirs) {
            for (Pattern pattern : mBlack) {
                Matcher matcher = pattern.matcher(dir);
                int mul = (role == 0)? 1 : -1;
                while (matcher.find()) {
                    value += mul * pattern2point(pattern);
                }
            }
            
            for (Pattern pattern : mWhite) {
                Matcher matcher = pattern.matcher(dir);
                int mul = (role == 0)? -1 : 1;
                while (matcher.find()) {
                    value += mul * pattern2point(pattern);
                }
            }
        }

        return value;
    }

    public static void copyBoard(int[][] board, int[][] newBoard) {
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                newBoard[i][j] = board[i][j];
            }
        }
    }
}

参考

1. 本文主要参考自该GitHub Issue javascript gobang AI，JS五子棋AI，源码+教程，基于Alpha-Beta剪枝算法（不是神经网络)

   ↩

2. Minimax算法解释与思路来源 Oi.wiki ↩
3. 依然参考自 Oi.wiki
   ↩