Крестики-нолики Монте-Карло - Бедный агент

Question

Я пытаюсь реализовать поиск по дереву Монте-Карло, чтобы играть в крестики-нолики в Python. Моя текущая реализация выглядит следующим образом:

У меня есть класс Board, который обрабатывает изменения в крестики-нолики. Состояние платы представлено массивом 2x3x3, где каждая из матриц 2 3x3 является двоичными матрицами, индивидуально представляющими наличие X и присутствие O.

class Board:
  '''
  class handling state of the board
  '''

  def __init__(self):
    self.state = np.zeros([2,3,3])
    self.player = 0 # current player's turn

  def copy(self):
    '''
    make copy of the board
    '''
    copy = Board()
    copy.player = self.player
    copy.state = np.copy(self.state)
    return copy

  def move(self, move):
    '''
    take move of form [x,y] and play
    the move for the current player
    '''
    if np.any(self.state[:,move[0],move[1]]): return
    self.state[self.player][move[0],move[1]] = 1
    self.player ^= 1

  def get_moves(self):
    '''
    return remaining possible board moves
    (ie where there are no O's or X's)
    '''
    return np.argwhere(self.state[0]+self.state[1]==0).tolist()

  def result(self):
    '''
    check rows, columns, and diagonals
    for sequence of 3 X's or 3 O's
    '''
    board = self.state[self.player^1]
    col_sum = np.any(np.sum(board,axis=0)==3)
    row_sum = np.any(np.sum(board,axis=1)==3)
    d1_sum  = np.any(np.trace(board)==3)
    d2_sum  = np.any(np.trace(np.flip(board,1))==3)
    return col_sum or row_sum or d1_sum or d2_sum

Затем у меня есть класс Node, который обрабатывает свойства узлов при построении дерева поиска:

class Node:
  '''
  maintains state of nodes in
  the monte carlo search tree
  '''
  def __init__(self, parent=None, action=None, board=None):
    self.parent = parent
    self.board = board
    self.children = []
    self.wins = 0
    self.visits = 0
    self.untried_actions = board.get_moves()
    self.action = action

  def select(self):
    '''
    select child of node with 
    highest UCB1 value
    '''
    s = sorted(self.children, key=lambda c:c.wins/c.visits+0.2*sqrt(2*log(self.visits)/c.visits))
    return s[-1]

  def expand(self, action, board):
    '''
    expand parent node (self) by adding child
    node with given action and state
    '''
    child = Node(parent=self, action=action, board=board)
    self.untried_actions.remove(action)
    self.children.append(child)
    return child

  def update(self, result):
    self.visits += 1
    self.wins += result

Наконец, у меня есть функция UCT, которая объединяет все. Эта функция берет объект Board и строит дерево поиска Монте-Карло, чтобы определить следующий наилучший возможный ход из данного состояния доски:

def UCT(rootstate, maxiters):

  root = Node(board=rootstate)

  for i in range(maxiters):
    node = root
    board = rootstate.copy()

    # selection - select best child if parent fully expanded and not terminal
    while node.untried_actions == [] and node.children != []:
      node = node.select()
      board.move(node.action)

    # expansion - expand parent to a random untried action
    if node.untried_actions != []:
      a = random.choice(node.untried_actions)
      board.move(a)
      node = node.expand(a, board.copy())

    # simulation - rollout to terminal state from current 
    # state using random actions
    while board.get_moves() != [] and not board.result():
      board.move(random.choice(board.get_moves()))

    # backpropagation - propagate result of rollout game up the tree
    # reverse the result if player at the node lost the rollout game
    while node != None:
      result = board.result()
      if result:
        if node.board.player==board.player:
          result = 1
        else: result = -1
      else: result = 0
      node.update(result)
      node = node.parent

  s = sorted(root.children, key=lambda c:c.wins/c.visits)
  return s[-1].action

Я искал этот код в течение нескольких часов и просто не могу найти ошибку в моей реализации. Я протестировал множество состояний форума и сравнил двух агентов друг с другом, но функция возвращает плохие действия даже для самых простых состояний форума. Что мне не хватает и / или что не так с моей реализацией?

edit: вот пример того, как могут быть реализованы два агента для игры:

b = Board() # instantiate board
# while there are moves left to play and neither player has won
while b.get_moves() != [] and not b.result():
    a = UCT(b,1000)  # get next best move
    b.move(a)        # make move
    print(b.state)   # show state

Answer 1

Проблема заключается в следующем:

• Ваш get_moves() Функция не проверяет, закончилась ли игра. Он может генерировать непустой список ходов для государств, в которых кто-то уже выиграл.
• При создании нового NodeВы также не проверяете, закончилось ли состояние игры, поэтому непустой список untried_actions создано.
• На этапах выбора и расширения алгоритма вы также не проверяете терминальные игровые состояния. Как только фаза расширения попадает на узел, который содержит игровое состояние, в котором кто-то уже выиграл, он с радостью применит дополнительное действие и снова создаст новый узел для дерева, который также будут успешно проходить на последующих фазах выбора.
• Для этих узлов, где игра продолжается после того, как кто-то уже выиграл, result() может вернуть неверного победителя. Он просто проверяет, выиграл ли последний игрок ход, что является правильным, если вы прекращаете играть, как только кто-то выигрывает, но может быть неверным, если вы продолжаете играть после того, как кто-то уже выиграл. Таким образом, вы распространяете все виды неверных результатов через дерево.

Самый простой способ исправить это будет изменить get_moves() такой, что он возвращает пустой список, когда игра уже закончена. Тогда эти узлы всегда будут выходить из строя if node.untried_actions != [] check, что означает, что фаза расширения полностью пропускается, и вы сразу переходите к фазе Play-out, где происходит надлежащая проверка состояний игры терминала. Это можно сделать следующим образом:

def get_moves(self):
    """
    return remaining possible board moves
    (ie where there are no O's or X's)
    """
    if self.result():
        return []

    return np.argwhere(self.state[0] + self.state[1] == 0).tolist()