java - 如何根据 MiniMax Alpha-Beta 的返回值在游戏板上移动？

Question

我所说的游戏类似于五子棋或井字游戏的“大型”简化版。基本上，您有一 block 8x8 的棋盘，获胜者是在一行或一列(无对角线)中连接 4 个棋盘的棋盘。

我已经设置了带有 alpha-beta 修剪的极小极大，我遇到的问题是我不确定返回值如何让您知道要采取哪一步。或者喜欢如何将值与 Action 联系起来。

目前，我考虑返回一个 GameStateNode。 GameStateNode 具有以下字段:char[][](棋盘的当前状态)、evaluationVal(非终端节点时的当前状态值)。

但是我仍然想不出一种方法来使用返回的节点来决定最佳的移动。

    // Alpha-Beta Pruning Search
    private static Node alphaBeta(Node initial, int depth) {
        Node bestMove = max(initial, depth, NEGATIVE_INFINITY, POSITIVE_INFINITY);
        return bestMove;
    }

    private static Node max(Node n, int depth, int alpha, int beta) {
        int value = NEGATIVE_INFINITY;
        Node currentBestMove = null;
        Node temp = null;

        // Terminal state
        if(n.fourInALine() != 0) {
            return n;
        }
        // Depth limit reached
        if(depth == 0) {
            return n;
        }

        ArrayList<Node> successors = n.generateSuccessors('X');
        // Iterate through all the successors, starting with best evaluationValues
        for(Node s : successors) {
            temp = min(s, depth - 1, alpha, beta);
            if(temp.evaluationVal > value) {
                value = temp.evaluationVal;
                currentBestMove = temp;
            }
            alpha = Math.max(alpha, value);
            if(alpha >= beta) {
                break;
            }
        }
        return currentBestMove;
    }

    // I have similar min method just with the correct comparison

Answer 1

您无法从返回的 bestMove 中获取移动信息，因为该节点代表 深度 移动后棋盘的位置。如果您比较 bestMove 的位置和 initial 的位置，您会发现多个差异，并且您将无法判断移动的执行顺序。

要通过搜索代码发挥作用:

1. 向 max() 添加一个 boolean isRoot 参数，以告知该方法是否直接从 alphaBeta() 调用，并且 n 是搜索树的根节点。
2. 在 max() 中，如果 isRoot 为 true，则不会跟踪 currentBestMove 的最佳 temp(从 min() 返回的节点)，而是跟踪最佳 s(来自 n.generateSuccessors() 的节点)。
3. 在 alphaBeta() 中，采用 bestMove(从 max() 返回的 Node)并将其状态数组与 initial 进行比较。查找 bestMove 有 'X' 而 initial 没有的位置的坐标。
4. 这就是下棋的步骤。

代码:

private static int[] alphaBeta(Node initial, int depth) {
    Node bestMove = max(initial, depth, NEGATIVE_INFINITY, POSITIVE_INFINITY, true);
    for(int i = 0; i < bestMove.state.length; i++) {
        for(int j = 0; j < bestMove.state[i].length; j++) {
            if(bestMove.state[i][j] != initial.state[i][j]) {
                return new int[] { i, j };
            }
        }
     }
}

private static Node max(Node n, int depth, int alpha, int beta, boolean isRoot) {
    int value = NEGATIVE_INFINITY;
    Node currentBestMove = null;
    Node temp = null;

    // Terminal state
    if(n.fourInALine() != 0) {
        return n;
    }

    // Depth limit reached
    if(depth == 0) {
        return n;
    }

    ArrayList<Node> successors = n.generateSuccessors('X');
    // Iterate through all the successors, starting with best evaluationValues
    for(Node s : successors) {
        temp = min(s, depth - 1, alpha, beta);
        if(temp.evaluationVal > value) {
            value = temp.evaluationVal;
            currentBestMove = isRoot ? s : temp;
        }
        alpha = Math.max(alpha, value);
        if(alpha >= beta) {
            break;
        }
    }
    return currentBestMove;
}

// I have a similar min() method with the opposite comparison,
// and without an isRoot argument.

请注意，这些都没有经过测试。