分治的蒙特卡洛树搜索解决目标导向的强化学习问题.

本文要解决的任务是目标导向（Goal-Directed）的强化学习问题。如上图所示，绿色像素是起始位置，希望能够在迷宫中走到蓝色像素的终止位置。

蒙特卡洛树搜索（Monte Carlo Tree Search，MCTS）是指在当前的每个状态搜索下一步可能的状态（上下左右），一次搜索构造一棵树。这样每个状态的下一步都有$4$种可能的状态，若从起始位置到终止位置距离为$k$，则构造的树深度为$k$，且最后一层有$4^k$个节点，这是一个很深的树：

本文提出分治的蒙特卡洛树搜索（Divide-and-Conquer Monte Carlo Tree Search，DCMCTS），在每次搜索中选择一个中间位置，分别构造起始位置到中间位置、中间位置到终止位置的两棵子树。而这个搜索本身也是一种树结构，可以选择任何一个中间像素作为中间位置，每一次选择产生了一个树节点。这样构造的树每一层的节点树都和问题中的可选像素数呈正比，这是一个很宽的树：

按照这种方法，每次选择一个中间像素，把一个问题分解成两个子问题；采用分治法不断分解，并在各自的搜索空间中搜索合适的路径，直至实现目标：

算法流程如下：

为了降低运算量，减小搜索空间，每次选择中间像素时不是考虑所有可能的像素，而是采用深度学习的方法确定出可能性较高的中间像素：

这一步模型在训练时，每次取出一个学习过程，将其当前位置作为终止位置，所经过的位置作为所有可能的中间位置，其余像素标签置0，进行监督学习。