这个《精粹7》里面一个AI设计的例子，方式是用行为克隆创建代理。《精粹7》上的描述实在是太粗略，很多东西都没提及。花了一星期的闲碎时间去看这个例子，感觉挺有收获的，整理了一下学习心得，希望能给跟我一样的菜鸟们带来一点帮助。这个例子代码不多，但是水挺深的。涉及了lua, 仿函数，决策树，信息论, 大堆循环递归等情况。 

这个DEMO实现了一个飞机对战射击小游戏，电脑控制那个飞机会学习你的行为进行模仿。

项目运行

首先，先把项目跑起来再说。我的IDE是VS2008

1. 配置好openGL和 lua环境。这里不细说了，请参考网上资料

2. 配置AI。打开项目工程，设置AIShoote为启动项，在AIShooter工程---属性---配置属性---调试---命令参数中填上 agent.lua。(这个是默认的决策树的脚本),当然了这个文件要放置在你的项目工程里。

3. 编译，运行。控制你的飞机跟对手打一架吧，经过数分钟的搏斗，你终于战胜了机器人。关掉窗口，后台会生成一个数据统计表叫training_data_xxx.dat文件。这个东东是用来后面生成决策树脚本用的。

4. 现在开始进行生成决策树，这课所谓的树就存放一个lua文件中。设置Learn为启动项, 在Learn工程---属性---配置属性---调试---命令参数中填上:
-s 1 training_data_xxx.dat 2.lua, 说明： -s 是跳过次数， dat文件是上一步骤产出的数据，2.lua是lua文件名。设置好了运行，就等吧，等待的时间要几分钟。然后提示你lua文件生成完毕。

5. 回到步骤2，把参数改成2.lua，再编译，运行，这时候,仔细观察，是不是发现电脑控制的飞机行为跟你操控很像呀。嘻嘻，有点意思吧。

功能分析

各个模块的功能

AIShooter：用openGL渲染战斗场景，玩家键盘输入检测, 使用决策树脚本控制机器人行为, 记录玩家行为数据。

DecisionTree： 核心算法，根据玩家行为数据生成决策树。

Learn: 使用DecisionTree提供的接口函数生成决策树,并把决策树生成脚本代码。

决策树的使用和实现

lua 与 c++交互:

C++创建lua的表对象，并传递类指针和函数指针给它，这样lua就可以调用到c++的函数

Agent类在init()中

   lua_newtable (mLua);//创建表对象

   lua_pushlightuserdata (mLua, this);// 将一个代表C指针的值放到栈

   lua_pushcclosure (mLua, Agent::setup_addInterval, 1);// 把一个新的 C closure 压入堆栈。

   lua_setfield (mLua, -2, "addInterval");以addInterval为键值注册到表中

lua_setglobal (mLua, "AIShooter");//设置表名

1.创建lua表AIShootert 设置项addInterval<->setup_addInterval.

2.创建lua表对象Agent, 设置项accel<->agent_accel turn<->agent_turn fire<->agent_fire

3.创建lua表对象GameState 设置项在act()中动态设置

处理过程:

1.      一开始调用lua函数setupFeatureMap 读取数据，然后通过 AIShooter.addInterval回调

1.

C++函数setup_addInterval进行数据传入

2. 游戏中的act()，通过对表GameState实时传入数据，然后调用lua的accelTree根据

GameState的数据进行逻辑处理,处理结果通过调用Agent.accel以参数形式传到C++函数

agent_accel中， 另外两个也类似

决策树的使用：

  初始化的时候，通过这样划定了每个行为的特征范围以及对应特征值

  AIShooter.addInterval ("opp_distance", 0, 0.0, 0.05);

  这些数据存放在mFeatureMap中

  在updata中实时传回当前状态数据，mFeatureMap根据范围来取他们对应的特征值,这些特征设置到GameState中,然后再根据脚本中的决策树进行逻辑判断。结果再返回c++相关的接口中

// Game state   

std::queue<DataSet::raw_row_t> mStateQueue;

typedef std::map<std::string, float> raw_row_t

// Training state

FeatureMap mFeatureMap; //数据管理类

类中类设计

Feature 基类

NominalFeature

ContinuousFeature 派生类

std::map <std::string, Feature*> mFeatures;

FeatureMap提供对外的接口再具体调具体的派生类

ContinuousFeature

有一个数据类型

typedef std::map<int, std::pair<float, float> > interval_t

所以的操作都是对其进行

1.添加数据

2.返回查找的值

3.保存文件和读取文件

DataSet mTrainingData; 仿函数的实战教程

for_each 和 transform

仿函数的关键

template< typename _t >

class cfun

{

  operator () ( _t value )

  {

       do some thing 给遍历用的

  }

  operator int() const 这个是返回整形，其他类型根据需要定

  {

       给返回值用

  }

}

数学:  log2(N) 在代码中这样获取 log10(N)/log10(2)

决策树的生成

ID3算法：从一系列统计数据中得到关键属性，并进行分类。重要概念是熵和信息增益

从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。

     设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：

     其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。

     现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：

     而信息增益即为两者的差值：

     ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：

其中s、m和l分别表示小、中和大。

     设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。

这里是计算结果的熵，共有10个结果, 3个是no, 7个yes, 如果结果不只是（yes和no两个结果，那么就按多个来算，那个倒M符合的意义就在这里）