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

用遗传算法加强足球游戏的人工智能广州网易互动娱乐 赖勇浩项目背景一直都想用遗传算法（Genetic Algorithms）实现足球游戏的人工智能，但因为实现一个足球游戏的对战平台太过于繁琐而没有动手。直到在Programming Game AI by Example一书中看到一个SimpleSoccer的demo（以下简称demo），实现了一个red-blue两队进行机器与机器对抗的简单足球游戏。在读过它的源码之后，我决定在demo上进行二次开发为它加入遗传算法，实验遗传算法在实时战略游戏（RTS）性质的体育游戏中的威力。demo的架构非常好，采用了状态机来实现游戏流程，并分开计算游戏决策。因此加入遗传算法非常容易，只要在原来的状态机中增加一两个状态即可。red-blue两个队伍相互对抗，每队有五位球员，其中一位是守门员。这个demo的足球规则是简化的，除了只有五个球员外，没有手球也没有越位等规则，甚至连边界球都没有球碰到边界就反弹回球场。简化的规则有利于我们简化实验的过程，不必把很多精力花费在过于复杂的规则上。 图一在demo的实现中，球场被分割为18块大小相等的区域（见图一）。每一个球员都一个属于自己的区域（称为HomeRegion），如图一中blue队的10号在自己的HomeRegion(Region5)中处于Wait状态（球员的状态之一）。当一个球员不处于进攻状态（Attacking）、助攻（SupportAttacker）、逐球（ChaseBall）、运球（Dribble）、踢球（KickBall）及返回（ReturnToHomeRegion）时，他就进入Wait状态等待球队发出的下一个行动指令。显然，就像人类进行足球比赛时需要排兵布阵一样，demo中球员站在哪个位置也相当重要，能否组织起有效的进攻或者防守，决定因素之一就是在合适的位置有没有球员可以快速有效地执行命令。在书中自带的demo中，球员的站位都是固定的，因此难以组织有效的进攻和防守，在某一时间段内容易形成一边倒的局势。使用遗传算法来对球员的站位进行决策分析，可以找出对当前局势就有利的位置编排方案。从而使得球队与球队之间的对抗趋于激烈、策略更加有效、攻守都更精彩。遗传算法概述遗传算法因为它在解决许多生产、生活中的问题上的卓越性能而经久不衰。随着计算机的计算能力日益增强和玩家对游戏中的人工智能的强烈需求，目前在单机游戏中已经开始应用遗传算法、人工神经网络等现代优化计算方法来增强游戏中的人工智能，并且形成了趋势。可见以后为加强机器的对抗性能，遗传算法、人工神经网络等都会越来越多地应用到游戏中。遗传算法是模拟自然界中的生物对自然界的适应而不断进化这一客观事实的算法。为了解决某一个问题，在遗传算法中，我们虚拟一个物种（即解的表现形式或者称为解的编码），并将其放到“自然环境”中天下繁殖、进化，根据优胜劣汰、适者生存的自然法则，繁衍若干代之后，种群中的佼佼者将非常适应“自然环境”，这个佼佼者就是我们求得的解了。关于生物学与遗传算法之间的概念的对应关系可以用表一的形式来表示：生物遗传概念遗传算法中的作用适者生存在算法停止时，最优目标值的解有最大的可能性被留住个体解染色体解的编码(二进制形式或者十进制形式的串即向量，或者字符串)基因解中每一分量的特征(如各分量的值)适应性适应函数的返回值群体选定的一组解(其中解的个数为群体的规模)种群根据适应函数选取的一组解交配通过交配原则产生一组新解的过程变异编码的某一分量发生变化的过程表一遗传算法的流程图如图二所示：图二遗传算法运行时，先生成初始群体（通常是随机产生一定数量的个体，这个数量就是群体的大小）；然后让群体繁殖下一代，繁殖的方式有交叉、复制和变异；经过繁殖后群体的数量增加，然后使用评估模块对每一个个体进行评估；如果群体中最佳个体已经足够优秀，那就跳出循环，返回最佳个体；否则判断是否已经繁殖了预定的代数，如果是就返回最佳个体，如果不是则淘汰一部分劣质个体并进入下一轮繁殖循环直至结束。在遗传算法的实现中，最重要的主要有三点：一是染色体的编码，即一个新物种怎么样来表示它，通常染色体是问题的一个可能解的特定格式的表示，通常以二进制或者十进制的方式编码；二是为染色体实现交叉、复制、变异等算子；三是估值模块的编写。下面以这三点为中心，谈谈demo中的遗传算法实现。染色体编码染色体编码的方式有很多种，常见的是二进制方法和十制字方式，也有字符串方式的。如著名的旅行商问题(TSP)里，假设有20个城市以019编码，那么7，6，9，819，3，0，4这个包含20个元素的序列A就可以看作是一个染色体，每一个元素Aj(0=j20)就是染色体的一个基因。这个染色体可以解码为从编号为7的城市出发，到达城市6、城市9等等，最后到达城市4完成20个城市的遍历。显然，这个序列是TSP的一个可能解，因此染色体就是问题的可能解的表示方式。回到我们的足球游戏中来，我们期望获得某一队的球员的合适站位，那么如果我们把四个球员以03编号(因为守门员不应离开禁区所以不必考虑他的位置)，那序列B14，11，12，6就是一个站位方案，表示0号球员站在ID为14的Region中，1号球员站在ID为11的Region中，等。序列B叫做一个可能解，序列B的编码方式即是我们染色体的编码方式十进制编码方式的一个序列。依照这个规则，我们编写代码如下：typedef unsigned int Genetype;class Chromosomeprivate:std:vector m_Geneme;int m_iScore;public:Chromosome();Chromosome();const std:vector& GetGeneme()constreturn 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 GTpublic:inline bool operator()(const Chromosome* c1, const Chromosome* c2)constreturn 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(0, GeneLen);unsigned int i = 0;for(; i IntercrossPoint; +i)c1.m_Genemei = p1.m_Genemei;c2.m_Genemei = p2.m_Genemei;for(; i GeneLen; +i)c1.m_Genemei = p2.m_Genemei;c2.m_Genemei = p1.m_Genemei;void Agamogenesis(const Chromosome& p, Chromosome& c)c.m_Geneme = p.m_Geneme;void Mutant(const Chromosome& p, Chromosome& c)unsigned int MutantPoint = RangeRandom(0, GeneLen);Genetype NewGene = RangeRandom(0,18);c.m_Geneme = p.m_Geneme;c.m_GenemeMutantPoint = NewGene;Intercross，Agamogenesis和Mutant三个函数分别对应交叉、复制和变异三个遗传算子。Intercross函数传入两个Chromosome的实例，随机选择一点进行交叉，组成两个新的染色体用作返回值。Agamogenesis函数传入一个Chromosome实例，返回一个相同的染色体，以保证优势的种群可以壮大，从而使得遗传算法可以在有限的运行时间内收敛。Mutant函数传入一个Chromosome实例，随机选择一个元素（分量）赋以一个随机的Region ID，返回这一改变后的染色体，变异可以使得遗传算法跳出局部最优，趋近全局最优。三个遗传算子的操作结果如表二所示：遗传算子输入的染色体输出的染色体Intercross17,9,4,316,13,7,917,9,7,916,13,4,3假定元素2为交叉点Agamogenesis17,9,4,317,9,4,3Mutant17,9,4,317,9,7,3假定元素2为变异点表二估值模块通俗一点说，估值模块就是阎罗王，个体淘汰与否就得看估值模块的脸色了。估值模块判定每一个染色体对“自然环境”的适应度：如前文关于TSP的染色体，它的估值函数就返回遍历20个城市要走过的路程的总长度，总长度越短的染色体适应度越高，反之则越低。在足球游戏中，估值模块就没有这么简单了，一个染色体就是一个站位组合，这个组合的优劣是与当前局势有很大关系，如球的位置、对方球员的站位、已方球员的站位和控球权等有关，综合以上各种因素，编写如下估值模块：int Environment: Evaluate (const std:vector& candidate)int iValue = 0;for( unsigned int i = 0; i CrossCostPerRgn;/有利于防守？iValue += GetDefendValue(candidatei, m_OppGeneme);/有利于进攻？iValue += GetAttackValue(candidatei, m_OppGeneme);/有利于抢球或者保球？if(m_iTeamColor = m_iControllingTeam& m_iBallRgnIdx = candidatei)iValue += m_pPrm-PlyrKeepBallValue;else if(m_iTeamColor != m_iControllingTeam& m_iBallRgnIdx = candidatei)iValue += m_pPrm-PlyrChaseBallValue;return iValue;int Environment:GetDefendValue(const int iPlyrIdx, const std:vector& OppGeneme)int iValue = 0;int OppInMyGround = 0;std:vector:const_iterator ci = OppGeneme.begin();for(; ci != OppGeneme.end(); +ci)if(IsInMyGround(*ci)+OppInMyGround;if(OppInMyGround 1 )if(IsInMyGround(static_cast(iPlyrIdx)iValue += m_pPrm-DefendValuePerPlyr;elseiValue += m_pPrm-DefendValuePerPlyr * 0.5;elseiValue += m_pPrm-DefendValuePerPlyr * 0.8;if(m_iControllingTeam = m_iTeamColor)iValue *= 1.2;elseiValue *= 0.8;return iValue;int Environment:GetAttackValue(const int iPlyrIdx, const std:vector& OppGeneme)int iValue = 0;int OppNoInMyGround = 0;std:vector:const_iterator ci = OppGeneme.begin();for(; ci != OppGeneme.end(); +ci)if( !IsInMyGround(*ci)+OppNoInMyGround;if( OppNoInMyGround 2 )if(IsInMyGround(static_cast(iPlyrIdx)iValue += m_pPrm-AttackValuePerPlyr * 0.5;elseiValue += m_pPrm-AttackValuePerPlyr;if(m_iControllingTeam = m_iTeamColor)iValue *= 1.2;elseiValue *= 0.8;return iValue;Evaluate函数主要从以下几方面来对染色体进行评估：从当前位置到目的位置所要经过的路径的代价是否有利于进攻或者防守是否有利于持球或者抢球其中计算是否有利于进攻或者防守是通过计算两个球队间球员的位置来判断的：对方的球员在已方半场时如果已方球员的目的位置也在已方半场就有利于防守；对方的球员在已方半场时如果已方球员的目的位置在对方半场则有利于进攻。通过这一简单的估值模块，可以使得遗传算法在淘汰劣质个体时有法可依，从而能够收敛得到较优解。通过精细化估值模块考虑更多因素（如对方球队可能采取的策略等）可使遗传算法的收敛速度加快，在真实的游戏项目中必定会使用精细化的估值模块的。程序架构确定了遗传算法的编码方式、实现了三个遗传算子和估值模块之后，这个遗传算法基本上就完成了。但我们还没有看到它是怎么初始化种群、怎么繁殖和怎么淘汰劣质个体的，这时候有必要了解一下遗传算法的程序架构。在demo中，我们设计的遗传算法的架构如图三：EnvironmentPopulationChromosomeGene图三Environment是自然环境的模拟，它实现了估值函数、繁殖迭代的控制和环境的初始化和销毁等功能，最重要的是它包含了一种成员变量Population的实例。每一个Environment还有一个算法参数包装类ParamLoader的实例指针m_pPrm用以存取配置文件。每一个球队拥有一个Environment实例，专门用以计算适合本队的球员位置编排。简化的Environment的声明如下：class Environmentprivate:ParamLoader* m_pPrm;Population m_Population;private:int Evaluate(const std:vector& candidate);int GetDefendValue(const int iPlyrIdx, const std:vector& OppGeneme);int GetAttackValue(const int iPlyrIdx, const std:vector& OppGeneme);bool IsInMyGround(unsigned int iRgnIdx)double DistOfTwoRgn(unsigned int iRgnIdx1, unsigned int iRgnIdx2)public:const std:vector GetBestGeneme();当调用GetBestGnenme()时，遗传算法便开始运行，GetBestGeneme()控制繁殖迭代的次数，并挑选最优的染色体个体，它的实现如下：const std:vector Environment:GetBestGeneme()for(unsigned int i = 0; i GAGeneration; +i)m_Population.NexGeneration();unsigned int uiPopulationSize = m_Population.GetPopulationSize();for(unsigned int i = 0; i ColonySize);return m_Population.GetBestGeneme();Population是物种群体的抽象，它实现一个最重要的函数就是NextGeneration()，Environment通过调用这个函数让群体执行繁殖任务；另一个重要的函数就是KeepColonySize()，这个函数淘汰掉劣质的个体，让竞争力较强的个体进入下一轮繁殖。简化的Population声明如下：class Populationprivate:std:vector m_Colony;unsigned int m_iColonySize;double m_dIntercrossRate,m_dAgamogenesisRate,m_dMutantRate;std:vector m_BestGeneme;public:void Initial(unsigned int iColonySize,double dIntercrossRate,double dAgamogenesisRate,double dMutantRate);void Release();void NexGeneration();void KeepColonySize(unsigned int size = 100)private:void Intercross();void Agamogenesis();void Mutant();Population用std:vector容器保存物种的所有个体（m_iColonySize个Chromosome的实例），m_dIntercrossRate、m_dAgamogenesisRate和m_dMutantRate三个变量分别是交叉率、复制率和变异率，其中染色体交叉是自然界中生物繁殖的最常见方式，可以保证优秀的基因可以遗传到下一代或者有很大的机会使得部分优秀基因和另一部分优秀基因结合为一个非常优秀的染色体，因此交叉率比较高，一般取值在0.10.5之间；复制率即是无性繁殖的机率，无性繁殖在自然界中是普遍存在的正常现象（如植物中的落地生根和动物中的蚯蚓），无性繁殖可以确保优秀的个体有一定的机会壮大自己的种群，一般复制率取值在0.030.1之间；变异在自然界中是发生机率极小的事件，而且变异多是恶性的，所以变异率的取值范围在0.0050.05之间，但变异可以让遗传算法跳出局部最优，因而是必须的一个操作算子。m_iColonySize是种群的大小，种群越大，找到解的机会越大，但花费的时间也相对比较多，一般设为可以接受的固定值，也可以编写与问题难度相关的函数来决定，本实验使用m_iColonySize=100的固定值方式。Population另外还有一个关键函数NextGeneration()是实现种群进行一代繁殖操作的，它的实现如下：void Population:NexGeneration()Intercross();Agamogenesis();Mutant();很简单地调用了Intercross()、Agamogenesis()和Mutant()三个成员函数，下面以Intercross()的实现为例看看这三个函数是怎么实现繁殖操作的：void Population:Intercross()unsigned int iIntercrossTimes = static_cast(m_Colony.size() * m_dIntercrossRate);for(unsigned int i = 0; i iIntercrossTimes; +i)unsigned int iChromoIdx1 = RangeRandom(0, m_Colony.size();unsigned int iChromoIdx2 = RangeRandom(0, m_Colony.size();if(iChromoIdx1 = iChromoIdx2)+iChromoIdx2;iChromoIdx2 = (iChromoIdx2 + 1) % m_Colony.size();Chromosome* Chromo1 = new Chromosome;Chromosome* Chromo2 = new Chromosome;:Intercross(*m_ColonyiChromoIdx1,