JavaFX实现四子棋Minimax算法时出现栈溢出错误

问题概述 #

使用JavaFX开发6列5行的四子棋（Connect 4）游戏时，实现Minimax算法触发StackOverflowError。AI回合调用movePiece(-1)，传入0-5范围内的随机列时运行正常，但Minimax函数执行时出现栈溢出。

错误代码分析 #

AiPlayer类代码 #

package lk.ijse.dep.service;
public class AiPlayer extends Player {

    private final Board board;

    public AiPlayer(Board board) {
        this.board = board;
    }

    @Override
    public void movePiece(int col) {
        col = minimax(5, true); // 错误：将评估值直接作为列索引使用

        board.updateMove(col, Piece.GREEN); // 在选中列放置棋子
        board.getBoardUI().update(col, false);

        Winner winner = board.findWinner();
        if (winner.getWinningPiece() == Piece.GREEN) {
            board.getBoardUI().notifyWinner(winner);
        }

        if (!board.existLegalMove()) {
            board.getBoardUI().notifyWinner(new Winner(Piece.EMPTY));
        }
    }

    private int minimax(int depth, boolean maximizingPlayer) {
        if(depth == 0 || !board.existLegalMove()) return 0;

        if (maximizingPlayer) {
            int maxEval = (int) Double.NEGATIVE_INFINITY;
            for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
                System.out.println(i);
                // 错误：递归时depth递增，永远无法触发depth==0的终止条件
                int heuristicVal = minimax(depth + 1, false); 
                maxEval = Math.max(heuristicVal, maxEval);
            }
            return maxEval;
        } else {
            int minEval = (int) Double.POSITIVE_INFINITY;
            for (int i = 0; i < this.board.NUM_OF_COLS; i++) {
                System.out.println(i);
                // 错误：递归时depth递增，永远无法触发depth==0的终止条件
                int heuristicVal = minimax(depth + 1, true); 
                minEval = Math.min(heuristicVal, minEval);
            }
            return minEval;
        }
    }
}

Board类existLegalMove函数代码 #

public boolean existLegalMove() {
    // 逻辑冗余：遍历整个棋盘，四子棋合法落子只需判断列是否未满
    for (int i = 0; i < NUM_OF_COLS; i++) {
        for (int j = 0; j < NUM_OF_ROWS; j++) {
            if (pieces[i][j].equals(Piece.EMPTY)) {
                return true;
            }
        }
    }
    return false;
}

核心问题点 #

1. 递归终止条件失效：Minimax递归时depth递增而非递减，导致永远无法触发depth == 0的终止条件，递归无限调用引发栈溢出。
2. 未模拟落子与回溯：未在递归前模拟落子、递归后撤销落子，无法正确评估局面，且existLegalMove始终返回true（棋盘未被修改），进一步加剧递归无限循环。
3. 返回值逻辑错误：Minimax函数返回的是局面评估值，但movePiece直接将其作为列索引使用，逻辑完全错误。
4. 合法落子判断低效且不匹配：existLegalMove遍历整个棋盘，且Minimax循环所有列时未先判断列是否可落子（列已满的情况无需递归）。

修复方案 #

1. 修正递归深度处理 #

递归时将depth递减，确保触发终止条件：

// 最大化玩家递归调用修改为
int heuristicVal = minimax(depth - 1, false);
// 最小化玩家递归调用修改为
int heuristicVal = minimax(depth - 1, true);

2. 添加落子模拟与回溯 #

在递归前模拟落子，递归后撤销落子，确保每一步递归基于真实局面：

private int minimax(int depth, boolean maximizingPlayer) {
    Winner winner = board.findWinner();
    // 新增终止条件：已分出胜负
    if (depth == 0 || !board.existLegalMove() || winner.getWinningPiece() != Piece.EMPTY) {
        return evaluateBoard(winner, depth, maximizingPlayer);
    }

    if (maximizingPlayer) {
        int maxEval = (int) Double.NEGATIVE_INFINITY;
        for (int col = 0; col < board.NUM_OF_COLS; col++) {
            // 先判断列是否可落子
            if (isColumnValid(col)) {
                // 模拟落子
                board.updateMove(col, Piece.GREEN);
                int eval = minimax(depth - 1, false);
                maxEval = Math.max(maxEval, eval);
                // 回溯：撤销落子
                undoMove(col);
            }
        }
        return maxEval;
    } else {
        int minEval = (int) Double.POSITIVE_INFINITY;
        for (int col = 0; col < board.NUM_OF_COLS; col++) {
            if (isColumnValid(col)) {
                board.updateMove(col, Piece.BLUE); // 假设人类玩家使用BLUE棋子
                int eval = minimax(depth - 1, true);
                minEval = Math.min(minEval, eval);
                // 回溯：撤销落子
                undoMove(col);
            }
        }
        return minEval;
    }
}

// 辅助函数：判断列是否可落子
private boolean isColumnValid(int col) {
    // 检查列的顶部是否为空（假设行索引0为顶部，NUM_OF_ROWS-1为底部）
    return board.pieces[col][0].equals(Piece.EMPTY);
}

// 辅助函数：撤销落子
private void undoMove(int col) {
    // 找到该列最顶部的非空棋子，设为EMPTY
    for (int row = 0; row < board.NUM_OF_ROWS; row++) {
        if (!board.pieces[col][row].equals(Piece.EMPTY)) {
            board.pieces[col][row] = Piece.EMPTY;
            break;
        }
    }
}

// 局面评估函数
private int evaluateBoard(Winner winner, int depth, boolean maximizingPlayer) {
    Piece winningPiece = winner.getWinningPiece();
    if (winningPiece == Piece.GREEN) {
        return maximizingPlayer ? 100 + depth : -100 - depth;
    } else if (winningPiece == Piece.BLUE) {
        return maximizingPlayer ? -100 - depth : 100 + depth;
    }
    return 0; // 平局或未分胜负
}

3. 调整Minimax返回逻辑 #

原函数返回评估值无法直接作为列索引，需通过类变量记录最佳列：

private int bestCol = -1;

private int minimax(int depth, boolean maximizingPlayer) {
    Winner winner = board.findWinner();
    if (depth == 0 || !board.existLegalMove() || winner.getWinningPiece() != Piece.EMPTY) {
        return evaluateBoard(winner, depth, maximizingPlayer);
    }

    if (maximizingPlayer) {
        int maxEval = (int) Double.NEGATIVE_INFINITY;
        for (int col = 0; col < board.NUM_OF_COLS; col++) {
            if (isColumnValid(col)) {
                board.updateMove(col, Piece.GREEN);
                int eval = minimax(depth - 1, false);
                undoMove(col);
                if (eval > maxEval) {
                    maxEval = eval;
                    bestCol = col; // 记录最佳列
                }
            }
        }
        return maxEval;
    } else {
        int minEval = (int) Double.POSITIVE_INFINITY;
        for (int col = 0; col < board.NUM_OF_COLS; col++) {
            if (isColumnValid(col)) {
                board.updateMove(col, Piece.BLUE);
                int eval = minimax(depth - 1, true);
                undoMove(col);
                minEval = Math.min(minEval, eval);
            }
        }
        return minEval;
    }
}

@Override
public void movePiece(int col) {
    minimax(5, true); // 调用后bestCol被赋值
    if (bestCol != -1) {
        col = bestCol;
        board.updateMove(col, Piece.GREEN);
        board.getBoardUI().update(col, false);
        
        Winner winner = board.findWinner();
        if (winner.getWinningPiece() == Piece.GREEN) {
            board.getBoardUI().notifyWinner(winner);
        }

        if (!board.existLegalMove()) {
            board.getBoardUI().notifyWinner(new Winner(Piece.EMPTY));
        }
    }
}

4. 优化existLegalMove函数 #

public boolean existLegalMove() {
    // 仅检查每列是否有可落子空间，无需遍历整个棋盘
    for (int col = 0; col < NUM_OF_COLS; col++) {
        if (pieces[col][0].equals(Piece.EMPTY)) {
            return true;
        }
    }
    return false;
}

内容的提问来源于stack exchange，提问作者SKS