這個《精粹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中的。
這里也應用了遞歸處理。
遍歷每個子節點的分支到葉子返回結果。