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