Альфа-бета обрезка в питоне

Question

Я пытаюсь внедрить компьютерный плеер в игру типа Connect Four. Обрезка альфа-бета казалась лучшим способом для достижения этой цели, но я не могу понять, что я делаю неправильно.

Ниже приведен код, который я придумал. Начинается с начального корневого состояния. Для каждого возможного, допустимого перемещения (и если отсечение не происходит) алгоритм: делает глубокую копию состояния, обновляет состояние (увеличивает глубину, переключает повороты, добавляет кусок, устанавливает эвристическое значение) и добавляет это новое состояние в корневой список наследников.

Если новое состояние не является листом (т.е. на максимальной глубине), оно рекурсивно продолжается. Если это лист, алгоритм проверяет значение корня и соответствующее локальное значение альфа / бета и обновляется соответствующим образом. После проверки всех возможных допустимых параметров алгоритм возвращает соответствующее локальное значение альфа / бета.

По крайней мере, это то, что я хотел. Каждый прогон возвращает значение 0. В соответствии с запросом здесь приведен код инициализации:

class GameState:

   def __init__(self, parentState = None):

      # copy constructor
      if not(parentState == None):

         self.matrix = copy.deepcopy(parentState.matrix)
         self.successor = copy.deepcopy(parentState.successor)
         self.depth = parentState.depth
         self.turn = parentState.turn
         self.alpha = parentState.alpha
         self.beta = parentState.beta
         self.connects = copy.deepcopy(parentState.connects)
         self.value = parentState.value
         self.algo_value = parentState.value
         self.solution = parentState.solution

      # new instance 
      else:

         # empty board
         self.matrix = [[0 for y in xrange(6)] for x in xrange(7)]

         ## USED WHEN GROWING TREE
         self.successor = [] # empty list
         self.depth = 0 # start at root
         self.turn = 1 # game starts on user's turn

         ## USED WHEN SEARCHING FOR SOLUTION
         self.alpha = float("-inf")
         self.beta = float("+inf")

         self.connects = [0, 0, 0] # connects in state
         self.algo_value = float("-inf")
         self.value = 0 # alpha-beta value of connects
         self.solution = False # connect four

    def alphabeta(root):

       if root.depth < MAX_EXPANSION_DEPTH:

          # pass down alpha/beta
          alpha = root.alpha
          beta = root.beta

          # for each possible move
          for x in range(7):

             # ALPHA-BETA PRUNING

             # if root is MAXIMIZER
             if (root.turn == 2) and (root.algo_value > beta): print "beta prune"

             # if root is MINIMIZER
             elif (root.turn == 1) and (root.algo_value < alpha): print "alpha prune"

             # CANNOT prune
             else:

                # if move legal
                if (checkMove(root, x)):

                   # CREATE NEW STATE
                   root.successor.append(GameState(root))
                   working_state = root.successor[-1]

                   # update state
                   working_state.successor = []
                   working_state.depth += 1
                   working_state.turn = (working_state.turn % 2) + 1
                   cons = dropPiece(working_state, x, working_state.turn)

                   # update state values
                   # MAXIMIZER
                   if working_state.turn == 2:
                      working_state.value = ((cons[0]*TWO_VAL)+(cons[1]*THREE_VAL)+(cons[2]*FOUR_VAL)) + root.value
                      working_state.algo_value = float("-inf")
                   # MINIMIZER
                   else:
                      working_state.value = ((-1)*((cons[0]*TWO_VAL)+(cons[1]*THREE_VAL)+(cons[2]*FOUR_VAL))) + root.value
                      working_state.algo_value = float("inf")

                   # if NOT a leaf node
                   if (working_state.depth < MAX_EXPANSION_DEPTH):

                      # update alpha/beta values
                      working_state.alpha = alpha
                      working_state.beta = beta

                      ret = alphabeta(working_state)

                      # if MAXIMIZER
                      if (root.turn == 2):
                         if (ret > root.algo_value): root.algo_value = ret
                         if (ret > alpha): alpha = ret
                      # if MINIMIZER
                      else:
                         if (ret < root.algo_value): root.algo_value = ret
                         if (ret < beta): beta = ret

                   # if leaf, return value
                   else:
                      if root.turn == 2:
                         if (working_state.value > root.algo_value): root.algo_value = working_state.value
                         if working_state.value > alpha: alpha = working_state.value
                      else:
                         if (working_state.value < root.algo_value): root.algo_value = working_state.value
                         if working_state.value < beta: beta = working_state.value

          if root.turn == 2: return alpha
          else: return beta

Answer 1

Решил вопрос. В приведенном выше алгоритме я проверяю сокращение после того, как цикл перешел к следующему преемнику (значения по умолчанию algo_values ​​- это соответствующие значения max и min).

Вместо этого алгоритм должен проверять первый узел в каждом списке преемников, обновлять его algo_value и затем проверять на сокращение остальных узлов в списке преемников.