面临为国际象棋游戏实施 minimax 的性能问题

Question

我正在尝试为一个小国际象棋游戏实现 minimax 算法。也许我的前提是错误的，这不是应该尝试的事情。是吗？

该程序可以运行，但存在很大的性能问题：

深度 = 0、1 或 2 结果立竿见影。
深度 = 3 结果需要 15 秒。
深度 = 4 - 还没有结果。

这是我的实现：

private Move findBestMove(Chessboard chessboard, int depth,
        boolean maximizingPlayer) {
    if (depth == 0) {
        return new Move(chessboard.calculateHeuristicValue());
    } else {
        Move bestMove;
        if (maximizingPlayer) {
            bestMove = new Move(Integer.MIN_VALUE);
            for (Move possibleMove : findAllPossibleMoves(chessboard,
                    !(maximizingPlayer ^ whiteTurn))) {
                Move move = findBestMove(
                        possibleMove.getResultChessboard(), depth - 1,
                        !maximizingPlayer);
                if (move.getValue() > bestMove.getValue()) {
                    possibleMove.setValue(move.getValue());
                    bestMove = possibleMove;
                }
            }
        } else {
            bestMove = new Move(Integer.MAX_VALUE);
            for (Move possibleMove : findAllPossibleMoves(chessboard,
                    !(maximizingPlayer ^ whiteTurn))) {
                Move move = findBestMove(
                        possibleMove.getResultChessboard(), depth - 1,
                        !maximizingPlayer);
                if (move.getValue() < bestMove.getValue()) {
                    possibleMove.setValue(move.getValue());
                    bestMove = possibleMove;
                }
            }
        }
        return bestMove;
    }
}

可能在算法的实现或对象的设计或使用中存在错误。我不能把我的手指放在上面。因此，在尝试优化代码或调整程序的内存配置之前，我想确保没有我忽略的主要问题。

注意：没有内存分析经验。

Answer 1

在国际象棋中，第一步有 20 种可能性（兵 16 种，马 4 种）。

为了简单起见，我们假设接下来的动作也是如此。

对于深度 1，MinMax 只考虑 20 步。
对于深度 2，MinMax 考虑 20 次移动和 20 个移动的答案，400 种可能的移动，没问题。
对于深度 3，MinMax 考虑 20^3 = 8.000 种可能的移动。在您的机器上已经 15 秒了。
对于深度 4，MinMax 考虑 20^4 = 160.000 种可能的移动。这将比前一个花费大约 20 倍的时间...

只是搜索 space 变得太大了 - 它随着输入（深度）大小呈指数增长。时间复杂度为 O(20^depth).

但是，我们不必搜索所有 space 来找到真正好的着法。

Alpha-beta pruning 是 MinMax 的流行优化。

如果这还不够，我会考虑切换到完全不同的算法 - 例如 Monte Carlo Tree Search（使用 UCT）。

着法数据库也有帮助 - 无需计算第一步，您可以已经准备好（预先计算的）开局。

著名Deep Blue who beat Kasparov in 1997 used them, you can check what else it used here.

面临为国际象棋游戏实施 minimax 的性能问题

Facing performance problems implementing minimax for a chess game

java

performance

recursion

artificial-intelligence

minimax