TicTacToe minimax 算法没有选择最佳着法

Question

我一直在为我的井字游戏编写极小极大算法，但它似乎没有选择正确的着法。有可能战胜计算机，所以我一定在这里搞混了。我认为算法本身看起来不错，所以我很确定问题在于我如何获得最佳着法。有人有什么建议吗？

极小极大法

private int minimax(Board board, boolean maximizingPlayer, char symbol){
    //System.out.println(symbol);
    Board copyBoard = new Board(board.getCells());
    char winner = copyBoard.checkWin();
    if(winner!='-' || copyBoard.checkDraw()){
        return score(winner);
    }


    if(maximizingPlayer){
        int bestValue = Integer.MIN_VALUE;
        for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
            int value = minimax(b,false,switchSymbol(mySymbol));
            if(bestValue < value){
                bestValue = value;
                bestMove = b.getLastMove();
            }
        }
        return bestValue;
    }
    else{
        int bestValue = Integer.MAX_VALUE;
        for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
            int value = minimax(b,true,mySymbol);
            if(bestValue > value){
                bestValue = value;
                bestMove = b.getLastMove();
            }
        }
        return bestValue;
    }
}

评分方法

private int score(char winner){
    if(winner == mySymbol)
        return 10;
    else if(winner == switchSymbol(mySymbol))
        return -10;
    return 0;
}

编辑：

游戏示例（人类是X，AI是O）

O 左上角
x 中心
O中左
X 左下
O 中上
X 右上角（人类获胜）

编辑 2：

更多代码，不确定错误是否在此处，不妨包含它。

private ArrayList<Integer> getPossibleMoves(Board board){
    ArrayList<Integer> moves = new ArrayList<>();
    for(int i = 0; i < board.getCells().length; i++)
        if(!board.isCellTaken(i))
            moves.add(i);
    return moves;
}

private ArrayList<Board> simulatePossibleMoves(Board board, char symbol){
    ArrayList<Board> possibleBoards = new ArrayList<>();
    for(Integer move : getPossibleMoves(board)){
        Board temp = new Board(board.getCells());
        temp.setCell(move, symbol);
        possibleBoards.add(temp);
    }
    return possibleBoards;
}

private char switchSymbol(char s){
    if(s=='X')
        return 'O';
    return 'X';
}

Answer 1

事实证明，我一直在尝试通过在 minimax 方法本身中选择最佳值来错误地使用该算法。通过创建另一个调用 minimax 方法的方法，我能够以这种方式找到最佳着法。以下代码对我有用。

public int getMiniMaxMove(Board board){
    int score = -1;
    int bestMove = -1;

    for(int i : getPossibleMoves(board)){
        Board copyBoard = new Board(board.getCells());
        copyBoard.setCell(i, mySymbol);
        int moveScore = minimax(copyBoard,false,mySymbol);

        if(moveScore >= score){
            score = moveScore;
            bestMove = i;
        }
    }

    return bestMove;
}


private int minimax(Board board, boolean maximizingPlayer, char symbol){
    Board copyBoard = new Board(board.getCells());
    char winner = copyBoard.checkWin();
    if(winner!='-' || copyBoard.checkDraw()){
        return score(winner);
    }


    if(maximizingPlayer){
        int bestValue = Integer.MIN_VALUE;
        for(Board b : simulatePossibleMoves(copyBoard,mySymbol)){
            int value = minimax(b,false,switchSymbol(mySymbol));
            if(bestValue < value){
                bestValue = value;
            }
        }
        return bestValue;
    }
    else{
        int bestValue = Integer.MAX_VALUE;
        for(Board b: simulatePossibleMoves(copyBoard, switchSymbol(mySymbol))){
            int value = minimax(b,true,mySymbol);
            if(bestValue > value){
                bestValue = value;
            }
        }
        return bestValue;
    }
}

TicTacToe minimax 算法没有选择最佳着法

TicTacToe minimax algorithm not picking best move

java

algorithm

tic-tac-toe

minimax