井字游戏脚趾αβ极小值

Question

为了更好地理解minimax算法是如何工作的，我一直在做一个tic-tac-toe程序。以下实现无法正常工作，因为计算机可能会丢失游戏。如果程序运行正常，理论上这是不可能的。。。

我是否在实施极大极小值或采取最佳行动时犯了错误？

我以前从未实现过算法： s

评价函数

public static int evaluate(char[] board, char turn) {
    if (isWinFor('x', board)) {
        return -1;
    } else if (isWinFor('o', board)) {
        return 1;
    } 
    return 0;
}

极小极大

public static int alphabeta(char[] board, int depth, char turn, int alpha, int beta) {
    if (depth == 0 || gameOver(board)) {
        return evaluate(board, turn);
    } else {
        for (int move : possibleMoves(board)) {
            makeMove(board, turn, move);
            turn = changeTurn(turn);
            int value = alphabeta(board, depth--, turn, alpha, beta);   
            makeMove(board, ' ', move);
            if (turn == 'o') {
                if (value > alpha) {
                    alpha = value;
                }
                if (alpha >= beta) {
                    return beta;
                }
            } else if (turn == 'x') {
                if (value < beta) {
                    beta = value;
                }
                if (beta <= alpha) {
                    return alpha;
                }
            }               
        }
        if (turn == 'o') {
            return  alpha;
        } else {
            return  beta;
        }             
    }
}

找到最好的办法

public static void getBestMove(char[] board, char turn) {
    Random random  = new Random();
    int bestValue = -10000;
    List<Integer> choices = new ArrayList<Integer>();
    for (int move : possibleMoves(board)) {
        makeMove(board, turn, move);
        turn = changeTurn(turn);
        int value = alphabeta(board, 3, turn, -10000, 10000);   
        makeMove(board, ' ', move);
        if (value > bestValue) {
            bestValue = value;
            //start code edit
            choices.clear();
            //end code edit
            choices.add(move);
        } else if (value == bestValue) {
            choices.add(move);
        }
    }
    makeMove(board, turn, choices.get(random.nextInt(choices.size())));
}

非常感谢。

Answer 1

除了前面的答案之外，我很确定你的GetBestMobile是错误的：每当一个移动更好或等于你当前最好的移动时，你都会添加一个选择。但是当最佳值改变时，你实际上并没有清除列表。这意味着你的选择列表中会有失败的动作。

Answer 2

这很简单：一个完美的玩家必须搜索整棵树的最大深度（除了截断节点），但是你把你的程序限制为只有4层！

“寻找最佳移动”中有一个错误：

int value = alphabeta(board, 3, turn, -10000, 10000);        

把它改成

int value = alphabeta(board, 8, turn, -10000, 10000);