井字棋Minimax算法异常：AI未选择最优落子问题求助

我开发的井字棋游戏中，Minimax算法运行异常：AI（玩家2）会连续落子，完全不遵循最优策略——既无视阻止人类玩家（玩家1）获胜的机会，也不主动争取平局。我已经尝试过用ChatGPT修改代码、参考教程重写，耗时4天仍未解决问题，特此求助。

核心涉及两个类：GameLogic与TicTacToeBoard，AI的落子逻辑在TicTacToeBoard中实现，棋盘以二维数组表示，通过updateGameBoard和setCell方法更新棋盘，checkRes方法检查游戏状态。以下是关键代码：

GameLogic类代码 #

class GameLogic{
private int[][] gameBoard;
private int player = 1;
//1st element —> row, 2nd element —> col, 3rd —> line type
private int[] wintype = {-1, -1, -1};

public boolean updateGameBoard(int row, int col, boolean show){ //works if cell is empty
        if(gameBoard[row-1][col-1] == 0){ //if cell is empty
            gameBoard[row-1][col-1] = player; //a cell number is assigned
            if(player == 1 && show){ //if human
                playerTurn.setText(playerNames[1] + "'s turn");
            }
            else if(player == 2 && show){ //if bot
                playerTurn.setText(playerNames[0] + "'s turn");
            }
            return true;
        }else{
            return false;
        }
    }
public String checkRes(){
        boolean isWinner = false;
        for(int r=0; r<3; r++){
            if(gameBoard[r][0] == gameBoard[r][1] && gameBoard[r][0] == gameBoard[r][2] && gameBoard[r][0] != 0){
                wintype = new int[]{r, 0, 1};
                isWinner = true;
            }
        }
        for(int c=0; c<3; c++){
            if(gameBoard[0][c] == gameBoard[1][c] && gameBoard[2][c] == gameBoard[0][c] && gameBoard[0][c] != 0){
                wintype = new int[]{0, c ,2};
                isWinner = true;
            }
        }
        if(gameBoard[0][0] == gameBoard[1][1] && gameBoard[0][0] == gameBoard[2][2] && gameBoard[0][0] != 0){
            wintype = new int[]{0, 2 ,3};
            isWinner = true;
        }
        else if(gameBoard[2][0] == gameBoard[1][1] && gameBoard[2][0] == gameBoard[0][2] && gameBoard[2][0] != 0){
            wintype = new int[]{2, 2 ,4};
            isWinner = true;
        }
        int boardFilled = 0;
        for(int r=0; r<3; r++){
            for(int c=0; c<3; c++){
                if(gameBoard[r][c] != 0){
                    boardFilled++;
                }
            }
        }
        if(isWinner){
            return "Won";
        }
        else if(boardFilled == 9){
            return "Tie";
        }else{
            return "Continue";
        }
    }
    public void showWin(){
        playAgainBTN.setVisibility(View.VISIBLE);
        homeBTN.setVisibility(View.VISIBLE);
        playerTurn.setText((playerNames[player-1] + " Won!"));

    }
    public void showTie(){
        playAgainBTN.setVisibility(View.VISIBLE);
        homeBTN.setVisibility(View.VISIBLE);
        playerTurn.setText("Tie game!");
    }
}

TicTacToeBoard类代码 #

class TicTacToeBoard{
   private final GameLogic game;
   private boolean winningLine = false;
public boolean onTouchEvent(MotionEvent event) { //the code for processing the course of the game tic-tac-toe
        float x = event.getX();
        float y = event.getY();

        int action = event.getAction();

        if (action == MotionEvent.ACTION_DOWN && game.getPlayer() == 1) {
            int row = (int) Math.ceil(y / cellSize);
            int col = (int) Math.ceil(x / cellSize);

            if (!winningLine) {
                if (game.updateGameBoard(row, col, true)) { //if there is an empty space, it assigns a value to this cell
                    invalidate();
                    if(game.checkRes().equals("Won")) {
                        winningLine = true;
                        game.showWin();
                    }
                    if(game.checkRes().equals("Tie")){
                        game.showTie();
                    }
                    game.setPlayer(2);
                }
            }
            return true;
        }

        else if (game.getPlayer() == 2) {
            hardDifficult();
        }
        return false;
    }
private void hardDifficult(){
        int[] bestMove = findBestMove();
        num1 = bestMove[0];
        num2 = bestMove[1];
        if(!winningLine){
            if(game.updateGameBoard(bestMove[0] + 1, bestMove[1] + 1, true)){
                invalidate();
                if(game.checkRes().equals("Won")){
                    winningLine = true;
                    game.showWin();

                }
                if(game.checkRes().equals("Tie")){
                    game.showTie();
                }
                game.setPlayer(1);
            }
        }
    }
    private int[] findBestMove() {
        int bestScore = Integer.MIN_VALUE;
        int[] bestMove = new int[2];
        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (game.updateGameBoard(r + 1, c + 1,false)){
                    int score = minimax(0, false);
                    game.setCell(r,c,0);
                    if (score > bestScore) {
                        bestScore = score;
                        bestMove[0] = r;
                        bestMove[1] = c;
                    }
                }
            }
        }
        return bestMove;
    }

    private int minimax(int depth, boolean isMaximizing) {
        if (game.checkRes().equals("Won")) {
            showInfo[0] = evaluateScore();
            return evaluateScore();
        }

        if (isMaximizing) {
            int bestScore = Integer.MIN_VALUE;
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    if (game.updateGameBoard(r + 1, c + 1, false)){
                        int score = minimax(depth+1, false);
                        game.setCell(r,c,0);
                        bestScore = Math.max(score, bestScore);
                    }
                }
            }
            return bestScore;
        } else {
            int bestScore = Integer.MAX_VALUE;
            for (int r = 0; r < 3; r++) {
                for (int c = 0; c < 3; c++) {
                    if (game.updateGameBoard(r + 1, c + 1, false)){
                        int score = minimax(depth+1, true);
                        game.setCell(r,c,0);
                        bestScore = Math.min(score, bestScore);
                    }
                }
            }
            return bestScore;
        }
    }

    private int evaluateScore() {

        if (game.checkRes().equals("Won") && game.getPlayer() == 2) {
// AI won
            return 10;
        } else if (game.checkRes().equals("Won") && game.getPlayer() == 1) {
// Player won
            return -10;
        } else if (game.checkRes().equals("Tie")) {
// Game tied
            return 0;
        }

        return 0;
    }
}

问题分析与修复方案 #

核心问题点 #

1. Minimax模拟时未切换玩家：调用updateGameBoard后未切换玩家，导致模拟对方回合时仍用当前玩家标记，evaluateScore无法正确判断获胜方。
2. evaluateScore判断逻辑错误：依赖game.getPlayer()判断获胜方，但模拟结束时的玩家并非实际获胜方，应直接从棋盘状态判断。
3. Minimax未处理平局情况：仅处理获胜状态，未判断平局，导致递归无法终止于平局场景。
4. findBestMove的isMaximizing参数错误：AI是最大化玩家，调用minimax时应传入true而非false。

修改后的关键代码 #

1. 修复findBestMove方法

private int[] findBestMove() {
    int bestScore = Integer.MIN_VALUE;
    int[] bestMove = new int[2];
    int originalPlayer = game.getPlayer(); // 保存原始玩家状态
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) {
            if (game.updateGameBoard(r + 1, c + 1,false)){
                // AI落子后切换到玩家1模拟对方回合
                game.setPlayer(1);
                int score = minimax(0, false);
                // 回溯棋盘和玩家状态
                game.setCell(r,c,0);
                game.setPlayer(originalPlayer);
                if (score > bestScore) {
                    bestScore = score;
                    bestMove[0] = r;
                    bestMove[1] = c;
                }
            }
        }
    }
    return bestMove;
}

2. 修复minimax方法（添加平局处理+玩家切换）

private int minimax(int depth, boolean isMaximizing) {
    String result = game.checkRes();
    if (result.equals("Won")) {
        return evaluateScore();
    }
    if (result.equals("Tie")) {
        return 0;
    }

    int originalPlayer = game.getPlayer();
    if (isMaximizing) {
        int bestScore = Integer.MIN_VALUE;
        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (game.updateGameBoard(r + 1, c + 1, false)){
                    // 最大化玩家（AI）落子后切换到最小化玩家（人类）
                    game.setPlayer(1);
                    int score = minimax(depth+1, false);
                    game.setCell(r,c,0);
                    game.setPlayer(originalPlayer);
                    bestScore = Math.max(score, bestScore);
                }
            }
        }
        return bestScore;
    } else {
        int bestScore = Integer.MAX_VALUE;
        for (int r = 0; r < 3; r++) {
            for (int c = 0; c < 3; c++) {
                if (game.updateGameBoard(r + 1, c + 1, false)){
                    // 最小化玩家（人类）落子后切换到最大化玩家（AI）
                    game.setPlayer(2);
                    int score = minimax(depth+1, true);
                    game.setCell(r,c,0);
                    game.setPlayer(originalPlayer);
                    bestScore = Math.min(score, bestScore);
                }
            }
        }
        return bestScore;
    }
}

3. 修复evaluateScore方法（直接从棋盘判断获胜方）

private int evaluateScore() {
    // 检查行获胜
    for(int r=0; r<3; r++){
        if(game.getGameBoard()[r][0] == game.getGameBoard()[r][1] && 
           game.getGameBoard()[r][0] == game.getGameBoard()[r][2] && 
           game.getGameBoard()[r][0] != 0){
            return game.getGameBoard()[r][0] == 2 ? 10 : -10;
        }
    }
    // 检查列获胜
    for(int c=0; c<3; c++){
        if(game.getGameBoard()[0][c] == game.getGameBoard()[1][c] && 
           game.getGameBoard()[0][c] == game.getGameBoard()[2][c] && 
           game.getGameBoard()[0][c] != 0){
            return game.getGameBoard()[0][c] == 2 ? 10 : -10;
        }
    }
    // 检查对角线获胜
    if(game.getGameBoard()[0][0] == game.getGameBoard()[1][1] && 
       game.getGameBoard()[0][0] == game.getGameBoard()[2][2] && 
       game.getGameBoard()[0][0] != 0){
        return game.getGameBoard()[0][0] == 2 ? 10 : -10;
    }
    if(game.getGameBoard()[2][0] == game.getGameBoard()[1][1] && 
       game.getGameBoard()[2][0] == game.getGameBoard()[0][2] && 
       game.getGameBoard()[2][0] != 0){
        return game.getGameBoard()[2][0] == 2 ? 10 : -10;
    }
    // 平局或未结束
    return 0;
}

注：需给GameLogic添加getGameBoard()方法，暴露棋盘状态供评估使用。

内容的提问来源于stack exchange，提问作者Влад КК