蒙特卡洛-树搜索方法

棋类问题求解属于PSPACE-HARD，以围棋为例，解空间约有为$10^{250}$种可能。就算是超级计算机每秒万万亿次计算速度，即每秒能够穷举$10^{16}$种状态，对于这么大的解空间来说也只是杯水车薪。

所以如果有人说如果算力足够，这个问题暴力搜索也可以，那他显然对$10^{234}$倍的差距不了解。

正文

为了解决这么大的解空间搜索问题，一种随机性的策略被提出来了——Mento Carlo Tree Search。蒙特卡洛树搜索是将蒙特卡洛方法中的随机性引入到搜索树当中。有关文献也将这棵搜索树称为博弈树，因为对于棋类游戏，对弈方的目标是正好相反的。

所以，MCTS算法本质上树的搜索算法，输入是当前局面状态，输出是可能的最优解。

如果你意图使用暴力搜索的方法，只需遍历这棵搜索树，穷举所有可能，思路自然非常简答，但是解空间规模不允许你这样做。MCTS在搜索这棵树的时候引入了随机性。

回想我们下棋的方式，通常是脑海中出现几个可用的选点，对比这些选点的对于局势的影响，选择其中最有利的选点。

对于暴力搜索有两个难点：

1. 如何找到可用选点？

2. 如何确定这些选点的相对好坏？

先讨论第二个问题，对于人类来讲，确定选点的好坏往往需要递归的进行这样的思考，直到人类可以“显而易见”看出某个局面的好坏。然而对于机器来来说，这个显而易见就不是那么好定义，为了处理这个“显而易见”，MCTS的方式是对于当前选点，随机选取n个可能对局，以胜的概率来表示这个点的好坏。

对于第一个问题，如何找到可用选点呢，有经验的人类棋手凭借“棋感”直接找到直接能够找到几个看起来不错的点，机器却没有棋感，对于这点，机器通过随机生成多次对局，在每次对局中被访问到的次数比较多的节点，被认为是较优的选点。

MCTS实现

那么在实现MCTS过程中，如何对外暴露接口和构造搜索树呢？

我们以五子棋为例，探讨这一过程。

class MCTS():
    # ...
    def play(self, row:int, column:int, board_state:list):
        '''AI exposed interface'''
        board = Board(row, column)
        board.set_state(board_state)

        for n in range(self.playout_num):
            board_copy = copy.deepcopy(board)
            self._playout(board_copy)
        move = max(self.root.children.items(), key=lambda a: a[1].visited_num)[0]

        x, y = board.interger_to_coordinate(move)
        return x, y

MCTS对外暴露的接口是拿到一个局面状态之后，返回推荐选点。

在这一步中，MCTS通过模拟一定次数的对局，以当前节点为根节点构造搜索树，然后查找搜索树中访问次数最多的二代子节点即可。

在每次对局当中，我们需要进行节点选择和评估，节点选择也是构造整个搜索树的过程，每次对局如果没有结束，就会以某一形式扩展当前节点。

在这个naive的实现当中，我们是直接扩展所有没有被棋子占据的节点。

class MCTS():
    # ...
    def _playout(self, board: Board):
        node = self.root
        while(True):
            if node.is_leaf():
                break
            action, node = self._select_best(node)
            board.move(action)

        action_probs, _ = self._policy(board)
        end, winner = board.who_win()
        if not end:
            self._expand(node, action_probs)
        leaf_value = self._evaluate_rollout(board)
        self._update_recursive(node, -leaf_value)

当扩展完当前节点之后，如果该到该节点游戏没有结束，为了避免无穷尽地递归搜索，需要评判该节点局面好坏，这部分通过在该节点内随机选点下棋实现。

class MCTS():
    # ...
    def _evaluate_rollout(self, board, limit=100):
        '''return -1 or 0 or 1'''
        player = board.get_cur_player()
        for i in range(limit):
            end, winner = board.who_win()
            if end:
                break
            action_probs = self._rollout_policy(board)
            max_action = max(action_probs, key=itemgetter(1))[0]
            board.move(max_action)
        else:
            print("tuoshi")
        return winner   

如此我们实现了基本MCTS的功能，即给定局面，返回推荐值。

总结一下，在这个过程中，关键是构造搜索树，通过模拟在当前状态之后的多次对局实现。在模拟的过程当中，一边添加叶节点，一边通过随机对局更改叶节点和祖先节点的评估值，每个叶节点对应一个棋盘状态。当多次对局完成之后，选择搜索树中二代节点评价最高的节点。