虫群版天网：伯克利如何“主宰”了“2010星际争霸人工智能挑战赛”

房间里洋溢着庆祝的喜悦，Oriol也不例外。打败他的是一个计算机人工智能程序，名叫伯克利“主宰”，由我们小组花了几个月的时间开发而成。“主宰”是我们参加“2010星际争霸人工智能挑战赛”的作品。在数十场比赛后，它终于第一次击败了我们的人类星际高手。

我们觉得很光荣，自尊心得到极大满足（不是John Henry那种），但我们并没有时间来细细品味这一切。距离提交代码的最后期限只剩三天了，我们还有很多清理和调试的工作。Dan Klein教授，我们的顾问、将军、教练和动力，微笑着转向了白板。他划掉了我们还需要测试的二十个场景之一。

“好了，”他说。“我们可以打败大脚机器人的战术了。下面来测哪一个？”

下面就是我们如何创造了伯克利“主宰”程序以及它背后的技术的故事。

迫不及待的想要改变未来

《星际争霸》是史上最流行的电子游戏，来自一家伟大的公司一款伟大的作品。它对玩家的技巧有很高的要求，是职业游戏联赛的主要项目。在韩国，《星际争霸》非常流行，其职业选手的合同收入达六位数，游戏比赛会在国家电视台上进行直播。

这对于人工智能来说也恰好是一个非常具有挑战性的舞台，一个成功的《星际争霸》人工智能必须解决很多困难的问题。在伯克利教授人工智能入门课程的Dan说：“我能一一列举这门课向你展示的所有概念以及它们分别在《星际争霸》以及我们的程序中的应用。”

《星际争霸》发布于1998年，在视频游戏领域看来这差不多是八百年以前了。多年以来，游戏的开发商暴雪一直在更新它，使得《星际争霸》成为史上制作最精良也是最平衡的即时战略游戏之一。游戏有三个种族：拥有我们熟悉的坦克和星舰人族（Terran），生物群落形态的虫族（Zerg）和科技发达、兵种强大而昂贵的神族（Protoss）。每个种族都有不同的单位和游戏理念，但没有任何一个种族或是兵种组合是无敌的。玩家的技巧、创造力和随机应变的能力都能决定胜负。

精细复杂的设计使得《星际争霸》成为人工智能研究的理想环境。在即时战略游戏中，所有事件都是实时的，玩家的指令会被立即执行。玩家需要收集资源来生产单位进行战斗。地图被“战争迷雾”所笼罩，敌方的单位和建筑都只有在己方的单位或建筑物的视线之内才可见。玩家需要采集并分配资源，生产单位，移动单位进行战斗，侦查、分析并对敌方的行动作出响应，这些都是实时的。对于计算机来说这些都是难题。

Dan有时会把《星际争霸》和那些曾经驱动了人工智能研究前进的游戏作比较。“国际象棋难在你必须能看的远，围棋难在每一步棋的可能性太多，而扑克则难在不确定性。”他说。“但在《星际争霸》中你每时每刻都面临着所有这些问题，而你能够用来计算的时间却非常少。”

人类高手通过培训和练习来掌握丰富的技巧和知识以解决这些问题。我们不可能简单的把这些人类掌握的知识移植到人工智能中去，因为它需要能够主动的判断游戏的形势并决定未来的行动。创建一个能够与人类选手匹敌的《星际争霸》人工智能需要把现在计算机的能力所及向前推进一大步，并且可能在游戏以外的领域得到应用。

“星际争霸人工智能挑战赛”的目的是以《星际争霸》为环境推进人工智能的研究。人工智能研究人员在过去也曾使用过即时战略游戏，但都受限于可用的技术。开源的游戏有很多缺陷并且缺乏测试，而像《星际争霸》这样的商业游戏则是封闭的。

在2009年初发布的母巢之战API（BWAPI）改变了这一切。BWAPI是由一群狂热的游戏爱好者开发的开源工具，使程序能够直接访问游戏。加州圣克鲁斯智能表现力实验室的学生Ben Weber一直致力于基于即时战略游戏的研究。他意识到了《星际争霸》和BWAPI对他的工作的影响以及对于人工智能领域的价值。于是他着手举办了这项星际争霸人工智能比赛，以期能够激起大家的兴趣并开启研究的进程。

比赛的消息正式宣布于2009年11月，并迅速在游戏类的网站和博客中传播开来：第一届“星际争霸人工智能挑战赛”将于2010年10月在斯坦福大学的“2010人工智能与互动数字娱乐大会”上举行。

课程：星际争霸 101

当Dan和他实验室的学生听说这项赛事时，他们立即兴奋了。“当我听说‘有API能够访问《星际争霸》’时，”他说，“我就知道有好玩的东西可以研究了，科学研究和课堂项目都有了很多新的空间。”

第一个挑战是定义问题域：一个星际玩家需要完成哪些操作，如何把这些操作转化成人工智能的行为？

此时小组的成员包括Dan和一些他的博士生，以及伯克利人工智能与机器人研究实验室的几个研究生（包括本文的作者）。这群人熟悉人工智能但却不会玩《星际争霸》，而伯克利的计算机科学的本科生中则有许多喜爱《星际争霸》的玩家。

为了填补这一鸿沟，Dan开设了一门介绍人工智能概念的课程，并在课上为比赛设计和创建我们的程序。这门课给了我们分享知识并探索如何将游戏中的问题转化为算法可以解决的具体问题的机会。这也正是展现和解释人工智能概念的非常好的方法。

这门课一经宣布便受到了热烈的回应，并且取得了巨大的成功。我们花了一学期的学习《星际争霸》和人工智能，探索算法和框架，并尽可能多的尝试了很多不同的东西。我们从中获得的宝贵的经验对我们的人工智能的进化非常有帮助。“可以肯定地说，没有这门课我们不可能做的这么好。”丹赛后说。

在这门课的最后，我们已经把游戏对人工智能的要求归结为三个方面的问题。首先，程序需要采集并管理资源并在何时建造什么建筑或单位。用游戏术语来说，这叫做“宏观管理”，或者叫“大局观”。它本质上是一个规划与优化的问题。

“你需要采集更多的vespene气体”

我们的人工智能要做的的第一件事就是收集资源并生产建筑和单位。这既非常容易又十分困难。开局策略，也就是开局时建筑物和单位的建造顺序，在星际社区中已经是被详细研究过的话题了。和象棋一样，不同的开局意味着玩家将会在游戏中期采取不同的策略。早期低级兵种的rush、空中骚扰或是中后期暴兵都会有不同的开局。

这些开局都是经过高度优化过的，用若干脚本或是有限自动机的方式简单的把它们直接硬编码到程序的“宏观规划”中去是十分诱人的想法。这正是《星际争霸》的内置AI以及很多其他游戏AI的工作方式：直接将人类专家的知识编码为一连串的动作或预定义的转型。生产坦克，并在对方生产空军单位的时候生产防空单位。如果敌人建造隐形单位，则生产探测器，等等。我们的人工智能的早期版本的确是采取了这种策略，用人族暴坦克。或许我们的第一个教训就是这种方法不靠谱。

我们这一课是在尴尬中度过的。我们的终极目标和深蓝挑战卡斯帕罗夫是类似的，而《星际争霸》正是一块人类选手表现的很优秀而人工智能则很糟糕的领域。因此，检验和改进人工智能的唯一办法就是让它和人类玩家对战。带着已经能够打败内置AI的自豪，我们在课堂上让我们的人工智能和John Blitzer玩一局。他是Dan的一名博士后，经常在iCCup上玩天阶。

这是一场灾难。

Blitzer使用的战术叫“偷气矿”，就是让一个农民到我们的人工智能的家里把气矿修了。这下程序只能在将对手的气矿建筑打掉并建造了自己的气矿建筑之后才能开始采集气体。我们完全没有预料到这种战术，而我们的AI，由于战术中的建筑物非常依赖于气体资源，完全陷入了一片混乱。当人工智能还在等待气体来建造坦克时，Blitzer的大军就已经兵临城下了。我们曾认为Blitzer也许会用更好的战术击败人工智能的坦克大军，但我们从未想过比赛也许根本进行不到那个份上。

“很抱歉，比赛和原计划略有不同，”Blitzer在赛后的一封邮件中分析了比赛。实际情况远不是这样。它给我们上了宝贵的一课：人工智能必须足够健壮，能够容忍干扰，否则它就会被卡住。

想让AI变得强壮，一种办法是让人类程序员预见到所有可能性并将应对措施教给它。完全不这么做很难，但是在《星际争霸》这么复杂的系统中，事先预料到所有的场景是不可能的。这也是为什么内置的AI很容易被打败的原因：只要找到了它的缺陷就可以反复利用。

下面的视频就是一个这样的例子。视频的主角是“神奇农民”Sparky。它是游戏早期我们的人工智能派出的一个探路农民，实际上也是我们这支队伍的吉祥物。“偷气矿”战术让我们对非常规早期战术重视起来，并且吸收了一部分到我们的人工智能中去。

应对Sparky的小把戏只需要一些人工干预，但管理资源和规划建造顺序则需要更灵活的策略。最终我们的建造规划器和资源分配器的结构和操作系统的调度器很相似。我们把动作和进程相对应。不同的动作需要向“主宰”的中央控制器请求不同的资源，比如水晶、气体或是单位。中央控制器负责根据优先级来满足不同动作的需求。这种体系结构给了我们很大的灵活性。

David Hall是Dan小组的博士生，也是小组长之一。建造规划器——“我们基本上考虑到了所有当前能做的事情，然后选那个最好的”，他说。我们不会使用固定的建筑和单位建造顺序，而是给出最需要的建筑以及单位的组合，让规划器自己去尽可能的达到它。

这样产生的建造顺序比固定顺序要强壮的多。人工智能不会再被无法预料到的敌方行动卡住。当对手成功的偷到了气矿的时候，我们的AI会去开另一片有气的新矿或是在恢复采气之前建造那些不需要气体的单位。

最终，规划器产生的建造顺序和我们在网上能够看到的高手开局非常接近，而且它具有变通的能力。要赢得《星际争霸》比赛，这种灵活性和强壮性是必不可少的，无论是对于人类选手还是对于人工智能而言。开发过程的主题就是一次又一次在人工智能中将游戏各方面的人工行为的替换为能够推理和决策的工具。

“我成为主宰之时，就是虫群统御天下之日”

到2010年夏天，建筑部分的基础设施终于完工，到了研究如何使用这些建筑的时候了。人工智能要能在战斗中控制己方的部队，选择进攻的目标并按照战术移动己方的单位。但现在我们腹背受敌：挑战赛的最后提交期限是九月，我们快没时间了。

我们必须有些节制。Dan的另一位博士生也是小组长David Burkett说：“我们发现控制混合部队有困难，因此生产多兵种的部队得不偿失。所以我们开始自问，哪个兵种的性价比最高？”

我们把注意力集中在了虫族的飞龙：既能对空也能对地的高速类龙生物。他们的机动性无与伦比，我们认为用计算机控制他们特别合适。飞龙价廉物美，但在比赛中很少看到人类选手大量使用他们，因为只有叠起来的飞龙才比较好操作，但是这样又容易被面攻击（区域伤害，而非单体伤害）大量杀伤。而计算机则不会有这样的局限。

另外，我们一直想设计一个虫族AI，并且把它命名为“主宰”，即《星际争霸》同名小说中控制虫群的大脑。Dan提出了唯一可能的反对意见：“你知道，从申请研究经费的角度来说，如果我们的AI控制的是人类力量而不是一群不断流口水的外星异形是不是更好一些……”

理论上来说，电脑没有人类的局限性，应该能够同时控制多个单位。事实上，一个普遍的误解认为，《星际争霸》的实时性意味着在游戏中反应速度最重要的。虽然速度的确很有用而且很重要，但是最重要的是别干蠢事。正确的决策才是带兵之道。即使是让飞龙在战场上机动也并不是一件简单的事情。飞龙应该去攻击他们的目标但同时避开其他的敌人；它们应该集中火力，但在遇到有面攻击能力的敌方单位时又可以迅速的散开。最后，所有的飞龙的行为都应该同步。

为了处理这些问题并限制的计算开销，我们的AI使用了人工势场来控制单位的移动。势场会使目标对飞龙产生引力而使有威胁的敌方单位对飞龙产生斥力，飞龙最终会飞向合力的方向，这样的的策略简单而强健。像飞龙这样的空中单位即不会受到地形的限制也不会相互碰撞让我们的工作轻松了很多。

势场控制非常强大。例如，只要在开火之后忽略引力就能实现“打了就跑”的战术，斥力会让飞龙自动在攻击间隙离开对方的武器射程。引力可以让编队中的单位集火，而一旦面杀伤的威胁出现时，斥力就使它们四散躲避。