收集和檢索從alphabeta框架的主要變化

Question

我想在python中寫一個國際象棋引擎，我可以找到給定位置的最佳舉動，但我努力從該位置收集主要變化，以下是我所到目前爲止已經試過：

def alphabeta(board, alpha, beta, depth, pvtable): 

    if depth == 0: 
     return evaluate.eval(board) 

    for move in board.legal_moves: 
     board.push(move) 
     score = -alphabeta(board, -beta, -alpha, depth - 1, pvtable) 
     board.pop() 
     if score >= beta: 
      return beta 
     if score > alpha: 
      alpha = score 
      pvtable[depth-1] = str(move) 
    return alpha 

我使用pvtable[depth - 1] = str(move)追加移動，但最後我發現，pvtable包含隨機非連貫的動作，像['g1h3', 'g8h6', 'h3g5', 'd8g5']的起始位置的事情。

我知道類似的問題已經被問到，但我仍然沒有弄清楚我能如何解決這個問題。

Answer 1

我認爲當搜索再次達到相同的深度時（在遊戲樹的不同分支中），您的動作將被覆蓋。

這個網站解釋相當不錯如何檢索的主要變化：https://web.archive.org/web/20071031100114/http://www.brucemo.com:80/compchess/programming/pv.htm

應用到你的代碼示例，它應該是這樣的（我沒有測試）：

def alphabeta(board, alpha, beta, depth, pline): 

    line = [] 
    if depth == 0: 
     return evaluate.eval(board) 

    for move in board.legal_moves: 
     board.push(move) 
     score = -alphabeta(board, -beta, -alpha, depth - 1, line) 
     board.pop() 
     if score >= beta: 
      return beta 
     if score > alpha: 
      alpha = score 
     pline[:] = [str(move)] + line 

    return alpha