涂 浩 劉洪星

(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢 430063)

一種改進(jìn)型Q學(xué)習(xí)算法及其在行為樹中的應(yīng)用

涂 浩 劉洪星

(武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 湖北 武漢 430063)

游戲中的非玩家角色(NPC)通過學(xué)習(xí)獲得智能，因此學(xué)習(xí)算法的設(shè)計(jì)是一個(gè)關(guān)鍵問題。提出一種改進(jìn)型Q學(xué)習(xí)算法(SA-QL)，它以模擬退火算法為基礎(chǔ)，在狀態(tài)空間、探索策略、報(bào)酬函數(shù)等方面改進(jìn)了Q學(xué)習(xí)算法的不足。將該算法運(yùn)用到行為樹的設(shè)計(jì)中，使NPC能在游戲過程中實(shí)時(shí)學(xué)習(xí)，調(diào)整行為樹中邏輯行為的最佳執(zhí)行點(diǎn)，從而產(chǎn)生合適的行為響應(yīng)。實(shí)驗(yàn)結(jié)果表明，SA-QL算法比傳統(tǒng)Q學(xué)習(xí)算法效率更高，控制NPC的效果更好。

游戲人工智能 行為決策 Q學(xué)習(xí) 行為樹

0 引 言

行為樹由于其簡(jiǎn)單、靈活和模塊化等優(yōu)勢(shì)，被廣泛用于設(shè)計(jì)游戲中非玩家角色(NPC)的行為決策。然而，對(duì)于大多數(shù)行為樹的設(shè)計(jì)，所有任務(wù)的控制細(xì)節(jié)通常都是手動(dòng)編碼的，因此開發(fā)過程往往花費(fèi)大量的時(shí)間和精力。不好的行為樹設(shè)計(jì)可能導(dǎo)致NPC行為異常，從而破壞玩家的體驗(yàn)。在行為樹的設(shè)計(jì)過程中，需要根據(jù)NPC與游戲世界的反饋信號(hào)不斷調(diào)整其結(jié)構(gòu)，從而使NPC更好地適應(yīng)環(huán)境。Q學(xué)習(xí)算法具有良好的在線自適應(yīng)和對(duì)非線性系統(tǒng)的學(xué)習(xí)能力，采用試錯(cuò)的方式與環(huán)境進(jìn)行交互，根據(jù)環(huán)境對(duì)動(dòng)作的評(píng)價(jià)性反饋信號(hào)改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境。將Q學(xué)習(xí)算法運(yùn)用于NPC的行為樹設(shè)計(jì)是一種可行的方法。然而在具有大規(guī)模狀態(tài)空間或連續(xù)狀態(tài)空間的游戲任務(wù)中，該方法也面臨著一些問題，其中之一就是在動(dòng)作選擇時(shí)的“探索和利用”問題：如果僅根據(jù)當(dāng)前狀態(tài)動(dòng)作值選擇最優(yōu)動(dòng)作，則容易陷入局部最優(yōu)，而無(wú)法得到最優(yōu)解；如果為了跳出局部最優(yōu)而選擇非最優(yōu)的動(dòng)作，獲取更多的知識(shí)，又往往會(huì)降低了算法的性能。

目前將Q學(xué)習(xí)算法應(yīng)用于游戲人工智能領(lǐng)域的研究還較少。Florez-Puga等[1]將案例推理應(yīng)用到行為樹中，使得NPC可以從知識(shí)庫(kù)中動(dòng)態(tài)獲取行為。Ibrahim Mahmoud[2]將HTN應(yīng)用于NPC的行為決策中，得到了較好的效果。但是這些方法往往過度依賴于經(jīng)驗(yàn)數(shù)據(jù)，需要手動(dòng)生成經(jīng)驗(yàn)記錄。為了減少對(duì)于經(jīng)驗(yàn)數(shù)據(jù)的依賴，讓NPC的行為更加智能，關(guān)鍵是賦予其學(xué)習(xí)能力，調(diào)節(jié)自身動(dòng)作以更好地適應(yīng)環(huán)境。針對(duì)以上問題，本文提出了一種改進(jìn)型Q學(xué)習(xí)算法，它是基于模擬退火算法的Q學(xué)習(xí)算法SA-QL(Simulated Annealing-Q-Learning)，從狀態(tài)空間、探索策略、報(bào)酬函數(shù)等方面改進(jìn)Q學(xué)習(xí)算法，利用模擬退火算法中的Metropolis準(zhǔn)則控制NPC在學(xué)習(xí)進(jìn)程中適當(dāng)?shù)販p少探索次數(shù)。然后將SA-QL算法運(yùn)用到行為樹的設(shè)計(jì)，最后通過實(shí)驗(yàn)進(jìn)一步對(duì)學(xué)習(xí)結(jié)果進(jìn)行分析并優(yōu)化行為樹。實(shí)驗(yàn)結(jié)果表明：該方法可以提高Q學(xué)習(xí)算法的收斂速度，幫助游戲設(shè)計(jì)者減少在行為樹設(shè)計(jì)中耗費(fèi)的精力，實(shí)現(xiàn)自動(dòng)化行為樹設(shè)計(jì)，并使NPC在游戲過程中實(shí)時(shí)學(xué)習(xí)，更好地適應(yīng)環(huán)境，提高了NPC的智能。

1 相關(guān)研究

1.1 行為樹

行為樹是由行為節(jié)點(diǎn)組成的樹狀結(jié)構(gòu)。行為樹處理周圍游戲世界變化的任務(wù)是由條件節(jié)點(diǎn)來(lái)完成的，這相當(dāng)于每次遍歷行為樹時(shí)，條件節(jié)點(diǎn)都向周圍世界發(fā)出某種“詢問”，以這種方式來(lái)監(jiān)視游戲世界發(fā)生的事情。行為樹中的每個(gè)節(jié)點(diǎn)表示一個(gè)行為，節(jié)點(diǎn)是有層次的，子節(jié)點(diǎn)由其父節(jié)點(diǎn)來(lái)控制，從而決定接下來(lái)做什么，父節(jié)點(diǎn)的類型決定了某種高級(jí)控制策略。節(jié)點(diǎn)不需要維護(hù)向其他節(jié)點(diǎn)的轉(zhuǎn)換，節(jié)點(diǎn)的模塊化被大大增強(qiáng)了。在大型的游戲邏輯設(shè)計(jì)當(dāng)中，如果需要為多個(gè)NPC設(shè)計(jì)不同的行為樹，可能這些NPC的行為樹在某個(gè)子樹處相同。為了避免重復(fù)的工作，可以復(fù)用這些子樹，在行為樹的某些位置增加單個(gè)行為節(jié)點(diǎn)或行為子樹。行為樹的選擇器中包含隨機(jī)選擇節(jié)點(diǎn)和概率選擇節(jié)點(diǎn)，若能合理地安排節(jié)點(diǎn)的權(quán)值，便能較好地實(shí)現(xiàn)合理的隨機(jī)性[3-5]。模塊化、可復(fù)用性、并發(fā)等特點(diǎn)使得行為樹有效地降低了NPC行為設(shè)計(jì)的復(fù)雜性。

雖然已被大量的游戲和項(xiàng)目使用，行為樹仍具有以下不足之處：1) 必須在每個(gè)行為節(jié)點(diǎn)處手動(dòng)編碼，隨著游戲規(guī)模增大，行為樹變得很復(fù)雜，并且調(diào)試比較困難；2) 缺乏學(xué)習(xí)機(jī)制，無(wú)法實(shí)現(xiàn)自動(dòng)行為樹設(shè)計(jì)。由于以上原因使得行為樹的設(shè)計(jì)不夠高效。

1.2 Q學(xué)習(xí)算法

Watkins提出的Q學(xué)習(xí)算法用于解決不確定環(huán)境下的學(xué)習(xí)問題，通過學(xué)習(xí)選擇能達(dá)到目標(biāo)的最優(yōu)動(dòng)作。Q學(xué)習(xí)的模型如圖1所示。

圖1 Q學(xué)習(xí)模型圖

定義Q(s,a)為Agent在狀態(tài)s下執(zhí)行動(dòng)作a所返回強(qiáng)化信號(hào)的累計(jì)值函數(shù)。Agent通過觀察環(huán)境得到狀態(tài)s，Agent按策略π選擇動(dòng)作a并執(zhí)行，在下一時(shí)刻，Agent 收到環(huán)境反饋的強(qiáng)化信號(hào)(報(bào)酬值)并作用于Q(s,a)，更新策略π并達(dá)到新狀態(tài)。當(dāng)滿足一定條件，Q(s,a)值會(huì)收斂到某一確定值。在做決策時(shí)只需要比較s下執(zhí)行每個(gè)動(dòng)作的Q值，即可明確s下的最優(yōu)策略，無(wú)需考慮s的后續(xù)狀態(tài)[6-7]。Q(s,a)值定義如下：

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′)]

(1)

式中：r為狀態(tài)s下執(zhí)行a動(dòng)作得到的瞬時(shí)報(bào)酬值；γ為折扣因子；α表示學(xué)習(xí)率，Q(s′)為s后續(xù)狀態(tài)下的最大Q值。

在學(xué)習(xí)過程中，Agent采用試探的方式與環(huán)境交互，得到最優(yōu)的控制策略。為了避免其動(dòng)作選擇時(shí)的“探索和利用”問題，通常給每個(gè)動(dòng)作設(shè)定固定的執(zhí)行概率，并按照概率對(duì)當(dāng)前非最優(yōu)動(dòng)作進(jìn)行探索，用貪心策略和隨機(jī)探索策略相結(jié)合的方式分配探索和利用的時(shí)間。常用的方法是ε-貪心策略。ε-貪心策略設(shè)定具有最高Q值函數(shù)的動(dòng)作被選中的概率為ε，如果該動(dòng)作沒有被選擇，則從所有動(dòng)作中隨機(jī)地選擇一個(gè)動(dòng)作執(zhí)行。這種方法在學(xué)習(xí)開始階段主動(dòng)探索非最優(yōu)動(dòng)作，能避免“局部最優(yōu)”的問題，取得一定的效果。隨著學(xué)習(xí)的不斷深入，Agent所取得的知識(shí)趨于精確，應(yīng)減少對(duì)非最優(yōu)動(dòng)作的探索，此時(shí)ε-貪心策略仍以不變的概率探索非最優(yōu)動(dòng)作，會(huì)造成不必要的探索，影響Q學(xué)習(xí)算法的收斂速度。

2 SA-QL算法

為了減少在學(xué)習(xí)知識(shí)趨于精確之后的探索次數(shù)，本文將模擬退火算法應(yīng)用于Q學(xué)習(xí)的動(dòng)作選擇策略中，提出了SA-QL算法。模擬退火算法可以保證在追求全局最優(yōu)解的同時(shí)，避免陷入局部最優(yōu)[8]。該算法主要根據(jù)Metropolis準(zhǔn)則對(duì)應(yīng)的轉(zhuǎn)移概率來(lái)決定是否接受從解到新解的局部變化。由于模擬退火算法不完全拒絕惡化解，使得它可以跳出局部最優(yōu)解，避免陷入局部搜索。隨著學(xué)習(xí)的深入，通過調(diào)整溫度等參數(shù)的變化來(lái)自動(dòng)減少Q(mào)學(xué)習(xí)中的探索次數(shù)，可有效平衡“探索-利用”問題。SA-QL算法描述如下：

輸入：動(dòng)作集合A(s)，<狀態(tài)-動(dòng)作>的值函數(shù)Q(s,a)；初始溫度temperature；學(xué)習(xí)率α，報(bào)酬函數(shù)r，折扣因子γ。

輸出：優(yōu)化的<狀態(tài)-動(dòng)作>的值函數(shù)Q(s,a)。

處理過程：

1．選擇待訓(xùn)練的狀態(tài)s，當(dāng)+前動(dòng)作為ap；

3．執(zhí)行下一步動(dòng)作，更新Q(s,a)和狀態(tài)動(dòng)作:

Q(s,a)=(1-α)Q(s,a)+α[r+γQ(s′)];s=s′;ap=ar

4．若s不是終止?fàn)顟B(tài)，則轉(zhuǎn)至第2步；

5．若Q(s,a)收斂，算法結(jié)束;否則，依等比降溫策略重新計(jì)算temperature，轉(zhuǎn)至第2步。

該算法改善了基于ε-貪心算法的Q學(xué)習(xí)算法中由于ε固定不變帶來(lái)的收斂速度慢問題，在學(xué)習(xí)過程中，隨著溫度的降低，Agent探索次數(shù)將隨之減少，最終幾乎不存在探索，從而提高了算法的性能。

3 基于SA-QL算法的行為樹

在行為樹的設(shè)計(jì)中應(yīng)用SA-QL算法，將經(jīng)SA-QL算法優(yōu)化的<狀態(tài)-動(dòng)作>的值函數(shù)Q(s,a)運(yùn)用到行為樹的設(shè)計(jì)中，可在構(gòu)建行為樹時(shí)，減少剛開始時(shí)需要設(shè)計(jì)的節(jié)點(diǎn)，特別是條件節(jié)點(diǎn)，并能調(diào)整邏輯行為的最佳執(zhí)行點(diǎn)，從而對(duì)整個(gè)行為樹進(jìn)行重排和優(yōu)化。

SA-QL算法應(yīng)用在在行為樹構(gòu)建的預(yù)處理階段。首先分析行為樹并找到最深的順序節(jié)點(diǎn)，這些節(jié)點(diǎn)將作為學(xué)習(xí)中的動(dòng)作，在Q值表中建立對(duì)應(yīng)的Q值。為了支持在線學(xué)習(xí)，將生成的Q值表根據(jù)動(dòng)作劃分為相應(yīng)的Q值子表。子表根據(jù)Q值從大到小進(jìn)行排序，進(jìn)而得到Q條件節(jié)點(diǎn)(動(dòng)作的狀態(tài)允許列表)代替之前的條件節(jié)點(diǎn)。如圖2所示。后續(xù)學(xué)習(xí)過程將根據(jù)報(bào)酬更新Q值，然后采用相應(yīng)的動(dòng)作選擇策略。隨著學(xué)習(xí)的深入，將Q條件節(jié)點(diǎn)中的狀態(tài)過濾，只剩下部分高Q值的對(duì)應(yīng)狀態(tài)。

圖2 將Q值信息整合到行為樹中

在行為樹的學(xué)習(xí)過程中還要用到Q條件節(jié)點(diǎn)中的最大Q值。如圖3所示，以最大的Q值替換其父節(jié)點(diǎn)的Q值，并且重排行為樹，使節(jié)點(diǎn)的子樹從左至右按照子樹的Q值從大到小排列。重排行為樹使得行為節(jié)點(diǎn)之間的執(zhí)行順序更加合理，便于找到邏輯行為的最佳執(zhí)行點(diǎn)。

按照上述方式遞歸至根節(jié)點(diǎn)，完成重排行為樹。這里不必像一般行為樹編輯器一樣手動(dòng)地去修改節(jié)點(diǎn)，SA-QL算法學(xué)習(xí)過程中會(huì)自動(dòng)重排行為樹，重排后的行為樹的執(zhí)行與原行為樹的執(zhí)行類似。只是在執(zhí)行到Q條件節(jié)點(diǎn)的時(shí)候，需要在該動(dòng)作節(jié)點(diǎn)的狀態(tài)允許列表查找當(dāng)前狀態(tài)，如果列表中存在對(duì)應(yīng)狀態(tài)則執(zhí)行后續(xù)子節(jié)點(diǎn)，否則返回失敗狀態(tài)。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)過程

實(shí)驗(yàn)平臺(tái)采用一款跨平臺(tái)的專業(yè)游戲引擎Unity。在一個(gè)簡(jiǎn)單地圖中進(jìn)行五對(duì)五的NPC對(duì)戰(zhàn)實(shí)驗(yàn)。 NPC的初始位置是隨機(jī)分布在地圖中，以一方NPC全部被消滅或執(zhí)行超時(shí)作為實(shí)驗(yàn)結(jié)束標(biāo)志。為了比較兩種算法的收斂速度，在實(shí)驗(yàn)過程中分別采用傳統(tǒng)Q學(xué)習(xí)算法(以ε-貪心算法作為動(dòng)作選擇策略)和SA-QL算法重排NPC的行為樹。NPC的初始行為樹如圖4所示。

4.2 狀態(tài)和動(dòng)作

在理論上，Q學(xué)習(xí)以所有狀態(tài)完全收斂，獲得全狀態(tài)空間的最優(yōu)策略為學(xué)習(xí)目標(biāo)。Q學(xué)習(xí)狀態(tài)收斂所需的探索次數(shù)隨狀態(tài)空間和動(dòng)作空間的增加呈指數(shù)增長(zhǎng)。在實(shí)際控制中，Q學(xué)習(xí)不可能遍歷系統(tǒng)所有狀態(tài)，因?yàn)閷?duì)連續(xù)的環(huán)境變量的遍歷，會(huì)造成“維數(shù)災(zāi)難”的問題。

實(shí)驗(yàn)對(duì)狀態(tài)空間和動(dòng)作空間進(jìn)行泛化，通過一定程度地犧牲控制精度來(lái)提高算法收斂速度。利用合適的知識(shí)表示設(shè)計(jì)狀態(tài)聚類或狀態(tài)空間離散化的方法，對(duì)環(huán)境因素進(jìn)行模糊化和離散化處理，并通過建立Q值函數(shù)，狀態(tài)-動(dòng)作模型實(shí)現(xiàn)狀態(tài)空間和動(dòng)作空間的泛化，減少Q(mào)學(xué)習(xí)所需探索和學(xué)習(xí)的狀態(tài)空間，從而加快學(xué)習(xí)過程的收斂速度。

在根據(jù)經(jīng)驗(yàn)數(shù)據(jù)初始化Q值表時(shí)，考慮了以下幾點(diǎn)規(guī)則：

1) 行為節(jié)點(diǎn)允許的狀態(tài)對(duì)應(yīng)的Q值必須大于0；

2) 同一行為節(jié)點(diǎn)允許的狀態(tài)數(shù)目不易過多；

3) 盡量減小同一動(dòng)作的允許狀態(tài)的Q值的差距。

NPC的狀態(tài)空間主要由血量HP，離最近加血處的距離Db，離最近敵人的距離De，是否正在被攻擊IsAttacked四個(gè)方面環(huán)境因素構(gòu)成。相應(yīng)環(huán)境因素經(jīng)模糊化和離散化處理后如下：

? 血量HP：(none，low，medium，high)；

? 離最近加血處的距離Db：(none，near，medium，far)；

? 離最近敵人的距離De：(none，near，medium，far)；

? 是否正在被攻擊IsAttacked：(yes，no)。

血量中的none表示Agent已被消滅，距離為none表示沒有察覺或距離過遠(yuǎn)。

NPC的主要行為定義如下：

? 尋覓加血：尋找并移至加血處，獲取加血效果；

? 群聚：朝著隊(duì)友聚集的方向移動(dòng)；

? 尋找敵人：如果沒有找到敵人的位置，就調(diào)整方向以找到敵人的位置；

? 交戰(zhàn)：與敵人交戰(zhàn)；

? 漫步：在地圖上一定范圍隨機(jī)移動(dòng)；

? 逃跑：朝著一個(gè)遠(yuǎn)離敵人的方向逃跑。

4.3 報(bào)酬函數(shù)

Q學(xué)習(xí)狀態(tài)收斂所需的探索次數(shù)與該狀態(tài)報(bào)酬值距離收斂報(bào)酬值的步長(zhǎng)呈指數(shù)關(guān)系。為了加快算法的收斂速度，實(shí)驗(yàn)減小動(dòng)作的報(bào)酬函數(shù)邊界，報(bào)酬信號(hào)將結(jié)合先驗(yàn)知識(shí)和學(xué)習(xí)更新過程中的效果，以加權(quán)的方式綜合報(bào)酬函數(shù)。

為了讓NPC的行為選擇符合人類認(rèn)知的行為邏輯，在設(shè)計(jì)報(bào)酬函數(shù)時(shí)，狀態(tài)離目標(biāo)狀態(tài)越近，執(zhí)行動(dòng)作到達(dá)該狀態(tài)的報(bào)酬值越高。表1是根據(jù)先驗(yàn)知識(shí)制定<狀態(tài)-動(dòng)作>報(bào)酬函數(shù)表。記NPC在狀態(tài)s下執(zhí)行動(dòng)作a的報(bào)酬值為R1(s,a),未出現(xiàn)的情況默認(rèn)報(bào)酬函數(shù)值為0。表1中符號(hào)定義為：L=low；M= medium；H=high；N=near；F=far。同時(shí)，報(bào)酬函數(shù)結(jié)合學(xué)習(xí)過程中的報(bào)酬R2(NPC血量增加，獎(jiǎng)勵(lì)；NPC血量減少，懲罰；NPC消滅敵人，獎(jiǎng)勵(lì)；NPC被消滅，懲罰)。

表1 先驗(yàn)知識(shí)<狀態(tài)-動(dòng)作>報(bào)酬函數(shù)表

綜合考慮以上信息，以加權(quán)的方法得到報(bào)酬函數(shù)：R=ω1·R1+ω2·R2，其中:ω1、ω2為對(duì)應(yīng)的加權(quán)系數(shù)，均大于或等于0且兩者之和為1。

4.4 實(shí)驗(yàn)結(jié)果分析

重排后的行為樹如圖5所示。可以看出重排后的行為樹與初始行為樹的不同，學(xué)習(xí)的結(jié)果傾向于游蕩和群聚對(duì)NPC生存下來(lái)的目標(biāo)作用較小。另一個(gè)變化是攻擊行為子樹被賦予更高的優(yōu)先級(jí)，撤退的優(yōu)先級(jí)高于攻擊，說明NPC更傾向于被動(dòng)攻擊。下面從對(duì)戰(zhàn)結(jié)果中驗(yàn)證重排后行為樹的合理性。

圖5 重排后的行為樹

圖6顯示了實(shí)驗(yàn)結(jié)果，每組實(shí)驗(yàn)進(jìn)行5次對(duì)戰(zhàn)，記錄以下結(jié)果：生存下來(lái)的NPC數(shù)量、生存下來(lái)NPC的血量，實(shí)驗(yàn)得分由二者綜合所得。根據(jù)實(shí)驗(yàn)結(jié)果可知，SA-QL算法的收斂速度明顯比傳統(tǒng)Q學(xué)習(xí)算法快。Q學(xué)習(xí)本身強(qiáng)調(diào)采用試錯(cuò)的方式與環(huán)境進(jìn)行交互，根據(jù)環(huán)境對(duì)動(dòng)作的評(píng)價(jià)性反饋信號(hào)改進(jìn)行動(dòng)方案以適應(yīng)環(huán)境。SA-QL算法可以在與環(huán)境的不斷交互中更新狀態(tài)動(dòng)作值函數(shù)，改進(jìn)動(dòng)作選擇策略，隨著學(xué)習(xí)的不斷深入，該方法能有效地減少探索次數(shù)，加快學(xué)習(xí)的收斂速度。從實(shí)驗(yàn)結(jié)果中還可以看出行為樹重排之后的合理性，將SA-QL算法應(yīng)用于NPC的行為樹設(shè)計(jì)中可實(shí)現(xiàn)行為樹的自動(dòng)重排，調(diào)整其邏輯行為的最佳執(zhí)行點(diǎn)，使得NPC的行為更加智能、擬人化，這對(duì)于游戲中的NPC行為設(shè)計(jì)有一定的實(shí)用價(jià)值。

圖6 兩種算法的實(shí)驗(yàn)得分

5 結(jié) 語(yǔ)

本文研究了游戲人工智能中NPC的行為決策問題，以模擬退火算法為基礎(chǔ)，提出了一種改進(jìn)型Q學(xué)習(xí)算法，并將其應(yīng)用到行為樹的構(gòu)建當(dāng)中。實(shí)驗(yàn)結(jié)果表明，該方法在行為樹的設(shè)計(jì)上為游戲設(shè)計(jì)者帶來(lái)諸多方便，能幫助確定NPC邏輯行為的最佳執(zhí)行點(diǎn)，提高Q學(xué)習(xí)算法的收斂速度，實(shí)現(xiàn)自動(dòng)化的行為樹設(shè)計(jì)，讓NPC表現(xiàn)得更加智能。為了進(jìn)一步優(yōu)化Q學(xué)習(xí)算法在行為樹中的效果，在結(jié)合模擬退火算法和Q學(xué)習(xí)算法的過程中，如何選擇合理的降溫策略以及Q學(xué)習(xí)算法的值函數(shù)，是下一步的研究方向。

[1] Puga G F,Gómez-Martín M A,Díaz-Agudo B,et al.Dynamic Expansion of Behaviour Trees[C]//Artificial Intelligence and Interactive Digital Entertainment Conference,October 22-24,2008,Stanford,California,USA.2008.

[2] Mahmoud I M,Li L,Wloka D,et al.Believable NPCs in serious games:HTN planning approach based on visual perception[C]//Computational Intelligence and Games.IEEE,2014:1-8.

[3] Kyaw A S,Peters C,Swe T N.Unity 4.x Game AI Programming[M].Packt Publishing,2013.

[4] Robertson G,Watson I.Building behavior trees from observations in real-time strategy games[C]//International Symposium on Innovations in Intelligent Systems and Applications.IEEE,2015:1-7.

[5] Dey R,Child C.QL-BT:Enhancing behaviour tree design and implementation with Q-learning[C]//Computational Intelligence in Games.IEEE,2013:1-8.

[6] 姜文軍.網(wǎng)絡(luò)游戲中人工智能的研究及應(yīng)用[D].上海交通大學(xué),2013.

[7] Nicolau M,Perez-Liebana D,O’Neill M,et al.Evolutionary Behavior Tree Approaches for Navigating Platform Games[J].IEEE Transactions on Computational Intelligence & Ai in Games,2016,9(3):227-238.

[8] 李炎武,陳渝,曾慶維.基于強(qiáng)化學(xué)習(xí)的非玩家角色行為改進(jìn)[J].四川大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,51(5):915-920.

ANIMPROVEDQ-LEARNINGALGORITHMANDITSAPPLICATIONINBEHAVIORTREE

Tu Hao Liu Hongxing

(CollegeofComputerScienceandTechnology,WuhanUniversityofTechnology,Wuhan430063,Hubei,China)

The non-player character (NPC) in a game gains intelligence by learning, so the design of the learning algorithm becomes the key issue. In this paper, an improved Q-learning algorithm (SA-QL) was proposed. Based on simulated annealing algorithm, the Q-learning algorithm was improved in the aspects of state space, exploration strategy and reward function. Then the algorithm was applied to the design of behaviour tree, so that the NPC could learn and adjust the best execution point of the logical behaviour in the process of the game in real time, and produced the appropriate behavior response. Experimental results showed that the SA-QL algorithm was more efficient than the traditional Q-learning algorithm, and had better control effect on NPC.

Game AI Behaviour decision Q-learning Behaviour tree

2016-12-06。國(guó)家自然科學(xué)基金項(xiàng)目(61472294)；中央高?；究蒲袠I(yè)務(wù)費(fèi)基金項(xiàng)目(15521004)。涂浩，碩士，主研領(lǐng)域：機(jī)器學(xué)習(xí)，信息系統(tǒng)集成。劉洪星，教授。

TP3

A

10.3969/j.issn.1000-386x.2017.12.045