为什么添加alpha beta后我的minimax这么慢？

Question

我的木板是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 [] []数组比复制该板并将其传递给递归调用要花费更少的时间（我认为）

Answer 1

我不确定这是什么游戏，但是如果它是由多个棋子（棋盘，跳棋等）组成的游戏，那么您将在每回合之后重新计算每一棋子的每一步，直到搜索深度。第一次使用minimax（）后，您可以保存很多状态，因为电路板每转不会改变那么多。如果您有一棵可能的未来董事会状态树，而不是2D整数数组，则当您或对手的举动影响该状态时，您可以标记节点/叶。然后，在循环中，如果未标记任何子节点，则跳过重新计算节点的alpha / beta。我希望这是有道理的。基本上，缓存您可以的内容。