AlphaGo简单解析

2024-03-08 17:37:10

AlphaGo

Go Game

围棋的棋盘是19*19的，一共有361个位置可以放棋子。
State：两方交替放棋子，这样棋盘的状态就是黑白棋子以及空的位置的排列。
- 可以用一个 19 × 19 × 2 19\times 19 \times 2 19×19×2的tensor就可以来表示了。这里假设黑棋位置的排列，可以用一个 19 × 19 19 \times 19 19×19的矩阵来表示，对应位置有黑棋就表示为1，否则就表示为0。同样，白棋也可以用同样的方法来表示。
- 但是实际上AlphaGo 使用一个 19 ∗ 19 ∗ 48 19*19*48 19∗19∗48的tensor来表示的，并且记录了很多其他的信息。
Action：就是往棋盘的空白位置放棋子，一开始有361个位置可以放棋子，随着游戏的进行，放棋子的位置也越来越少了。
- Action space： A ⊂ { 1 , 2 , 3 , . . . , 361 } \mathcal{A} \subset \{1,2,3,...,361\} A⊂{1,2,3,...,361}。动作空间A是1-361这个集合的一个子集，动作等于几就在几号位置放置棋子
围棋游戏的复杂度非常高，动作序列的组合大约是 1 0 170 10^{170} 10170

Alpha Go的主要设计思路

Training and Execution

训练分三步来做：
- 模仿学习，AlphaGo根据16万局人类的游戏记录中，来学习一个策略网络，这是一个监督学习，就是多分类，不是强化学习。
- 用策略梯度来进一步训练上面得到的策略网络。这里它让两个策略网络来自我博弈，拿胜负结果来训练策略网络。强化学习可以让策略网络的实力变得更强。
- 训练一个价值网络。这里Alpha Go没有使用Actor-Critic方法，Actor-Critic方法要求同时训练价值网络和策略网络，但是Alpha Go中它是先训练了一个策略网络，然后再训练一个价值网络。
当Alpha Go实际下棋的时候用的是蒙特卡洛树搜索(Monte Carlo Tree Search，MCTS)
- 这里的搜索时用到了策略网络和价值网络，他们可以排除掉没有必要搜索的动作。

Policy Network

State：AlphaGO有多个版本，它们定义的状态是不一样的，它的第一个版本里面是 19 × 19 × 48 19 \times 19 \times 48 19×19×48的一个tensor，来表示围棋的状态，最新版本AlphaGo Zero用的是 19 × 19 × 17 19\times 19 \times 17 19×19×17的tensor，这里解释 19 × 19 × 17 19\times 19 \times 17 19×19×17的tensor。
- 这里的 19 × 19 19 \times 19 19×19是棋盘的大小，可以用一个 19 × 19 19 \times 19 19×19的矩阵来表示黑色棋子的位置，如果一个位置上有黑色棋子，矩阵对应的元素就为1，否则为0。同样使用另一个矩阵来表示白色的棋子。17是这么来的，把当前黑色的棋子用一个矩阵来表示，之前7步的位置用另外7个黑色矩阵来表示。白色棋子类似。这样就用了16个矩阵，第17个矩阵就是，如果现在该下黑色棋子了，这个矩阵就是一个全1的矩阵，如果现在该下白色棋子了，这个矩阵就是一个全0的矩阵。这样状态就被表示出来了。
如果让你设计策略网络，怎么设计呢？
- 将上面的得到的状态作为输入，然后使用卷积层得到一个特征向量，最后用一个或多个全连接层，输出一个361维的向量，输出层的激活函数是softmax，因为输出是一个概率分布。输出向量的每一个位置代表一个动作，每一个元素代表该动作的概率值。
AlphaGo最初的版本有些不同，它只有卷积层没有全连接层，输出是一个 19 × 19 19\times 19 19×19的矩阵，每一个位置对应棋盘上的位置，每一个元素就是下在该位置的概率。
训练策略网络的第一步是Behavior Cloning，从人的经验中学习一个初步的策略网络。2016年的版本用了behavior Cloning，Alpha Zero并没有使用。
- 一开始策略网络的参数是随机初始化的，如果一开始让机器自我博弈，他们会做出很随机的动作，这样他们会打很久才能找到一个合理的动作。这就是AlphaGo最初为什么用人的知识来训练策略网络的原因。它使用的KGS中的十六万局六段以上玩家的记录训练。
- Alpha Go用Behavior cloning这种监督学习的方法来学习一个策略网络，进过Behavior Cloning之后，机器已经可以打败业余玩家了，但是还是打不过职业玩家。
Behavior Cloning：
- 这不是强化学习，强化学习靠的是奖励来学习，这是一种模仿学习，Behavior Cloning只要让策略网络去模仿人的动作就好了。
- Behavior Cloning是一种模仿学习，是强化学习的替代品。
- 其其实就是回归或分类方法和强化学习完全不是一回事。
- 训练策略网络步骤
  - 每一步都会观察到一个状态 s t s_t st，它是用一个tensor来表示棋盘上的格局。
  - 把状态作为策略网络 π \pi π的输入，它的输出是一个361维的向量 p t p_t pt，这个向量是这361个动作的概率。这里的动作就是将棋子放在哪一个位置上。
  - 人类玩家真实的动作为 a t ∗ a_t^* at∗，
  - 将人类玩家真实的动作变为一个361维的向量，这个是全0的只有对应的放置棋子的位置的元素是1。将这个one-hotting code记为向量 y t y_t yt
  - 使用CrossEntropy来作为loss 函数来衡量人类玩家和机器的差异，越接近就越小
  - 求出损失函数关于神经网络参数 θ \theta θ的梯度，然后做一次梯度下降来更新 θ \theta θ
- 使用behavior cloning训练完一个策略网络之后，就可以让它和人类玩家博弈了。那么为什么behavior cloning有效呢？
  - 当当前的状态出现在了训练数据中，那么策略网络就可以根据人的行为做出动作。那么做出的非常好。
- 既然Behavior cloning 的效果不错，为啥还要用RL呢？
  - 因为他的效果不如RL，他的缺陷在，当状态s没有出现在训练数据中怎么办呢？它的决策就不会太好，错误会累加，当一个状态没有出现在棋谱中的时候，策略网络就会做一个较差的结果，下一个动作就会更差，一直这样就会更更差。
- Behavior Cloning经常会失败，这是为啥呢？
  - 因为围棋棋盘非常复杂，涉及到的状态是一个天文数字。所以没有出现在训练集中的状态是非常正常的，这样它就会乱下，然后错误会累加，就会输掉比赛。
- Behavior Cloning + RL的胜率大于Behavior Cloning，AlphaGo的文章也证明了这一点
Train Policy Network Using Policy Gradient
- AlphaGo使用两个策略网络来做博弈，一个叫做Player，另一个叫做Opponent。Player就是Agent，它是由策略网络来控制的，是策略网络最新的模型参数，每下完一局用胜负作为奖励，将奖励来更新参数。Opponent相当于环境，它只是用来陪Agent玩的，每当Player下一个棋子，Opponent也跟着走一步，相当于随机状态转移，它也是用策略网络来控制的，但是它的参数不用学习，随机从旧的参数中选出一个座位Opponent的参数，就可以了。
- 怎么定义奖励呢？让Player和Opponent做博弈，一直到一局游戏结束为止，假设走了t步之后，一局游戏结束了，当游戏没有结束的时候，奖励为0，游戏结束后最后一个奖励要么是+1，要么是-1，取决于Agent的输赢。
- 根据奖励的定义可以算出回报(return) U t U_t Ut，这里不做折扣，如果Agent赢了，那么从第一步到最后一步所有的回报就是就是+1，如果Agnet输了就是-1。这里的意思就是假设Agent赢了，就假设Agent的所有的动作都是好的，反之。
- Alpha Go使用policy gradient来更新参数。
  - 之前我们使用 ∂ l o g π ( a t ∣ s t , θ ) ∂ θ ⋅ Q π ( s t , a t ) \frac{\partial log\pi (a_t|s_t,\theta)}{\partial \theta}\cdot Q_{\pi}(s_t,a_t) ∂θ∂logπ(at∣st,θ)⋅Qπ(st,at)来近似策略梯度
  - 这里的动作价值函数 Q π ( s t , a t ) = E [ U t ∣ s t , a t ] Q_{\pi}(s_t,a_t)=\mathbb{E}[U_t|s_t,a_t] Qπ(st,at)=E[Ut∣st,at]。动作价值函数是随机变量 U t U_t Ut的条件期望。
  - 假设观测到了随机变量 U t U_t Ut的值 u t u_t ut，这样我们就可以拿 u t u_t ut的值来近似 U t U_t Ut，所以就可以近似 Q π Q_{\pi} Qπ的函数值
  - 这样策略梯度就可以近似为： ∂ l o g π ( a t ∣ s t , θ ) ∂ θ ⋅ u t \frac{\partial log\pi (a_t|s_t,\theta)}{\partial \theta}\cdot u_t ∂θ∂logπ(at∣st,θ)⋅ut
  - 玩完一局游戏我们就知道 u t u_t ut的值了，我们还知道策略网络的参数，这样我们就可以算出这个策略梯度了。
- 策略网络训练概括
  - 需要让两个策略网络博弈，每玩完一局更新一次模型的参数。
  - 玩完游戏会得到一个trajectory： s 1 , a 1 , s 2 , a 2 , ⋯ , s T , a T s_1,a_1,s_2,a_2,\cdots , s_T,a_T s1,a1,s2,a2,⋯,sT,aT
  - 有了trajectory的和奖励，我们就可以更新Player的参数了。
    - 如果胜利回报 u t u_t ut都为1，反之失败都是-1
    - 然后算一下近似策略梯度： g θ = Σ t = 1 T ∂ l o g π ( a t ∣ s t , θ ) ∂ t h e t a ⋅ u t g_{\theta}=\Sigma_{t=1}^T\frac{\partial log\pi(a_t|s_t,\theta)}{\partial theta}\cdot u_t gθ=Σt=1T∂theta∂logπ(at∣st,θ)⋅ut
    - 最后做策略梯度上升 θ ← θ + β ⋅ g θ \theta \leftarrow \theta + \beta \cdot g_{\theta} θ←θ+β⋅gθ
  - 只需要管player的参数，不需要管opponent
至此，AlphaGo已经使用了Behavior Cloning和策略梯度算法训练好了策略网络，现在就可以使用这个策略网络 π \pi π来和别人下棋了。下棋之前将当前棋盘的状态 s t s_t st作为输入，输入策略网络 π \pi π，策略网络的输出是一个概率分布，每一个动作都有一个概率值，然后使用随机抽样得到一个动作 a t a_t at，也就是棋盘上的位置。这时候策略网络已经很强了，但是还不够打败冠军。比策略网络更好的方法是蒙特卡洛树搜索，他的表现会更稳定。

Train the Value Network

为了进行蒙特卡洛树搜索还需要学习一个价值网络。这个价值网络和我们之前的不太一样。这里的价值函数是对状态价值函数V的近似，而不是对Q的近似。
- V π ( s ) = E [ U t ∣ S t = s ] V_{\pi}(s)=\mathbb{E}[U_t|S_t=s] Vπ(s)=E[Ut∣St=s]，它是回报 U t U_t Ut的条件期望。
- 期望是对未来的动作A和状态S求的，用期望消除了除了 s t s_t st意外的所有的随机变量。
- 给定策略函数 π \pi π，状态价值函数 V π V_{\pi} Vπ可以评价当前局势的好坏，如果 V π V_{\pi} Vπ的值接近1表示当前的局势很好表示快要赢了，如果接近-1说明快要输了。
- 这里AlphaGo使用了一个神经网络 v ( s ; w ) v(s;w) v(s;w)来近似 V π V_{\pi} Vπ，他可以评价当前的局势好不好。
- 在AlphaGo使用的价值网络和策略网络是两个独立的部分，Alpha Zero中则让两个网络共享一些卷积层。这是很有道理的，价值网络和策略网络都是将当前的状态作为输入，底层的卷积从输入中提取特征，这些特征对两个神经网络都适用。策略网络的输出是361个概率值，每一个值对应一个动作。表示下一步该怎么走。价值网络的输出是一个标量，是对当前状态的打分，反映当前状态下的胜算有多大。
策略网络和价值网络是分别训练的，Alpha Go先训练策略网络，然后在训练价值网络。
价值网络的训练步骤
- 先让两个机器博弈，每下完一局就更新一次网络，当游戏结束的时候就知道回报 u t u_t ut了。
- 价值网络的学习就像是回归一样，将真实观测的到的 u t u_t ut作为target，希望价值网络的预测和真实观测的接近。然后就有了损失函数。
- 然后根据损失函数来更新网络的参数。
到了这里Alpha Go的训练已经基本结束了。但是跟李世石下棋的时候，它既没有用策略网络，也不是用的价值网络。他用的是蒙特卡洛搜索。之前学习两个神经网络就是为了帮助AlphaGo进行蒙特卡洛树搜索。

Monte Carlo Tree Search

Alpha Go会向前看搜索出未来可能发生的状态，找出其中胜算最大的。主要思想是：
- 首先选出一个动作a，这个动作不是均匀随机抽样的，动作有好几百个算不出来。所以要先排除不好的动作，使用策略函数就可以排除大多数动作了，策略函数可以算出每个动作的概率值，概率值非常低的都可以排除。然后用两个策略网络进行自我博弈，看这次是胜还是负，然后根据胜负和价值函数，这两个因素来给这个动作打分。重复这个过程很多次，然后每个动作都有很多个分数，可以看一下哪个动作的总分最高，这个分数就可以反映出动作的好坏。然后Alpha Go就会根据这个最高的分来下棋。这就是蒙特卡洛树的主要思想。
Monte Carlo Tree Search（MCTS）主要步骤，Alpha Go每一步都要重复很多次。
- 按照动作的分数来选出一个动作，这个动作是一个假想的动作，AlphaGo并不会真的去做这个动作，只是为了方便接下来的模拟。看看这个动作好不好。
- 让对手走一步，但是这一步指示模拟，不知道对手怎么走，所以就要用到策略网络了，假想的对手会根据策略函数 π \pi π来随机走一步
- 给这次选出的动作打一个分数，分数由两部分组成。一个是价值网络给当前状态打的分数记作v，另一个是自我博弈后的得到奖励r，然后去r和v的平均值作为a的分数
- 用上一步得到的分数来跟新动作的分数，
Step 1: Selection. 选出一个动作
- 观测棋盘当前的状态 s t s_t st，alphaGo直到有哪些棋盘可以放棋子，肯定有不止一个位置可以放棋子，所以可有很多个动作，我们可以根据动作的好坏程度来探索，优先探索好的动作，排除掉不好的动作。
- 首先给所有的动作都打一个分数。记为： s c o r e ( a ) = Q ( a ) + η ⋅ π ( a ∣ s t ; θ ) 1 + N ( a ) score(a)=Q(a)+\eta \cdot \frac{\pi (a|s_t;\theta )}{1+N(a)} score(a)=Q(a)+η⋅1+N(a)π(a∣st;θ)，可以反映动作的好坏程度，有两个部分组成，一个是 Q ( a ) Q(a) Q(a)，是搜索计算出来的分数，叫做动作价值，其实 Q ( a ) Q(a) Q(a)就是一张表，记下了361个动作的分数。另一个是策略函数 π \pi π给a打的分数除以1+N(a)，也就是动作a越好，策略函数打的分数就越高，但是搜索越多次打的分就越高，但是如果搜索很多次了分母N(a)就会变大，这样就避免了重复探索一个动作太多次。这里的 η \eta η是一个超参数。初始化的时候，所有的 Q ( a ) Q(a) Q(a)为0，做了很多次搜索之后，N(a)的值会逐渐变大，后面一项的值就会逐渐变小，这样策略函数就变得无关紧要了，这时候探索哪个动作几乎完全由Q(a)来决定。
- 只有分数最高的动作会被探索
Step 2: Expansion
- 将上一步选中的动作记为 a t a_t at， a t a_t at只是一个假想的动作而不是真正的动作。假如AlphaGo做出了 a t a_t at的动作，那么下一步对手该怎么走呢？AlphaGo需要揣测对方的意图，AlphaGo可以推己及人，如果Alpha Go觉得一步棋比较好，对手也会这么认为，所以可以根据策略网络随机抽样一个动作，假设对手会执行这个动作。这里的 s t ′ s_t^{'} st′是站在对手的角度看到的棋盘的状态， a t ′ a_t^{'} at′是对手执行的动作，假设对手有两个动作可选，经过策略函数 π \pi π的计算，这两个动作概率分别为0.4和0.6，做个随机抽样，产生新的状态 s t + 1 s_{t+1} st+1。我们并不知道对手心里怎么想，所以我们不知道状态转移函数，但是我们可以使用策略函数来代替状态转移函数。
Step 3: Evaluation
- 从状态 s t + 1 s_{t+1} st+1开始，后面就由策略网络自我博弈，双方挨个放棋子直到分出胜负。当这局分出胜负之后，就有了奖励 r t r_t rt，如果赢了就是+1，输了就是-1，这个奖励就可以拼价状态 s t + 1 s_{t+1} st+1好坏，要是赢了，就可以增加状态 s t + 1 s_{t+1} st+1的评分，如果输了就可以降低 s t + 1 s_{t+1} st+1的评分。除了用奖励来评价以外，AlphaGo还用价值网络V来评价 s t + 1 s_{t+1} st+1，直接将状态输入价值网络得到 v ( s t + 1 , w ) v(s_{t+1},w) v(st+1,w)，这个分数也可以反映出胜算大小。然后求出奖励和价值网络的值的平均得到分数，这个分数可以反映出，状态 s t + 1 s_{t+1} st+1的好坏。
Step 4: Backup
- 由于这个模拟会进行很多次，所以每个状态下会都会有很多条记录，每个动作 a t a_t at都有很多这样的子节点，所以 a t a_t at就会对应很多条这样的记录，把 a t a_t at下面所有的分数加起来做一个平均，作为 a t a_t at的价值，记为: Q ( a t ) Q(a_t) Q(at)。计算这个Q值的用途是：蒙特卡洛树搜索的第一步selection的时候，要选择最好的动作来搜索，做选择的时候要用到Q值，每个动作都有一个Q值，这些Q值初始化的时候为0，每当动作搜索一次就留下一条记录，Q值就是所有记录V值的平均，有了这个Q值，蒙特卡洛树就知道哪个动作最好，在第一步selection的时候选择这个动作