Antkillerfarm Hacking V7.0

深度强化学习（六）——AlphaGo（2）

2019-10-08

AlphaGo

其他关键点（续）

由于很多人类的棋局都是因为中间偶然的失误导致了全盘覆灭（所谓“一着不慎满盘皆输”），其中的偶然性非常大，局部的优劣往往和棋局的最终结果无关，因此Value Network并没有用人类棋谱来训练。

AlphaGo每更新一个“小版本”后，都要将这个版本和迄今最好的版本对比，如果新的版本胜率超过55%，才会用来取代以前最好的版本。这样做显然是为了防止AlphaGo自我博弈得“走火入魔”，陷入局部最优。

AlphaGo Zero

论文：

《Mastering the game of Go without human knowledge》

AlphaGo Zero对AlphaGo进行了全面提升：

  • input plane去掉了手工特征，基本全由历史信息组成。

  • Policy Network和Value Network不再是两个同构的独立网络，而是合并成了一个网络，只是该网络有两个输出——Policy Head和Value Head。

  • 骨干结构采用了Resnet，层数大大增加。

  • 完全采用自我博弈，去掉了人类棋谱。

  • 取消了Fast rollout。AlphaGo Zero的实践表明，如果有足够好的Value函数的话，MCTS的采样效率要远远高于传统的alpha-beta剪枝。因此，rollout也不是必须的。

稍后的AlphaZero的实践表明：AlphaZero搜索80000个节点的棋力，已经超过了Stockfish搜索70000000个节点的棋力。

  • Policy Gradient vs. Policy Iteration

AlphaGo依赖快速走子的结果，获得最终的结果信息。因此，它的奖励来源比较单一：只有对局的最终结果。这种做法实际上就是通常说的Policy Gradient。

但正如之前指出的：棋下输了，不意味着每步棋都是臭棋。因此，只使用最终结果，既会导致奖励稀疏，也不利于实时评估走子的价值。

AlphaGo Zero转而采用Policy Iteration方法，实时对盘面进行估计，不再依赖终局结果。

AlphaZero

论文：

《Mastering Chess and Shogi by Self-Play with aGeneral Reinforcement Learning Algorithm》

AlphaZero相对于AlphaGo Zero的改进不算大，毕竟也就只差2个月。它的贡献在于，证明了DRL对于很多棋类都是有效的。

MuZero

MuZero是DeepMind 2019年11月的作品。

论文：

《Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model》

参考代码：

https://github.com/AppliedDataSciencePartners/DeepReinforcementLearning

2020.12，MuZero登上了Nature，算是炒了回冷饭。。。

基本结构

MuZero在不具备任何底层动态知识的情况下，通过结合基于树的搜索和学得模型，在Atari 2600游戏中达到了SOTA表现，在国际象棋、日本将棋和围棋的精确规划任务中可以匹敌AlphaZero，甚至超过了提前得知规则的围棋版AlphaZero。

传统方法的局限：

  • Model-based RL在Atari 2600游戏上表现不佳。这类游戏的Model很难刻画，规则比较抽象。

  • Model-Free RL在棋类游戏上表现不佳。棋类的规则十分明确。

上图是MuZero和AlphaZero的网络结构对比图。从中可以看出：

1.AlphaZero只有一个网络。（虽然有两个用途：Policy和Value）

2.MuZero有三个网络：

  • Prediction Network。这个和AlphaZero相同。

  • Dynamics Network。

  • Representation Network。

Representation & Dynamics Network

Representation & Dynamics Network的主要思想来自如下论文：

1.《The Predictron: End-To-End Learning and Planning》

2.《Value Prediction Network》

上文已经指出Model-based方法的困难在于：有的时候Model是很难刻画的，而环境本身也许并不如模拟器那么纯粹、简单。

一个很自然的思路就是：既然NN能表示Policy和Value，那么能不能表示Model呢？

参考论文1提出了Predictron框架，它的主要思路是：

  • 构建一个abstract MDP model。虽然我们并不知道它的state，更不清楚它的transition，但是不要紧，假设它存在就好。

  • 状态表示。(即上图中的\(s^0,s^1,\dots\))

\[\vec{s} = f(s)\]

这里用\(\vec{s}\)表示系统的抽象状态以区别其实际状态s。也就是说，在系统模型中，预测的不是实际的状态s, 而是抽象的状态。即：建立real state space到abstract state space的映射。

  • 模型预测，不只是状态流的预测，还包括立即回报和折扣因子的预测。
\[\vec{s}',\vec{r},\gamma = m(\vec{s}, \beta)\]
  • 抽象状态\(\vec{s}\)处的值函数：
\[\vec{v} = v(s)\]
  • 由回报、折扣因子和值函数计算得到估计值。这里可以对这个abstract MDP model应用TD(n)和TD(\(\lambda\))算法，得到如上图所示的k-step和\(\lambda\)-weighted的预测值。其中的g表示累计奖励值。

这里的套路其实和DQN非常像，都是让预测值（这里是g）尽可能接近真实值。区别在于：这里既然是Model-based方法，那么自然有利用Model生成模拟样本的步骤，而DQN没有这样的步骤。

参考论文2的做法也是类似的。

\[\mathbf{Encoding}\quad f_\theta^{enc}: x\to s\] \[\mathbf{Value}\quad f_\theta^{value}: s\to V_\theta(s)\] \[\mathbf{Outcome}\quad f_\theta^{out}: s,o\to r,\gamma\] \[\mathbf{Transition}\quad f_\theta^{trans}: s,o\to s'\]

x：观测值（observation）。

s：abstract state。

o：abstract state上的option。

s’：下一个abstract state。

也是预测若干步的奖励值。

实现细节

重新回到MuZero，下图是MuZero的关键步骤图。

A部分：Representation Network + Dynamics Network + MCTS

B部分：从policy:\(\pi_t\)中采样得到action：\(a_{t+1}\)，环境根据\(a_{t+1}\)得到observation：\(o_{t+1}\)、h和reward：\(u_{t+1}\)。这些样本在用过后，被存入replay buffer。

C部分：训练时，从replay buffer中，采样得到\(o_t\)，通过h函数，得到\(s_t\)，然后执行K-step展开，得到p,v,r。

loss公式为：

\[l_t(\theta)=\sum_{k=0}^K l^r(u_{t+k},r_t^k)+l^v(z_{t+k},v_t^k)+l^p(\pi_{t+k},p_t^k)+c\|\theta\|^2\]

其中，p,v,r分别是policy、value、reward的预测值。而\(\pi\)、z、u则是对应的target值。（参见《深度强化学习（二）》中DQN一节中的current Q-value和target Q-value的定义）

MuZero和VPN一样，都是在abstract state space中用dynamics model做planning。MuZero的改进在于增加了对每个abstract state上policy的预测，因此效率比VPN要高一些。

最后需要澄清一点的是：模拟的Model永远比不上确定的规则。MuZero在棋类上的表现并不如AlphaZero。对比数据中，围棋项目的优势，更多的在于MuZero使用了更宽的网络。

参考

https://mp.weixin.qq.com/s/BLQF8WNsIe4a_rDeGWo_Vg

通用AlphaGo诞生？DeepMind的MuZero在多种棋类游戏中超越人类

https://www.zhihu.com/question/356976342

如何评价DeepMind新提出的MuZero算法？

https://zhuanlan.zhihu.com/p/31344949

联合模型的强化学习算法（三）

https://mp.weixin.qq.com/s/IcaxjdDLjihCK-nKBlJVWg

从α到μ：DeepMind棋盘游戏AI进化史

https://mp.weixin.qq.com/s/BWWCqAoSRkNAWXMiTOFhAA

DeepMind推出Agent57，在所有雅达利游戏上超越人类玩家

https://mp.weixin.qq.com/s/CvkIFuLTBDW0L8A9rJL7Ng

新算法MuZero登顶Nature，AI离人类规划又近了一步

https://mp.weixin.qq.com/s/dTJ7NvVs7qjF2FRoAZ_WlQ

MuZero算法过程详解

Leela Zero

Leela Zero是比利时人Gian-Carlo Pascutto开源的围棋AI。它的算法与AlphaGo Zero相同。而训练采用GTP协议，集合全球算力，进行分布式训练。

官网：

http://zero.sjeng.org/

代码：

https://github.com/gcp/leela-zero

GTP

Go Text Protocol，其目的是建立一个比GMP（Go Modem Protocol）协议的ascii接口更合适于双机通信、更简单、更有效、更灵活的接口。

官网：

http://www.lysator.liu.se/~gunnar/gtp/

参考：

https://www.tianqiweiqi.com/go-gtp.html

围棋引擎的GTP协议

minigo

Google员工Andrew Jackson作品。但tf官方一再强调这并非TensorFlow项目的一环，也不是DeepMind的AlphaGo官方版本，而是由独立的团队依照AlphaGo Zero的论文而实做出的版本。

官网：

https://github.com/tensorflow/minigo

参考：

https://zhuanlan.zhihu.com/p/352536850

AlphaGo Zero中的强化学习算法和google开源工程实现——从原理到代码实现

AI作弊/对抗

十多年前，当我还是一个中二青年的时候，就幻想有朝一日能够拿围棋世界冠军。当然，就算再中二，我自己也明白靠实力那是不可能的，当时做梦的法宝是制造一个AI，然后碾压一下所谓的国手。

按照当时(2000年前后)人们的预计，这个AI在2030年之前，都不可能造出来，然而，最终的结果实际上只花了一半左右的时间。

再之后，随着AI围棋的平民化，我的中二梦终于也有人将之付诸实现了：

https://mp.weixin.qq.com/s/npt2zZrKwPnNdY-hsa2RjQ

AI再乱围棋圈：“食言之战”柯洁落败；首例素人作弊引风波

这次作弊风波所使用的AI就是Leela Zero，可见目前（2018.5）它的棋力已经超过了顶尖棋手。

论文：

《Adversarial Policies Beat Superhuman Go AIs》

官网：

https://goattack.far.ai/

参考：

https://www.zhihu.com/question/569568604

如何看待katago被找到致命缺陷？

https://www.zhihu.com/question/584836681

如何看待美国业余围棋爱好者战胜顶级围棋AI，15局胜14局？

https://www.zhihu.com/question/554569740

国际象棋比赛疑用智能肛珠作弊，比赛作弊是如何靠人工智能和肛珠实现的？

ELF OpenGo

ELF OpenGo是Facebook开源的围棋AI，它是FB的AI游戏框架ELF的一部分。

官网：

https://github.com/pytorch/ELF

参考：

https://mp.weixin.qq.com/s/lOAx3suLIS-pEWyi8xZl6Q

“全民体验”AlphaZero：FAIR田渊栋首次开源超级围棋AI

PhoenixGo

PhoenixGo是腾讯微信团队的AlphaGo Zero复刻版。

官网：

https://github.com/Tencent/PhoenixGo

参考：

https://mp.weixin.qq.com/s/tJDmxsuS1QigYS75ZIdzRA

微信团队开源围棋AI技术PhoenixGo，复现AlphaGo Zero论文

Antkillerfarm
antkillerfarm@sohu.com

github.com/antkillerfarm

Fork me on GitHub