1. 首页
  2. 资料库

《星际2》最强AI复现计划:如何打造自己的AlphaStar

《星际2》最强AI复现计划:如何打造自己的AlphaStar


  新智元专栏  

作者:Maxwell、破破的桥

编辑:闻菲

【新智元导读】AlphaStar再次展现了DeepMind对研究方向的精准把控和卓越的工程实力。本文根据DeepMind博文及相关资料做了推演,试图在研究论文公布前复现AlphaStar的训练过程。沿用这套方法,你也创建自己的星际2训练环境!


自AlphaGo解决围棋问题之后,《星际争霸2》就成了DeepMind公司的新目标。在2018年6月,DeepMind发表了一篇论文,展示如何运用深度强化学习,解决诸如采矿最大化这样的小游戏。

 

没想到仅6个月后,他们的AI就已经可以和职业选手过招了。AlphaStar在Catalyst LE地图上打神族内战(PvP),以 5:0 战胜了职业选手TLO与MaNa,只是到了现场比赛时,被MaNa找到了一个无法应对棱镜骚扰的Bug致败。DeepMind公司那批机器学习天才们,研究方向掌握之精准,工程控制能力之强大,令人印象深刻。

 

这样的表演赛是DeepMind常见的预热,相信不久后它就会对Serra l 和Maru这样的顶级职业选手提出挑战。后者假如迎战,大概率菊花不保。

 

不过,与围棋不同的是,星际争霸这类即时战略游戏还有操作技能这一环。AlphaStar有不切屏看大地图的功能,以及偶尔爆出超越人类极限的有效手速(eAPM),都被指责为不够公平。相信DeepMind在正式邀战时会解决这些问题。

 

很多人最关心的一个问题是,AlphaStar究竟是如何训练出来的呢?我们尝试在正式论文尚未放出之前,通过DeepMind的博客文章作一些分析解读。


玩星际争霸的AI面对的问题

 

星际争霸2是一个困难的即时战略游戏。玩家必须实时地在成百上千个可行的操作中作出决断。


与人类相仿,AI的控制流同样由一轮轮操作组成。在每一轮中,AI先获取当前游戏状态,据此衡量并选择一次操作,然后提交给星际争霸2环境。


AI经由Blizzard和DeepMind联合创建的PySC2接口,与星际争霸2的游戏核心进行交互。每一步中,AI能够获取的游戏信息是一个矩形网格,网格的每个位置代表地图上的一个位置。每个位置上都有若干数值,代表此地的有效信息。

 

《星际2》最强AI复现计划:如何打造自己的AlphaStar

 

另一种理解方式是,游戏信息被组织成若干个网格,每份网格代表某一项特定信息(见上图右侧)。比如说“fog-of-war”网格代表是否存在战争迷雾;“height-map”网格代表地形高度;“unit-type”网格代表建筑或者作战单位。详细说明可参考报告论文[1]的第3.2节。

 

在操作方面,AI定义了300多个“宏操作”,在每一轮中,AI从这个集合内选取某个宏操作执行。宏操作由一系列基本操作组成。例如,“把当前选中的单位移到A处”,可以分成三步:1) 决定移动,2) 决定是否把操作排队,3) 点击某个地图位置。而上述操作又可以进一步分解为“按m键;松开m键;决定是否按shift键;地图A处按下鼠标左键;松开鼠标左键”。

 

不同粒度的操作分解,会将问题焦点分配到不同抽象层面。如果操作种类特别基本,到了按键盘鼠标的程度,单个操作的意义就非常小,探索有意义的策略就很难。反之,如果宏操作非常复杂,虽然意义显著,但每一步的选择空间又变得过于宽广,选中合适的策略也很难。PySC2取了一个平衡点,每个宏操作的意义,与人类逻辑层面上感知的操作接近,比如上面移动单位的例子,它就给了一个专门的操作。

 

AI一旦从决策空间选定了宏操作之后,就会生成一条 (a0, a1, a2, a3, a4, …) 形式的指令,其中“a0”指定了300多个基本操作之一,而“a1, a2…”是操作参数,比如给需要移动单位指定目的地。直观图示如下:


《星际2》最强AI复现计划:如何打造自己的AlphaStar

为什么都说星际争霸2问题难?


因为需要探索的空间太大。


根据DeepMind的报告,考虑操作和参数的各种组合,在典型对战环境中,决策空间的大小约有10^26 (简短的介绍可参见报告论文[1]第3.3节)。如果把星际争霸想像成一盘棋局,那么

 

  • 棋局的状态就是战场的全部信息,但由于战争迷雾的存在,星际2中一位弈者相当于遮挡住部分棋盘来对局;

  • 每一步可以落子的位置对应于此步可以进行的操作,其可能性的数量级大致相当于一大瓶可乐里水分子的数量。

 

注意以上讨论的仅仅是AI决定单步操作时需要面对的挑战,在对战中每一步对应一个的时间节点,如果按照职业玩家的操作频率来计算,每分钟需要行棋数百步,每步都在前一步的基础上以乘数拓展一个状态空间!

 

学习一步的操作固然困难,但尚可算入当前最成熟的统计学习方法——监督学习——可实际解决的问题的范畴。即给机器提供大量可观测的输入,即学习样本,并提供期望产生的输出。AI从这些配对样本中,学到输入与输出的变量应该怎样对应。


监督学习方便简单,而且从工程实现的意义来说,其实是我们唯一可以成熟使用的范式。但实际应用到学习对战这种任务上立即就会呈现出局限性 。


我们想象一个最简单例子,监督学习范式可以方便地运用到单个人脸识别,单个数字识别,单个物体识别这样的任务中。但如果不是“单个”数字识别,而是识别“一串”手写数字,那么我们应当如何构建监督学习呢?


1) 可观测的输入:整个图像;期望产生的输出:类似于“02971736”这样的数字串。 


假设输出的数字有个固定的长度上限,比如5位数字。那么对一副图像就可能有高达10^5种可能的输出。想训练好一个“5位数字串”识别器,就需要对每一种可能的字串,提供与其对应的图像例子,比如10000张不同的“01234”图像。那么,对所有的类别,“34567”,“34555”,“23588”…都提供10,000张用于训练的例子,其耗费将不可忍受。而每种类别10,000个例子的数量还是十分保守的估计,在典型的数字图像数据集,比如MNIST中,每个单个数字“0”,“1”,……的例子就有此数。

   

2) 可观测的输入:矩形图像块;期望产生的输出:“0”,……,“9”这类单个数字

   

在这种情况下,我们只需要针对10个数字作训练,例子数量呈指数级缩减。但它并不能直接解决“从图像中识别数字串”这个问题,因为还需面对“发现原始输入图像的哪些区域包含有意义的数字并截取”的难题。我们要仔细制定规则来确认哪些区域包含数字及其顺序,这是OCR任务中常用的方法,但恰如批评所言,这属于“人工+智能”。

   

3) 可观测的输入:整个图像,一个初始的矩形区域;期望产生的输出:矩形区域中的图像内容“0……9”,矩形区域在图像上的下一步移动,是否终止检测。

 

这就开始脱离监督学习的范式了。系统并非一次性的完成对输入的分析,产生输出,而是试图做一个决策流,每个步骤都要根据一个本步观测(输入)得到一个相应的决策(输出)。而一个步骤的决策又会影响下一个步骤的观测。如下图所示:


《星际2》最强AI复现计划:如何打造自己的AlphaStar

   

它更加符合人类智能解决实际问题的方式,而游戏环境则是这类方案天然的试炼场。这也是通过人工智能程序玩游戏,在近年来获得如此关注的原因之一。事实上:


  • 把上面流程中的“数字串原始图像”换成“星际争霸2游戏环境”,

  • 把判定和决策的输出结果换成上面讨论过的单步宏操作,

  • 把“截取出的图像块”换成上面讨论过的AI的对游戏的观测,


我们就基本定义好了“玩星际争霸的AI”所面对的问题


《星际2》最强AI复现计划:如何打造自己的AlphaStar

AlphaStar面对的就是这样一个问题,我们从它的博客文章[2]提到的若干技术要素出发,对其训练方法进行解说与猜测。它使用的这套技术分为如下三个大类:


  • 宏观训练策

  • 单个智能体强化学习策略

  • 智能体的构造和训练的具体实现   


拆解:AlphaStar的训练策略


1. 宏观的群体学习策略

 

简略地讲,AlphaStar 的总体训练过程,是一组多回合的“AI联赛”。在介绍联赛规则之前,我们先讲为什么要训练一群,而不是一个AI,来挑战星际争霸2。首先,星际争霸2本质上是一个对抗性游戏,玩家追求胜利需要考虑对手的活动,并无全局意义上的最优策略。其次,相比于围棋,星际争霸2对战场状态只能作不完全观测,且其状态空间更加庞大,导致一系列AI会各有偏好并相互克制。

 

对于一个的AI算法来说,强化学习任务中的诸要素,自然地分作两类:受控变量和外界环境。在学习的每个时间点,AI选择好的动作和观测结果,是两边交换信息的载体。

 

算法设计者须将外界环境视为黑箱,不能或不会在学习过程中加以控制。比如设计一个 AI 来挑战 Atari 主机中的某个游戏,算法设计者只能启动强化学习 AI 后从旁观察。对于星际争霸这类对战式的任务,被AI视为“外界环境”的元素,除游戏程序之外,对手一方同样满足:


  • 不在AI的控制范围

  • 对“本” AI 的行动作出反馈

  • 影响游戏状态,从而影响“本” AI 在下一个时间节点取得的观测结果


因此解决方案中需要考虑对手,为此构建的学习环境中也需要包含一个对手。

 

AlphaStar从一个单一的“种子选手”启动联赛,每一轮挑选有潜力的互相挑战,对优胜AI略微变通后令其加入扩大联赛队伍。一轮接一轮地将联赛开展下去。启动的种子AI来自基础的监督学习:从Blizzard战网下载人类玩家对战数据,训练深度神经网络学习每局对战每个时刻的(游戏状态,玩家操作)的对应关系。(更详细的,我们猜测应该是若干步的游戏状态序列和操作流之间的对应关系)

 

获得启动种子后的联赛式训练见下图(取自Deepmind blog)


《星际2》最强AI复现计划:如何打造自己的AlphaStar

博客中详细介绍的是第四轮训练Network-006的过程。首先我们注意到这个训练过程能够进行就有两个前提条件:i) 本轮的Network-006是前一轮Network-004的两个变异后裔之一。ii)Network-006被选中参加本轮联赛的比赛,以绿色表示,而每一轮当中不参加比赛的AI选手以蓝色表示。无论是否参加比赛,一轮当中所有的AI选手都会被原封不动地拷贝到下一轮。

 

之后,Network-006本场比赛的对手选定为Network-008,设定好学习参数,就可以进行强化学习训练了。注意Network-008在这次训练中充当“陪练”的角色,其本身的网络参数不会获得调整。Network-006将Network-008当作靶子来训练,会习得专门对付008的方案。至于008的出场是根据“Matchmaking Probability”算法抽取的,大约是在随机分布的基础上,让高等级选手出场的机会略多,具体计算方式必须等论文出来才能确定。

 

“星际争霸AI大联盟”始终保留其历史上的所有会员,每个AI都有出场机会。这样可以避免学习终局的那些高等级AI,只会针对其它高等级AI,反而不懂如何应对菜鸟的事件。训练的时候还会给一些比较弱的人工指导,比如“初期鼓励出狂战士”等。这类指导策略也是随机选取的,为的是进一步提升下一轮联盟中AI选手的多样性。

 

从他们博文看来,联赛举行了800轮之多。最后一轮过后,“星际争霸AI大联盟”中存在高达877个训练过的AI神经网络。在测试阶段出战者的选择方式,则是从这些AI选手中以Nash Distribution采样。

 

2. 单个 AI 的训练

 

下面我们分析特定轮比赛中AI个体的学习问题。这是一个强化学习任务

 

在“强化学习”中,AI 自行尝试输出不同的决策,训练者反馈给 AI 激励和新的数据。这些配对数据用于后期的“监督学习”,从机器在探索中得到的数据对,来学习环境输入与操作输出这两大要素之间的联系,在星际争霸2单个AI训练中,我们将这两个层面称作“强化学习探索”“构建 AI 模型本体来学习样本数据中的关联”

从“种子”选手开始,每个 AI 模型就继承了以前的模型从它们对战经验数据中学习到的决策策略。而首个种子选手继承的是人类选手的经验。一旦启动学习,AI 就立即面临强化学习领域经典的“守成探索不能得兼”(exploitation-vs-exploration)的问题。

 

根据 Deepmind 的介绍,AlphaStar 强化学习的骨干算法选用了“实干家-批评家”方法(Actor-Critic,AC)。为了加速训练以及取得稳定和可靠的效果,AlphaStar 使用了大规模并行的 AC 实现,另外结合了若干节约和利用有效经验的技巧来对付星际争霸2任务中学习远期回报的挑战。

 

AlphaStar 具体使用的 AC 算法是 2018 年 DeepMind提出的 IMPALA 算法[5]。其设计目的是解决高度并行的大规模学习问题。运行星际争霸2这样的大型游戏环境,令 AI 与之互动产生数据,是一个昂贵的计算任务。由于在 AC 算法框架下对模型参数的求导是一个伴随剧烈波动的随机性操作,用这种方法估计出来的导数来优化策略模型,只能让策略大致上变得越来越好。这个所谓“大致”的靠谱程度,就取决于我们能不能把导数的“剧烈波动”处理得不是那么剧烈。


一个自然的想法是:把策略多跑几遍,导数多求几次,求平均值。并行 AC 学习算法[6]就是对上述思路的直接实现—— 由于在 AC 架构中实际产生数据,探索环境的乃是“实干家”。我们在分配计算资源时偏向它,多雇佣实干家(多分配一些相应的策略执行进程),同时生成多条执行轨迹,并通过一个中心学习者从这些多线历史中估算策略参数的导数,结果会更准确,这些实干家相当于中心学习者的分身。IMPALA 框架则更进一步,所有分身实干家都只是“傀儡执行者”,既不需要优化策略参数,也不需要计算导数,只是负责执行生来所继承的策略,把经验数据忠实地记载下来,传回中心学习算法


《星际2》最强AI复现计划:如何打造自己的AlphaStar

即便不考虑对稳定导数计算的作用,这种做法也极大缓解了高并行复杂模型学习中的节点通讯问题。“傀儡执行者”和学习核心的关系,见上图,它们之间的通信频率比起频繁传递网络参数要少得(可以完成一个 episode 才更新一次策略参数)。而执行策略的历史数据往往比大型网络的导数(大小约为整个网络参数集)来得经济很多。

 

AlphaStar 还采用了几项对 AC算法的补充措施。其中重要的一项是,每个 AI 选手在训练期间,都会把自己的对战历史保存下来,供 AC 算法在估计参数导数时使用,即模仿自己的优秀历史。这种在学习者“脑海”里面重放历史经验(Experience Replay)的做法,之前在估值方法与深度神经网络结合的工作中采用过(Deep Q-Learning,DQN),并首次实现了AI在视频游戏上的突破。在直接学习策略参数的方案中,一般来说,这样做会导致估计偏差——因为 AC 算法“期望”它见到的数据是执行“本”策略得来。单采用参考历史数据的方案算出的模型改进方向,其出发点就有一点过时了。但由于从少量样本估计的模型参数的导数往往会有巨大波动。为更稳定地标定正确的学习方向,可以牺牲终点的最优特性。

 

还有一个措施,是把学习过的 AI 的策略精髓抽取出来,转移到正在学习的 AI 模型中(Policy Distillation)[7]。这个方法可以使用更紧凑的模型(参数小一个数量级)来逼近更大更复杂的模型的表现;可以合并多个策略来形成一个比其中每个个体都更可靠的策略——注意由于优秀策略的分布不是连续的,这不是一个简单平均的问题。比如考虑超级玛丽兄弟:策略A是跳起来踩扁蘑菇,策略B是发射火球然后直接前进,如何在A和B之间折衷相当困难;还可以在策略学习这个层面形成迭代:每一轮的学习都把上一轮学习到策略的精髓转移出来,在此基础上开始。由于Deepmind语焉不详,目前还不清楚这个方法是如何用于AlphaStar训练上的。

 

3. 神经网络模型和训练

 

强化学习AI算法。最终落实到具体的调整策略/模型的单个学习步骤上,也就是训练迭代的最内层循环中,还是要回归到监督学习范式,变成“针对这样的输入,鼓励(惩罚)模型产生如此的输出”的优化操作。在传统强化学习研究历史上,建立策略或者估值是理论重点。系统的状态往往被少数几个变量完美的描述,比如一个牛顿力学系统中各个刚体的位置和速度。但是在任何稍微复杂一点的问题中,数据表示问题仍然是一个挑战:即使强化学习算法非常有效,AI也必须知道当前观察到的状态与之前经历过的状态之间的联系。星际争霸游戏这类问题,其观测是十分复杂的对象(序列),于是我们也就要面对统计学习中的典型问题:通过分析数据,建立(输入,输出)之间的联系

 

目前大家的共识是,这个问题的核心是把输入的数据转换成一种有效的表示,这个“有效”是从期望产生的输出结果的角度来评判的。具体一点说,如果我们的训练数据中有两个样本(输入A,输出A)和(输入B,输出B),后来又观测到了(输入C)。一个好的输入数据的表达应当能帮助我们估计想要的“输出C”。比如我们做完“输入A->表达A”,“输入B->表达B”和“输入C->表达C”,然后比一比相似度(表达C,表达A)和(表达C,表达B),然后从A和B当中挑选更相似的那个,用它的输出来预估C的输出。如果这种估计方式真的能得到对于C来说合适的输出,我们说这个表达方式对于这个数据分析任务来说是好的。如果能完美的完成这个相似度辨别的任务,那么很多问题就可以简化成“查询一下现在遇到的状况跟训练时碰到的哪个情况类似,照当初的经验办理”。从另一方面说,如果能将每一个原始数据样本变换到一个多维向量,这些向量之间可以用简单的做差算距离来衡量相似度,那么这个变换也算解决了衡量数据样本之间的相似度的问题。这个任务有个术语叫做“数据表示”。

 

注意从上面的讨论我们可以看出,没有绝对“好”的数据表示,我们根据对某个特定的任务是否有效来衡量一种表示方法的好坏。数据表达的质量可不仅仅取决于输入数据的形式,而是跟整个数据分析的任务密切相关。比方说输入的对象是自然人,人当然是个十分复杂的对象,如果要量化描述之,那么对于“预估此人能否成为优秀的篮球队员”这个任务,“身高、摸高、100米跑时间”这些量化的指标就比较合理;而对于“预估此人会不会去观看某部电影”的任务,“票价与此人月收入的对比、前一年上映的每部电影此人是否观看过……”这些量化指标就显得合适。

 

深度学习的兴起的最大功臣是在随这类模型而得到的有效数据表示:从输入到输出之间架构好深度神经网络之后,我们就自然而然地把输入数据的转换,预测输出的数据模型,模型产生的输出与真实样例之间的对比,这三者统一到了同一个训练过程中。神经网络的结构也就同时规定了“怎样整理转换输入数据”和“怎样用整理过的输入数据预测所需的输出”这两个在数据分析中的关键步骤。

 

 •序列转换模型

 

根据Deepmind的说法,AlphaStar 采用了基于注意力机制的序列转换的表示模型。这种数据表达方法的起源是在自然语言处理领域,我们能够想象,这种方法擅长于表示成序列出现的数据样本。具体地说,transformer模型来自于自然语言处理中的翻译任务,把一句话——即一串单词和标点(语言的基本单位,tokens)——转换成另一种语言的基本单位。Deepmind同样没有详述这个模型在 AlphaStar 中的具体使用方法。不过据上文提到的使用人类对战数据预训练作为“种子AI”的做法来看,有可能预训练的任务被制定成了学习从输入“游戏状态序列”到输出“操作指令序列”之间的联系。

 

•策略模型

 

基于注意力机制的序列转换目前已经发展成为一个大的模型家族(刚刚在自然语言处理领域大放异彩的BERT也是其中一员),Deepmind 提到 AlphaStar 的输出策略的计算模型是一种产生“指针”来“引用”自己的输入序列从而构建输出序列的自回归(auto-regression)模型。

 

•基于多智能体的批评家

 

AlphaStar 的强化学习核心是“实干家-批评者”(AC)算法族。其具体的选择是引入一种更加适应多个AI共同学习,但每个AI的观测受限的学习环境的估值方法。其基本原理是采用“要不然”式估值(原名为Counterfactual Multiagent,直译为“反事实多智能体”),批评家在评判AI之前做的一项决策的价值时,使用“要是当时不这么做”的话平均下来会有若干回报,那么当初这么做的优势(劣势)也就相应得出。

 

以上大致是我们从目前已有的知识所能推测的AlphaStar的详细训练方案。在Deepmind正式论文发表之后,补足其中少量细节,我们就可以沿用这套方法,创建自己的星际争霸2训练环境。

 

参考资料

[1] https://deepmind.com/documents/110/sc2le.pdf

[2] https://deepmind.com/blog/alphastar-mastering-real-time-strategy-game-starcraft-ii/

[3] https://papers.nips.cc/paper/5866-pointer-networks.pdf

[4] https://www.cs.ox.ac.uk/people/shimon.whiteson/pubs/foersteraaai18.pdf

[5] https://arxiv.org/pdf/1802.01561.pdf

[6] https://arxiv.org/abs/1602.01783

[7] https://arxiv.org/pdf/1511.06295.pdf

更多阅读

点击“阅读原文”查看论文


【加入社群】


新智元AI技术+产业社群招募中,欢迎对AI技术+产业落地感兴趣的同学,加小助手微信号:aiera2015_2   入群;通过审核后我们将邀请进群,加入社群后务必修改群备注(姓名 – 公司 – 职位;专业群审核较严,敬请谅解)。

《星际2》最强AI复现计划:如何打造自己的AlphaStar

发布者:新智元,转转请注明出处:http://www.aiwuyun.net/archives/6305.html

发表评论

登录后才能评论

联系我们

在线咨询:点击这里给我发消息

邮件:admin@aiwuyun.net

工作时间:周一至周五,9:30-18:30,节假日休息