Negamax算法 - 製作/取消製作與複製

我對Negamax算法以及如何將其應用於實際情況有點困惑。在網上我發現了以下的C/C++代碼（編號：https://chessprogramming.wikispaces.com/Unmake+Move）Negamax算法 - 製作/取消製作與複製

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)被稱爲時間，但沒有副本董事會似乎被創建。

[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)調用返回副本（所以董事會對象的新實例）。這就是爲什麼Negamax函數需要2個參數而不是1個。

[2]我又對了嗎？

[3]如果[1]和[2]都是正確的，哪種方式通常更快？如果董事會的代表性很簡單（我想Board類作爲一個數組包裝）我想一個副本是首選，但否則我會去make/unmake。

在此先感謝！

*************** EDIT ***************

[4]在化妝/ unmake溶液

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

比

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

代碼不同的行爲？

由於我的板級存儲移動列表，我認爲unmakeLastMove()工作以及unmakeMove(m)。但這不是一個好想法，對吧？

來源

2015-05-23 c.bear

這取決於遊戲，細節你板收納什麼，等

基本上，真正的答案將是：同時實現和配置文件的解決方案。

如果你有一些額外的信息附加到董事會，如果你的評分不是微不足道的，並且你帶有一些預先計算的值，如果這些舉動有複雜的規則，並且你的撤銷信息在同一邊，那麼Make/Unmake可能會變得複雜作爲董事會本身等。

克隆董事會也可能更簡單，如果某種語言鼓勵不可變的數據共享，因爲您不復制所有內容。克隆不會保留你的移動歷史，所以如果你有興趣，你必須保持這一點。

兩種方式對不同情況的工作方式不同。試想一下每種方式的實現意味着什麼和/或比較兩種結果。

來源

2015-05-23 08:23:34 viraptor

Negamax算法 - 製作/取消製作與複製

回答

相關問題