用遗传算法加强足球游戏的人工智能

终于等够了三个月，杂志的约定已经到期，可以把这篇文章发表到网络跟大家分享。本文原发表于《游戏创造》杂志www.chinagcn.com，如蒙转载，请保留原文和本声明完整，并注明转载自恋花蝶的博客：http://blog.csdn.net/lanphaday

用遗传算法加强足球游戏的人工智能

广州网易互动娱乐 赖勇浩

项目背景

一直都想用遗传算法（Genetic Algorithms）实现足球游戏的人工智能，但因为实现一个足球游戏的对战平台太过于繁琐而没有动手。直到在《Programming Game AI by Example》一书中看到一个SimpleSoccer的demo（以下简称demo），实现了一个red-blue两队进行机器与机器对抗的简单足球游戏。在读过它的源码之后，我决定在demo上进行二次开发——为它加入遗传算法，实验遗传算法在实时战略游戏（RTS）性质的体育游戏中的威力。

demo的架构非常好，采用了状态机来实现游戏流程，并分开计算游戏决策。因此加入遗传算法非常容易，只要在原来的状态机中增加一两个状态即可。red-blue两个队伍相互对抗，每队有五位球员，其中一位是守门员。这个demo的足球规则是简化的，除了只有五个球员外，没有手球也没有越位等规则，甚至连边界球都没有——球碰到边界就反弹回球场。简化的规则有利于我们简化实验的过程，不必把很多精力花费在过于复杂的规则上。<shapetype id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"></shapetype>

<shapetype coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"><a target="_blank" href="http://p.blog.csdn.net/images/p_blog_csdn_net/lanphaday/277551/o_4543569074063472462.jpg"><img alt="" src="http://p.blog.csdn.net/images/p_blog_csdn_net/lanphaday/277551/o_4543569074063472462.jpg"></a></shapetype>

<shapetype coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"></shapetype>

<shapetype coordsize="21600,21600" o:spt="75" o:preferrelative="t" path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"></path><lock v:ext="edit" aspectratio="t"></lock></shapetype><shape id="_x0000_i1025" style="WIDTH: 415.5pt; HEIGHT: 237pt" type="#_x0000_t75"><imagedata src="http://p.blog.csdn.net/images/p_blog_csdn_net/lanphaday/209780/t_blog_ss_board.jpg" o:title="sc"></imagedata></shape>

图一

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

遗传算法概述

遗传算法因为它在解决许多生产、生活中的问题上的卓越性能而经久不衰。随着计算机的计算能力日益增强和玩家对游戏中的人工智能的强烈需求，目前在单机游戏中已经开始应用遗传算法、人工神经网络等现代优化计算方法来增强游戏中的人工智能，并且形成了趋势。可见以后为加强机器的对抗性能，遗传算法、人工神经网络等都会越来越多地应用到游戏中。

遗传算法是模拟自然界中的生物对自然界的适应而不断进化这一客观事实的算法。为了解决某一个问题，在遗传算法中，我们虚拟一个物种（即解的表现形式或者称为解的编码），并将其放到“自然环境”中天下繁殖、进化，根据优胜劣汰、适者生存的自然法则，繁衍若干代之后，种群中的佼佼者将非常适应“自然环境”，这个佼佼者就是我们求得的解了。关于生物学与遗传算法之间的概念的对应关系可以用表一的形式来表示：

生物遗传概念	遗传算法中的作用
适者生存	在算法停止时，最优目标值的解有最大的可能性被留住
个体	解
染色体	解的编码(二进制形式或者十进制形式的串即向量，或者字符串)
基因	解中每一分量的特征(如各分量的值)
适应性	适应函数的返回值
群体	选定的一组解(其中解的个数为群体的规模)
种群	根据适应函数选取的一组解
交配	通过交配原则产生一组新解的过程
变异	编码的某一分量发生变化的过程

表一

遗传算法的流程图如图二所示：

<shape id="_x0000_i1026" style="WIDTH: 254.25pt; HEIGHT: 336.75pt" type="#_x0000_t75" o:ole=""><imagedata src="http://p.blog.csdn.net/images/p_blog_csdn_net/lanphaday/209780/t_blog_ss_lc.jpg" o:title=""><font size="3"></font></imagedata></shape>

图二

遗传算法运行时，先生成初始群体（通常是随机产生一定数量的个体，这个数量就是群体的大小）；然后让群体繁殖下一代，繁殖的方式有交叉、复制和变异；经过繁殖后群体的数量增加，然后使用评估模块对每一个个体进行评估；如果群体中最佳个体已经足够优秀，那就跳出循环，返回最佳个体；否则判断是否已经繁殖了预定的代数，如果是就返回最佳个体，如果不是则淘汰一部分劣质个体并进入下一轮繁殖循环直至结束。

在遗传算法的实现中，最重要的主要有三点：一是染色体的编码，即一个新物种怎么样来表示它，通常染色体是问题的一个可能解的特定格式的表示，通常以二进制或者十进制的方式编码；二是为染色体实现交叉、复制、变异等算子；三是估值模块的编写。下面以这三点为中心，谈谈demo中的遗传算法实现。

染色体编码

染色体编码的方式有很多种，常见的是二进制方法和十制字方式，也有字符串方式的。如著名的旅行商问题(TSP)里，假设有20个城市以[0…19]编码，那么[7，6，9，8…19，3，0，4]这个包含20个元素的序列A就可以看作是一个染色体，每一个元素Aj(0<=j<20)就是染色体的一个基因。这个染色体可以解码为从编号为7的城市出发，到达城市6、城市9等等，最后到达城市4完成20个城市的遍历。显然，这个序列是TSP的一个可能解，因此染色体就是问题的可能解的表示方式。回到我们的足球游戏中来，我们期望获得某一队的球员的合适站位，那么如果我们把四个球员以[0…3]编号(因为守门员不应离开禁区所以不必考虑他的位置)，那序列B[14，11，12，6]就是一个站位方案，表示0号球员站在ID为14的Region中，1号球员站在ID为11的Region中，等。序列B叫做一个可能解，序列B的编码方式即是我们染色体的编码方式——十进制编码方式的一个序列。依照这个规则，我们编写代码如下：

typedef unsigned int Genetype;

class Chromosome{

private:

std::vector<Genetype> m_Geneme;

int m_iScore;

public:

Chromosome();

~Chromosome(){};

const std::vector<Genetype>& GetGeneme()const{return m_Geneme;}

void SetScore(int iScore){m_iScore = iScore;}

friend void Intercross(const Chromosome& p1, const Chromosome& p2,

Chromosome& c1, Chromosome& c2);

friend void Agamogenesis(const Chromosome& p, Chromosome& c);

friend void Mutant(const Chromosome& p, Chromosome& c);

friend class GT;

};

class GT{

public:

inline bool operator()(const Chromosome* c1, const Chromosome* c2)const{

return c1->m_iScore > c2->m_iScore;

}

};

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

遗传算子

交叉、复制和变异三个遗传算子是遗传算法能够找到最优解的途径。这三个遗传算子模拟了自然界的物种交配和生殖的方式，为产生新的可行解提供了有效手段(见表一)。遗传算子声明为染色体类Chromosome的友元函数是为了方便操作它的私有变量，实现如下：

void Intercross(const Chromosome& p1, const Chromosome& p2,

Chromosome& c1, Chromosome& c2){

unsigned int IntercrossPoint = RangeRandom<unsigned int>(0, GeneLen);

unsigned int i = 0;

for(; i < IntercrossPoint; ++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];

}

}

void Agamogenesis(const Chromosome& p, Chromosome& c){

c.m_Geneme = p.m_Geneme;

}

void Mutant(const Chromosome& p, Chromosome& c){

unsigned int MutantPoint = RangeRandom<unsigned int>(0, GeneLen);

Genetype NewGene = RangeRandom<Genetype>(0,18);

c.m_Geneme = p.m_Geneme;

c.m_Geneme[MutantPoint] = NewGene;

}

Intercross，Agamogenesis和Mutant三个函数分别对应交叉、复制和变异三个遗传算子。Intercross函数传入两个Chromosome的实例，随机选择一点进行交叉，组成两个新的染色体用作返回值。Agamogenesis函数传入一个Chromosome实例，返回一个相同的染色体，以保证优势的种群可以壮大，从而使得遗传算法可以在有限的运行时间内收敛。Mutant函数传入一个Chromosome实例，随机选择一个元素（分量）赋以一个随机的Region ID，返回这一改变后的染色体，变异可以使得遗传算法跳出局部最优，趋近全局最优。三个遗传算子的操作结果如表二所示：

遗传算子	输入的染色体	输出的染色体
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为变异点

表二

估值模块

通俗一点说，估值模块就是阎罗王，个体淘汰与否就得看估值模块的脸色了。估值模块判定每一个染色体对“自然环境”的适应度：如前文关于TSP的染色体，它的估值函数就返回遍历20个城市要走过的路程的总长度，总长度越短的染色体适应度越高，反之则越低。在足球游戏中，估值模块就没有这么简单了，一个染色体就是一个站位组合，这个组合的优劣是与当前局势有很大关系，如球的位置、对方球员的站位、已方球员的站位和控球权等有关，综合以上各种因素，编写如下估值模块：

int Environment:: Evaluate (const std::vector<Genetype>& candidate){

int iValue = 0;

for( unsigned int i = 0; i < GeneLen; ++i){

//减去移动需要的损耗

iValue -= DistOfTwoRgn(candidate[i], m_CurrGeneme[i]) * m_pPrm->CrossCostPerRgn;

//有利于防守？

iValue += GetDefendValue(candidate[i], m_OppGeneme);

//有利于进攻？

iValue += GetAttackValue(candidate[i], m_OppGeneme);

//有利于抢球或者保球？

if(m_iTeamColor == m_iControllingTeam

&& m_iBallRgnIdx == candidate[i])

iValue += m_pPrm->PlyrKeepBallValue;

else if(m_iTeamColor != m_iControllingTeam

&& m_iBallRgnIdx == candidate[i])

iValue += m_pPrm->PlyrChaseBallValue;

}

return iValue;

}

int Environment::GetDefendValue(const int iPlyrIdx, const std::vector<Genetype>& OppGeneme){

int iValue = 0;

int OppInMyGround = 0;

std::vector<Genetype>::const_iterator ci = OppGeneme.begin();

for(; ci != OppGeneme.end(); ++ci){

if(IsInMyGround(*ci))

++OppInMyGround;

}

if(OppInMyGround > 1 ){

if(IsInMyGround(static_cast<unsigned int>(iPlyrIdx)))

iValue += m_pPrm->DefendValuePerPlyr;

else

iValue += m_pPrm->DefendValuePerPlyr * 0.5;

}

else{

iValue += m_pPrm->DefendValuePerPlyr * 0.8;

}

if(m_iControllingTeam == m_iTeamColor)

iValue *= 1.2;

else

iValue *= 0.8;

return iValue;

}

int Environment::GetAttackValue(const int iPlyrIdx, const std::vector<Genetype>& OppGeneme){

int iValue = 0;

int OppNoInMyGround = 0;

std::vector<Genetype>::const_iterator ci = OppGeneme.begin();

for(; ci != OppGeneme.end(); ++ci){

if( !IsInMyGround(*ci))

++OppNoInMyGround;

}

if( OppNoInMyGround > 2 ){

if(IsInMyGround(static_cast<unsigned int>(iPlyrIdx)))

iValue += m_pPrm->AttackValuePerPlyr * 0.5;

else

iValue += m_pPrm->AttackValuePerPlyr;

}

if(m_iControllingTeam == m_iTeamColor)

iValue *= 1.2;

else

iValue *= 0.8;

return iValue;

}

Evaluate函数主要从以下几方面来对染色体进行评估：

·从当前位置到目的位置所要经过的路径的代价

·是否有利于进攻或者防守

·是否有利于持球或者抢球

其中计算是否有利于进攻或者防守是通过计算两个球队间球员的位置来判断的：对方的球员在已方半场时如果已方球员的目的位置也在已方半场就有利于防守；对方的球员在已方半场时如果已方球员的目的位置在对方半场则有利于进攻。通过这一简单的估值模块，可以使得遗传算法在淘汰劣质个体时有法可依，从而能够收敛得到较优解。通过精细化估值模块考虑更多因素（如对方球队可能采取的策略等）可使遗传算法的收敛速度加快，在真实的游戏项目中必定会使用精细化的估值模块的。

程序架构

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

<group id="_x0000_s1026" style="MARGIN-TOP: 0px; Z-INDEX: 1; MARGIN-LEFT: 0px; WIDTH: 414pt; POSITION: absolute; HEIGHT: 241.8pt; mso-position-horizontal-relative: char; mso-position-vertical-relative: line" coordsize="8280,4836" coordorigin="1800,2334"><lock v:ext="edit" aspectratio="t" rotation="t" position="t"></lock><shape id="_x0000_s1027" style="LEFT: 1800px; WIDTH: 8280px; POSITION: absolute; TOP: 2334px; HEIGHT: 4836px" o:preferrelative="f" type="#_x0000_t75"><font size="3"><fill o:detectmouseclick="t"></fill><path o:extrusionok="t" o:connecttype="none"></path><lock text="t" v:ext="edit"></lock></font></shape><group id="_x0000_s1028" style="LEFT: 2232px; WIDTH: 7561px; POSITION: absolute; TOP: 2490px; HEIGHT: 4524px" coordsize="7561,4524" coordorigin="2232,2490"><rect id="_x0000_s1029" style="LEFT: 2232px; WIDTH: 7561px; POSITION: absolute; TOP: 2490px; HEIGHT: 4524px" fillcolor="silver"><font size="3"></font></rect><rect id="_x0000_s1030" style="LEFT: 2772px; WIDTH: 6299px; POSITION: absolute; TOP: 3426px; HEIGHT: 3276px" fillcolor="#969696"><font size="3"></font></rect><rect id="_x0000_s1031" style="LEFT: 3852px; WIDTH: 4320px; POSITION: absolute; TOP: 4205px; HEIGHT: 2185px" fillcolor="gray"><font size="3"></font></rect><rect id="_x0000_s1032" style="LEFT: 4931px; WIDTH: 2521px; POSITION: absolute; TOP: 4986px; HEIGHT: 780px" fillcolor="#333"><font size="3"></font></rect><shapetype id="_x0000_t202" coordsize="21600,21600" o:spt="202" path="m0,0l0,21600,21600,21600,21600,0xe"><stroke joinstyle="miter"></stroke><path gradientshapeok="t" o:connecttype="rect"></path></shapetype><shape id="_x0000_s1033" style="LEFT: 5292px; WIDTH: 1440px; POSITION: absolute; TOP: 2646px; HEIGHT: 624px" stroked="f" type="#_x0000_t202" fillcolor="silver"><textbox style="mso-next-textbox: #_x0000_s1033"><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-LEFT-COLOR: #d4d0c8; BORDER-BOTTOM-COLOR: #d4d0c8; BORDER-TOP-COLOR: #d4d0c8; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #d4d0c8"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span lang="EN-US"><font face="Times New Roman" size="3">Environment</font></span></p> </div> </td> </tr></tbody></table></textbox></shape><shape id="_x0000_s1034" style="LEFT: 5292px; WIDTH: 1440px; POSITION: absolute; TOP: 3582px; HEIGHT: 468px" stroked="f" type="#_x0000_t202" fillcolor="#969696"><textbox><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-LEFT-COLOR: #d4d0c8; BORDER-BOTTOM-COLOR: #d4d0c8; BORDER-TOP-COLOR: #d4d0c8; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #d4d0c8"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span lang="EN-US"><font face="Times New Roman" size="3">Population</font></span></p> </div> </td> </tr></tbody></table></textbox></shape><shape id="_x0000_s1035" style="LEFT: 5292px; WIDTH: 1440px; POSITION: absolute; TOP: 4404px; HEIGHT: 582px" stroked="f" type="#_x0000_t202" fillcolor="gray"><textbox><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-LEFT-COLOR: #d4d0c8; BORDER-BOTTOM-COLOR: #d4d0c8; BORDER-TOP-COLOR: #d4d0c8; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #d4d0c8"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span lang="EN-US"><font face="Times New Roman" size="3">Chromosome</font></span></p> </div> </td> </tr></tbody></table></textbox></shape><shape id="_x0000_s1036" style="LEFT: 5292px; WIDTH: 1440px; POSITION: absolute; TOP: 5142px; HEIGHT: 468px" stroked="f" type="#_x0000_t202" fillcolor="#333"><textbox><table cellspacing="0" cellpadding="0" width="100%"><tbody><tr> <td style="BORDER-LEFT-COLOR: #d4d0c8; BORDER-BOTTOM-COLOR: #d4d0c8; BORDER-TOP-COLOR: #d4d0c8; BACKGROUND-COLOR: transparent; BORDER-RIGHT-COLOR: #d4d0c8"> <div> <p class="MsoNormal" style="MARGIN: 0cm 0cm 0pt"><span lang="EN-US"><font face="Times New Roman" size="3">Gene</font></span></p> </div> </td> </tr></tbody></table></textbox></shape></group><anchorlock></anchorlock></group><shape id="_x0000_i1027" style="WIDTH: 414pt; HEIGHT: 241.5pt" type="#_x0000_t75"><imagedata croptop="-65520f" cropbottom="65520f"></imagedata><lock v:ext="edit" rotation="t" position="t"></lock></shape>

图三