AlphaGo-171主机测评

1. 围棋游戏规则

2. 设计思路

3. 训练流程

3.1 behavior cloning初步训练策略网络

3.2 reforcement learning进一步训练策略网络

3.3 用策略网络训练价值网络

4. Monte Carlo Tree Search

4.1 Selection

4.2 Expansion

4.3 Evaluation

4.4 Backup

4.5 总结

5. AlphaGo Zero

5.1 使用蒙特卡洛树搜索训练策略网络

1. 围棋游戏规则

棋盘有19行19列，共有361个落子点。

状态（State）就是黑白棋子以及空位的组合，状态可以用由0和1组成的19x19x2的tensor来表示（与论文不完全相同，便于理解），具体来说就是分别用两个19×19的矩阵来对应黑子和白子，若某位置有黑子（白子），矩阵对应元素为1，否则为0。AlphaGo实际使用19x19x48的tensor来记录其他信息。

动作（Action）就是往棋盘的空白位置上放一个棋子。动作空间 Action space： $\\mathcal{A}\\subset\\{1,2,3,\\dots,361\\}$ 。AlphaGo中可能的动作序列数量为 $10^{170}$ 。

2. 设计思路

用behavior cloning来初步学习策略网络（policy network）：AlphaGo从16万局人类的游戏记录中学习一个策略网络。behavior cloning既是模仿学习又是监督学习方法，本质是多分类，不是强化学习。

用策略梯度算法训练策略网络：AlphaGo用两个策略网络做自我博弈，拿胜负结果来训练策略网络。

在策略网络训练完成后，用策略网络训练价值网络（value network）（用的不是actor-critic方法，actor-critic方法要求同时训练策略网络和价值网络，而AlphaGo先训练策略网络后训练价值网络）。

在真实下棋时，AlphaGo用策略网络和价值网络执行蒙特卡洛树搜索（Monte Carlo Tree Search, MCTS），用于指导搜索，排除无用搜索。

3. 训练流程

3.1 behavior cloning初步训练策略网络

观测当前状态

。

策略网络输出向量做预测，表示各动作概率 $p_t=[\\pi(1|s_t,\\theta),\\cdots,\\pi(361|s_t,\\theta)\\in(0,1)^{361}$ 。

观测到人类真实动作是 $a^{\\star}_t=281$ 。

将真实动作 $a^{\\star}_t$ 用独热编码（one-hot）表示，记作 y_t

，

也就是361维向量，其中第281个位置元素为1，其余位置元素为0。

使用CrossEntropy作为损失函数，衡量策略网络预测和人类真实动作之间的差距， Loss=CrossEntropy(y_t,p_t)

。

计算损失函数关于参数 $\\theta$ 的梯度，使用梯度下降算法更新一次参数 $\\theta$ 。

使用behavior cloning初步训练策略网络时，若当前状态 s_t 在训练数据（棋谱）中出现过，那么策略网络可以很好地模仿人类真实动作；若当前状态 s_t 在训练数据（棋谱）中未出现过，那么策略网络模仿人类真实动作的表现会很糟糕，因为可能的状态数量太多，并且有很大概率状态在训练数据（棋谱）中未出现过。

之后使用强化学习进一步训练策略网络可以改进状态 s_t 在训练数据（棋谱）中未出现过，策略网络模仿人类真实动作的表现会很糟糕这一表现。

3.2 reforcement learning进一步训练策略网络

让两个策略网络Player(Agent)和Opponent(Environment)进行博弈：Player使用策略网络模型的最新参数；Opponent中的参数不用更新，随机从之前的参数中选择一个即可。

用每一局的胜负作为奖励更新参数，游戏未结束时奖励为0，若Player最终胜利，则 $r_T=+1,u_1=u_2=\\cdots =u_T=+1$ ；若Player最终失败，则 $r_T=-1,u_1=u_2=\\cdots =u_T=-1$ 。

下面为RL更新参数 $\\theta$ 的完整流程。

从开始到结束，把整个游戏的轨迹记录下来: $s_{1},a_{1},s_{2},a_{2},\\cdots,s_{T},a_{T}$ 。

计算Player的回报 $u_1=u_2=\\cdots =u_T= \\text{-1 or 1}$ 。

计算策略梯度，由之前策略学习中的内容，可用 $g_\\theta$ 来近似策略梯度， $g_\\theta=\\sum\\limits_{t=1}^T\\frac{\\partial \\log \\pi(a_t|s_t,\\theta)}{\\partial \\theta}\\cdot u_t$ 。

使用梯度上升更新参数 $\\theta$ ， $\\theta\\leftarrow \\theta +\\beta \\cdot g_\\theta$ 。

3.3 用策略网络训练价值网络

策略网络训练完成后，观测当前的状态 s_t ，根据策略函数 $\\pi(\\cdot|s_t,\\theta)$ 概率分布随机抽样得到动作 a_t ，Agent如果按照策略网络的指示执行下去的话，已经可以击败业余选手，但策略网络的表现还是不够稳定，只要犯一点错也许就会改变游戏的结果。比策略网络更稳定的方法是蒙特卡洛树搜索，为了完成蒙特卡洛树搜索，需要增加价值网络学习，这里的价值网络是对状态价值函数V的近似而不是Q的近似（之前的价值学习那里是对最优动作价值函数Q的近似）。

给定策略函数，状态价值函数 $V_\\pi(s)=\\mathbb{E}[U_t|S_t=s]$ 可以评价当前状态的好坏。使用价值网络 v(s;w) 来近似状态价值函数 $V_\\pi(s)$ ， v(s;w) 来评价当前状态优劣。

让两个策略网络Player(Agent)和Opponent(Environment)进行博弈，Player已训练完成，参数不用更新。Opponent中的参数也不用更新，随机从之前的参数中选择一个即可。每下完一局更新一次价值网络。

下面是用策略网络训练价值网络的完整流程。

从开始到结束，把整个游戏的轨迹记录下来: $s_{1},a_{1},s_{2},a_{2},\\cdots,s_{T},a_{T}$ 。

计算Player的回报 $u_1=u_2=\\cdots =u_T= \\text{-1 or 1}$ 。

计算损失函数，损失函数反映价值网络预测的是否准确， $L=\\sum\\limits_{t=1}^T\\frac{1}{2}[v(s_t;w)-u_t]^2$ 。

使用梯度下降更新参数

， $w\\leftarrow w -\\alpha \\cdot \\frac{\\partial L}{\\partial w}$ 。

4. Monte Carlo Tree Search

实际下棋时，使用蒙特卡洛树搜索方法，不需要训练，但需要策略网络和价值网络辅助

蒙特卡洛树搜索方法的每一轮模拟有四步（Selection、Expansion、Evaluation、Backup），每下一次棋需要重复模拟动作很多次。

4.1 Selection

观测到状态 s_t ，首先对于所有的动作，计算每个动作的得分，选择得分最高的动作 a_t （这个动作并不会真的执行，只是为了模拟）。

4.2 Expansion

然后，假设Agent已经执行了动作 a_t ，对手观测到了当前状态 s_t' ，对手根据策略函数 $\\pi(\\cdot|s_t';\\theta)$ 概率分布随机抽样的到动作 a_t' ，假设对手执行动作 a_t' ，我们观测到新状态 $s_{t+1}$ 。

4.3 Evaluation

从状态 $s_{t+1}$ 开始，后面让策略网络做自我博弈，双方都由策略网络控制，双方依次放棋子，知道分出胜负为止。Agent要是赢了，奖励就是1；Agent要是输了，奖励就是-1。这个奖励可以用来评价状态 $s_{t+1}$ 的好坏。

价值网络 $v(s_{t+1};w)$ 也可以用来评价状态 $s_{t+1}$ 的好坏。那么关于状态 $s_{t+1}$ 的分数就是 $V(s_{t+1})=\\frac{1}{2}v(s_{t+1};w)+\\frac{1}{2}r_T$ ，这个分数就反映了状态 $s_{t+1}$ 的好坏。

4.4 Backup

由于模拟会重复很多次，所以每个状态下都会有很多条记录，那么 a_t 下面就有很多子节点，把 a_t 下面的记录做一个平均记作 Q(a_t) ，作为 a_t 新的价值。 Q(a_t) 就是对动作 a_t 好坏的评价。

4.5 总结

蒙特卡洛树搜索根据当前状态选择分数最高的动作 a_t ，用策略网络模拟对手动作，产生新的状态 $s_{t+1}$ ；通过自我博弈和价值网络两个途径得到 r_T 和 $v(s_{t+1};w)$ ，记录其平均值 $V(s_{t+1})$ ；用上一步分数 $V(s_{t+1})$ 更新该动作的分数 Q(a_t) ，并且根据选择动作 a_t 的次数来更新 N(a_t) 。最终经过很多次重复后，选择使 Q(a_t) 最大的动作 a_t ，让Agent执行动作 a_t 。

人类玩家在下棋时只会向前看几步，而AlphaGo则是每一步都看到每个动作最终导致的棋局结束状态。

5. AlphaGo Zero

AlphaGo Zero没有使用behavior cloning，即未从人类经验进行学习，而是训练策略网络时就使用蒙特卡洛树搜索。但并不意味着behavior cloning就无用，由于behavior cloning不需要最终奖励就可以使用，因此对于一些代价很严重的事件，使用behavior cloning更合适（例如做手术）。

AlphaGo

1. 围棋游戏规则

2. 设计思路