0

我正在研究带有井字游戏（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
}

给定一个初始网格以及接下来谁将移动，我可以知道下一个玩家的最佳得分和最佳位置。但是，我不知道如何为这个最佳动作打印整个路径。（注意 - 我不想要整个搜索路径。我只想打印出从这个最佳移动到叶子的单个搜索路径）。有什么想法吗？谢谢！

4

3 回答 3

2

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

于 2012-10-13T19:57:39.827 回答
1

您需要一些方法来跟踪搜索中的最佳移动。我的建议是保留一个包含最佳移动列表的数据结构。AStack似乎是最适合这种情况的数据结构。在每次递归调用中，将第一个动作压入堆栈（因为这是迄今为止最好的动作）。当找到更好的移动时，弹出堆栈并推送新的。在您的 alpha-beta 修剪算法完成后，只需弹出堆栈并打印每个动作。这将给出“最佳”动作的顺序，直到游戏结束。

于 2012-10-13T19:57:13.813 回答
1

http://xkcd.com/832/是一种可视化 TTT 树的有效方法

于 2012-10-13T21:29:27.813 回答