java - MinMax 算法无法正常工作

Question

我正在研究国际象棋引擎，现在正在尝试实现 Minimax 算法。目前我已经整理了一个 mimimax 代码，但它并没有真正正常工作。鉴于我不是一个好的棋手，我在几分钟内就击败了引擎。

我希望有人好心地查看我的 minimax 代码并告诉我我写的是正确的。

提前致谢。

这是我的代码:

private int MiniMax(Game game, int depth){

    return Max(depth);
}
private int Max(int depth){
    if (depth <= 0
            || this.chessgame.getGameState() == Game.GAME_STATE_END_YELLOW_WON
            || this.chessgame.getGameState() == Game.GAME_STATE_END_BROWN_WON){ 
        return EvaluatePieceScore();
        }
    int max = -Integer.MIN_VALUE;
    List<Move> moves = generateMoves(false);

     for(Move allMove : moves){
           executeMove(allMove);
           int score = -Mini(depth - 1);
           undoMove(allMove);

            if( score > max){
                max = score;
            }
        }
    return max;
}

private int Mini(int depth) {
    if (depth <= 0
            || this.chessgame.getGameState() == Game.GAME_STATE_END_YELLOW_WON
            || this.chessgame.getGameState() == Game.GAME_STATE_END_BROWN_WON){ 
        return EvaluatePieceScore();
        }
    int min = Integer.MIN_VALUE;
    List<Move> moves = generateMoves(false);

     for(Move allMove : moves){
           executeMove(allMove);
           int score = -Max(depth - 1);
           undoMove(allMove);

            if( score > min){
                min = score;
            }
        }
    return min;
}

Answer 1

你完成了一个相当复杂的任务:) MiniMax 实现本身几乎没问题，看看 WIKI 页面:

Minimax Algorithm

我认为最小化玩家应该使用 best move = +infinity(在您的情况下为 Integer.MAX_VALUE)

但是，既然你说你的程序运行得相当糟糕，我将提供另一个观察结果。我认为只有当你有一个非常好的评估函数(在你的情况下是 EvaluatePieceScore() 方法)时，该算法才会起作用。这就是“艺术”所在。您确定您的方法实现足够好吗？我这么说是因为通常人们将主要精力花在实现此功能上，而不是算法本身。

希望对你有帮助