AlphaGo(Zero) 学习笔记
AlphaGo(Zero) 学习笔记
AlphaGo结构解析
首先,AlphaGo的本质依然是启发式搜索,和DL有关的是估值函数是一个CNN网络. 抛开技术细节,对于任意一个局面,估值(预测)函数做了两件事情:
- 我们需要对当前局面估值,取值是[-1,+1]区间,-1代表最后一步棋必败(当前局面必胜),+1代表最后一步棋必胜(当前局面必败).
- 其次,我们要预测每个空白位置的落子概率.
有了估值函数,我们就可以对搜索剪枝. 剪枝的手段其实很直观:
- 一是多搜索大概率的落子位置,
- 二是多搜索估值更好的局面.
把这两点结合在一起就是AlphaGo所使用的搜索算法, Monte Carlo Tree Search.
搜索带来的另一个好处是,可以让当前局面的预测更加精确. 那么我们就可以拿这些更加精确的局面估值来训练网络.
对于搜索来讲,估值函数的作用是剪枝.对于估值函数来讲,搜索的作用是获取改良的数据集用于训练. 所以估值函数与搜索两者相辅相成,可以在自我博弈中不断训练改进.
以上就是整个AlphaGo的训练和运行架构.
MCTS如何改进预测值
MCTS算法不同于其他RL算法的一个地方在于,他只专注于当前给定的局面. 通常的RL算法,会试图同时迭代更新所有局面的估值,而MCTS只试图改进当前局面的估值. 因为局面状态空间庞大,同时更新大量局面的估值不现实. 更重要的是,对于训练来讲,这样会更快的产生出更好的训练集.
给定一个局面$s$,我们估值函数$s.p,s.v = Q(s)$,其中$s.p$是落子分布,$s.v$是当前局面的估值. 对于每个落子位置$x$,我们设定三个属性,一是$x$的概率$x.pr$,二是落子后局面的估分$x.v$,三是该位置已经搜索过多少次$x.n$. 值得注意的是,开始时我们只知道$x$的落子概率$x.pr$,并不知道落子之后的局面估值$x.v$. 同时对这三个属性实现一个权重函数用于搜索时贪心选择落棋位置.
每次我们贪心选择权重最大的位置$x_0$进行搜索,一直到达某个叶子节点(未预测过的局面),
\[s_k = move(s,x_0,x_1,\dots, x_k); \\ s_k.p, s_k.v = Q(s_1).\]$s_k$是通过权重贪心树上的路径,由根节点到达的一个叶子节点,是一个我们还没使用$Q$预测过的一个局面,我们调用$Q$得到$s_k$的估值$s_k.v$和落子预测$s_k.p$. $s_k.p$用于未来可能的搜索. 而拿到$s_k.v$做了两件事情:
- 一个是更新了一系列$x$的权重,
- 二是可以用来向上更新一系列祖先节点局面们的估值.对于根节点$s.v$,我们获得了更准确的估值.
落棋分布的更新方法是,对根节点局面$s$搜索完成后,用(每个落棋点的搜索次数/总的搜索次数)来作为新的落棋分布来用于训练.
对于$s$有了新的落子分布和估值,就可以继续训练估值函数了~ MCTS更具体算法的请参见其他资料~~~
CNN的结构
这里的CNN结构非常简单,第一层3x3的Conv,接下来10+层Residual,最后是双头Conv+Dense,一个用softmax预测policy(落子分布),一个用tanh预测value(当前局面估值). 没有任何黑科技,用Keras就可以轻松实现.
训练
明显MCTS是CPU密集的一个算法,每一次搜索只展开一个局面,单线程训练没办法批量调用Q,所以使用尽量多的线程训练,可以提高GPU利用率.
代码
训练了5000局之后…反正我是下不过了,但是还是下不过yixin(那是肯定的…)
补: AlphaGo Zero与AlphaGo的不同之处
忘记写Zero做了哪些改进了…这部分比较细节一点,对讲解框架上没太大区别.
第一点是MCTS算法上的不同. 首先要科普一下传统MCTS的四个步骤:
- 权重函数贪心选择叶子节点
- 使用policy function展开叶子节点–预测叶子节点接下来一步的落子分布
- 使用rollout计算叶子节点的估值
- 向上传播估值更新祖先节点
Zero并没有使用rollout来计算叶子节点的估值,而是用了双头网络的另一头value function直接预测了一个估值. 这样的更新方式更偏向于TD算法.
传统MCTS中的rollout也叫playout,简单讲就是以当前节点为起点,使用当前policy模拟$N$盘游戏直到结束,然后按照输赢数量来计算估值,注意这里模拟的游戏局面并不加入到MC树中. 原始的AlphaGo是使用快速走棋网络来rollout.
第二点不同是网络结构不同. Zero使用了双头网络,policy和value共享了底层网络.原始AlphaGo中,有三个独立的网络,除了policy network和value network,还有一个Fast Rollout policy network,就是rollout中用来快速走棋的网络.简单讲就是快速走棋网络速度比前两个快了1000倍.
在AlphaGo中,policy network用来展开叶子节点,而value network只是用来初始化叶子节点估值. 所以原始的AlphaGo是传统的MCTS,完全基于policy function和试图优化policy function,而value function仅仅是锦上添花,因为即便没有value function,rollout依然可以有效的对叶子节点估值.Zero则不同,它完全使用value function估值,而没有做任何rollout,让value function起到了不可或缺的作用.
第三点不同是网络的input不同. 对于AlphaGo,policy和value网络速度过慢的另一个原因在于,他们的input不仅是原始的棋面状态,还有许多层人工设计的特征层,比如有8层liberites, 8层Capture size… 这些特征层还是需要另外的hardcode来计算出来的. 从另一个角度来说AlphaGo的网络是针对于围棋设计的一个网络. 而Zero宣称自己是通用棋类算法,没记错的话,他的input仅仅是最近的k步棋面状态.
第四点可有可无,AlphaGo是棋谱预训练的,而Zero是完全自我博弈的.