是策略网络的输出。一个有意思的点在于一个节点被访问次数越多,选择它作为子节点的可能性越小,这是为了搜索多样性考虑。
2. 扩展
如果 L 节点上围棋对弈没有结束,那么可能创建一个节点 C。
3. 模拟
用价值网络和快速走子计算节点 C 的质量度。
4. 反向传播
根据 C 的质量度,更新它爸爸爷爷祖先的质量度。
上述搜索步骤反复进行,直到达到某个终止条件。搜索结束后,MCTS 选择根节点的质量度最高的子节点作为 AlphaGo 的着法。从上面描述来看,策略网络、快速走子和价值网络主要用于减少搜索宽度和减少搜索深度两个方面。策略网络用于使得搜索朝着几个恰当的候选集中,从而减少了搜索宽度。价值网络和快速走子用在评估叶子节点质量度上,使得搜索就不用继续往下搜索,从而减少了搜索的深度。
策略网络,快速走子和估值网络的训练
AlphaGo 将策略网络,估值网络和快速走子三者在蒙特卡罗搜索树框架下构成的一个系统。这三者的效果和效率就很关键。那么 DeepMind 是怎么训练这三者呢?
1.策略网络的训练
策略网络就是一个深层的 CNN 模型。策略网络输入是棋局,输出是1919个概率值(棋盘是1919的方格),对应下一步落子位置的概率。其实 AlphaGo 一共训练了两个策略网络:有监督学习策略网络 (Supervised Learning network, SL network) 和强化学习策略网络 (Reinforcement Learning network, RL network)。SL network 用的人类棋谱做训练数据。田渊栋的知乎文章评论有 SL network,“这种做法一点也没有做搜索,但是大局观非常强,不会陷入局部战斗中,说它建模了‘棋感’一点也没有错”,“当然,只用走棋网络问题也很多,就我们在DarkForest上看到的来说,会不顾大小无谓争劫,会无谓脱先,不顾局部死活,对杀出错,等等。有点像高手不经认真思考的随手棋”。
训练好 SL network 之后,然后使用强化学习进行自我对局进一步更新参数,从而得到 RL network 。RL network 是 SL network 的加强,能力得到了很大提高。据论文报告的结果,RL network 对 SL network 的胜率达到了 80%。不过 AlphaGo 搜索使用的是 SL network, 理由是 SL network 着法比较多样。
2.快速走子的训练
论文里说局部特征匹配(local pattern matching)加逻辑回归(logistic
regression)的方法。局部特征匹配就是一些匹配局部形势的特征,比如周围有多少个敌方棋子,有多少个我方棋子。训练数据是人类棋谱。但论文没有太看重这一块。
3.价值网络的训练
价值网络也是一个深层的 CNN 模型,输入棋局,输出获胜的概率。价值网络的训练有意思的是训练数据的选择。从人类棋谱里,我们能整理出棋局-胜负对应关系。但如果用人类棋谱,数据量好像不是很够,训练直接过拟合了。论文中报告的结果,如果用人类棋谱,价值网络的训练误差为0.19而测试误差达到了0.37。因此作者们用的是 RL network 自我对弈的3000万棋局作为训练数据,价值网络的训练误差为0.226而测试误差达到了0.234。
AlphaGo 各个模块的训练流程可以用论文中的一张图表示。