耶鲁编程马拉松：用神经网络学习超级马里奥游戏

Joe Crozier 和我最近刚从YHack 回来，那是一个耶鲁大学举办的36小时编程马拉松，有1500人参加。这是我们连续第二年参加这个比赛，也是我们第二次成功进入前8 ！

我们的项目，“crAIg”，是一个自我学习算法，它会学习怎么玩红白机上的超级马里奥。一开始它对超级马里奥毫无了解，不知道它到底是什么、怎么玩、怎么才算赢；使用进化的神经网络算法（neuroevolution）慢慢建立起基础，最后它可以学会玩这个游戏。

在这个项目中，我将注意力放在了如何把crAIg的进化算法与项目融合的各种细节上，于是我发现我应该为此写一篇相对深度的博文。

crAIg的进化基于一种叫做“NEAT”的算法，它来自于一篇名为《运用增强拓扑使神经网络进化》（EvolvingNeural Networks through Augmented Topologies）的论文（文末附下载）。我以下的博文内容将谈到我是如何将这种算法融合到超级马里奥的项目中去的，希望我写得足够浅显易懂。

crAIg的大脑

在我们直接开始谈论算法之前，我打算先介绍一下crAIg的大脑的构成。在游戏中的任何时间，他的“大脑”都是由一群“神经元”和“突触”组成的，叫它们“节点”和“连接”也可以。在本质上，他的大脑是一幅有向图（directedgraph）。

上图是这个项目的第二部分，一个可以显示当前crAIg大脑状态（或者说他在“想”什么）的Node.js服务器。让我们快速了解一下这幅图的含义。

左边，你可以看到大片的正方形网格。这是游戏现在看上去的样子，或者说crAIg的“眼里”游戏现在的样子。他不知道网格中任何一个方块的意思，但他知道“空气”格子和“地面”格子在某些方面是不同的。每一个方块实际上就是一个输入神经元。

右边，你可以看到4个“输出神经元”，或者说crAIg可以按的4个按钮。你也可以看到一条线连接左图一个黑色格子和右图的“R”神经元，被标记成“1”。这是一个突触，当左边的输入神经元放电时，信号会沿着突触传导，告诉crAIg应该按“R”键。用这种方法，crAIg可以正确地行走。随着crAIg不断进化，更多的神经元和突触被创造出来了，最终他的大脑看上去会更像这种样子：

在这张图上有几件事我想指出来。首先，左边的绿色方块是一只板栗仔（goomba）。其次，你可以在非常低的位置看到一个标记为176的神经元，它被称为隐藏神经元，表示既不属于输入神经元也不属于输出神经元。随着crAIg不断进化，复杂度上升，隐藏神经元会出现在他的大脑中。你也可以看到，在他死掉的时候（马里奥被板栗仔碰到了），他正在尝试按“R”键和“B”键。

进化神经模型为何酷炫

当学习玩超级马里奥变成单纯地应用神经网络和进化神经模型，这个游戏在很大程度上就成为了一种展示这些自我进化的神经网络的方法。虽然crAIg只学习了如何玩简单的红白机游戏，但其中用到的算法可以被应用在机器人身上，为你打扫房间、在工厂劳作或者甚至是绘制出美丽的油画。

从crAIg可以窥探到一个机器不再需要被人编程来完成特定任务的未来，取而代之的是给机器设定指导原则，让它们从经验中自我学习。随着我们将越来越难的工作寄托在机器身上，想要通过硬编码（hardcode，译者注：指在软件实现上，把输出或输入的相关参数（例如：路径、输出的形式或格式）直接以常量的方式书写在源代码中，而非在运行时期由外界指定的设置、资源、数据或格式做出适当回应。来自维基百科）的方式编写任务程序就变得越来越不可能。我们需要更多的多功能机器为我们服务，而让神经网络自我进化就是往这个方向迈出了一步。

NEAT（增强拓扑的神经网络进化，NeuroEvolution ofAugmented Topologies）

如果你好奇于神经网络进化遇到的问题背后是怎样的历史，我非常推荐你读一下这个算法的论文（就是前面提到的那一篇）。论文第一部分论述了实现神经网络进化的许多方法和它们各自的优点。

NEAT是一种基因算法，它测试了crAIg大脑的每一次迭代运算，然后从中遴选出质量高的、繁衍它们的后代，与自然界中物种的进化非常相似。其层级是这样的：

突触/神经元：构建出crAIg大脑的组成部分

基因组：crAIg大脑的一次迭代，本质上是一堆神经元和突触。

物种：一堆基因组

世代：NEAT算法的一次迭代。这被不断地重复，让crAIg得到进化。

1. 计算适应度（fitness）

每一个世代中，第一步是计算之前世代里每个基因组各自的适应度。这包括了在每个基因组上运行同样的函数，以此让NEAT知道每个基因组是优是劣。对于crAIg来说，这意味着用某个基因组，或者说“大脑”，玩一遍超级马里奥的一个关卡。结束游戏以后，我们用这个公式来计算这个基因组的适应度：

一旦每个基因组的适应度都计算完成，我们就可以进入到算法的下一个阶段了。

2. 计算调整后的适应度（adjusted fitness）

这一部分的算法可能是最不直观的了。需要调整适应度数值是为了防止种群变得过于庞大。当一个物种的种群大小上升时，个体（基因组）的“调整后适应度”随之下降，迫使基因多样化（diversify）。

要恰当地将这个算法融入我们的代码中是相对高强度的工作，所以在crAIg这个项目中我们把它简化成了下面这个样子：

重要的事情是，现在每一个基因组都各自有一个调整后适应度数值了。

3. 适者生存

这里就是自然选择的部分！“适者生存”指的是有多少基因组可以存活到下一个世代，以及种群中会诞生多少新的后代。那篇论文没有直接写出这一部分的算法，所以这些算法大部分是通过不断试错得到的。

第一步是决定有多少个体（基因组）将要死亡，来为新生儿腾出空间。这依据整个物种的调整后适应度决定：调整后适应度越高，这个世代死亡的个体也就越多。

第二步是决定种群中应该诞生多少新生儿。这同样也是由整个物种的调整后适应度决定的。

这两部分完成以后，种群中就将有确定数量的基因组死去，并产生了确定数量的“新生儿配额”——也就是存活基因组数量与种群大小的差值。

4. 灭绝

这一部分算法实现了让一些物种被淘汰掉。有时候一个物种会走上完全错误的进化道路，于是就没有必要再留着他们继续进化了。这部分算法的逻辑非常简单：如果一个物种处在了整个世代所有物种的最后百分之X的位置，它就被标上了需要被淘汰的记号；如果一个物种连续Y个世代都被打上这个记号，那么这个物种里的所有基因组都会被消灭。

5. 交配的季节

现在来到了基因算法最有趣的部分！每个物种中都有了一定数量的基因组以及一定数量等待新生儿填补的空位。现在这些空位就要被补上了。

每个空位都需要被填补，可以通过两种方式：“无性”繁殖或者“有性”繁殖。换句话说，新生儿可以通过种群中单个基因组变异或是两个基因组融合的方式产生。在我讨论“融合”两个基因组的过程之前，我先来讨论一下变异。

变异

在NEAT中，对于一个基因组而言存在3种变异，如下所示：

(1) 突触权重

这包括了将一个基因组中所有突出的权重重新做一次分布。这可以是彻底完全的重新分布，也可以是仅仅是“扰动”（perturbed），也就是说轻微的改变。

(2) 增加突触

增加一个突触意味着，找到两个之前不相连的节点，然后用突触把它们相连。这个新突触将被赋予一个随机的权重。

(3) 增加节点

这是几种变异中最复杂（tricky）的一种。当你加入一个新节点时，你需要将现存的1个突触变成2个——在原本的两个神经元（N1，N2）之间加入一个新的神经元（N3），建立起N1与N3、N2与N3之间的突触连接。原本这个突触的权重被传递给两个新突触中的第二个，而第一个突触则获得1的权重。有一个重要的地方需要注意，原先的突触（图中红色的部分）并没有被删除，而只是被“停用”（disabled）了。这个意思是，它仍然存在于基因组中，但被标记为“不活跃”（inactive）。

当突触增加发生以后——无论通过增加节点的变异、还是通过增加突触的变异——这个新增加的突触会被标记上一个独特的“id”，称为“历史标记”，在交叉（交配）算法中需要使用到这个标记。

交叉算法

两个基因组“交配”来产生后代的过程，需要依照NEAT中一个详细描述的算法。这个算法背后的直觉性理解是，我们将一对普通的父代配对（别忘了，我们保留过它们的“历史标记”），接着拿出那些无法匹配的变异点，将它们搅和在一起（mix），匹配完成以后就创造出了子代。一旦通过这种方式造出了一个子代，它就已经经历过以上那些变异过程了。我不会太详细地解说这种算法，但如果你很好奇，那么你可以在这篇论文的Section3.2找到更详细的解释，或者你可以看我使用的代码（https://github.com/joenot443/crAIg/blob/master/NEAT/matingSeason.lua#L41）。

6. 重组物种

一旦每个物种中的新生儿都被创造完成以后，我们终于可以开始基因算法的最后一个步骤：重组物种。从本质上来说，我们先从每个物种中都选出一个“候选基因组”（candidategenome）。这个基因组现在是这个物种的代表。所有没有被选上的基因组们都被放进一个通用池（genericpool）中，然后重新规划它们的分组。重组依赖于一个称为“兼容差距公式”（compatibilitydistance equation）的公式：

这个公式确定了任意两个给定基因组有多相似（或者不相似）。我不会深入解释这个公式的原理，因为它在论文的Section3.3以及我们的代码中（https://github.com/joenot443/crAIg/blob/master/NEAT/util/calculateCompatibilityDistance.lua）已经被解释得相当好了。

如果一个基因组与任何一个候选基因组都有太大的区别，它会被立为另一个独立物种。通过这个过程，所有在通用池中的基因组都被重新归类到一个物种中。

一旦这个过程完成，新一代就搞定了，于是我们就开始着手重新计算其中每一个基因组的适应度了。

感想

虽然创造crAIg意味着在YHack比赛中只能有很少的睡眠时间，这是非常值得的，因为以下这些原因:

首先，NEAT算法是一个很复杂的算法。学习如何将一个复杂的算法融合到自己的算法中、同时又要保持自己不在它的复杂中迷失，这对于代码整洁性是一次很好的练习，虽然因为编程马拉松的原因我们在时间方面压力很大。

创造一个大部分基于一篇论文的算法，与创造一个有示范代码的算法不同，这也是一件非常有趣的事情。通常这意味着仔细查看论文中的用词，以此决定我在代码中是应该用“>”还是“>=”之类的事情。

这个项目中最困难的部分是，当我在编程的时候，我不能测试它。本质上所有的代码都是我在毫无测试的情况下编写的，然后当编写完成以后才能够测试和调试。这是有原因的：一部分是因为编程马拉松的时间限制，一部分是因为这个算法作为一个整体有许多互相串联的部分，意味着它们都需要做好准备以后我才能对代码进行测试。

整体来说，我和Joe能够在短短36小时内应对住压力、从零开始创造一个如此深度和复杂的项目，我为这件事感到高兴和自豪。我们不仅享受了这场比赛、对名次也很开心，我们也很高兴能够成功教会crAIg一些酷炫的技能，比如在第一关中跳过第二根水管：