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

alpha(α)是希腊字母表的第 1 个字母,代表起点;mu(μ)是第 12 个,代表中途。从书写了传奇的 AlphaGo 开始,DeepMind 一直在不断更新迭代这一系列的新算法,创造了 AlphaGo Zero、AlphaZero 和 MuZero。通用性更强的 MuZero 算法不仅能出色地掌握棋盘游戏,而且还在 57 款不同的 Atari 游戏上达到了超越人类的水平。

本文将简单介绍这些算法的演进历程。未来,DeepMind 能否创造出这一系列的终极算法 OmegaZero 呢?

DeepMind 近期发布了他们开发的 MuZero 算法,并强调其在 57 款不同的 Atari 游戏上达到了超人类的水平。

能玩 Atari 游戏的强化学习智能体非常值得研究,这些游戏不仅视觉状态空间非常复杂,而且与国际象棋、日本将棋围棋不一样的是,在 Atari 游戏中,智能体无法使用完美模拟器(perfect simulator)来执行规划。

「完美模拟器」的思想是推动 AlphaGo 及 AlphaGo Zero 和 AlphaZero 等后续进展的关键限制条件之一。这使得这些智能体受限于国际象棋、日本将棋围棋,对机器人控制等现实世界应用而言没什么用处。

马尔可夫决策过程(MDP)为框架,可以将强化学习问题描述为:

国际象棋、日本将棋围棋智能体带有一个知道如何去玩的模拟器

AlphaGo、AlphaGo Zero、AlphaZero 和 MuZero 系列算法对这一框架进行了扩展——使用了规划(planning),如下图所示:

通过整合规划来扩展强化学习问题框架。

DeepMind 的 AlphaGo、AlphaGo Zero 和 AlphaZero 使用了「(动作, 状态) → 下一个状态」这样的完美模型,以蒙特卡洛树搜索(MCTS)的形式执行前向规划。在策略映射和价值估计方面,MCTS 能为深度神经网络提供完美的补充,因为它能平均化这些函数近似中的误差。MCTS 为 AlphaZero 在下国际象棋、日本将棋围棋方面提供极大的帮助,让其可以在完美的环境模型中执行完美的规划。

MuZero 利用 MCTS 规划的方式是通过学习一个动态模型,如下图所示:

MuZero 的蒙特卡洛树搜索。

MuZero 实现有参数模型映射 (s,a) → (s』, r) 的基于模型的强化学习方法是不完全重建 s' 处的像素空间。可以将其与下面来自 Ha and Schmidhuber 的 World Models 的图像相对照:

基于模型的强化学习在模型中重建像素空间的示例,来自:https://worldmodels.github.io/。

来自 MuZero 的规划算法在 Atari 领域内非常成功,对强化学习问题具有非常巨大的应用潜力。本文将解释 AlphaGo、AlphaGo Zero、AlphaZero 和 MuZero 一路以来的演化历程,以便让你更好地理解 MuZero 的工作方式。这里有一段解释视频:

AlphaGo

AlphaGo 是该系列算法中的第一个,表明深度神经网络可以通过预测策略(从状态到动作的映射)和价值估计(从给定状态获胜的概率)来下围棋。在给定状态下,这些策略和价值网络被用于选取之后的动作以及值得进一步探索的状态,进而增强基于树的前向搜索。

AlphaGo 使用了 4 个深度卷积神经网络、3 个策略网络和 1 个价值网络。其中 2 个策略网络是使用专家下法的监督学习训练的。

监督学习的损失函数是由某些类型的 L(y』, y) 组成的。在这里,y' 是指基于给定状态预测的策略网络的动作,y 是人类专业玩家在该状态下的动作。

rollout 策略是一个更小型的神经网络,其输入也是更小的状态表征。由此造成的结果是 rollout 策略对专家下法的建模准确度显著低于更高容量的网络。但是,这个 rollout 策略网络的推理时间(基于给定状态给出预测结果的时间)仅有 2 微秒,相比而言更大型的网络需要 3 毫秒,这使其在蒙特卡洛树搜索模拟中非常有用。

监督学习策略网络被用于初始化第 3 个策略网络,其是通过自对弈和策略梯度训练的。策略梯度的思想是直接根据所得到的奖励来优化策略;相比而言,其它强化学习算法则是学习一个价值函数,然后再根据该价值函数来使该策略贪婪。这个策略梯度训练的策略网络可以与自身参数之前迭代版本进行对抗,优化自己的参数,然后选择能取得最终胜利的下法。这种自博弈数据集然后再被用于训练一个价值网络,进而预测给定状态下一局游戏的获胜者。

AlphaGo 的最终力量源自将策略网络和价值网络组合到了 MCTS 中,如下图所示:

MCTS 的思想是执行提前搜索,以便更好地估计马上就要采取的动作。这种搜索先从根节点(棋盘的当前状态)开始,然后通过选择一个动作来扩展该节点,然后再基于该状态所得到的状态和动作变换,重复这一操作。MCTS 基于这一 Q + u(P) 项来选择所要跟踪的树的边,即价值网络对状态的估计、策略网络为该状态赋予的原始概率密度和节点已被访问次数的负加权(因为这要重复一次又一次)的加权组合。AlphaGo 的独特之处是使用了 rollout 策略模拟来平均化价值网络的贡献。这个 rollout 策略模拟会一直到 episode 结束,得到胜利或失败的结果;并且其会通过一个额外的参数 lambda 与价值函数对该状态的估计融合到一起。

AlphaGo Zero

AlphaGo Zero 在 AlphaGo 的基础上实现了显著的提升,它更加通用,而且是从零人类知识开始的。AlphaGo Zero 没有使用专家下法的监督学习来进行初始化,而是将价值网络和策略网络组合到了单个神经网络中。相比于 AlphaGo 中所使用的更简单的卷积网络,该网络扩展到也可使用 ResNet。ResNet 来执行价值映射和策略映射的优势是很显著的,下图比较了双任务 ResNet 与单任务 CNN:

AlphaGo Zero 最有趣的特点之一是其训练策略网络的方式,这种方式使用了 MCTS 找到的动作分布,如下图所示:

MCTS 通过使用其作为监督来更新策略网络,从而实现对策略网络的训练。这是一个很聪明的想法,因为相比于直接从状态到动作进行映射,MCTS 能让策略网络通过前向搜索得到更好的动作分布。

AlphaZero

AlphaZero 是 AlphaGo 系列算法泛化到围棋之外的第一步,研究了下国际象棋和日本将棋所需的变化。这需要为残差神经网络构建输入状态和输出动作表征。

在 AlphaGo 中,状态表征使用了一些人工设计的特征平面,如下所示:

AlphaGo Zero 则使用了更通用的表征,就是简单地通过传入双方玩家的前 8 步走子的位置和一个二元特征平面来告诉智能体它是哪一方玩家,如下所示:

AlphaZero 在国际象棋和日本将棋中使用了类似的思想来编码输入状态表征,如下所示:

AlphaZero 的算法也有一些细微的改变,比如宣布自博弈胜者的方式以及消除了围棋棋盘上的反转和旋转等数据增强方式。

MuZero

下面就是这一系列当前最佳的算法 MuZero。MuZero 表现出了非常强大的泛化能力,并且无需完美模拟器也能进行学习。国际象棋、日本将棋围棋都是带有完美模拟器的游戏,也就是说你的任何动作都能导致棋盘上出现明确的且可观测的变化。但是,对于非常复杂操作任务(比如 OpenAI 开发的那种操作魔方的机器手),情况却非如此,你很难知道向给定关节施加 30 牛顿的力会怎样。

下图给出了 MuZero 的关键思想:

图 A 给出了使用表征函数 h 将原始观察映射到隐藏状态 s0,然后再使用 s0 进行基于树的规划的流程。在 MuZero 中,组合到一起的价值/策略网络在这个隐藏状态空间中执行推理,因此它不是将原始观察映射成动作或价值估计,而是以这些隐藏状态为输入。动态函数 g 学习的是从隐藏状态和动作到未来隐藏状态的映射。

图 B 展示了与 AlphaGo Zero 首次引入的方法类似的训练策略网络的方式,即通过模仿 MCTS 所产生的动作分布。

图 C 展示了这个系统的训练方式。这三个神经网络中的每一个训练目标,都联合了优化价值网络和实际返回结果之间的差异、动态模型经历和预测的中间奖励之间的差异、MCTS 动作分布和策略映射之间的差异。

表征函数 h 是如何在这个优化环路中完成训练的呢?

表征函数 h 通过「通过时间的反向传播」在这个联合优化方程中发挥作用。假设你要求取 MCTS 动作分布 pi(s1) 和策略分布 p(s1) 之间的差。p(s1) 的输出是 p(g(s0, a1)) 的一个结果,这又是 p(g(h(raw_input), a1)) 的一个结果。这也是通过时间的反向传播向隐藏层送回更新信息的好方式。

AlphaGo → AlphaGo Zero → AlphaZero → MuZero

我希望这篇文章能帮你在 AlphaGo、AlphaGo Zero 和 AlphaZero 的背景中清楚理解 MuZero!

论文链接:

  • AlphaGo: https://www.nature.com/articles/nature16961

  • AlphaGo Zero: https://www.nature.com/articles/nature24270

  • AlphaZero: https://arxiv.org/abs/1712.01815

  • MuZero: https://arxiv.org/abs/1911.08265

原文链接:https://towardsdatascience.com/the-evolution-of-alphago-to-muzero-c2c37306bf9

产业AI棋盘游戏DeepMind
相关数据
DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年,最初名称是DeepMind科技(DeepMind Technologies Limited),在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯,谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后,Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏,例如即时战略游戏《星际争霸II》(StarCraft II)。深度AI如果能直接使用在其他各种不同领域,除了未来能玩不同的游戏外,例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作,基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

https://deepmind.com/
AlphaZero技术

DeepMind 提出的 AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。DeepMind 推出的 AlphaGo 曾在围棋项目中取得了超越人类的表现,其研究曾经两次登上 Nature。2018 年 12 月,AlphaGo 的「完全自我博弈加强版」AlphaZero 的论文又登上另一大顶级期刊 Science 的封面。在论文中,AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。

马尔可夫决策过程技术

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型,为动态规划与强化学习的最优化问题提供了有效的数学工具,广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时,我们一般特指其在离散时间中的随机控制过程:即对于每个时间节点,当该过程处于某状态(s)时,决策者可采取在该状态下被允许的任意决策(a),此后下一步系统状态将随机产生,同时回馈给决策者相应的期望值,该状态转移具有马尔可夫性质。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

围棋技术

围棋是一种策略性棋类,使用格状棋盘及黑白二色棋子进行对弈。起源于中国,中国古时有“弈”、“碁”、“手谈”等多种称谓,属琴棋书画四艺之一。西方称之为“Go”,是源自日语“碁”的发音。

将棋技术

将棋,日语平假名:しょうぎ 片假名:ショウギ 罗马音:syo u gi也叫本将棋,又称日本象棋,一种流行于日本的棋盘游戏。

推荐文章
暂无评论
暂无评论~