2013年4月1日

1.建立一个目录.
 mkidr test
2.建立一个测试文件
vi main.cpp
  1 #include <iostream>
  2 
  3 int main(int argc, char* agrv[])
  4 {
  5     std::cout << "hello!" << std::endl;
  6     return 0;
  7 }
3.创建configure.ac文件
autoscan
提示configure.ac不存在,但是会生成一个configure.scan
mv configure.scan configure.ac
vi configure.ac修改为如下
  1 #                                               -*- Autoconf -*-
  2 # Process this file with autoconf to produce a configure script.
  3 
  4 AC_PREREQ(2.59)
  5 AC_INIT([loki], [1.0], [])
  6 AM_INIT_AUTOMAKE
  7 AC_CONFIG_SRCDIR([main.cpp])
  8 AC_CONFIG_HEADER([config.h])
  9 AC_CONFIG_FILES([Makefile])
 10 
 11 # Checks for programs.
 12 AC_PROG_CXX
 13 
 14 # Checks for libraries.
 15 
 16 # Checks for header files.
 17 
 18 # Checks for typedefs, structures, and compiler characteristics.
 19 
 20 # Checks for library functions.
 21 AC_OUTPUT

4.创建相关文件
touch AUTHORS ChangeLog NEWS README

5.编写Makefile.am
vi Makefile.am
1 noinst_PROGRAMS = loki
2 loki_SOURCES = main.cpp

6.
autoreconf -i

7.
./configure

8. 配置完工,使用make即可看到编译出的执行文件loki
make
./loki

要了解具体为什么要这样做,请看这篇教程http://www.freesoftwaremagazine.com/books/autotools_a_guide_to_autoconf_automake_libtool

posted @ 2013-04-01 15:53 菜鸟想学飞 阅读(348) | 评论 (0)编辑 收藏


2012年5月20日

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

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

项目运行

首先,先把项目跑起来再说。我的IDEVS2008

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.创建luaAIShootert 设置项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实时传入数据,然后调用luaaccelTree根据

 

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为用类别对训练元组进行的划分,则Dentropy)表示为:

     

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

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

     

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

     

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

 

 

其中sml分别表示小、中和大。

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

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

 

     

      

所以根据公式详细点应该为

 

         - 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

     用同样方法得到HF的信息增益分别为0.0330.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中的。

 

这里也应用了递归处理。

遍历每个子节点的分支到叶子返回结果。

posted @ 2012-05-20 13:29 菜鸟想学飞 阅读(928) | 评论 (4)编辑 收藏


仅列出标题  

posts - 2, comments - 4, trackbacks - 0, articles - 0

Copyright © 菜鸟想学飞