并行蒙卡树搜索，性能无损，线性加速，勇闯「消消乐」1000关！

正文

请到「今天看啥」查看全文

然而，蒙特卡洛搜索树本身是一个串行的算法（每一步迭代需要所有当前已知信息），这导致对其并行将带来不可避免的性能损失。因此，如何最小化并行带来的性能损失就显得十分重要。

如上图(a)所示，MCTS在不断地重复选择（selection）、扩展（expansion）、仿真（simulation）、反向传播（backpropagation）的过程。其中“选择”步骤通过搜索树选择一个节点（对应环境中的一个状态state），“扩展”为搜索树增加一个节点，“仿真”通过环境模型对此节点的回报进行估计，“反向传播”更新得到的回报估计值。

具体而言，在“选择”步骤中，我们通过下式不断选择最优孩子节点：

其中 V_s 是节点 s 的回报平均估值，N_s 是节点 s 的访问次数，C(s) 是 s 的所有孩子节点的集合。

并行 MCTS 的难点可以通过上图中 (b)-(c) 展示。因为有多个 worker 在同时执行上述选择->扩展->仿真->反向传播过程，某一个 worker 在进行「选择」的时候，其他 worker 未结束的仿真结果是无法获取的，这导致大量 worker 只能看到过时且类似的信息，严重影响了搜索树选择节点的好坏，破坏了串行状态下的探索-利用平衡（exploration-exploitation balance）。

为解决这一问题，我们提出了 WU-UCT 算法（Watch the Unobserved in UCT）。这个算法借用了异步并行算法的思想 [2]。 WU-UCT 算法的核心在于维护一个额外的统计量用于记录每个节点上有多少个正在对其进行仿真的 worker，并用其对选择算法进行调整：

其中 O_s 是如上所述节点 s 的未返回访问次数统计（unobserved samples）。

此外，根据上面的核心想法，为最大化算法的效率，我们设计了一个并行 MCTS 系统 (a)。我们使用了主-从工作模式的系统。由主进程维护一个完整的搜索树，并进行选择（selection）和反向传播（backpropagation）操作。同时，主进程负责将扩展（expansion）和仿真（simulation）的任务分配给对应的子进程，由子进程完成后将结果返还主进程。这样做的好处在于很好地保证了统计信息对于每次选择都是完整的，同时避免了进程间共享内存和访问冲突等问题。

请到「今天看啥」查看全文