我正在尝试为一个小国际象棋游戏实现极小极大算法。也许我的前提是错误的，这不是应该尝试的事情。是吗？
该程序可以运行，但存在很大的性能问题:
- 深度 = 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;
}
}
也许算法的实现、对象的设计或使用中存在错误。我无法指指点点。因此，在尝试优化代码或调整程序的内存配置之前，我想确保没有忽略任何重大问题。
注意:没有内存分析经验。
最佳答案
在国际象棋中，有 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)例如。
走法数据库也可以提供帮助 - 您可以准备好(预先计算的)策略，而不是计算第一个走法。
关于java - 面对为国际象棋游戏实现极小极大的性能问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31213219/