這個《精粹7》里面一個AI設計的例子，方式是用行為克隆創(chuàng)建代理。《精粹7》上的描述實在是太粗略，很多東西都沒提及。花了一星期的閑碎時間去看這個例子，感覺挺有收獲的，整理了一下學習心得，希望能給跟我一樣的菜鳥們帶來一點幫助。這個例子代碼不多，但是水挺深的。涉及了lua, 仿函數(shù)，決策樹，信息論, 大堆循環(huán)遞歸等情況。
這個DEMO實現(xiàn)了一個飛機對戰(zhàn)射擊小游戲，電腦控制那個飛機會學習你的行為進行模仿。
項目運行
首先，先把項目跑起來再說。我的IDE是VS2008
1. 配置好openGL和 lua環(huán)境。這里不細說了，請參考網(wǎng)上資料
2. 配置AI。打開項目工程，設置AIShoote為啟動項，在AIShooter工程---屬性---配置屬性---調試---命令參數(shù)中填上 agent.lua。(這個是默認的決策樹的腳本),當然了這個文件要放置在你的項目工程里。
3. 編譯，運行。控制你的飛機跟對手打一架吧，經(jīng)過數(shù)分鐘的搏斗，你終于戰(zhàn)勝了機器人。關掉窗口，后臺會生成一個數(shù)據(jù)統(tǒng)計表叫training_data_xxx.dat文件。這個東東是用來后面生成決策樹腳本用的。
4. 現(xiàn)在開始進行生成決策樹，這課所謂的樹就存放一個lua文件中。設置Learn為啟動項, 在Learn工程---屬性---配置屬性---調試---命令參數(shù)中填上:
-s 1 training_data_xxx.dat 2.lua, 說明： -s 是跳過次數(shù)， dat文件是上一步驟產(chǎn)出的數(shù)據(jù)，2.lua是lua文件名。設置好了運行，就等吧，等待的時間要幾分鐘。然后提示你lua文件生成完畢。
5. 回到步驟2，把參數(shù)改成2.lua，再編譯，運行，這時候,仔細觀察，是不是發(fā)現(xiàn)電腦控制的飛機行為跟你操控很像呀。嘻嘻，有點意思吧。
功能分析
各個模塊的功能
AIShooter：用openGL渲染戰(zhàn)斗場景，玩家鍵盤輸入檢測, 使用決策樹腳本控制機器人行為, 記錄玩家行為數(shù)據(jù)。
DecisionTree： 核心算法，根據(jù)玩家行為數(shù)據(jù)生成決策樹。
Learn: 使用DecisionTree提供的接口函數(shù)生成決策樹,并把決策樹生成腳本代碼。
決策樹的使用和實現(xiàn)
lua 與 c++交互:
C++創(chuàng)建lua的表對象，并傳遞類指針和函數(shù)指針給它，這樣lua就可以調用到c++的函數(shù)
Agent類在init()中
lua_newtable (mLua);//創(chuàng)建表對象
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.創(chuàng)建lua表AIShootert 設置項addInterval<->setup_addInterval.
2.創(chuàng)建lua表對象Agent, 設置項accel<->agent_accel turn<->agent_turn fire<->agent_fire
3.創(chuàng)建lua表對象GameState 設置項在act()中動態(tài)設置
處理過程:
1. 一開始調用lua函數(shù)setupFeatureMap 讀取數(shù)據(jù)，然后通過 AIShooter.addInterval回調
1.
C++函數(shù)setup_addInterval進行數(shù)據(jù)傳入
2. 游戲中的act()，通過對表GameState實時傳入數(shù)據(jù)，然后調用lua的accelTree根據(jù)
GameState的數(shù)據(jù)進行邏輯處理,處理結果通過調用Agent.accel以參數(shù)形式傳到C++函數(shù)
agent_accel中， 另外兩個也類似
決策樹的使用：
初始化的時候，通過這樣劃定了每個行為的特征范圍以及對應特征值
AIShooter.addInterval ("opp_distance", 0, 0.0, 0.05);
這些數(shù)據(jù)存放在mFeatureMap中
在updata中實時傳回當前狀態(tài)數(shù)據(jù)，mFeatureMap根據(jù)范圍來取他們對應的特征值,這些特征設置到GameState中,然后再根據(jù)腳本中的決策樹進行邏輯判斷。結果再返回c++相關的接口中
// Game state
std::queue<DataSet::raw_row_t> mStateQueue;
typedef std::map<std::string, float> raw_row_t
// Training state
FeatureMap mFeatureMap; //數(shù)據(jù)管理類
類中類設計
Feature 基類
NominalFeature
ContinuousFeature 派生類
std::map <std::string, Feature*> mFeatures;
FeatureMap提供對外的接口再具體調具體的派生類
ContinuousFeature
有一個數(shù)據(jù)類型
typedef std::map<int, std::pair<float, float> > interval_t
所以的操作都是對其進行
1.添加數(shù)據(jù)
2.返回查找的值
3.保存文件和讀取文件
DataSet mTrainingData; 仿函數(shù)的實戰(zhàn)教程
for_each 和 transform
仿函數(shù)的關鍵
template< typename _t >
class cfun
{
operator () ( _t value )
{
do some thing 給遍歷用的
}
operator int() const 這個是返回整形，其他類型根據(jù)需要定
{
給返回值用
}
}
數(shù)學: log2(N) 在代碼中這樣獲取 log10(N)/log10(2)
決策樹的生成
ID3算法：從一系列統(tǒng)計數(shù)據(jù)中得到關鍵屬性，并進行分類。重要概念是熵和信息增益
從信息論知識中我們直到，期望信息越小，信息增益越大，從而純度越高。所以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個類別在整個訓練元組中出現(xiàn)的概率，可以用屬于此類別元素的數(shù)量除以訓練元組元素總數(shù)量作為估計。熵的實際意義表示是D中元組的類標號所需要的平均信息量。
現(xiàn)在我們假設將訓練元組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算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂。下面我們繼續(xù)用SNS社區(qū)中不真實賬號檢測的例子說明如何使用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")
所以根據(jù)公式詳細點應該為
-（ 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為分裂屬性，分裂后的結果如下圖表示：
在上圖的基礎上，再遞歸使用這個方法計算子節(jié)點的分裂屬性，最終就可以得到整個決策樹。
上面為了簡便，將特征屬性離散化了，其實日志密度和好友密度都是連續(xù)的屬性。對于特征屬性為連續(xù)值，可以如此使用ID3算法：
先將D中元素按照特征屬性排序，則每兩個相鄰元素的中間點可以看做潛在分裂點，從第一個潛在分裂點開始，分裂D并計算兩個集合的期望信息，具有最小期望信息的點稱為這個屬性的最佳分裂點，其信息期望作為此屬性的信息期望。
底數(shù)公式
①loga(MN)=loga(M)+loga(N)
②loga(M/N)=loga(M)-loga(N)
代碼中info()實現(xiàn)那段函數(shù)實質上是經(jīng)過一推導沒有直接用
假設現(xiàn)在套用標準的公式，有 C 1 + C2 = T
Info = - ( C1 / T )* log2 ( C 1 / T ) - ( C2 / T )* log2 ( C 2 / T )
根據(jù)底數(shù)公式2可以得出
Info = -( C1 / T ) * (log2C1 –log2T) - ( C2 / T ) * (log2C2 –log2T)
把被除數(shù)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: 屬性數(shù)據(jù)
workingSet: 分析數(shù)據(jù)集
這個函數(shù)完成了決策樹的生成。根據(jù)熵的分裂理論。要對這個集進行分支劃分。以其中最大值作上限，0作下限。在范圍（0，最大值）之間每一個值都列為一個分支。這些分支作為本節(jié)點的子節(jié)點。子節(jié)點也要進行這樣的處理。一直到“純”的節(jié)點為止。
在程序實現(xiàn)上使用遞歸來實現(xiàn)處理.
處理步驟
1. 設置遞歸返回點。根據(jù)這組屬性的“純度”來決定是否為遞歸終點，在這里返回的是葉子節(jié)點的值，就是決策結果。
2. 對所有分支進行處理，提取分支所屬的數(shù)據(jù), 獲取其中最大增益信息組，并開始遞歸
3. 填充范圍值內缺乏分支的節(jié)點，取近似的值的分支作為填充。
把決策樹寫成lua配置
每個屬性的范圍劃分，這部分數(shù)據(jù)是從features.dat從拷出來，添加到lua中的。
這里也應用了遞歸處理。
遍歷每個子節(jié)點的分支到葉子返回結果。