我的木板是15 x 15平方。如果搜索深度为2,我的minimax算法需要不到5秒才能完成;如果搜索深度为3,则需要5到10秒;如果搜索深度为4,则需要超过10秒(超出我的设置限制)。这是正常现象,还是我的alpha-beta修剪实施错误?
问题:在加深游戏搜索树的同时,如何使我的minimax算法更快?
我的minimax()
实现:
最大播放器:
if (maximizingPlayer) {
int bestScore = Integer.MIN_VALUE;
for (String move : board.getPossibleMoves(board.getCurrentPlayer())) {
int[][] grid = board.apply(move);
int currentScore = minimax(board, depth - 1, false, alpha, beta);
board.setBoardGrid(grid); // Undo
if (currentScore > bestScore) {
bestScore = currentScore;
alpha = Math.max(alpha, bestScore);
bestMove = move;
if (alpha >= beta) {
break;
}
}
}
return bestScore;
最小玩家:
int bestScore = Integer.MAX_VALUE;
for (String move : board.getPossibleMoves(board.getEnemyPlayer())) {
int[][] grid = board.apply(move);
bestScore = minimax(board, depth - 1, true, alpha, beta);
beta = Math.min(beta, bestScore);
board.setBoardGrid(grid); // Undo
if (alpha >= beta) {
break;
}
}
return beta;
board.apply(move)
方法将move
参数应用于电路板。该方法会在应用移动之前返回木板的副本(15 x 15,名为grid
),因此在递归结束后可以撤消移动。网格是一个double int数组:int[][] grid = new int[15][15]
,所以复制到一个新的double int [] []数组比复制该板并将其传递给递归调用要花费更少的时间(我认为)
我不确定这是什么游戏,但是如果它是由多个棋子(棋盘,跳棋等)组成的游戏,那么您将在每回合之后重新计算每一棋子的每一步,直到搜索深度。第一次使用minimax()后,您可以保存很多状态,因为电路板每转不会改变那么多。如果您有一棵可能的未来董事会状态树,而不是2D整数数组,则当您或对手的举动影响该状态时,您可以标记节点/叶。然后,在循环中,如果未标记任何子节点,则跳过重新计算节点的alpha / beta。我希望这是有道理的。基本上,缓存您可以的内容。