吃豆游戏中的遗传算法

作者：吕默威

本文故事来源：《卓老板聊科技》第二季第53期《用计算机模拟进化》

世界上第一位计算机科学专业的博士叫约翰·霍兰德，估计知道他的人不多，他是1959年在密歇根大学拿到的博士学位，全世界第一个正式的计算机系也是在密歇根大学建立的。他的导师是计算机工程师巴克斯，你看第一个计算机博士的导师却不是计算机博士，巴克斯曾经协助冯·诺依曼建造EDVAC，这台计算机是世界上第一台计算机ENIAC的改进版。

霍兰德被称为“遗传算法之父”，是最早研究复杂理论（Complexity）和非线性理论的科学家。这多亏了他手中有计算能力超强的工具，在他之前很多好想法都由于计算量过大被卡住了，因为像EDVAC和ENIAC最初设计的目的都是给国防部用来计算导弹弹道的。为什么霍兰德能在那个年代，这么早就能拿到计算机，用来研究非军事目的呢，别忘了，他的导师巴克斯就是搭建计算机EDVAC的，霍兰德理所当然的就近水楼台先得月了。

当时霍兰德研究的是进化策略，他的这篇开山之作叫《自然与人工系统中的适应》，霍兰德所研究的内容，可以简单的描述为吃豆游戏。

吃豆游戏的规则是这样的，有一个10*10的格子空间，边界是墙，在格子里随机撒下50颗豆子，然后随机位置放一个吃豆人，这个吃豆人的视野和活动能力都是有限的，他只能看到自己当前格子和自己前后左右4个格子的情况，而对于每一个格子有三种情况——空的、有豆子、墙（边界也可以看成是一排格子）。

吃豆人能做的动作有7种：上移、下移、左移、右移、不动、随机移动、吃豆。

然后规定一下吃豆人的收益和损失，吃到豆得10分，移动位置分数不变，执行吃豆的动作，但是格子里没有豆子，减1分，撞墙了减5分。限制吃豆人总共能做200次动作。理论上最高得分就是在不扣分的情况下把豆子全部吃掉，有50个豆子，最高得分就是500分。

吃豆人能观察到的，是前后左右和自己所在格子的状态。所以一共是5个格，每个格子有三种状态，总的状态数就是3的5次方，就是243种状态，然后在除去一些地图中不存在的状态（如三面是墙，左右是墙），最后总共剩下128种状态。

吃豆人根据当前状态，决定采取什么样的动作。用0-6，分别代表上移、下移、左移、右移、不动、随机移动、吃豆。这样就可以用一个128列的表格来保存当前状态和吃豆人动作之间的对应关系，这128列的表格就是这个吃豆人的生存策略。所以每个吃豆人，下一步应该怎么行动，按照当前状态查一下这个表格就可以知道了。

这个研究的目的就是要找到这个吃豆生存游戏中得分最高的吃豆策略是什么，这个策略就是指的这128列的表格，一共有多少种呢，每一位可以取0-6七个数，所以总共的策略组合就有7¹²⁸种，如果用线性思维，把每个生成的策略组合都去试试看得分多少的话，把这些策略都执行完，也比整个宇宙的历史要长，所以这就是一个典型的计算量远远超过全球算力加和的计算任务。所以想要通过穷举法去计算，这个问题是无解的，但是遗传进化算法可以从另一个思路解决这个问题。

这个研究的实验步骤如下：

1. 随机生成200个策略，就是生成了200个采用不同策略吃豆的人；

2. 让每种策略都进行1000场吃豆挑战赛。每场比赛让吃豆人行动200次，在1000场挑战赛中，每场比赛的50个豆子都是随机撒下的。最后评估在这1000场挑战赛中，平均每走200步，得到的分数是多少；

3. 根据得分的高低从200个策略里随机选出2个策略，得分越高被选中的概率越高。然后用所选中的2个策略，生成出一个新的策略，新的策略的每一列有一半概率使用第一个策略的对应列，一半概率使用第二个策略的对应列。在生成新策略的过程中，会有小概率产生策略的变异；

4. 用第3步的方法不断生成新策略，直到生成了200个为止；

5. 返回第2步，用新生成的策略进行比赛，再按照分数生成再下一代的策略；

按照上面的方法循环1000次，就是生成1000代吃豆人。第一代吃豆人的策略是随机生成的，在大规模的高频的比赛中，他们按照自己的策略来执行行动，因为场次多频率高，所以得分可以反映出他持有的策略是否有竞争力。评分最高500分，对应着把所有的豆子都吃光，也没有白做功，也没有撞墙。实验引入了进化的行为，把每个吃豆人策略列表中的每条策略看成基因一样，重组生成下一代的过程有点像染色体的分裂和组合，第一代成绩较高的吃豆人，就有更高的几率留下后代，后代还遗传了上一代的策略。得分低的也有几率生成后代，只是没有得分高的概率高。在生成下一代的过程中，下一代的策略还有非常低的几率产生遗传变异，有的策略位会随机变成其他数。

在当时，这个实验就受限于计算机的性能，不过现在算起来就容易多了。大概用了3个小时，生成了1000代吃豆人。每一代最优评分的吃豆人评分情况如下：

每一代全部吃豆人平均评分情况如下：

可以看到第一代策略随机生成的吃豆人的分情况非常差，最高评分是-95分，最低是-300多。因为策略是随机生成的，就会总出现撞墙、没有豆子时吃豆的这种被扣分的情况。但是这种情况在第19代就有了本质上的改观，从第19代开始子代的平均得分就已经超过0了，此后得分逐渐上升，但上升的速度越来越缓慢，第48代开始超过100，第175代超过200，第604代超过300，从第650代之后，得分超过了400，最后在第1000代的时候，上升到了470。我们可以看出那些差的、不合理的策略，被淘汰的速度非常的快。这些有重大错误的策略，在最开始的迭代中，就被淘汰掉了，剩下的都是稍稍有些竞争力的策略。

如果我们人为去制定策略，怎么制定呢，最简单的就是：当前格子有豆子就吃，旁边格子有豆子就移过去，都没有就随机走一步，像这种策略实际评分为346分。

到第1000代，最好的策略平均得分是471分，这个策略很难像上面我们自己制定策略那样用几条规则总结描述出来，它大致也有一些规律可循，也能观察到，当前格子里有豆，它可能会吃，旁边格子有豆，会移过去，但是它又时不时的不按这个规则来，比如当前格子和挨着的好几个格子都有豆子，这时它并不是直接把当前格子里的豆子吃掉，而是先向其他方向移，直到移动到没有豆子的格子，才开始吃它旁边的豆。这种吃豆的方式描述起来就不太容易，但是比我们之前自己定义的策略会少走不少弯路。另外在一直没有豆的情况，它会去找墙，然后沿着墙走，然后发现内圈有豆子就吃。

虽然能看出一些规律，但是想用线性的几条规则去描述这个策略还是基本上办不到的。想要描述这个策略还是的靠那个128条规则，每一种状态做什么动作来逐条来描述。这就是一个复杂系统，我们很难通过简单的思辨来理解和总结。通过这个例子也可以明白，一个复杂系统中的最优解，你想描述它，其实它的所有的行为就是你描述他的方法，想通过约化和简化的方式描述他，这种方式是徒劳的。

怎么去证明这个策略显示出来的一些特点，比如当前格子有豆子不去吃，是不是真的在吃豆游戏中是有优势的呢？可以这样去做：把这个策略中当前格子里有豆子状态的动作都改成吃豆，然后进行实验，结果这个策略的评分从471分下降到了456分。所以从这一点说明进化出来的这些基因还是有自己的优势的，这种实验方法在科学研究中有个名字叫基因敲除法。

这个就是用计算机来模拟进化过程的研究，它逐渐掀起了进化论的主流观点的改变，这种遗传算法将突变式的进化用计算机模拟出来了。进化是一个复杂过程，通过计算机在算法上做简单规定就能模拟出来，而且还能在7¹²⁸的可能性中，短时间找出最优解，这也给研究算法的科学家提供了一个新的思路。用遗传算法进化出来的那个最优解，往往是人类思维无法理解的，它还往往照顾到很多思维的死角。今年年初战胜李世石的AlphaGo，用的是深度神经网络，也有研究算法的人提出，如果采用遗传算法的方式，也能设计出一套围棋对弈的策略，同样可以战胜人类。

本文来自网易实践者社区，经作者吕默威授权发布