周麗芳 文佳黎

(重慶郵電大學 重慶 400065)

基于遺傳算法的虛擬足球游戲設計

周麗芳 文佳黎

(重慶郵電大學 重慶 400065)

隨著計算機軟硬件以及網(wǎng)絡技術的發(fā)展，人們開始把目光轉向有人工智能的高質量競技游戲，這種游戲能給人們帶來更多的樂趣和耐玩性。為加強游戲的對抗性能，遺傳算法、神經(jīng)網(wǎng)絡等越來越多的智能化算法將會被應用到游戲中。采用遺傳算法來強化虛擬足球游戲的人工智能特性，一方面提出了基于遺傳算法的角色分配方案，使技能釋放更合理，效果更佳；另一方面參考了機器人足球比賽中的路徑規(guī)劃策略，利用遺傳算法實現(xiàn)了該虛擬足球游戲中的動態(tài)避障和最短路徑兩個部分。

人工智能 遺傳算法 技能釋放 路徑規(guī)劃

0 引 言

近年來，隨著游戲產(chǎn)業(yè)的發(fā)展，人工智能的引入使得游戲更具吸引力和魅力。

本文中虛擬足球游戲的設計開發(fā)主要是依據(jù)現(xiàn)實足球比賽的場景進行的模擬，通過遺傳算法來加強游戲的人工智能特性。足球游戲主要包括三個目標：① 通過角色分配和技能釋放完成某項動作；② 動態(tài)避障；③ 實現(xiàn)路徑最短。由于場上情況復雜多變，使得開發(fā)者制定游戲規(guī)則時需要對游戲全面地了解，要考慮到多個方面的情況，這對于開發(fā)者來說是一個難題。因此，能實現(xiàn)全局優(yōu)化的遺傳算法可以助我們一臂之力。本文主要采用遺傳算法來加強游戲的人工智能[1]，完成角色的分配和動態(tài)路徑規(guī)劃。

1 遺傳算法

1.1 遺傳算法簡介

遺傳算法GA(Genetic Algorithm)[2]是20世紀60年代末到70年代初期提出的一個算法理論，是根據(jù)生物在自然界中復雜適應過程(適者生存，優(yōu)勝劣汰)構造的模型。經(jīng)過幾十年的研究發(fā)展，遺傳算法已形成了一個完整的理論方法，被廣泛應用于眾多領域[3]，成為了人工智能研究的一個重要方向。

1.2 遺傳算法原理

遺傳算法是一個全局優(yōu)化的自適應概率搜索算法。它將達爾文進化論的原理引入編碼串集合中，通過對自然界中的繁殖、交叉和變異現(xiàn)象的模擬，在編碼串群體間進行有規(guī)律的但又有一定隨機性的信息交換。隨著信息交換的進行，根據(jù)“優(yōu)勝劣汰”的原則，適應性高的個體被保留下來并重新組合，進而產(chǎn)生新的個體，直至產(chǎn)生最優(yōu)解。研究遺傳算法的主要目的之一，就是將自然系統(tǒng)的機理運用到人工系統(tǒng)的設計中。

1.3 遺傳算法的特點和步驟

遺傳算法不依賴于問題的種類，是一個通用的框架。它作為一種自適應算法，具有較高的魯棒性和內(nèi)在的并行性，以及良好的收斂性。

遺傳算法的主要步驟[4]如下：

① 制定合理的編碼方案，把目標問題的解空間轉換為串結構的編碼空間；

② 確定適應度函數(shù)；

③ 遺傳操作相關參數(shù)的分析和選擇，即群體大小的確定，遺傳算子的設計，以及交叉概率、變異概率的選擇；

④ 隨機生成初始群體，個體數(shù)目一定；

⑤ 根據(jù)適應度函數(shù)計算適應值；

⑥ 按照相應策略，運用遺傳操作形成下一代群體；

⑦ 判斷進化過程是否可以結束，若沒有則返回步驟⑤。

遺傳算法流程如呼1所示。

圖1 遺傳算法流程

2 基于遺傳算法的角色分配技能釋放方案

在該足球游戲中，由于雙方都可釋放技能，場上形勢每時每刻都在發(fā)生著變化，游戲角色此時需要釋放什么技能也是不斷變化的。為此，我們需要為場上的每一個角色分配一個最優(yōu)技能釋放方案。目前用于角色分配的方法主要有機器學習[5]、模糊一致關系[6]、遺傳算法等。模糊一致關系方法雖然實時性好，但是建模困難。機器學習方法能夠動態(tài)適應多變的場上環(huán)境，但是多個對象的學習，算法空間會隨著對象數(shù)目成指數(shù)增長，收斂速度過慢，實時性較差。而遺傳算法是模擬自然界生物進化機制的全局尋優(yōu)算法，計算簡單又具有較強的適應性，在人工智能的眾多領域有著廣泛的應用[7]。

本文利用遺傳算法的特性取得全局范圍內(nèi)的最優(yōu)的游戲角色技能釋放方案[8]，提高角色技能分配的準確性與合理性。本游戲雙方都設定了4名游戲角色，每名游戲角色都有4種技能釋放。這里定有4種技能S={s1,s2,s3,s4}，其中s1、s2、s3、s4分別為射門、傳球、快速移動搶球、防御搶球四種技能。

(1) 染色體編碼

技能的編碼也就是染色體的編碼，這里我們采用二進制編碼。本文每個角色有四個技能，每個技能用兩位即可完成編碼。例如S={01,00,10,11}這就表示該游戲的0號隊員使用2號技能，1號、2號、3號隊員分別使用1號、3號、4號技能。

(2) 適應度函數(shù)設計

每個角色使用何種技能以及在什么情況下使用都是通過這個適應度函數(shù)確定出最優(yōu)解。適應度函數(shù)直接影響遺傳算法的計算效率和計算時間。對于每個游戲技能的分配方案是否合理我們通過求各個游戲角色適應度來確定最佳技能施放策略。

其適應度函數(shù)F的計算如下：

F=f1+f2+f3+f4

(1)

設x為角色距離球門距離，技能s1的適應度函數(shù)為：

(2)

設x為敵方離我方的距離，y為當前角色距離球門最近角色的距離，技能s2的適應度函數(shù)為：

(3)

設x為敵人帶球角色距離該角色的距離，y為敵人角色距離該角色球門距離s3的適應度函數(shù)為：

f3=100-x-3y

(4)

技能s4的適應度函數(shù)為：

(5)

通過F來評價方案的適應度，F(xiàn)越大，方案越好。

(3) 初始種群的產(chǎn)生

初始群體的個體一般是隨機產(chǎn)生的，主要原因是為了保證遺傳算法的全局最優(yōu)性。由于本文涉及的技能只有四個，用八位即可表示所有的一個基因序列，所以我們只需簡單地采用計算機隨機生成產(chǎn)生初始種群。為保證基因序列的多樣性，應排除產(chǎn)生的相同序列。

(4) 遺傳操作

① 選擇：以一定的概率來確定參與重組的個體，選擇的過程其實就是一個優(yōu)勝劣汰的過程，性能優(yōu)良的個體將會被保留，劣質個體將會被淘汰。本文采用的選擇策略是“比例選擇”，即個體被選中的概率與其適應度成正比。假設群體的個體總數(shù)是N，那么個體Xi被選中的概率為：

(6)

按照適應度進行選擇有多種算法，這里算法實現(xiàn)采用的是“輪盤賭算法”。輪盤賭的操作方法：將輪盤分為N個扇形區(qū)，在(0,1)區(qū)間產(chǎn)生N個隨機數(shù)，比如產(chǎn)生隨機數(shù)r，若P(i-1)

② 交叉：是一個產(chǎn)生新個體的過程，即將選擇出來的個體按一定概率相互交換某些基因，基因重組形成新個體的過程。交叉操作是一種增加種群多樣性的手段。本文在此處采用單點交叉。

③ 變異：在繁殖過程，某一些新產(chǎn)生的個體以某一很小的概率改變某些基因，稱為變異。變異操作能夠保持群體的多樣性，是一種防止遺傳算法出現(xiàn)早熟的措施。這里我們設定遺傳變異發(fā)生率為1/1000。

(5) 遺傳終止條件

當?shù)螖?shù)達到500時，相鄰兩代之間的適應度值變化非常小，即算法達到收斂。因此我們設定終止條件為遺傳達到500代，并將其作為從中選出參數(shù)值最高的作為四個角色技能釋放的最優(yōu)解。

3 基于遺傳算法的路徑規(guī)劃

人工勢場法和柵格法等傳統(tǒng)的路徑規(guī)劃算法都存在著容易陷入局部最小和計算量大等缺陷。而遺傳算法計算簡單并具有良好的魯棒性，將遺傳算法運用到足球游戲的路徑規(guī)劃中可以避免很多傳統(tǒng)算法存在的不足。

所謂路徑規(guī)劃就是在坐標位置已知的不斷運動的障礙物、目標等動態(tài)環(huán)境中，引導對象從起點出發(fā)，避開障礙物，并找到一條合適的路徑，到達目標，即動態(tài)規(guī)劃。因此，在游戲運行時，路徑控制算法需根據(jù)障礙物位置對游戲中角色進行自動控制。本文將機器人足球中的路徑規(guī)劃方案用于虛擬足球游戲的開發(fā)中，把最短路徑要求和無碰撞要求結合起來，利用遺傳算法實現(xiàn)了一種簡單、有效的尋優(yōu)路徑策略[9-11]。

O={OB1,OB2,…,OBq}

(7)

其中，q為搜索范圍內(nèi)的障礙物個數(shù)。

圖2 障礙物描述示意圖

(1) 染色體編碼

以經(jīng)過的點組成一條染色體，即為路徑。如圖2所示，假設起始點為M和標點為G均已知，在矩形區(qū)域內(nèi)，將距離MG分為m+1等份，在每個等分點處做MG的垂線，得到VL1,VL2,…,VLm，再將每條垂線分為n+1等份，那么就有m×n個路徑點。由起始點到終點所經(jīng)過的點構成的集合，即為一條路徑，亦即一條染色體。

Ci={VL1(x(o),y(o)),VL2(x(p),y(p)),…,VLm(x(q),y(q))}

(8)

在VLi(x(j),y(j))中，當i確定之后，VLi(x(j),y(j))可以簡化表示為VLi(j),i∈[1,m]j∈[1,n]，則公式中一條路徑可以簡化表示為：

Ci={VL1(o),VL2(p),…,VLm(q)}

(9)

圖3 路徑點示意圖

(2) 適應度函數(shù)設計

(10)

② 避障策略：

(11)

(y(k)-yi)2-r2)}

(12)

其中，i=1,2,…,q。

建立總體適應度函數(shù)：

f=αfit1+βfit2

(13)

其中，α、β均為可調(diào)整的參數(shù)。適應度函數(shù)由兩部分組成：前半部分是為了滿足路徑盡可能短這一條件，可調(diào)整α，α越大，路徑較短這一條件在適應度函數(shù)中占的比例越高，一般α∈[100,300]；第2部分是為了滿足到達目標點過程中不會撞著障礙物這一條件，可調(diào)整β，一般β∈[0.1,0.5]。通過f來評價相應路徑在遺傳過程中的優(yōu)化程度。

(3) 初始種群的產(chǎn)生

隨機產(chǎn)生初始種群W個路徑集合，一般W∈(50,60)較為合適。

(4) 遺傳操作

① 選擇：此處同樣采用“比例選擇”和“輪盤賭算法”。

② 交叉：一般交叉概率Pc∈(0.6,0.8)較為合適。由選擇過程中所確定的路徑樣本，按Pc進行交叉操作。在(0,1)區(qū)間產(chǎn)生一個隨機數(shù)t，當t

③ 變異：變異概率Pm∈(0.003,0.007)。對于每一條路徑上的一位產(chǎn)生(0,1)區(qū)間的一個隨機數(shù)，若其小于Pm，則進行變異操作。將原來第i條垂線上的第j個點變成第j-1個點，如果第j個點是上邊界點，則不變。

(5) 遺傳終止條件

當?shù)螖?shù)達到300時，相鄰兩代之間的適應度值變化非常小，即算法達到收斂。因此我們設定終止條件為遺傳達到300代，并將其作為從中選出參數(shù)值最高的最優(yōu)解。

4 游戲界面展示

該游戲是基于Unity3D開發(fā)的一款既可以用于移動平臺又可以用于PC端的足球游戲，游戲界面如圖4所示。

圖4 游戲界面展示

選擇Unity3D開發(fā)該游戲的主要原因是因為其集成了MonoDeveloper的編譯平臺，支持JavaScript、C#和Boo這三種編輯語言[12-13]，是一個多平臺的游戲開發(fā)工具。為了實現(xiàn)簡單代碼間類的相互操作，該游戲的開發(fā)設計采用的是C#。

同時，Unity3D還對當前狀態(tài)的直接觀測、代碼的運行效率、資源的開銷提供了分析(如圖5所示)。這使得我們對算法的實時性的觀測以及遺傳終止條件(遺傳代數(shù))的選擇非常有利。

圖5 Stats窗口統(tǒng)計參數(shù)展示

由參數(shù)信息可知，每秒可執(zhí)行300幀左右，可見每秒渲染速度極快，算法運行效率高，實時性強。

并且，Unity3D是一個全面整合的專業(yè)游戲引擎[14]，場景中的游戲對象都由其場景編輯管理(如圖6所示)，使得開發(fā)游戲時對于對象的設計、添加、美化都更為方便。

圖6 游戲對象之球員

5 結 語

游戲效果證明遺傳算法有效加強了游戲中的人工智能。遺傳算法不僅可以用在角色分配和路徑規(guī)劃上，在其他很多方面都有良好性能，在未來肯定會被更多地用到游戲中去以加強游戲的人工智能。

然而遺傳算法雖然具有較強的全局搜索能力，但是其存在局部搜索能力較差以及在進化后期搜索速度慢等問題。對此，可考慮在下一步的改進中加入梯度算法和模擬退火算法[15-16]，進而克服此類問題。

[1] 楊科選,梁昔明.遺傳算法在游戲開發(fā)中的應用[J].計算機系統(tǒng)應用,2009,18(5):128-130,143.

[2]HollandJH.Adaptationinnaturalandartificialsystems:anintroductoryanalysiswithapplicationstobiology,control,andartificialintelligence[M].AnnArbor,MI,USA:TheUniversityofMichiganPress,1975.

[3] 李金娟.遺傳算法及應用的研究[J].電腦與信息技術,2013,21(2):5-7,12.

[4] 徐雁飛,幸海瓊.遺傳算法的應用及研究分析[J].電腦學習,2010(3):113-115.

[5]HwangKS,TanSW,ChenCC.CooperativestrategybasedonadaptiveQ-Learningforrobotsoccersystems[J].IEEETransactionsonFuzzySystems,2004,12(4):569-576.

[6]PlayneD.Knowledge-basedroleallocationinrobotsoccer[C]//10thInternationalConferenceonControl,Automation,RoboticsandVision,Hanoi,Vietnam,2008:1616-1619.

[7] 李文蕙,劉嵩.基于遺傳算法的人工智能分析[J].計算機光盤軟件與應用,2013(1):240-241.

[8] 金奎,程家興,李志俊,等.基于佳點集遺傳算法的足球機器人策略設計[J].計算機技術與發(fā)展,2008,18(11):123-124,162.

[9] 黨璐.虛擬人足球比賽決策系統(tǒng)的建模與設計[J].價值工程,2015(2):188-190.

[10] 樊朋濤,楊宜民.基于遺傳算法的雙足足球機器人路徑規(guī)劃[J].現(xiàn)代計算機,2012(24):3-6,22.

[11] 黃鴻,郭巧,金璽,等.基于遺傳算法的足球機器人避障策略[J].哈爾濱工業(yè)大學學報,2003,35(9):1093-1094,1097,1101.

[12] 倪樂波,戚鵬,遇麗娜,等.Unity3d產(chǎn)品虛擬展示技術的研究與應用[J].數(shù)字技術與應用,2010(9):54-55.

[13]SantosoM,GookLB.ARkanoid:developmentof3Dgameheldaugmentedreality[J].InternationalJournalofComputationalEngineeringResearch,2012,2(4):1053-1059.

[14] 林深華,范志尚,蔣建兵,等.基于Android平臺Unity3D游戲設計與實現(xiàn)[J].企業(yè)科技與發(fā)展,2013(10):40-42.

[15] 左宏濤,盧錦波,馮新桓.基于改進遺傳算法的足球機器人角色分配[C]//全國第20屆計算機技術與應用(CACIS)學術會議論文集,2009:313-317.

[16]JiangW,LuoD,XuY,etal.Hybridgeneticalgorithmresearchanditsapplicationinproblemoptimization[C]//Proceedingsofthe5thWorldCongressonIntelligentControlandAutomation,2004:2122-2126.

THE VIRTUAL SOCCER GAME BASED ON ARTIFICIAL INTELLIGENCE

Zhou Lifang Wen Jiali

(ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China)

With the development of hardware, software and network technologies, people begin to focus on the high quality of artificial intelligence games, which brings people more joy and resistance to play. In order to strengthen the fight machine performance, genetic algorithm, neural network, and more modern optimization algorithms will be applied to the game. The genetic algorithm is proposed to enhance the artificial intelligence of games. On the one hand , role assignments scheme based on genetic algorithms is presented to make the releasing skills more reasonable and better; on the other hand, referencing the avoidance strategy in robot soccer, the genetic algorithm is utilized for dynamic path planning of game.

Genetic algorithm Artificial intelligence Skill release Path planning

2015-10-06。重慶市基礎與前沿一般項目(cstc2015jcyjA40011)；重慶市研究生科研創(chuàng)新項目。周麗芳，副教授，主研領域：模式識別與圖像處理。文佳黎，碩士生。

TP311.52

A

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