Minimax递归树

Question

当我递归备份时，我的板子变得一团糟。

如何在不总是复制的情况下return到上一个板（我的 minimax 需要快速的性能）

我的代码：

 for all possible moves:
            board.apply(move);
            int currentScore = minimax(board, depth - 1, false); // recursive call
            int newScore = Math.max(value, currentScore);
            // Undo move on the board or create a temp board for recursive calls, as the recursive calls will mess up the current board
            board.undo(move);

我想到了棋盘 class 中的撤消方法，它采取了一步并撤消它，但这会让我回到我当前的棋盘吗？

Answer 1

是的，只要您撤消以相反顺序应用的所有移动，您就会找回原来的棋盘。但是，move 本身对象通常不会携带足够的信息来撤消自身，因此实现看起来更像：

for all possible moves:
    // apply the move and remember how to undo it
    undomove = board.apply(move);

    // minimax function promises to return the board unmodified
    int currentScore = minimax(board, depth - 1, false); // recursive call
    int newScore = Math.max(value, currentScore);

    // Undo move to recover the original board
    board.apply(undomove);

Minimax递归树

Minimax recurse back up the tree

algorithm

minimax