國際象棋negamax功能

Question

嗨！

我想爲我的國際象棋引擎寫一個negamax搜索算法，但我似乎無法得到它的工作。我使用wikipedias僞代碼作爲示例，但不知何故，它不會產生預期的結果。當我用2層運行它時，它會改變我的板數據結構，但它不應該。功能完成後，使用層2運行，所有的白色（或黑色）取決於玩家所稱的功能。小兵從起始位置向前移動2個空格。

我的make和unmake move函數工作得很完美，因爲我用一個非遞歸函數測試它們，最多搜索5層。然後，它完美地工作。我的negamax實現一定有什麼問題。

非常感謝您的幫助！

def negaMax(self, board, rules, ply, player): 
     """ Implements a minimax algorithm. """ 
     if ply == 0: 
      return self.positionEvaluation() 

     self.max_eval = float('-infinity') 

     self.move_list = board.generateMoves(rules, player) 
     for self.move in self.move_list: 
      board.makeMove(self.move, player) 
      self.eval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player)) 
      board.unmakeMove(self.move, player) 

      if self.eval > self.max_eval: 
       self.max_eval = self.eval 

     return self.max_eval 

Answer 1

這裏的主要問題是我相信使用對象變量而不是局部變量。

self.move是對象變量，每次你改變它的時間 - 遞歸的每級「看到」的轉變，這通常是遞歸算法是一件壞事。

遞歸算法應該是自包含的，並且在調用環境發生任何變化時做的工作量最小 - 這使得遍歷算法流程變得更容易。

我在代碼中看到的兩個主要問題是：

1. self.move應該是本地變量（聲明爲move）。當你以後做：board.unmakeMove(self.move, player) - 我懷疑董事會正在撤銷一個不同的舉動，它在遞歸樹中設置得更深，而不是你想要的那個。使用局部變量將消除這種不希望的行爲。
2. 遞歸調用的每個級別都設置爲self.max_eval = float('-infinity')--所以你不斷地改變它，儘管它可能不是你想要做的。

的解決方案應該是類似的東西：

def negaMax(self, board, rules, ply, player): 
     """ Implements a minimax algorithm. """ 
     if ply == 0: 
      return self.positionEvaluation() 

     max_eval = float('-infinity') 

     move_list = board.generateMoves(rules, player) 
     for move in move_list: 
      board.makeMove(move, player) 
      currentEval = -self.negaMax(board, rules, ply - 1, board.getOtherPlayer(player)) 
      board.unmakeMove(move, player) 

      if currentEval > max_eval: 
       max_eval = currentEval 
     return max_eval 

我不是100％肯定它確實會在代碼解決一切（但它會解決它的一些），但我100％肯定避免使用對象變量會使您的代碼更易於理解和調試。