用遗传算法在游戏开发中的应用

直都想用遗传算法(GeneticAlgorithms)实现足球游戏人工智能但实现个足球游戏对战平台太过于繁琐而没有动手直到在ProgrammingGameAIbyExample书中看到个SimpleSoccerdemo(以下简称demo)实现了个red-blue两队进行机器和机器对抗简单足球游戏在读过它源码的后我决定在demo上进行 2次开发——为它加入遗传算法实验遗传算法在实时战略游戏(RTS)性质体育游戏中威力
demo架构非常好采用了状态机来实现游戏流程并分开计算游戏决策因此加入遗传算法非常容易只要在原来状态机中增加两个状态即可red-blue两个队伍相互对抗每队有 5位球员其中位是守门员这个demo足球规则是简化除了只有 5个球员外没有手球也没有越位等规则甚至连边界球都没有——球碰到边界就反弹回球场简化规则有利于我们简化实验过程不必把很多精力花费在过于复杂规则上

图
在demo实现中球场被分割为18块大小相等区域(见图)每个球员都个属于自己区域(称为HomeRegion)如图中blue队10号在自己HomeRegion(Region5)中处于Wait状态(球员状态的)当个球员不处于进攻状态(Attacking)、助攻(SupportAttacker)、逐球(ChaseBall)、运球(Dribble)、踢球(KickBall)及返回(ReturnToHomeRegion)时他就进入Wait状态——等待球队发出下个行动指令显然就像人类进行足球比赛时需要排兵布阵样demo中球员站在哪个位置也相当重要能否组织起有效进攻或者防守决定原因的就是在合适位置有没有球员可以快速有效地执行命令在书中自带demo中球员站位都是固定因此难以组织有效进攻和防守在某时间段内容易形成边倒局势使用遗传算法来对球员站位进行决策分析可以找出对当前局势就有利位置编排方案从而使得球队和球队的间对抗趋于激烈、策略更加有效、攻守都更精彩

遗传算法概述
遗传算法它在解决许多生产、生活中问题上卓越性能而经久不衰随着计算机计算能力日益增强和玩家对游戏中人工智能强烈需求目前在单机游戏中已经开始应用遗传算法、人工神经网络等现代优化计算思路方法来增强游戏中人工智能并且形成了趋势可见以后为加强机器对抗性能遗传算法、人工神经网络等都会越来越多地应用到游戏中
遗传算法是模拟自然界中生物对自然界适应而不断进化这客观事实算法为了解决某个问题在遗传算法中我们虚拟个物种(即解表现形式或者称为解编码)并将其放到“自然环境”中天下繁殖、进化根据优胜劣汰、适者生存自然法则繁衍若干代的后种群中佼佼者将非常适应“自然环境”这个佼佼者就是我们求得解了有关生物学和遗传算法的间概念对应关系可以用表形式来表示:
生物遗传概念

遗传算法中作用


适者生存



在算法停止时最优目标值解有最大可能性被留住


个体

解


染色体

解编码( 2进制形式或者十进制形式串即向量或者串)


基因

解中每分量特征(如各分量值)




适应性

适应返回值


群体

选定组解(其中解个数为群体规模)


种群

根据适应选取组解


交配

通过交配原则产生组新解过程




变异

编码某分量发生变化过程



[Page]

表
遗传算法流程图如图 2所示:



图 2
遗传算法运行时先生成群体(通常是随机产生定数量个体这个数量就是群体大小)；然后让群体繁殖下代繁殖方式有交叉、复制和变异；经过繁殖后群体数量增加然后使用评估模块对每个个体进行评估；如果群体中最佳个体已经足够优秀那就跳出循环返回最佳个体；否则判断是否已经繁殖了预定代数如果是就返回最佳个体如果不是则淘汰部分劣质个体并进入下轮繁殖循环直至结束
在遗传算法实现中最重要主要有 3点:是染色体编码即个新物种如何样来表示它通常染色体是问题个可能解特定格式表示通常以 2进制或者十进制方式编码； 2是为染色体实现交叉、复制、变异等算子； 3是估值模块编写下面以这 3点为中心谈谈demo中遗传算法实现

染色体编码
染色体编码方式有很多种常见是 2进制思路方法和十制字方式也有串方式如著名旅行商问题(TSP)里假设有20个城市以[0…19]编码那么[7698…19304]这个包含20个元素序列A就可以看作是个染色体每个元素Aj(0<=j<20)就是染色体个基因这个染色体可以解码为从编号为7城市出发到达城市6、城市9等等最后到达城市4完成20个城市遍历显然这个序列是TSP个可能解因此染色体就是问题可能解表示方式回到我们足球游戏中来我们期望获得某队球员合适站位那么如果我们把 4个球员以[0…3]编号(守门员不应离开禁区所以不必考虑他位置)那序列B[1411126]就是个站位方案表示0号球员站在ID为14Region中1号球员站在ID为11Region中等序列B叫做个可能解序列B编码方式即是我们染色体编码方式——十进制编码方式个序列依照这个规则我们编写代码如下:
typedefunsignedGenetype;
Chromosome{
private:
std::vector<Genetype>m_Geneme;
m_iScore;
public:
Chromosome;
~Chromosome{};
conststd::vector<Genetype>&GetGenemeconst{m_Geneme;}
voidSetScore(iScore){m_iScore=iScore;}
friendvoidIntercross(constChromosome&p1,constChromosome&p2,
Chromosome&c1,Chromosome&c2); [Page]
friendvoidAgamogenesis(constChromosome&p,Chromosome&c);
friendvoidMutant(constChromosome&p,Chromosome&c);
friendGT;
};
GT{
public:
inlinebooloperator(constChromosome*c1,constChromosome*c2)const{
c1->m_iScore>c2->m_iScore;
}


};
类Chromosome是染色体封装它成员变量m_Geneme是个基因序列用std::vector容器来保存；成员变量m_iScore是这个染色体对“自然环境”适应值由评估模块评定友元类GT实现了两个Chromosome大小比较；还定义了 3个友元分别实现交叉、复制及变异 3个遗传算子详见下节

遗传算子
交叉、复制和变异 3个遗传算子是遗传算法能够找到最优解途径这 3个遗传算子模拟了自然界物种交配和生殖方式为产生新可行解提供了有效手段(见表)遗传算子声明为染色体类Chromosome友元是为了方便操作它私有变量实现如下:
voidIntercross(constChromosome&p1,constChromosome&p2,
Chromosome&c1,Chromosome&c2){
unsignedIntercrossPo=RangeRandom<unsigned>(0,GeneLen);
unsignedi=0;
for(;i<IntercrossPo;i){
c1.m_Geneme[i]=p1.m_Geneme[i];
c2.m_Geneme[i]=p2.m_Geneme[i];
}
for(;i<GeneLen;i){
c1.m_Geneme[i]=p2.m_Geneme[i];
c2.m_Geneme[i]=p1.m_Geneme[i]; [Page]
}
}
voidAgamogenesis(constChromosome&p,Chromosome&c){
c.m_Geneme=p.m_Geneme;
}
voidMutant(constChromosome&p,Chromosome&c){
unsignedMutantPo=RangeRandom<unsigned>(0,GeneLen);
GenetypeNewGene=RangeRandom<Genetype>(0,18);
c.m_Geneme=p.m_Geneme;
c.m_Geneme[MutantPo]=NewGene;
}
IntercrossAgamogenesis和Mutant 3个分别对应交叉、复制和变异 3个遗传算子Intercross传入两个Chromosome例子随机选择点进行交叉组成两个新染色体用作返回值Agamogenesis传入个Chromosome例子返回个相同染色体以保证优势种群可以壮大从而使得遗传算法可以在有限运行时间内收敛Mutant传入个Chromosome例子随机选择个元素(分量)赋以个随机RegionID返回这改变后染色体变异可以使得遗传算法跳出局部最优趋近全局最优 3个遗传算子操作结果如表 2所示:


遗传算子

输入染色体

输出染色体




Intercross

[17,9,4,3]

[16,13,7,9]

[17,9,7,9]

[16,13,4,3]

假定元素2为交叉点


Agamogenesis

[17,9,4,3]

[17,9,4,3]


Mutant

[17,9,4,3]



[17,9,7,3]

假定元素2为变异点






表 2

估值模块
通俗点说估值模块就是阎罗王个体淘汰和否就得看估值模块脸色了估值模块判定每个染色体对“自然环境”适应度:如前文有关TSP染色体它估值就返回遍历20个城市要走过路程总长度总长度越短染色体适应度越高反的则越低在足球游戏中估值模块就没有这么简单了个染色体就是个站位组合这个组合优劣是和当前局势有很大关系如球位置、对方球员站位、已方球员站位和控球权等有关综合以上各种原因编写如下估值模块:
Environment::Evaluate(conststd::vector<Genetype>&candidate){
iValue=0;
for(unsignedi=0;i<GeneLen;i){
//减去移动需要损耗
iValue-=DistOfTwoRgn(candidate[i],m_CurrGeneme[i])*m_pPrm->CrossCostPerRgn; [Page]
//有利于防守？
iValueGetDefendValue(candidate[i],m_OppGeneme);
//有利于进攻？
iValueGetAttackValue(candidate[i],m_OppGeneme);
//有利于抢球或者保球？
(m_iTeamColorm_iControllingTeam
&&m_iBallRgnIdxcandidate[i])
iValuem_pPrm->PlyrKeepBallValue;
(m_iTeamColor!=m_iControllingTeam
&&m_iBallRgnIdxcandidate[i])
iValuem_pPrm->PlyrChaseBallValue;
}
iValue;
}
Environment::GetDefendValue(constiPlyrIdx,conststd::vector<Genetype>&OppGeneme){
iValue=0;
OppInMyGround=0;
std::vector<Genetype>::const_iteratorci=OppGeneme.begin;
for(;ci!=OppGeneme.end;ci){
(IsInMyGround(*ci))
OppInMyGround;
} [Page]
(OppInMyGround>1){
(IsInMyGround(_cast<unsigned>(iPlyrIdx)))


iValuem_pPrm->DefendValuePerPlyr;

iValuem_pPrm->DefendValuePerPlyr*0.5;
}
{
iValuem_pPrm->DefendValuePerPlyr*0.8;
}
(m_iControllingTeamm_iTeamColor)
iValue*=1.2;

iValue*=0.8;
iValue;
}
Environment::GetAttackValue(constiPlyrIdx,conststd::vector<Genetype>&OppGeneme){
iValue=0;
OppNoInMyGround=0;
std::vector<Genetype>::const_iteratorci=OppGeneme.begin;
for(;ci!=OppGeneme.end;ci){
(!IsInMyGround(*ci))
OppNoInMyGround;
}
(OppNoInMyGround>2){
(IsInMyGround(_cast<unsigned>(iPlyrIdx)))
iValuem_pPrm->AttackValuePerPlyr*0.5; [Page]

iValuem_pPrm->AttackValuePerPlyr;
}
(m_iControllingTeamm_iTeamColor)
iValue*=1.2;

iValue*=0.8;
iValue;
}
Evaluate主要从以下几方面来对染色体进行评估:
·从当前位置到目位置所要经过路径代价
·是否有利于进攻或者防守
·是否有利于持球或者抢球
其中计算是否有利于进攻或者防守是通过计算两个球队间球员位置来判断:对方球员在已方半场时如果已方球员目位置也在已方半场就有利于防守；对方球员在已方半场时如果已方球员目位置在对方半场则有利于进攻通过这简单估值模块可以使得遗传算法在淘汰劣质个体时有法可依从而能够收敛得到较优解通过精细化估值模块考虑更多原因(如对方球队可能采取策略等)可使遗传算法收敛速度加快在真实游戏项目中必定会使用精细化估值模块

架构
确定了遗传算法编码方式、实现了 3个遗传算子和估值模块的后这个遗传算法基本上就完成了但我们还没有看到它是如何化种群、如何繁殖和如何淘汰劣质个体这时候有必要了解下遗传算法架构在demo中我们设计遗传算法架构如图 3:

Environment
Population
Chromosome
Gene


图 3
Environment是自然环境模拟它实现了估值、繁殖迭代控制和环境化和销毁等功能最重要是它包含了种成员变量——Population例子每个Environment还有个算法参数包装类ParamLoader例子指针m_pPrm用以存取配置文件每个球队拥有个Environment例子专门用以计算适合本队球员位置编排简化Environment声明如下:
Environment{
private:
ParamLoader*m_pPrm;
Populationm_Population;
private:
Evaluate(conststd::vector<Genetype>&candidate);


GetDefendValue(constiPlyrIdx,conststd::vector<Genetype>&OppGeneme);
GetAttackValue(constiPlyrIdx,conststd::vector<Genetype>&OppGeneme); [Page]
boolIsInMyGround(unsignediRgnIdx)
doubleDistOfTwoRgn(unsignediRgnIdx1,unsignediRgnIdx2)
public:
conststd::vector<Genetype>GetBestGeneme;
};
当GetBestGnenme时遗传算法便开始运行GetBestGeneme控制繁殖迭代次数并挑选最优染色体个体它实现如下:
conststd::vector<Genetype>Environment::GetBestGeneme{
for(unsignedi=0;i<m_pPrm->GAGeneration;i){
m_Population.NexGeneration;
unsigneduiPopulationSize=m_Population.GetPopulationSize;
for(unsignedi=0;i<uiPopulationSize;i){
score=Evaluate(m_Population.GetGenemeByID(i));
m_Population.SetScoreByID(i,score);
}
m_Population.KeepColonySize(m_pPrm->ColonySize);
}
m_Population.GetBestGeneme;
}
Population是物种群体抽象它实现个最重要就是NextGenerationEnvironment通过这个让群体执行繁殖任务；另个重要就是KeepColonySize这个淘汰掉劣质个体让竞争力较强个体进入下轮繁殖简化Population声明如下:
Population
{
private:
std::vector<Chromosome*>m_Colony;
unsignedm_iColonySize;
doublem_dIntercrossRate,
m_dAgamogenesisRate, [Page]
m_dMutantRate;
std::vector<Genetype>m_BestGeneme;
public:
voidInitial(unsignediColonySize,
doubledIntercrossRate,
doubledAgamogenesisRate,
doubledMutantRate);
voidRelease;
voidNexGeneration;
voidKeepColonySize(unsignedsize=100)
private:
voidIntercross;
voidAgamogenesis;
voidMutant;
};
Population用std::vector容器保存物种所有个体(m_iColonySize个Chromosome例子)m_dIntercrossRate、m_dAgamogenesisRate和m_dMutantRate 3个变量分别是交叉率、复制率和变异率其中染色体交叉是自然界中生物繁殖最常见方式可以保证优秀基因可以遗传到下代或者有很大机会使得部分优秀基因和另部分优秀基因结合为个非常优秀染色体因此交叉率比较高般取值在0.1～0.5的间；复制率即是无性繁殖机率无性繁殖在自然界中是普遍存在正常现象(如植物中落地生根和动物中蚯蚓)无性繁殖可以确保优秀个体有定机会壮大自己种群般复制率取值在0.03～0.1的间；变异在自然界中是发生机率极小事件而且变异多是恶性所以变异率取值范围在0.005～0.05的间但变异可以让遗传算法跳出局部最优因而是必须个操作算子m_iColonySize是种群大小种群越大找到解机会越大但花费时间也相对比较多般设为可以接受固定值也可以编写和问题难度相关来决定本实验使用m_iColonySize=100固定值方式


Population另外还有个关键NextGeneration是实现种群进行代繁殖操作它实现如下:
voidPopulation::NexGeneration{
Intercross;
Agamogenesis;
Mutant;
}
很简单地了Intercross、Agamogenesis和Mutant 3个成员下面以Intercross实现为例看看这 3个是如何实现繁殖操作: [Page]
voidPopulation::Intercross{
unsignediIntercrossTimes=_cast<unsigned>(
m_Colony.size*m_dIntercrossRate);
for(unsignedi=0;i<iIntercrossTimes;i){
unsignediChromoIdx1=RangeRandom<unsigned>(0,m_Colony.size);
unsignediChromoIdx2=RangeRandom<unsigned>(0,m_Colony.size);
(iChromoIdx1iChromoIdx2){
iChromoIdx2;
iChromoIdx2=(iChromoIdx2+1)%m_Colony.size;
}
Chromosome*Chromo1=Chromosome;
Chromosome*Chromo2=Chromosome;
::Intercross(*m_Colony[iChromoIdx1],*m_Colony[iChromoIdx2],
*Chromo1,*Chromo2);
m_Colony.push_back(Chromo1);
m_Colony.push_back(Chromo2);
} [Page]
}
交叉操作先根据交叉率计算出要进行多少次交叉繁殖然后在执行每次交叉繁殖时随机选择两个染色体前文Intercross算子实施交叉并将新产生两个新染色体加入到群体中复制和变异都是相似因篇幅所限就不在这里赘述了详见源码

实验结果
遗传算法是有效但费时个算法为了保证游戏运行流畅我们不可能在每次刷新时候都执行次遗传算法因此隔多久执行次遗传算法和控制遗传算法遗传代数是很重要demo中是在控球权发生改变时执行遗传算法为red-blue两个球队计算新站位方案同时为了游戏能比较流畅遗传代数控制在20左右
实验证明遗传算法对足球决策有非常好效果主要表现为:1、使用遗传算法后球员站位比较到位跑动积极比较少进入Wait状态结果就是当进攻或者防守时候很容易在周边发现支持者可以轻易将球传出这使得看起来球员的间配合非常有默契攻守两方都能打出更好组合战术增加了可观赏性简单来说就是加了遗传算法的后踢球越来越像人踢2、遗传算法加强了球队对抗能力未增加遗传算法时候运行本游戏20分钟总进球数在20~30在增加遗传算法后20分钟总进球数减少到10~20个主要原因是球员站位更加合理能根据当前局势变换站位这非常有效地抵抗了进攻单刀入球也大大减少了同时在变换站位时球员跑动积极能够很好地增加抢球和断球事件发生增强了两队竞争
遗传算法不仅可以用在球员站位策略上也可以用在确定传球路线、寻找最佳射门角度和障碍回避等多个方面在未来肯定会应用更多游戏中去欢迎大家齐学习、探讨

延伸阅读