【代码札记】基于Chrome内置游戏Dino的基因算法实现

本项目受启发于Code Bullet的Youtube视频「AI学习如何玩Chrome内置的游戏Dino || 你能打败它吗？？」（代码参见视频下方简介）。本项目Github地址：https://github.com/hurui200320/Genetic-Algorithm-with-Chrome-dino 。

简介

最近刷Youtube看到了Code Bullet的一系列关于AI学习某一动作的视频，了解到了Genetic algorithm，我感觉它的翻译方式有很多种，我就按照字面意思取了，无伤大雅。关于基因算法，Code Bullet还做过教学视频(Youtube)，其第二期还使用了一个实例展现对应的代码该如何编写。我觉得这个视频挺简单易懂的，感兴趣的各位欢迎移步去看看。

这个项目是看到了如开头说的视频而受到了启发。视频中的代码我也下载下来看过了，感觉有些地方比较复杂（我太菜了没能理解他那样实现的目的），因此我在这些地方做出了一些简化（就是单纯的懒以及玄学上的感觉这样的简化是可行的）。

实现

游戏

我按照Chrome原版的Dino（Chrome用户可以通过访问 chrome://dino 来尝试游戏。按空格可以开始游戏以及操作游戏角色跳跃，方向键下键可以控制游戏角色下蹲，游戏的目标是躲避障碍物）使用Java8和Processing3复刻了一个（我感觉）差不多的游戏，只是游戏比较简陋，截图如下：

我参照Code Bullet的实现选定了一些参数：例如角色的高度、宽度，角色在下蹲时的宽度、高度，以及各类障碍物的尺寸及位置。其余参数则是通过经验和多次尝试得到的。这些参数并不意味着完美，只是我觉得差不多了。

物理系统

我这里用的是高中物理，不考虑空气阻力，重力加速度在各高度上保持不变。每一帧代表的时间间隔由Game类的deltaT决定，地面和障碍物的行进速度一致，由基速（Game类的groundBaseSpeed字段）和补正（Game类的speedFix）相加得到。每一帧行进的距离由前述二者相乘得到。速度补正在每一帧结束后增加0.002，上限是1.3倍基速。

游戏角色的跳跃是通过赋予初速度实现的，大小跳跃分别赋予角色不同的初速度即可。两个初速度在游戏过程中保持不变。

游戏机制

游戏角色

游戏角色直接使用黑色方块代替，我懒得整贴图了。游戏角色由Dino类定义，每个Dino对象可以通过调用bigJump()、smallJump()和setDown(status)（status为布尔型，true表示下蹲，false表示不下蹲）三个函数来操作其动作。Dino对象的move()方法将在游戏的每一帧被调用以使角色的位置被更新。

障碍物

障碍物分两种：仙人掌（Obstacle类）和鸟（Bird类）。这里我使用红色方块代替，原因同前述。其move()方法将被游戏的每一帧被调用，用以更新障碍物的位置。而collided(dino)方法会在被调用时判断该障碍物是否与给定的dino碰撞，若碰撞则返回true，否则返回false。判断碰撞的算法借鉴了Code Bullet的算法。

基因算法

玩家

玩家由Player类定义，每一个玩家持有一个Dino类，代表他们所操作的游戏角色。同时还有一个Brain类对象，当玩家需要决策时，其think(obstacles)方法被调用，brain对象将根据当前的障碍物做出计算，随后玩家依据此进行操作。每次玩家位置更新后将对玩家与障碍物判断是否碰撞，若碰撞则判定当前玩家的游戏结束，后面不再计算该玩家的更新。

神经网络（Brain类）

神经网络是含有一个隐藏层的MLP（多层感知器）。10个输入（第一个要遇到的障碍物的横纵坐标位置、宽高；游戏速度；游戏角色的高度；第二个要遇到的障碍物得横纵坐标、宽高） + 1个偏置，3个输出（是否跳跃；大跳或小跳；是否下蹲），隐藏层有五个神经元（无偏置）。所有神经元（Node类）的激活函数都是Sigmoid。在第一世代时需要通过调用randomWeight()方法随机化权重，其中调用的nextDouble()可以提供$\pm10$以内的双精度浮点随机数。需要决策时，player先调用brain.lookAround(obstacles, dino)方法，获取玩家与屏幕中障碍物的状态并作为神经网络的输入，随后调用brain.computeAction()计算当前的操作。神经网络的输出以大于0.8为真，小于0.8为假，返回对应输出的布尔型以供player做出操作决策。

世代迭代

当所有玩家都判定为游戏结束时（game.isGameOver()返回true），该世代结束。程序先调用game.naturalSelection()进行自然选择，产生下一代。程序将首先找到分数最高的玩家并计算所有玩家的分数总和。其中最高分的玩家直接克隆至下一世代，各世代之前玩家数量保持稳定不变，克隆后空缺位置将调用game.selectParent()按照分数比例选择亲代进行克隆，分数越高者被选作亲代克隆至下一世代的几率越高¹。最后调用game.mutateAndPrepareNextGeneration(rate)方法，对所有玩家神经网络的所有权重和1个偏置进行遍历，每个权重以给定的几率rate进行突变。若突变，则该权重被随机化。同时该方法还重置所有障碍物和速度，世代数（gen）自加1。

原理

程序模拟生物的进化：第一世代随机产生一定数量的玩家，在游戏中操作。由于开始每个玩家的神经网络权重随机的，所以其行为也不可预见，有可能上来就全灭，也可能会有些由于运气跳过了一些障碍。每一世代结束后程序都会挑选表现最好的玩家，将他们保留到下一世代，并产生一定数量的变异，因此通过不断地变异与选择，世代中的玩家总体上朝向熟练的方向进化。最终当一个世代内的玩家可以一直将游戏进行下去而不撞到障碍物时，可以认为MLP收敛，AI已经学会了如何玩dino游戏了。

现实

上面的原理是这么说，可是在实际操作中因为涉及到随机，因此收敛还是挺看脸的一件事。我第一次尝试的时候在23世代就收敛了。而随后又试了几次，80多世代还没收敛。而今天写文章的时候尝试，第一次在30世代收敛，第二次70多世代还未收敛，第三次在53世代收敛。因此可以认为如果程序在20多世代时最好的分数还在个位数时，可以考虑重开一盘了。如果60世代以后还没有收敛，我觉得就不用等了。因为等他进化也是挺好费时间的。通过调整一些参数或许可以加快收敛，例如增加变异几率，有更大可能产生出能正确操作的玩家，但也有可能导致上一世代中优秀的个体变异后被淘汰。而总体上最有效的还是加快世代迭代的时间，但是计算能力有限，我将每次玩家的更新独立到线程中，玩家可以多线程的并行计算神经网络结果（sigmoid函数中使用到了指数运算，非常耗时），但由于我使用的是笔记本，因此并没有对这些想法加以测试。但是欢迎各位修改源码并实测一下这些改进，看看效果。

↑如图收敛的两次世代不同，其收敛的结果也不同。30世代收敛的会跳会蹲，53世代的那个只会跳过障碍。

-全文完-

---

【代码札记】基于Chrome内置游戏Dino的基因算法实现 由 天空 Blond 采用 知识共享 署名 - 非商业性使用 - 相同方式共享 4.0 国际 许可协议进行许可。
本许可协议授权之外的使用权限可以从 https://skyblond.info/about.html 处获得。