Negamax算法-制作/撤销vs复制

Question

我对Negamax算法以及如何在实际案例中应用Negamax算法有点困惑。在网络上，我发现了以下C/C++代码(ref：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“实例都会发生变化，但似乎没有创建板的副本。

[1]，我是正确的，这个概念，还是我错过了什么？

现在，我也找到了一个Negamax实现(ref：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)调用返回一个副本(所以是董事会对象的一个新实例)。这就是为什么Negamax函数需要两个参数而不是一个参数。

[2]，我又说对了吗？

[3]如果[1]和[2]都是正确的，那么哪种方式通常更快？如果板表示非常简单(我假设一个Board类作为数组包装器)，我想最好是一个副本，但否则我会选择make/unmake。

提前感谢！

*编辑*

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

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

有不同的行为

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

密码？

由于我的董事会类存储了移动列表，我认为unmakeLastMove()和unmakeMove(m)一样有效。但这不是个好主意对吧？

Answer 1

这取决于游戏，你储存什么细节与板子，等等。

基本上，真正的答案是:实现两者并分析解决方案。

如果你有额外的信息附加到黑板上，如果你的得分不是微不足道的，而且你携带了一些预先计算好的值，如果移动有复杂的规则，并且你的撤销信息与董事会本身大致相同，等等，你可能会变得复杂。

在某些鼓励不可变数据共享的语言的情况下，克隆板也可能更简单，因为您没有复制所有的东西。然而，克隆并不能保存你的移动历史，所以如果你感兴趣的话，你必须把它放在一边。

这两种方式在不同的情况下都有不同的作用。只需想一想每一种实现方式意味着什么和/或比较这两种结果。