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实现本身几乎没问题，看看维基页面：

Minimax Algorithm

我认为最小化玩家应该使用best move = +infinity (在你的例子中是Integer.MAX_VALUE)

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

希望这能有所帮助