蒙特卡罗树搜索井字棋--弱智能体

Question

我正在尝试在Python中实现Monte Carlo树搜索来玩井字游戏。 我当前的实现如下：

我有一个Board类来处理对井字游戏板的修改。 板的状态由2x3x3 numpy数组表示，其中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

我已经花了几个小时查找这段代码，但仍然无法找到我实现中的错误。我已经测试了很多棋盘状态，并让两个代理相互对抗，但即使是最简单的棋盘状态，该函数也会返回糟糕的行动。我错过了什么，或者我的实现有什么问题？

编辑：以下是两个代理如何实现游戏的示例：

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

- sam

---

请添加所有相关的代码，以便我们可以自己运行。如果UCT是入口点，那么应该给它什么参数？ - Alex Hall

@AlexHall 我已经添加了一个简单的实现，使用空棋盘开始对决代理。 - sam

好的，我不知道这个算法，也不想去解决这个问题，但是对于其他尝试的人，这里是完整的代码，可以让你快速开始：https://pastebin.com/RB9K7cDD 我还添加了一个方法来漂亮地显示棋盘。 - Alex Hall

Answer 1

问题似乎是这样的：

• 您的get_moves()函数没有检查游戏是否已经结束。它可以为某个人已经获胜的状态生成非空的动作列表。
• 在创建新的Node时，您也不检查游戏状态是否已经结束，因此会创建一个非空的untried_actions列表。
• 在算法的Selection和Expansion阶段中，您也没有检查终止游戏状态。一旦Expansion阶段碰到包含某个人已经赢得比赛的游戏状态的节点，它就会愉快地应用额外的操作，并再次为树创建一个新的节点，随后的Selection阶段也会愉快地进行。
• 对于这些在某个人已经赢得比赛后仍然继续玩的节点，result()可能会返回错误的赢家。它只是检查最近下棋的玩家是否获胜，如果您停止玩游戏，则是正确的，但如果您在某个人已经赢了之后继续玩，则可能是不正确的。因此，您将所有类型的不正确结果传播到整个树中。

修复此问题的最简单方法是修改get_moves()，使其在游戏已经结束时返回空列表。然后，这些节点将始终未通过if node.untried_actions != []检查，这意味着扩展阶段将完全跳过，然后您直接进入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()

- Dennis Soemers

---

谢谢！那正是问题所在。发布后不久，我注意到由于我实现result()函数的方式，某些终端状态正在被忽略。我只需添加一个测试来检查状态是否为终端状态，然后再执行扩展步骤，这似乎解决了问题。感谢您详细的回复，祝好！ - sam