用机器学习玩转FlappyBird

2019-09-06 Machine Learning

  两年前刚毕业的时候由于兴趣爱好就接触到了一些机器学习的内容，今天想到写这么一篇文章的主要原因是由于公司安排昨天去接送了一位做数据挖掘方向的教授，在接送途中跟她聊了一些有关数据挖掘与机器学习方面的内容并且从中受益，加上自己的部分兴趣于是就想产出一篇文章来说一下自己对于这块内容的理解，由于专业性的问题其中说法如果有误还请指出。

本篇博客相关代码托管于**github**
游戏引擎与AI基于Vuejs+TypeScript+Tensorflow.js实现，点此在线预览
如果这个项目激起了你的兴趣，欢迎分享与Star

概述

本篇文章我将从三个方面去阐述我个人的机器学习经历及理解，也算是我这部分知识的一个成长经历。

  1. 初探机器学习：这里主要是描述一下我毕业不久后接触的一个Github仓库FlappyLearning，这个仓库用了一个很形象的例子来描述机器学习的作用，这个例子解决了我的一个疑惑，机器如何针对一个问题做出决策？
  2. 反向传播与遗传算法：这两个算法很具有代表性，机器决策的核心是一个函数模型，问题的决策和模型的出参与阈值有关，所以机器学习的目的就是构造一个适用于问题的函数以及合适的分类阈值，而构造的过程可以用这两个算法来实现
  3. 基于Tensorflow玩转FlappyBird：Tensorflow是谷歌的一个机器学习开源库，能够很方便的构造一个神经网络，现在在js中也有实现版本，学习的途径也很多，这次我将基于Tensorflow来改造FlappyLearning这个仓库，顺便让自己学习Tensorflow的途中不那么枯燥

初探机器学习

对于机器学习的概念解释我本人不是解释的很清楚，但是我可以从应用场景方面来分析一下机器学习在什么场景下会适用，机器学习现有的应用场景主要包括各种识别、推荐、广告、客服，这些场景我认为有以下几个共性

  1. 不容易用统一的逻辑归纳：比如人脸的特征值比对，我们很难编写统一的逻辑代码来确定怎样的两组特征值才算是比对成功
  2. 根据历史数据给出预测：比如网易云音乐的每日推荐，当你用得越久收藏/喜欢点击的越多，它推荐给和你口味歌曲的占比就越大，但是没有历史数据就会不准确。
  3. 都属于分类或聚类问题：在这里解释一下什么是分类与聚类，并给出相应的例子
  • 分类：通过学习得到一个目标函数f，把每个属性集x映射到一个预先定义的类标号y中，比如根据人脸特征值来判断此次比对是属于比对成功/失败的哪种类别。
  • 聚类：事先并不知道任何样本的类别标号，希望通过某种算法来把一组未知类别的样本划分成若干类别，比如广告投放业务中将用户群体分类然后分别投放不同的广告。

接下来我们利用FlappyLearning来了解一下机器是怎么通过自我学习做出决策的，首先我们来介绍一下这个游戏

  • Score：当前游戏得分
  • Max Score：代表游戏最高得分
  • Generation：代表鸟的代数，当50只鸟死完了就会通过遗传算法的优胜劣汰原则经过遗传变异生成新的五十只鸟参加游戏
  • Alive：代表当前游戏下鸟的存活量以及总数量
  • x1/x2…按钮：代表游戏运行速率，可以调快一点大概经过10-20代机器便能学会此游戏

机器如何通过自我学习来通关游戏的，我将从以下两个方面分析一下：

  1. 机器是如何来决策游戏走向的？
  2. 如何获得一个合适的决策函数？

机器是如何来决策游戏走向的

我们上面讲到机器学习大部分可以分为分类与聚类两类问题，我们先来了解一下FlappyBird这个游戏的玩法，玩家需要根据小鸟所处的当前位置来控制小鸟的飞行（跳跃），从而使得小鸟不会撞到障碍物。

现在我们来换个更接机器地气的说法，假设每个小鸟都有一个飞行判断函数y=f(x1,x2…)，其中x1,x2…都是函数的输入参数，y是函数的输出参数，我们要根据结果y来决策当前环境是否需要跳跃，如果**f(x1,x2…)**这个函数适合于这个问题，那么小鸟就能根据这个函数完美的通关游戏。

如果按照上述方式去理解的话，机器学习的目的是什么就显而易见了，就是为了寻找一个适合于特定场景的决策函数，起到高准确率的预测效果，拿FlappyBird这个游戏举例，这个游戏的输入可以是以下很多种并且不限于此

  • 一帧图片
  • 小鸟距离的障碍物的垂直距离
  • 小鸟距离障碍物的水平距离

为什么要专门拿输入这个概念来说？我们来模拟人类玩这个游戏，人类通过眼睛来获取小鸟的位置信息（其实在关注小鸟和障碍物的相对距离），来决策小鸟是否需要跳跃，我们把这个过程抽象成一个函数，那么你眼睛获取的位置信息就是输入，你的决策即是输出，而我要在这里说的是你获取的这个位置信息并不是最好的输入，设想一下，如果屏幕上打印了你现在距离障碍物的水平和垂直距离并且告诉了你每次跳跃将会相对移动多少距离，你是不是能更加容易的掌握这个游戏。

同理，一个更好更合理更有关联性的输入对于机器来说也能降低它的学习成本，假如你只给机器一个小鸟无关与障碍物的垂直距离作为输入参数，那么无论你用什么算法，他都永远无法学会玩这个游戏。在FlappyLearning这个仓库中，作者给予机器的输入信息为小鸟距离的障碍物的垂直距离与小鸟距离障碍物的水平距离。

讲到这里其实已经能够解答第一个问题了，机器其实是通过一个决策函数来代入一组输入然后根据输出结果关联到游戏的具体操作。如果你已经看到了这里你可以发现我的文章中将部分机器行为类比了人类行为，同样在后文中我也会使用类比这个思想去更通俗易懂的讲述其他问题。

如何获得一个合适的决策函数

在FlappyLearning这个仓库中作者是使用了遗传算法去解决决策函数的构造问题，那么我们就要思考作者为什么选择遗传算法？遗传算法适用的场景有什么？如何在程序中使用遗传算法？在这部分我将围绕着这三个问题来解释。

  1. 为什么选择遗传算法

遗传算法属于一种随机搜索算法，这种算法很多时候不会给出一个“最优解”，而是给出一些较为接近的次优解，从中矮子里面拔将军。Flappy这个游戏从刚开始的一无所有到后面的随便通关依赖的就是随机搜索，先随机参数得到一个函数模型再不断的迭代得到一个次优解参与游戏。

其实在计算机世界中的很多理论都是根据现实生活中的理论映射来的，我们都知道达尔文进化论有一个核心思想叫做物竞天择适者生存，生物在不断进化的路途中总是会淘汰掉不适合的基因，所以最终留下的都是能够在这个世界正常生存下去的基因，如果我们将FlappyBird这个游戏当作一个世界，那么里面的小鸟不断的更新换代进化，保留下优质基因（游戏得分高的），最后总会有一批基因能够适应这个世界（通关这个游戏）。

  1. 遗传算法适用的场景
  • 调度类问题，车间工程流程、飞机航线等等。工程、航行中所需要的资源消耗、时间等等权值看做“染色体”，几种染色体排列组合，最终选择其中的较优方案
  • 辅助神经网络调节参数，FlappyLearning其实就是在做自动参数调节
  • 游戏场景，比如我玩的游戏Dota2这种推塔生存类游戏，每局游戏后AI都可以总结自己不足的地方进行自我进化从而不断增强
  1. 遗传算法的运行流程
  • 在知道了遗传算法的概念之后，它的运作流程概括来说应该是这样的：
    • 生成一批随机的基因并加入游戏
    • 保留游戏得分高的优质基因，淘汰游戏得分低的劣质基因，通关杂交变异生成部分新的基因，重复此流程
    • 经过不断的迭代进化的基因能够基本适应游戏，达到**通关（不死）**的效果

反向传播算法

简介

反向传播要求有对每个输入值期望得到的已知输出，来计算损失函数的梯度，通常被认为是一种监督式学习方法，主要用于以下几个方面

  1. 函数逼近：用输入向量和相应的输出向量训练一个网络逼近一个函数
  2. 模式识别：用一个待定的输出向量将它与输入向量联系起来
  3. 分类：把输入向量所定义的合适方式进行分类

如何运用于FlappyBirdAI

反向传播算法有一大特性就是需要有预期的输入输出集合，那我们就要思考如何给FlappyBirdAI提供一个训练数据集合，最简单的方式就是让玩家玩游戏从而生产训练数据，大体思路如下

这里有一个需要注意的问题，数据数据即函数模型的输入及预测项定义成什么？

模型输入项

首先我们要明白输入项需要有什么样的特性？

前面我们讲到，与决策结果关联性越强的输入训练效果越好，还类比了人去玩游戏会注意哪些数据，所以在这里我们就采用人类玩游戏所观测的数据作为AI的训练数据，这里我设计了以下几个输入

  • 小鸟当前的高度值
  • 下一个障碍物的高度值
  • 小鸟距离下一个障碍物的水平距离

模型预测项

模型的预测输出项将作为小鸟的决策依据，我们需要设计一个可以较好判断决策的输出，举个两种输出设计作为例子

  • 方案1：使用单项数字作为输出，并定义1代表跳跃，0代表保持不变（即下降）
  • 方案2：使用数组作为输出，数组第一项代表跳跃概率，第二项代表保持不变概率

我们来分析以下这两项输出的优劣，首先我们知道训练出来的函数模型只能给出一个估计值（即不会绝对是0/1）

假设我们使用方案1作为输出结构，那根据这个结果我们怎么判断现在小鸟是否需要跳跃呢？< 0.5？那么0.5这个数字又是怎么来的，没有任何依据

假设我们使用方案2作为输出结构，那么小鸟如何判断是否需要跳跃呢？result[0] > result[1]即可，因此在这里我使用方案2作为输出结构

基于反向传播算法设计FlappyBirdAI

流程设计

  1. 玩家通过玩游戏生成游戏数据，这里将采集游戏在每个时间点的小鸟高度、障碍物高度、小鸟距下一个障碍物的水平距离作为输入，以这个时间点玩家的操作作为输出
  2. 将游戏数据统一存储到浏览器的LocalStorage统一管理
  3. AI利用玩家产生的游戏数据基于反向传播算法建立决策模型
  4. AI进行游戏测试

界面设计

界面左右分成两块内容，左侧为游戏界面，右侧为控制台界面，训练模型列表右侧有一个❓图标，点击可打开教学提示，下面描述一下如何训练一个FlappyBirdAI参与游戏

  1. 点击创建一个新的模型完成必要信息填写，这里主要是关联神经网络以及训练迭代次数的一些配置
  2. 在新的模型行中点击教学（或按空格）开始游戏，此时左侧游戏开始，玩家按J跳跃，游戏进行过程中左侧模型训练框中的数据量会不断增加，这些数据将持久化在LocalStorage中并作为AI的训练数据
  3. 当玩家认为数据量达到预期时（建议大于3000）可终止游戏，点击训练按钮开始训练决策函数模型，此时右侧会弹出训练进度图表
  4. 训练完成后游戏将由AI接手自动开始，右侧行会记录AI的最高得分
  5. 模型训练完成，玩家可以点击数据预测使用玩家生成的游戏数据样本交与AI进行预测分析，预测完成后将给出AI预测结果与玩家输入预期不符的数据列表

模型训练效果展示

这里我人工玩了3万左右的数据量，相当于过了2500个障碍物，小鸟的最高得分是2400，具体运行效果如下

开发计划

  • [X] 参照FlappyLearning完成游戏引擎开发
  • [X] 完成用户游戏数据采集器与其持久化模块
  • [X] 引入Tensorflow.js基于游戏数据训练决策模型并使用其参与游戏
  • [X] 完成数据预测模块，便于对模型预测结果进行分析
  • [ ] 分析AI参与游戏的能力，优化AI使其能够更好的适应游戏

机器训练过程中遇到的问题

可能采集到错误数据

游戏中机器训练的数据由玩家不断产生，也就是由玩家重复一局又一局的游戏来产生，那么玩家在游戏终止（小鸟死亡）前的一部分数据其实是属于错误操作数据，这类数据不应该交与机器去学习

解决方案 丢弃游戏结束前的部分数据
在这里我维护了一个指定了大小的队列，负责缓存游戏最新的部分数据，脱离缓存的数据直接进入持久化模块，当游戏结束时还在缓存队列中的数据将被丢弃

数据样本分布不均匀

在上述设计中游戏数据会基于运行的每一个时刻点来采集，这将导致数据集中操纵跳跃的数据会远小于无操作的数据，实际运行中也证明了这一点，跳跃操作数据大概占总数据集的3%，如此不均匀的数据集加入训练将使得决策模型出现一边倒的情况，即小鸟一直不跳跃，处理样本不平衡问题，主要有3种策略：从数据角度、从算法层面和模型评价层面，这边给出以下几种处理方案

方案一 扩大数据集
当遇到类别不均衡问题时，首先应该想到，是否可能再增加数据，使得样本平衡，显然在我们这个场景中是不可能扩大了

方案二 重采样

  • 上采样 通过增加稀有类训练样本数的方法，降低不平衡程度，一般用于数据集比较少的情况，重复的扩增样本中比例较小的那类数据达到样本平衡，此方法容易造成过拟合，而且会导致样本增大需要更多的计算资源
  • 下采样 通过舍弃部分大类样本的方法，降低不平衡程度，一般用于数据集比较多的情况，随机的丢弃样本中比例较大的那类数据达到样本平衡，此方法会不可避免地丢弃大部分多数类样本造成信息损失

方案三 使用Focal loss损失器
焦点损失函数Focal Loss被提出用于密集物体检测任务。它可以训练高精度的密集物体探测器，哪怕前景和背景之间比例为1:1000，在我们这个游戏中样本类别的数量比例大概是3:97，此损失函数是适用的
但是现有的资料中Focal Loss损失函数基于Python的实现代码较多，而基于JS的几乎没有（也许是我没找到），经过一段努力的理解后，我放弃了此方案

最终我采用了上采样的方案，因为下采样方案丢弃掉大部分样本后会导致小鸟训练结果非常不理想，于是我选择牺牲计算资源的方式来保证小鸟的训练智能性，当然如果能写出Focal loss损失器的js版本也许会是个更好的解决方案

参考资料

推荐阅读