Dong Guo's Blog

AlphaGo Zero浅读

| Comments

上周在滴滴内部分享了这篇文章读后感,这里记录一下浅见。

1.问题的本质和AlphaGo的解决思路

1.1 下围棋在计算机中是什么问题?

这是有限空间的解搜索问题,问题的复杂性来自于搜索空间的巨大和不可穷尽。类似但更简单的的问题包括:走迷宫,下五子棋,以及各种策略游戏。这些问题很多已经被较好地解决(超过人类专家的水准)。

AlphaGo之所以获得这么大的反响,是由于这个问题大得多的空间复杂性以及之前对该问题的论断(预测几十年之后才能超越人类)。以及David Silver团队一牛的技术营销能力。

1.2 AlphaGo的解法思路是直观的

AlphaGo(包括Zero)解决下围棋问题的“思路”是比较朴素的,受过基础算法训练的同学应该能想到一些,当然难度在于有了思路之后解决的方式和程度。

  • look forward(向前多看几步,人类下五子棋、象棋、围棋都是这个思路)
  • 学习高手是如何落子的
  • 评估某个棋局的赢面

这也是AlphaGo的Methodology。

2.AlphaGo(2016年)的解法

2.1 核心之一:MCTS

MCTS(Monto Carlo Tree Search)是go中的一个核心算法(在AlphaGo之前的各种围棋程序基本都基于MCTS)。MCTS核心思想是基于反复的episode sampling高效地建立一棵树状结构,高效体现在其重点exploit较优的path,且兼顾了exploration。树建立好之后,每个节点记录了Q-value信息,直接可用于Action决策。几个步骤如下:

  1. Selection:基于棋局当前的state定位到Tree的一个叶子节点,每个节点存储Q-value(以及prior probability)和visit count;Q-value的初始值通过Policy Network的prediction
  2. Expansion:当叶节点visit count大于某个阈值,继续从深度上拓展该path,使用default policy做sampling;
  3. Evaluation:combine Q-value with one random rollout result, and update value of state
  4. Backup: 更新tree(update visit count,and Q-value)

在AlphaGo之前,各种围棋程序的解法基本就是依赖MCTS及其变种,问题是go的解空间(包括深度和宽度)巨大,AlphaGo的主要改进是使用Policy Network作为MCTS的先验将树搜索宽度限制在了高概率的分支上(narrow down search to high-probability moves),以及使用Value Network减少了树的搜索深度(当Value Network预测叶节点的胜率比较极端,就没有必要做expansion或rollout了),将探索集中在高效的空间,从而显著提升了power。

2.2 整体步骤

  1. Policy Network的第一步训练:基于Human knowledge(专业棋手的落子),使用DNN,有监督学习人类的落子(Q-value),就是一个分类问题;

  2. Policy Network的第二步训练:在第一步有监督学习到的Network参数基础上,使用self-play(不同的policy)进行对弈,基于Policy Gradient RL进一步优化Network;

  3. Value Network训练:学习每个state的赢面,使用policy network一样的网络结构(除输出层),基于MC value-based RL进行训练

  4. 将学习到的Policy Network作为MCTS节点的prior probability,指导子节点的选择。将学习到的Value Network作为MCTS节点state value的prior probability,结合rollout的结果,一起update MCTS各个节点的信息

3.AlphaGo Zero

3.1 算法改进点

AlphaGo Zero相比AlphaGo最大的不同是将MCTS的建立过程和Network的训练融合在一起,互相迭代(而不是像AlphaGo中先单独训练Network,再将Network灌到MCTS中)。第一,MCTS的Q-value和eposide self-play的胜负一起指导Network的训练(trust MCTS);第二,MCTS的Q-value指导Network self-play的move;第三,Network的预估结果迭代地作为MCTS节点Q-value的prior probability(而不是第一版AlphaGo中一次性地加入)

  1. 随机初始化Network(注意Zero中Policy和Value共享一个Network),初始化MCTS(各个node的信息)
  2. 如下几个步骤不断迭代
  3. 在当前棋局state下,基于MCTS的selection,指导Network self-play的move
  4. 基于上一轮的Network参数,指导MCTS做selection(update Q-value的prior probability)
  5. 一盘棋结束,基于eposide的胜负(state value),以及MCTS的Q-value,指导Network参数的迭代

Loss function如下:

如上是我理解AlphaGo Zero在算法上的最大改进。其余几点改进如下(部分是由于前者间接带来的):

  1. 2个Network合成一个(这个我没有太多感受,一些文章提到通过2个network分别来建模policy和state-value是之前的best practice)
  2. without any supervision of human data(不再依赖学习人类棋手的move做policy network的初始化);这一点我理解是由算法改进带来,之前的版本在训练Policy Network时没有MCTS的协助,仅仅依靠policy network本身做self-policy确实肯定搞不定;
  3. Network结构:使用了residual network,这一点提升了600 Elo;不同blocks数目power有一定差异
  4. MCTS不再需要rollout:这一点也好理解,当MCTS的buiding和Network training融合,training过程从self-play中拿到了eposide胜负信息输入

3.2 效果对比

paper中这张图除了表明Zero的威力,还表达了Zero相比Supervised Learning得到的Policy并不能更好地预估Human expert的move,但是Elo却高很多,即:Zero学到的技艺和人类围棋知识不同,且人类大脑有限的计算能力很可能陷入了局部解。

几个不同算法的performance差异,提示:2个player如果Elo差距400分,分高的胜率在90%。

4.综合感受

  1. RL在解决无及时反馈问题上的能力扩宽了想象力
  2. 不使用human expert move进行学习,这个我也觉得比较好理解,围棋本质就是有限空间的解搜索问题,在有强大计算能力和好的算法时,不依赖人的数据理论上是可行的(况且确实有被人类带入狭隘解空间的风险,本来就是要PK掉人类的)
  3. 适用性:围棋是一个非常有确定性的问题,一方面输赢的定义很明确,另一方面除了落子没有其他因素影响到棋局;而很多我们在滴滴遇到的问题并没有如此简单;
  4. 很多ML理论和实践的工作都用到了sampling,以及左右互搏迭代的思想,Alphago Zero也是。该思想值得在工作创新中重视
  5. Engineering的重要性,不仅是集群和计算能力,更多的是通过所谓的tricks(其实大多是从数据中发现问题)解决仅有理论或idea搞不定的问题(DQN和alphaGo这3篇paper中deepmind体现的淋漓尽致)
  6. 从16年到17年,alphaGo的复杂性是降低了(算法过程、计算需求、网络),更简洁却更好地解决问题,这个是境界了
  7. deepmind团队(或者说google)体现的强大技术营销能力,确实佩服!

5.几篇文章和code

  1. 2015, Human-level control through deep reinforcement learning: Beat human in some games without human knowledge
  2. 2016, Mastering the Game of Go with Deep Neural Networks and Tree Search: Beat human in Go game partially rely on human knowledge
  3. 2017, Mastering the Gmme of Go without Human knowledge: Dominate human in Go game without human knowledge
  4. 在知乎看到有Alphago Zero的开源实现版本,未验证仅供参考

Comments