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

问题描述 投票:3回答:1

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

java minimax alpha-beta-pruning
1个回答
0
投票

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

推荐问答
热门问答
最新问答