游戏的强化学习简史
2020-06-12 11:24:54 作者：佚名
|
两年前，我参加了有关人工智能（AI）和机器学习的会议。 当我离开时，我遇到了一个由蒙特利尔初创公司Maluuba（当时是对微软的最近收购）的研究人员组织的一次演讲。 研究人员展示了他们如何创建一个AI代理，该代理在1980年代流行的街机游戏《吃豆人》中获得了999,990的最高分。 兴奋和好奇的气氛使房间里的每个人都无语。 我感到怀旧。 当我还是个小男孩的时候，很酷的孩子曾经在电子游戏中获胜。 如今，好孩子们写程序来为他们赢得游戏。 研究人员将他们当时的成功归因于强化学习（RL）。 我花了接下来的几天研究主题。 我发现了一些令人着迷的想法，而我今天的狂喜并没有减弱或消亡。 在本文中，我们讨论了人类对游戏性问题（无论是视频游戏还是棋盘游戏）的痴迷，以及为什么此类问题长期以来一直没有引起人们的注意。 我们简要地提到了利基算法，例如RL和神经网络（NN），这些算法有助于克服长达数十年的僵局。 简而言之，游戏：动作，奖励和状态 看，游戏具有状态，奖励和动作。 玩家通常执行动作以达到游戏的特定状态，并且一路上，他们会累积一些奖励。 最终分数是他们能够收集的所有奖励的总和。 "状态空间"是一个奇特的词，用于表示特定状态表示下的所有状态。 状态是人类在特定时间点上代表游戏的尝试。 这不是游戏本身的固有属性。 因此，游戏状态可以代表不同的人不同的事物。 对于视频游戏，游戏状态可以代表游戏地图上玩家的坐标，以及宝藏和对手的坐标。 视频游戏的其他丰富状态表示形式将每个视频帧都呈现为状态。 在吃豆人女士中，动作在向左，向右，向上和向下移动。 吃豆人或吃"强力颗粒"时吃掉彩色的鬼魂会给Pac-Man女士带来回报。 状态代表了吃豆人女士的位置，幽灵在特定时间点的位置和颜色。 它们还包含有关当前迷宫形状以及剩余颗粒的信息，吃豆子女士尚未食用这些颗粒。 > Pac-Man. Source: SourceAndPixel, via pixabay (CC0) 致命状态（吃豆人女士应避免）是幽灵吞噬吃豆人女士时的状态。 胜利的状态是吃豆女士吃掉所有颗粒并完成水平。 以棋盘游戏为例，在国际象棋中，动作是指移动到一块，无论是骑士，主教还是其他任何一块。 游戏的状态由所有未捕获的棋子放在游戏板上的位置表示。 奖励有些棘手，因为在整个游戏过程中，外行人无法说出此举对游戏其余部分的重要性。 需要由专家来确定哪些策略在战略上更胜一筹，哪些玩家更有可能获胜。 现在，这是马尔可夫决策过程（MDP）的非技术性介绍。 这是一张由过渡连接的状态图，上面有奖励。 在任何状态下都采取措施以最大化最终总奖励的方式遍历图形。 为什么游戏性具有挑战性？ 很难创造出高分并在游戏中击败人类的程序。 也许这就是为什么游戏性在寻求多巴胺的AI研究人员中很受欢迎的原因之一。 最近，优秀的游戏程序使用了RL模型和神经网络（NN）。 他们使用具有内部MDP表示形式的RL模型来了解周围的世界。 他们使用NN来概括从当前对世界的了解中从未遇到过的状态。 现在，这些RL模型容易受到一些主要障碍的影响，例如状态表示，奖励体系结构问题和计算问题（资源（例如AI代理消耗的处理时间和内存））。 我们将在接下来的三个部分中讨论这些障碍。 表示问题：游戏状态应该是什么样？ 研究人员断言，就像父母抚养孩子一样，他们断言他们比所创造的代理人更了解。 研究人员没有让探员像婴儿那样探索周围的世界，而是限制了游戏状态的细节，仅使用他们认为相关的信息子集来制作游戏状态。 被称为" RL之父"的理查德·萨顿（Richard Sutton）展示了这种短期优势复合体如何伤害了整个学科。 在他的博客" Incomplete Ideas"中，他写了一篇题为"痛苦的教训"的文章，他在其中将利用人类对游戏的理解与普通的搜索和学习进行了比较，后者获得了更大的成功。 代理商一次又一次地证明研究人员是错误的。 事实证明，研究人员几乎不知道AI代理商在试图赢得比赛时认为游戏的哪些部分有用。 以前游戏空间的减少以研究人员无法完全理解的方式损害了特工的效率。 当人们选择并选择要包含在状态中的要素时，他们就会注入偏见。 奖励架构问题 象棋这样的棋盘游戏没有分数。 例如，在国际象棋中，唯一的目的是夺取对手的国王。 俘虏主教或骑士并没有得到部分荣誉。 问题变成了：当游戏在非终端状态中没有明确的得分时，我们如何评估游戏状态？ 奖励功能是一种激励AI代理优先于其他行为的行为。 赢得比赛是一个极好的但尚不清楚的动机。 一个不好但很明显的诱因是夺取对手的所有骑士。 代理商在短期和长期内都能获得清晰有效的激励，从而表现最佳。 一个更直观的例子是，一个健康意识强的人避免食用美味的芝士蛋糕，尽管这会带来短期的欢乐，这仅仅是因为它长期会对他们的身体造成伤害。 同样，使用"良好"奖励功能的AI代理可以避免长期获胜的一些短期收益（收益）。 历史上，国际象棋大师创建了框架，以根据棋子的相对值将复杂策略的评估减少为某些数值。 例如，根据这些框架之一，为赢得女王而丢掉车队是一个简单的决定。 但是，这些框架带来了很大的警告。 他们可能会损害长期收益。 例如，捕获一个免费的兵可以在短期内为您带来（+1）优势，但可能会导致您缺乏连贯的兵结构，而兵无法相互保护和加强，这最终可能会带来挑战 游戏。 例如，典当结构之类的元素难以量化，因为它们依赖于玩家的"风格"及其感知的有用性。 计算问题：如何在大状态空间中搜索？ 在Atari游戏中，状态空间可以包含10 1至10 11个状态。 同时，象棋这样的游戏具有大约10⁴⁶有效状态，而象围棋这样的游戏则具有3⁶3有效状态。 为了更好地理解这些数字，可观察的宇宙中的原子数为10-2。 现在，尽管计算机随着时间的推移而变得越来越快，但它们却无法解决两个主要的子问题：状态空间的探索和NN的训练。 探索问题正在尝试访问尽可能多的州，以便代理商可以创建更现实的世界模型。 神经网络的训练将对部分可观察状态空间的推论推广到对非可观察部分的推论。 也就是说，未访问状态与被访问状态的相似程度。 在以下两个部分中，我们将对两个问题中的每个问题进行更详细的介绍。 RL和勘探/开发权衡 在整个人生中，很难确定一个"转弯"对一个人的满足感和富裕程度有多大贡献。 与您不接受或拒绝的求职者相比，您无法说出一份工作或一段关系带来了多少欢乐。 同样的问题也存在于游戏中。 很难准确地确定游戏不同阶段的动作对最终得分的贡献。 此类问题的技术术语是"信用分配"问题。 RL在解开值得在特定游戏状态中采取的行动方面一直是胜利的。 作为回报，信用分配问题为RL赢得了应有的名望。 RL模型通过为每个州分配信用值来解决"信用分配"问题。 RL分为两个交织阶段-学习和计划。 学习是指代理漫游模型以了解状态。 计划是指代理人将功劳分配给每个州并确定哪些行动比其他行动更好。 规划和学习是反复的过程。 在一次迭代中，在学习了—收集有关状态的信息之后，该代理对RL模型进行了规划。 通过选择一种可以最大化未来回报的状态，它可以构建从一种状态到另一种状态的过渡。 在下一次学习迭代中，当提示您为特定状态选择哪种操作时，它将选择导致最终状态得分最高的过渡状态。 仅当代理访问每个州时，它才能为州提供准确的信用值。 但是，由于许多值得解决的问题具有难以置信的庞大状态空间，因此RL代理不会访问每个州。 代理仅与世界上发现的部分合作； 它根据访问国家的"知识"来估计未访问国家的信用。 这种近似需要NN，我们将在下一部分中对其进行说明。 一种状态的信用取决于代理选择访问的以下状态。 通常，RL模型使用"探索/开发权衡"确定要访问的后续状态（或选择的操作）。 当您去餐厅订购您喜欢的菜肴时，您就在利用一顿本来就不错的饭菜。 如果您探索新菜，有可能比您喜欢的菜还要糟糕，但是同时，它可能会成为您最喜欢的菜。 正如谚语所说："没有冒险，就没有收获。" 在游戏玩法中，探索使模型探测到状态空间中更为重要的部分。 相反，利用剥削使其只能探查有限的但有希望的状态空间区域。 现在，状态空间搜索问题由RL模型可以访问多少个状态以做出更好的近似来定义。 区域越广，勘探范围越广，信用分配就越准确，并且模型变得越健壮。 然而，针对一个状态尝试许多动作会成倍增加计算复杂度。 神经网络呢？ 由于RL模型仅查看状态空间的一个子集，因此无法说出哪种操作最适合未访问状态。 在运行期间，代理可能会遇到一些以前从未见过的状态。 它需要一种机制来捕获最佳状态空间转换状态之间的相似模式。 尽管他们的训练在计算上可能令人生畏，但神经网络是捕获此类模式的绝佳工具。 > Neural Networks. Courtesy of Maged Abdelsalam 可以看到，研究人员试图模仿人脑的结构，这种结构在学习模式方面非常有效。 然而，人脑具有860亿个神经元和100万亿个突触。 希伯来的理论试图解释大脑的可塑性："神经元一起发射，相互连接。" 唐纳德·赫布（Donald Hebb）解释说，活动的持久性或重复性倾向于诱发持久的细胞变化。 例如，几年后驾驶成为某人的第二天性，因为在数百次激活后，涉及驾驶的路径或突触会变得更严格。 在游戏玩法中，研究人员使用具有足够延展性的NN，以了解状态空间中的所有不同模式。 同时，这些NN足够深（就层而言），以了解状态空间中转换之间的所有细微差异。 RL永远改变了视频游戏的玩法 在2010年代初期，一家以DeepMind命名的伦敦创业公司雇用RL来玩1980年代的Atari游戏，例如Alien，Breakout和Pong。 这种"实用"的应用程序使大多数研究界感到惊讶，因为RL仅一次被视为一项学术工作。 这家初创公司的估值为十亿美元，并成为Google的一部分。 DeepMind的研究人员随后在热门杂志《自然》上发表了一篇论文，内容涉及计算机Atari游戏中的人为控制。 在我们前面描述的三个问题中，电子游戏遭受状态空间表示和密集计算的困扰。 为了克服状态表示问题，研究人员将视频帧中的原始像素原样传递给了AI代理。 为了克服计算问题，研究人员利用了一些技巧。 他们通过应用下采样技术和跳帧机制减少了枚举的状态空间。 当涉及到神经网络时，他们跳过了超参数调整。 用非技术术语来说，他们使用的是神经网络，而不是最佳的神经网络。 > Atari games results. Source: DeepMind DQN Nature Paper 棋盘游戏也有相当大的成功份额 对棋盘游戏玩法的迷恋并不是吸引人的迷幻游戏。 不同的棋盘游戏具有各种影响其状态空间和计算可处理性的内在属性。 尽管计算机能够在1960年代的跳棋和1990年代的国际象棋等游戏中击败人类，但"中国围棋"似乎毫不动摇，但研究人员认为赢得"围棋"是AI的圣杯。 > Shogi. Source: Wikimedia Common 伦敦大学学院教授，DeepMind RL负责人David Silver一直是游戏的狂热粉丝。 从剑桥大学毕业后，他与人共同创立了一家视频游戏公司。 然后，他返回学术界并获得博士学位。 在Richard Sutton的监督下进行游戏。 2016年，Silver与Aja Huang一起为DeepMind工作时，创建了AI代理" Alpha Go"，从而有机会与世界卫冕人类冠军对抗。 1亿人在观看比赛，写了3万篇有关该主题的文章； 希尔弗对他的创作充满信心。 AlphaGo以4比1赢得比赛，这一胜利引发了人们对RL的另一波兴奋。 对这样的AI代理人的炒作只是合适的。 它获得了有关将人类带走数千年的游戏的知识。 在我们上面描述的游戏性问题中，玩Go的AI代理遭受了计算问题和奖励架构问题。 这次，研究人员仅使用蒙特卡罗树搜索（MCTS）枚举了状态空间中最可能的子集，从而减少了对计算的苛刻要求。 研究人员还利用带有大量TPU的分布式计算，这些TPU是专门为训练NN而定制的硬件。 为了克服奖励架构问题，AlphaGo既利用了基于MCTS的基于模型的学习，又利用了基于NN的无模型的学习。 无模型部分代表主体的直觉，而基于模型的部分代表长期的思维。 Alpha Zero和学习所有完美的信息游戏 银子并没有就此停止； 然后，他创建了另一个特工Alpha Zero，这是一个更强大的特工，能够下棋，将棋（Shoji）和围棋。 Alpha Zero比任何其他前辈都更积极地利用"自我比赛"，即，它只是通过多次与自己比赛而不是研究职业球员的比赛来教自己如何比赛。 为了测试AlphaZero的出色程度，它必须在每场比赛中与计算机冠军一较高下。 它击败了Stockfish，在最近的十个世界计算机国际象棋锦标赛中，他赢得了六届冠军，是的，这是一个冠军。 在将棋中，它击败了顶级将棋节目Elmo。 当AlphaZero和AlphaGo正面交锋时，AlphaZero歼灭了AlphaGo 100-0。 区别很简单：AlphaGo接受过人类玩游戏的培训，而AlphaZero只是自学了如何玩。 人类的知识似乎伤害了AI特工，再次证实了萨顿的论点。 AlphaZero能够掌握三种不同的游戏，这意味着它的统治地位将扩展到任何其他完美的信息游戏，其中有关该游戏的所有信息可供该游戏的所有参与者使用。 国际象棋，将棋和围棋是完美的信息游戏，与扑克或Hanabi不同，后者的对手看不到对方的手。 结论 人工智能的潜力是无法估量的，并且只有通过对神经科学的更好理解和计算机科学的扩展，才能继续蓬勃发展。 尽管我们在本文中描述了游戏性问题，但它本身并不是目的。 除了激励人们之外，游戏玩法还提供了一个完善的测试环境来开发AI模型，这通常是因为它们是难题。 这些相同的模型被用于现实生活中，例如我们所说的识别癌症和自动驾驶汽车。 而这仅仅是个开始，他们知道这些模型将来将适用于哪些真正的潜力或不同的应用程序！ 最初发布在Nash项目上。 (本文翻译自Shehab Yasser的文章《A Brief History Of Reinforcement Learning In Game Play》，参考： https://medium.com/swlh/a-brief-history-of-reinforcement-learning-in-game-play-d0861b2b74ef) 作者：闻数起舞 原地址：https://www.toutiao.com/a6831981856699712013/ |