algorithm - Negamax 算法 - 制作/取消制作与复制

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” 实例都会发生变化，但似乎没有创建板的副本。

[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) 调用返回一个 copy(因此是 board 对象的一个​​新实例)。这就是 Negamax 函数需要 2 个参数而不是一个参数的原因。

[2] 我又对了吗？

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

提前致谢!

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

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

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

与

有不同的行为

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

代码？

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

Answer 1

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

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

Make/Unmake 可能会变得复杂，如果你有一些额外的信息附加到棋盘上，如果你的得分不是微不足道的并且你有一些预先计算的值，如果移动有复杂的规则并且你的撤消信息与董事会本身等。

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

这两种方式在不同情况下的工作方式不同。只需考虑每种方式意味着什么实现和/或比较两个结果。