这个《精粹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）表示为：
=-\sum%20^m_{i=1}p_ilog_2(p_i) "info(D)=-\sum ^m_{i=1}p_ilog_2(p_i)")
其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。
现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：
=\sum%20^v_{j=1}\frac{|D_j|}{|D|}info(D_j) "info_A(D)=\sum ^v_{j=1}\frac{|D_j|}{|D|}info(D_j)")
而信息增益即为两者的差值：
=info(D)-info_A(D) "gain(A)=info(D)-info_A(D)")
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：
其中s、m和l分别表示小、中和大。
设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。
这里是计算结果的熵，共有10个结果, 3个是no, 7个yes, 如果结果不只是（yes和no两个结果，那么就按多个来算，那个倒M符合的意义就在这里）
=0.3*(-\frac{0}{3}log_2\frac{0}{3}-\frac{3}{3}log_2\frac{3}{3})+0.4*(-\frac{1}{4}log_2\frac{1}{4}-\frac{3}{4}log_2\frac{3}{4})+0.3*(-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3})=0+0.326+0.277=0.603 "info_L(D)=0.3*(-\frac{0}{3}log_2\frac{0}{3}-\frac{3}{3}log_2\frac{3}{3})+0.4*(-\frac{1}{4}log_2\frac{1}{4}-\frac{3}{4}log_2\frac{3}{4})+0.3*(-\frac{1}{3}log_2\frac{1}{3}-\frac{2}{3}log_2\frac{2}{3})=0+0.326+0.277=0.603")
所以根据公式详细点应该为
-（ 7 / 10 ）log2( 7 / 10 ) – ( 3 / 10 ) log2( 3 / 10 )
计算日志的熵:
详解:
第一项是按日志L划分，即。 (3 / 10) * ( - ( 0 / 3 ) log2( 0 / 3 ) – ( 3 / 3 )log2( 3 / 3 ) ), 这个 3 / 10 是指l值有3个
因此日志密度的信息增益是0.276。
用同样方法得到H和F的信息增益分别为0.033和0.553。
因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：
在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法：
先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。
底数公式
①loga(MN)=loga(M)+loga(N)
②loga(M/N)=loga(M)-loga(N)
代码中info()实现那段函数实质上是经过一推导没有直接用
假设现在套用标准的公式，有 C 1 + C2 = T
Info = - ( C1 / T )* log2 ( C 1 / T ) - ( C2 / T )* log2 ( C 2 / T )
根据底数公式2可以得出
Info = -( C1 / T ) * (log2C1 –log2T) - ( C2 / T ) * (log2C2 –log2T)
把被除数T移出来
Info = ( - C1 * (log2C1 –log2T) - C2 * (log2C2 –log2T) ) /T
Info = ( - C1 log2C1 + C1log2T - C2 log2C2 + C2log2T ) /T
Info = ( - C1 log2C1 - C2 log2C2 + C1log2T + C2log2T ) /T
Info = ( - C1 log2C1 - C2 log2C2 + ( C1 + C2 ) log2T ) /T
C1 + C2 = T
Info = ( - C1 log2C1 - C2 log2C2 + T log2T ) /T
所以代码里最终是用这个公式来计算的，明显减少了除法运算量
代码中决策树生成的代码分析：
static TreeNode* learnNode (const std::string& targetName,
const std::string& columnName, const col_t& column,
const col_set_t& workingSet, unsigned int threshold);
targetName: 决策树的目标属性
columnName: 传入的属性名
column: 属性数据
workingSet: 分析数据集
这个函数完成了决策树的生成。根据熵的分裂理论。要对这个集进行分支划分。以其中最大值作上限，0作下限。在范围（0，最大值）之间每一个值都列为一个分支。这些分支作为本节点的子节点。子节点也要进行这样的处理。一直到“纯”的节点为止。
在程序实现上使用递归来实现处理.
处理步骤
1. 设置递归返回点。根据这组属性的“纯度”来决定是否为递归终点，在这里返回的是叶子节点的值，就是决策结果。
2. 对所有分支进行处理，提取分支所属的数据, 获取其中最大增益信息组，并开始递归
3. 填充范围值内缺乏分支的节点，取近似的值的分支作为填充。
把决策树写成lua配置
每个属性的范围划分，这部分数据是从features.dat从拷出来，添加到lua中的。
这里也应用了递归处理。
遍历每个子节点的分支到叶子返回结果。