java - 面对为国际象棋游戏实现极小极大的性能问题

Question

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

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

• 深度 = 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 种)。

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

• 对于深度 1，MinMax 仅考虑 20 步。
• 对于深度 2，MinMax 会考虑 20 个 Action 以及该 Action 的 20 个答案，400 个可能的 Action ，没问题。
• 对于深度 3，MinMax 考虑 20^3 = 8.000 种可能的移动。您的机器已运行 15 秒。
• 对于深度 4，MinMax 考虑 20^4 = 160.000 种可能的移动。这将比前一个花费大约 20 倍的时间...

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

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

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

如果这还不够，我会考虑切换到完全其他算法 - Monte Carlo Tree Search (使用 UCT)例如。

走法数据库也可以提供帮助 - 您可以准备好(预先计算的)策略，而不是计算第一个走法。

著名Deep Blue 1997年击败卡斯帕罗夫的人使用了它们，你可以查看它还使用了什么here .