本文是根据AlphaGo论文:
D. Silver, A. Huang, C. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, D. Hassabis. Mastering the Game of Go with Deep Neural Networks and Tree Search. Nature 2016.
制作的一次AlphaGo算法培训的第二部分, 关于AlphaGo如果使用policy network和value network进行异步MCTS搜索, 对应的论文中的4. Searching with Policy and Value Networks.
欢迎提出宝贵意见.


AlphaGo Overview

  1. Supervised Learning of Policy Networks
  2. Reinforcement Learning of Policy Networks
  3. Reinforcement Learning of Value Networks
  4. Searching with Policy and Value Networks

Contents

  • 什么是 MCTS
  • AlphaGo 中使用的 MCTS
  • APV-MCTS 实现细节

  • MCTS (Monte-Carlo Tree Search) 是一种用于某些决策过程的启发式搜索算法。
  • Rémi Coulom (Crazy Stone作者) 首先描述了蒙特卡洛方法在游戏树搜索的应用并命名为蒙特卡洛树搜索。
  • AlphaGo出现前所有的顶尖围棋AI均采用 MCTS 方法。

一般的树搜索

logo center 60%

  • 需要搜索的状态多,耗费计算量大

MCTS

logo center 60%

  • MCTS通过大量的随机模拟未来可能的棋局,不断逼近真实结果

MCTS的四个步骤:

logo center 100%


AlphaGo中的MCTS

AlphaGo 采用了 APV-MCTS (Asynchronous Policy and Value MCTS) 的方法:

  • Asynchronous 异步搜索: CPU进行搜索和 $p\pi$ 计算,GPU进行 $p\sigma$ 和 $p_\theta$ 计算
  • Policy network: 给出下一步棋的可能的概率分布,减少搜索宽度
  • Value network: 给出某个搜索局面的评分,减少搜索深度

使用Policy network减小搜索宽度

logo center 65%

  • 更加有效的扩展树的分支,减少树的宽度

使用Value network减小搜索深度

logo center 62%

  • 给出某个搜索局面的评分,在较少搜索树深度时得到更准确的局面评估

APV-MCTS 的具体实现

      选择       扩展         评估            回溯
logo center


Step 1. Selection 选择

从根节点开始,根据$at=\arg\max\limits{a}(Q(s_t,a)+u(s_t,a))$选择下一步走法,直到到达叶节点

  • $Q(s,a)=(1-\lambda)\frac{W_v(s,a)}{N_v(s,a)}+\lambda\frac{W_r(s,a)}{N_r(s,a)}$    $(\lambda=0.5)$
             value评分 rollout评分

  • $u(s,a)=c_{puct}P(s,a)\frac{\sqrt{\sum_bN_r(s,b)}}{1+Nr(s,b)}$    $(c{puct}=5)$
             policy  UCT


Step 2. Expansion 扩展

当一个叶节点的访问次数使用$Nr(s,a)\gt n{thr}$时,扩展该叶节点。$(n_{thr}=40)$

  • 首先在CPU上用tree policy $p_\tau(a|s’)$临时扩展下一步走法的概率分布
  • 同时在GPU上计算SL policy $p\sigma(a|s’)$,计算完成时替换$p\tau$的结果

  • $P(s’,a)\leftarrow p_\sigma^\beta(a|s’)$
    $(\beta$为softmax temperature, 使概率分布更加光滑, $\beta=0.67)$


Step 3. Evaluation 评估

当选择到一个叶节点时,对当前的局面进行评估

  • Value network 打分得到$v_\theta\in(-1,1)$ (on GPU)
  • Rollout policy 模拟走子$at\sim p\pi$到局终,结果$z_t\in{-1,0,1}$ (on CPU)

Step 4. Backup 回溯

从该叶节点开始,向根节点回溯,迭代更新父节点评分值:

  • $N_v(s,a)\leftarrow N_v(s,a)+1$, $W_v(s,a)\leftarrow Wv(s,a)+v\theta$
  • $N_r(s,a)\leftarrow N_r(s,a)+1$, $W_r(s,a)\leftarrow W_r(s,a)+z_t$
  • $Q(s,a)=(1-\lambda)\frac{W_v(s,a)}{N_v(s,a)}+\lambda\frac{W_r(s,a)}{N_r(s,a)}$    $(\lambda=0.5)$
             value评分 rollout评分

Step 5. End 结束

循环以上过程直至达到最大搜索次数或者设定时间,选择根节点下访问次数最多的走法。

若 $\max\limits_aQ(s,a)<-0.8$,AlphaGo认输。


Results

Short name Policy network Value network Rollouts Mixing constant Policy GPUs Value GPUs Elo rating
$\alpha_{rvp}$ $P_\sigma$ $v_\theta$ $P_\pi$ $\lambda=0.5$ 2 6 2890
$\alpha_{vp}$ $P_\sigma$ $v_\theta$ - $\lambda=0$ 2 6 2177
$\alpha_{rp}$ $P_\sigma$ - $P_\pi$ $\lambda=1$ 8 0 2416
$\alpha_{rv}$ [$P_\tau$] $v_\theta$ $P_\pi$ $\lambda=0.5$ 0 8 2077
$\alpha_{v}$ [$P_\tau$] $v_\theta$ - $\lambda=0$ 0 8 1655
$\alpha_{r}$ [$P_\tau$] - $P_\pi$ $\lambda=1$ 0 0 1457
$\alpha_{p}$ $P_\sigma$ - - - 0 0 1517

Elo ratings (Nature AlphaGo)

logo center 100%


Elo ratings (Seoul AlphaGo)

logo center 63%


AlphaGo vs Lee Sedol: Game 1

logo center 63%


AlphaGo vs Lee Sedol: Game 2

logo center 63%


AlphaGo vs Lee Sedol: Game 3

logo center 63%


AlphaGo vs Lee Sedol: Game 4

logo center 63%


AlphaGo vs Lee Sedol: Game 5

logo center 63%


Thanks