java - Tic-Tac-Toe 打印游戏树搜索中最佳移动的路径？

Question

我正在研究 Tic-Tac-Toe 游戏 (3x3) 的 alpha-beta 剪枝算法。目前，对于任何给定的 3x3 网格实例，我都能找出最好的情况:

public Best chooseAlphaBetaMove(int whosMov, int alpha, int beta) {

    Best reply = new Best();  
    Best myBest = new Best();

    if ((scoreGrid()==COMPUTER_WIN) || (scoreGrid()==OPPONENT_WIN) || 
                                       (scoreGrid()==GAME_DRAW)) {
        int score = scoreGrid();
        return new Best(score,-3,-3,count);
    }

    if (whosMov==COMPUTER_MOVE) {
        myBest.score = alpha;
    } else {
        myBest.score = beta;
    }

    for (int i=0; i<3; i++) {
    for (int j=0; j<3; j++) {
        if (layOut[i][j]==0) {
            moveGrid(whosMov,i,j);
            reply = chooseAlphaBetaMove(-whosMov,alpha,beta); 
            unmoveGrid(i,j);

            if ((whosMov==COMPUTER_MOVE)&&(reply.score>myBest.score)) {
                myBest.score = reply.score;
                alpha = reply.score;
                myBest.row = i;
                myBest.column = j;
            }

            if  ((whosMov==OPPONENT_MOVE)&&(reply.score<myBest.score)) {
                myBest.score = reply.score;
                beta = reply.score;
                myBest.row = i;
                myBest.column = j;
            }
            if (beta <= alpha) return myBest;
        }
    }
    }

        return myBest;
}

最佳结构是:

public class Best {

    public int score;
    public int row;
    public int column;
    public int count
}

给定初始网格和下一个移动的人，我可以知道下一个玩家的最佳得分和最佳位置。但是，我不知道如何打印这个最佳 Action 的整个路径。 (注意 - 我不需要整个搜索路径。我只想打印出从这个最佳移动开始直到叶子的单个搜索路径)。有什么想法吗？谢谢!

Answer 1

当您递归地沿着每条路径前进时，您需要跟踪它，可能通过将对列表/堆栈的引用传递到每个 chooseAlphaBetaMove 调用中。当您找到比当前最佳路径更好的路径时，您将复制当前路径，并将其存储为“迄今为止的最佳路径”。完成后，您可以打印出最佳路径。