체스 네가 맥스 기능

Question

안녕하세요!

체스 엔진에 대해 네가 막스 검색 알고리즘을 쓰려고하는데, 제대로 작동하지 않는 것 같습니다. 예를 들어 wikipedias pseudocode를 사용하고 있지만 어떻게 든 예상 결과가 나오지 않습니다. 내가 2의 플라이와 함께 그것을 실행하면, 그것은하지 않아야하지만, 내 보드 데이터 구조를 변경합니다. 플라이 2로 실행이 끝난 후, 모든 흰색 (또는 검은 색은 플레이어가 어떤 기능을 호출하는지에 달려 있습니다.) 폰은 시작 위치에서 2 칸 앞으로 이동합니다.

내 make와 unmake 이동 함수는 최대 5-ply까지 검색하는 비 재귀 함수를 사용하여 완벽하게 작동합니다. 그런 다음 완벽하게 작동했습니다. 내 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 % 확신 해요 코드에서 모든 것을 해결할 특정 객체 변수를 사용하지 않으면 코드를 훨씬 쉽게 이해하고 디버그 할 수 있습니다.