寫在前頭
2017/08/03 編輯：
1. 修正計算錯誤。
2. 備註加入新連結。
你可以從這篇文章得到：
1.
BPN基本概念。
2.
如何實作BPN，並應用在遊戲裡。
3.
提供一個使用BPN決策的DEMO NPC。
BPN簡介
BPN的網路架構為多層感知器(multilayer
perceptron, MLP)，就是輸入層與輸出層之間多一層隱藏層(hidden layer)，使用誤差倒傳遞演算法(Error Back Propagation, EBP)為學習演算法，屬於多層前饋式網路，以監督式學習方式，處理輸入輸出之間非線性映射關係。
圖 1 BP網路圖
簡單說，BPN是由向前傳遞(forward
pass)及向後傳遞(backward pass)兩個部份組成，向前傳遞(如圖1 由左至右黑線)是先將訓練資料丟進網路去跑，在計算出輸出結果與對應目標之間誤差，而向後傳遞(如圖1 由右至左紅線)是依誤差值去調整網路權重，經過這樣多次訓練後，就會將網路修正到誤差極小範圍內的輸出結果。其主要特性如下：
1.
學習精確度高
2.
回想速度快
3.
可處理非線性問題
提一下BPN會用到的數學公式。
l 向前傳遞
1.使用sigmoid為激活函數：
$$f(x)=1/{1+e^{-x}$$
2.以均平方誤差(mean squared
error,MSE)為計算誤差值方法：
$$MSE={{(O_desired-O_actual)}^2}/2$$
l 向後傳遞
1.計算輸出層及隱藏層誤差值：
$$δ_o={(C_i-u_i)} u_i{(1-u_i)}$$
$$δ_i=(∑↙{m:m>i}w_{m,j}δ_o)u_i(1-u_j)$$
2.調整隱藏到輸出層和隱藏層到輸入層的權重：
$$w*_{i,j}=w_{i,j}+ρδ_o u_i$$
$$w*_{i,j}=w_{i,j}+ρ{δ_i}{u_i}$$
看了一大推數學算式，也不知道該怎麼實作。最後，可以參考AI Application Programming,
2ed這本書提供的倒傳遞演算法例子。
圖 2 BP實例
l The Feed-Forward Pass
計算各隱藏層的值和MSE。
$$\table u_3,=,f(w_{3,1}u_1+w_{3,2}u_2+w_{3,b}*bias_3);,=,f(1*0+0.5*1+1*-1);,=,f(-0.5);,=,0.377541$$
$$\table u_4,=,f(w_{4,1}u_1+w_{4,2}u_2+w_{4,b}*bias_4);,=,f(-1*0+2*1+1*1);,=,f(3);,=,0.952574$$
$$\table u_5,=,f(w_{5,3} u_3+w_{5,4}u_4+w_{5,b}*bias_5);,=,f(1.5*0.377541+-1.0*0.952574+1*1);,=,f(0.613738);,=,0.648793$$
$$\table MSE,=,0.5*(1.0-0.648793)^2;,=,0.0616733$$
l The Error Backward-Propagation Pass
計算出輸出層和隱藏層誤差值，在調整輸出層和隱藏各權重值及偏差值。(學習率為 ρ=0.5 )
$$\table δ_o,=,(1.0-0.648793)*0.648793*(1.0-0.648793);,=,0.080026$$
$$\table δ_{u4},=,(δ_o*w_{5,4})*u_4*(1.0-u_4 );,=,(0.080026*-1.0)*0.952574*(1.0-0.952574);,=,-0.00361531$$
$$\table δ_{u3},=,(δ_o*w_{5,3})*u_3*(1.0-u_3 );,=,(0.080026*1.5)*0.377541*(1.0-0.377541);,=,0.0282096$$
$$\table w_{5,4},=,w_{5,4}+(ρ*δ_o*u_4);,=,-1+(0.5*0.080026*0.952574);,=,-0.961885$$
$$\table w_{5,3},=,w_{5,3}+(ρ*δ_o*u_3);,=,1.5+(0.5*0.080026*0.377541);,=,1.51511$$
$$\table w_{5,b},=,w_{5,b}+(ρ*δ_o*bias_5);,=,1+(0.5*0.080026*1);,=,1.04001$$
$$\table w_{4,2},=,w_{4,2}+(ρ*δ_{u4}*u_2 );,=,2+(0.5*-0.00361531*1);,=,1.99819$$
$$\table w_{4,1},=,w_{4,1}+(ρ*δ_{u4}*u_1);,=,-1+(0.5*-0.00361531*0);,=,-1.0$$
$$\table w_{4,b},=,w_{4,b}+(ρ*δ_{u4}*bias_4 );,=,1.0+(0.5*-0.00361531*1);,=,0.998192$$
$$\table w_{3,2},=,w_{3,2}+(ρ*δ_{u3}*u_2);,=,0.5+(0.5*0.0282096*1);,=,0.514105$$
$$\table w_{3,1},=,w_{3,1}+(ρ*δ_{u3}*u_1);,=,1.0+(0.5*0.0282096*0);,=,1.0$$
$$\table w_{3,b},=,w_{3,b}+(ρ*δ_{u3}*bias_3 );,=,1.0+(0.5*0.0282096*-1);,=,0.985895$$
經過調整後，再跑一次向前傳遞，重新計算MSE有明顯變低。
$$\table u_3,=,f(w_{3,1}u_1+w_{3,2}u_2+w_{3,b}*bias_3);,=,f(1*0+0.514105*1+0.985895*-1);,=,f(-0.47179);,=,0.384193$$
$$\table u_4,=,f(w_{4,1}u_1+w_{4,2}u_2+w_{4,b}*bias_4);,=,f(-1.0*0+1.99819*1+0.998192*1);,=,f(2.99638);,=,0.952411$$
$$\table u_5,=,f(w_{5,3}u_3+w_{5,4}u_4+w_{5,b}*bias_5);,=,f(1.51511*0.384193+-0.961885*0.952411+1.04001*1);,=,f(0.705995);,=,0.669516$$
$$\table MSE,=,0.5*(1.0-0.669516)^2;,=,0.0546099$$
BPN如何應用在NPC決策行為
首先，容許我說明一下遊戲設定，在遊戲中會有一位NPC和玩家對抗，基本上，NPC會有下列屬性：
1.
生命值：範圍會介於0~2之間，如果~生命值=0時，NPC就會消失不見。
2.
小刀：NPC必須要擁有小刀，才能與玩家進行近距離攻擊，其數值為0或1。
3.
手槍：除了要佩帶手槍外，NPC還要有足夠的子彈數，就可以射擊玩家，其數值為0或1。
4.
子彈數：範圍會介於0~2之間，每發射一次，就會耗損一枚子彈，若子彈數為0時，就不能發射，必須要填充子彈後，才可以繼續射擊。
當賦予NPC這些屬性後，會在遊戲中與玩家的互動過程中，會產生一連串決策行為，其下列是NPC設定之行為：
1.
射擊：當NPC有佩帶手槍且子彈數夠(大於0)，就會發動射擊玩家，若玩家被射中，就會損失一點生命值。
2.
小力攻擊：當沒有手槍可以攻擊，若NPC身上還有小刀時，NPC會選擇用小刀來攻擊玩家，直到NPC生命值很低，就會選擇逃跑模式。
3.
裝彈：當NPC身上佩帶手槍的子彈用盡時，就會到裝彈的地方補充彈藥，繼續攻擊玩家。
4.
逃跑：如果NPC無計可施，就會採最壞打算「逃跑模式」，直到自己被消滅為止。
將上述邏輯轉成M╳N的數值矩陣(如表1所示)，前四欄為輸入屬性，而後四欄是輸出目標，即為NPC對應的行為，當輸出目標的其中之一欄為1時，NPC就會去執行該動作。
表 1 訓練資料
生命值
|
小刀
|
手槍
|
子彈數
|
射擊
|
小刀攻擊
|
裝彈
|
逃跑
|
2.0
|
0.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
2.0
|
0.0
|
1.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
2.0
|
0.0
|
1.0
|
2.0
|
1.0
|
0.0
|
0.0
|
0.0
|
2.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
0.0
|
2.0
|
1.0
|
0.0
|
1.0
|
0.0
|
1.0
|
0.0
|
0.0
|
2.0
|
1.0
|
0.0
|
2.0
|
0.0
|
1.0
|
0.0
|
0.0
|
2.0
|
1.0
|
1.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
2.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
1.0
|
2.0
|
1.0
|
1.0
|
2.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
1.0
|
0.0
|
1.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
1.0
|
2.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
0.0
|
1.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
0.0
|
1.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
0.0
|
1.0
|
1.0
|
1.0
|
1.0
|
1.0
|
0.0
|
0.0
|
0.0
|
1.0
|
從這些NPC訓練資料中， BPN會去找出它們之間的Pattern，在利用這些訓練好的Pattern去完成決策。
略談遊戲程式碼
這個DEMO中所用的程式碼，如下列所示：
名稱
|
說明
|
Backpropagation.cs
|
為BPN運作核心，先將訓練資料讀入，並把網路權重訓練好，傳入參數至action方法，得到對應指令。
|
BulletCollision.cs
|
當子彈碰撞時，會產生爆炸效果，若子彈是和Player或NPC發生碰撞，並計算扣血值。
|
Detection.cs
|
當NPC跑到補充點，就會補充NPC手槍彈藥。
|
FireBullet.cs
|
Player或NPC發射子彈時，會丟出剛建立的子彈物件。
|
KnifeCollision.cs
|
NPC拿小刀攻擊時，如果發生碰撞，就會傷害Player。
|
MainGUI.cs
|
顯示Player的生命值。
|
NPC.cs
|
定義NPC所有屬性和對應行為。
|
PlayerScript.cs
|
定義Player所有屬性和對應行為。
|
總結
這一篇主要核心是利用BPN作分類器，由訓練資料集去劃分四個對應動作類別，在有限訓練資料筆數中，其分類準確度極高，但缺點是若輸入參數超出訓練資料集的數值範圍，就會造成誤判的問題，故必須要時時擴充訓練資料集，若能將所有發生的可能都放進去，就可避免此情形發生。
參考資料
1.
M. Tim Jones, “AI Application
Programming”, Second Edition, 2005
2.
Brian Schwab, “AI Game Engine
Programming”, Second Edition, 2009
備註
