1

所以我为我的奥赛罗游戏准备了一个小棋盘游戏。在这个游戏中，人工智能应该使用 Alpha Beta Prune 搜索算法来决定要移动什么。我使用了以下伪代码形式 geeksforgeeks：

function minimax(node, depth, isMaximizingPlayer, alpha, beta):

    if node is a leaf node :
        return value of the node

    if isMaximizingPlayer :
        bestVal = -INFINITY 
        for each child node :
            value = minimax(node, depth+1, false, alpha, beta)
            bestVal = max( bestVal, value) 
            alpha = max( alpha, bestVal)
            if beta <= alpha:
                break
        return bestVal

    else :
        bestVal = +INFINITY 
        for each child node :
            value = minimax(node, depth+1, true, alpha, beta)
            bestVal = min( bestVal, value) 
            beta = min( beta, bestVal)
            if beta <= alpha:
                break
        return bestVal

这就是我实现它的方式：

//Called when it's the AI's turn to make a move. 
    public Board makeMove(Board board) {
        setRoot(board);
        int alpha = Integer.MIN_VALUE;
        int beta = Integer.MAX_VALUE;

        int val = alphaBetaSearch(tree.getRoot(), 0, true, alpha, beta);
        Board resultBoard = //Should be AI Board/move

        setRoot(resultBoard);
        return resultBoard;
    }

    private int alphaBetaSearch(Node node, int depth, boolean maximizing, int alpha, int beta) {
        currentDepth = depth;
        if (node.isLeaf()) {
            return evaluateUtility(node.getBoard());
        }

        if (maximizing) {
            int bestValue = Integer.MIN_VALUE;
            for (Node child : node.getChildren()) {
                int value = alphaBetaSearch(child, depth + 1, false, alpha, beta);
                bestValue = Integer.max(bestValue, value);
                alpha = Integer.max(alpha, bestValue);
                if (beta <= alpha) {
                    break;
                }
                return alpha;
            }

        } else {
            int bestValue = Integer.MAX_VALUE;
            for (Node child : node.getChildren()) {
                int value = alphaBetaSearch(child, depth + 1, true, alpha, beta);
                bestValue = Integer.min(bestValue, value);
                beta = Integer.min(beta, bestValue);
                if (beta <= alpha) {
                    break;
                }
                return beta;
            }
        }
        return 0; //Not sure what should be returned here
    }

    private int evaluateUtility(Board board) {
        int whitePieces = board.getNumberOfWhiteCells();
        int blackPieces = board.getNumberOfBlackCells();
        int sum = (blackPieces - whitePieces);
        return sum;
    }

由于我的棋盘很小（4x4），我已经能够在游戏开始前大约 20 秒计算出完整的搜索树。这应该会改善我的搜索，因为我在玩游戏时没有构建任何东西。我的树中的每个节点都包含一个 Board，它本身有一个 2D 单元格数组。根节点/板如下所示：

EMPTY EMPTY EMPTY EMPTY
EMPTY WHITE BLACK EMPTY
EMPTY BLACK WHITE EMPTY
EMPTY EMPTY EMPTY EMPTY

现在当我开始游戏时，这是起跑板，我叫 AI 采取行动。执行 minimax 调用后，它在深度 12 处返回值 2。深度 12 是我树中的叶节点/板。在使用调试器运行它之后，我的实现似乎没有遍历树。它所做的只是下到最左边的树并返回它的评估。

4

0 回答 0