AlphaGo

概览

状态S - 19×19×48（棋盘长×宽×k），k至少为2，一张记录黑子分布，一张记录白子分布
动作A - 361维one-hot向量（所有动作序列的可能性有10^170之多，不可能穷举）

训练步骤：

通过Behavior Cloning初始化Policy Network PN（监督学习）
通过强化学习再训练PN
通过PN训练Value Network VN（输出是一个标量）

预测：通过PN和VN进行蒙特卡洛树搜索 MCTS

PN结构：S通过Conv获得A

通过Behavior Cloning初始化PN （π(a|s;θ)）

方式：通过模仿16w张6段以上棋手的棋谱来初始化PN。
与RL的区别：没有reward，只有模仿，属于分类或回归。
目标函数：CrossEntropy(yt, pt)，yt是专家action，pt=[π(1|s,θ),...,π(361|s,θ)]是PN输出（类似361类多分类）。
通过梯度下降迭代PN即θ。
限制：如果s出现过则效果很好，如果s没见过则效果糟糕。

通过强化学习再训练PN

定义Player(Agent)：最新参数的PN；Opponent(Environment)：旧参数的PN。
定义Reward: 棋局未结束时r=0，结束时r=±1（赢为正）。总回报ut=∑r=±1（即折扣因子γ=1），即赢的话每一步的return都是1，反之则都是-1，不区分输局中的好棋和赢局中的坏棋。
策略学习的梯度下降见https://www.jianshu.com/p/19f77a973dc6 中策略学习RL一节计算∂V/∂θ的法一。

通过PN训练VN

价值函数不是Q(s,a)，而是Vπ(s)=E(Ut|St=s)，ut=±1（赢为正）。用VN近似Vπ(s)，用来衡量当前局势。
目标函数：v(st;w)和ut的平方差。
通过梯度下降迭代VN即w。

通过PN和VN进行蒙特卡洛树搜索 MCTS

预测时，即下棋时，不会通过PN输出action，因为PN输出的是概率，带有随机性，而一步错就往往意味着失败，所以需要尽量消灭这种随机性。
MCTS分为4步：
Selection: 己方落子a。选择score(a)最高的a，score(a)=Q(a)+η·π(a|s;θ)/ (1+N(a))，N(a)是a被探索过的次数，Q(a)即a的评价
Expansion: 对方落子a'。根据π(a'|s';θ)随机选择a'，s'即己方落子后的棋盘，此时π相当于状态转移函数，因为对方落子可看做环境对action的反馈。
Evaluation: 计算Q(a)。Fast Rollout（即双方依次落子直到棋局结束），V(st)=(rt+v(st;w))/2，rt=±1（赢为正），v(st;w)即VN输出。对所有V(st)（以t为变量）求平均，得到Q(a)
Backup: 更新score(a)。
MCTS搜索结束后，选择使N(a)最大的a