Negamax 算法 - Make/Unmake vs 复制

Question

我对 Negamax 算法以及如何在实际案例中应用它有点困惑。在网上我找到了以下 C/C++ 代码（参考：https://chessprogramming.wikispaces.com/Unmake+Move）

int negaMax( int depth ) {
    if ( depth == 0 ) return evaluate();
    int max = -oo;
    generateMoves(...);
    while ( m = getNextMove(...) )  {
        makeMove(m); 
        score = -negaMax( depth - 1 );
        unmakeMove(m); 
        if( score > max )
            max = score;
    }
    return max;
}

据我所知，每次调用 makeMove(m) 和 unmakeMove(m) 时，"board" 实例都会发生变化，但没有 board 的副本似乎是被创造出来的。

[1] 我对这个概念是否正确，或者我错过了什么？

现在，我也找到了 Negamax python 实现（参考：http://blogs.skicelab.com/maurizio/connect-four.html）

def negamax(board, depth):
    if check_end(board) is not None:
        return endscore(board)

    if depth <= 0:
        return [], evaluate(board)

    bestmove = []
    bestscore = -INF
    for m in board.moves():
        nextmoves, score = negamax(board.move(m), depth-1)
        score = -score
        if not bestmove or score >= bestscore:
            bestscore = score
            bestmove = [m] + nextmoves

    return bestmove, bestscore

在第二种情况下，我假设 board.move(m) 调用 returns a copy（因此是 board 对象的新实例）。这就是 Negamax 函数需要 2 个参数而不是一个参数的原因。

[2]我又说对了吗？

[3] 如果[1] 和[2] 都正确，一般来说哪种方式更快？如果董事会表示非常简单（我假设 Board class 作为数组包装器）我想最好是复制一份，否则我会选择 make/unmake.

提前致谢！

*************** 编辑 ***************

[4] 在 make/unmake 解决方案中

makeMove(m); 
score = -negaMax( depth - 1 );
unmakeLastMove();

与

的行为不同

makeMove(m); 
score = -negaMax( depth - 1 );
unmakeMove(m);

代码？

因为我的棋盘 class 存储了移动列表，所以我认为 unmakeLastMove() 和 unmakeMove(m) 一样有效。但这不是一个好主意，对吧？

Answer 1

这取决于游戏，您在棋盘上存储了哪些详细信息等。

基本上，真正的答案是：同时实施并分析解决方案。

Make/Unmake 可能会变得复杂，如果你有一些额外的信息附在棋盘上，如果你的得分不是微不足道的并且你有一些预先计算的值，如果移动有复杂的规则并且你的撤消信息是周围的与电路板本身相同的一面等

在某些鼓励不可变数据共享的语言的情况下，克隆板也可能更简单，因为您不会复制所有内容。但是，克隆不会保留您的移动历史记录，因此如果您有兴趣，则必须将其保留在一边。

这两种方式在不同情况下的工作方式不同。想想每种方式意味着什么实现 and/or 比较两个结果。

Negamax 算法 - Make/Unmake vs 复制

Negamax Algorithm - Make/Unmake vs Copy

algorithm

minimax