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

用遗传算法加强足球游戏的人工智能 广州网易互动娱乐 赖勇浩 项目背景 一直都想用遗传算法（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个城市以[0…19]编码，那么[7，6，9，8…19，3，0，4]这个包含20个元素的序列A就可以看作是一个染色体，每一个元