TGFC Lifestyle - Powered by Discuz! Board

标题: [其他] 回合制战略游戏的AI算法设计 [打印本页]

作者: xat 时间: 2007-9-7 00:31 标题: 回合制战略游戏的AI算法设计

转载请注明出处，并保留原文链接

译自Ed Welch《Designing AI Algorithms For Turn-Based Strategy Games》

在动作游戏里由电脑控制的对手总是有着先天的优势：完美的命中率，快如闪电的反应，所以为这类游戏设计AI的挑战在于使其更“人性化”，可以被玩家打败。

在回合制战略游戏中，局面却正好相反。速度和命中率已经不再举足轻重了，人类玩家的敏锐和直觉可以轻易地战胜任何AI对手。事实上，要设计出可以打败一名有经验的玩家的AI几乎是不可能的，但毕竟那也不是我们想要的。

挑战在于让AI的攻防策略看上去是聪明的，经过考虑的，保持游戏中挑战的同时，让玩家取得最后的胜利。一旦玩家熟悉了AI的战术之后，游戏很快就会变得无聊起来，因此一定程度上的不可预见性[译注：随机因素]还是很必要的。

面临的挑战：一款典型的战略游戏分析
引用实际的例子是理解AI设计问题最容易的方法。在这里我们来看一款太空战题材的游戏。

我们的例子是一款俗称“4X”的游戏。[译注：4X游戏，战略游戏的一种，其主要的四个游戏目的分别是：eXplore（探索），eXpand（扩张），eXploit（掠夺），eXterminate（毁灭）]在这款游戏里，你必须扩张并征服整个星系。每个玩家都拥有战舰以及殖民舰，始于己方行星，能够殖民化适合居住的行星。

为其设计AI的最初尝试可能只是一个简单的算法，分派针对各资源（如行星，或舰队）的任务，从最重要的任务开始执行。守卫正在生产的行星具有最高的优先级，因为它们最有价值。

第二重要的是守卫没有生产任务的殖民地，接着是进攻敌人的主行星，之后是殖民能居住的行星，再是进攻敌人的舰队，然后修理受损的飞船，最后是探索尚未开垦的领域。总之，我们从最高优先级的任务做起，检查在离我们的行星附近是否有敌人舰队存在。

正如你在图片中所看到的，敌方护卫舰X，Y威胁到AI的基地和殖民地。于是，我们找到最近的驱逐舰，分配进攻任务。你可能已经留意到我们的算法在这里的漏洞。如果碰巧，护卫舰Y先行动，距离最近的是驱逐舰A，它会被分派去作攻击。而此时护卫舰X又行动了，剩下能进攻的只有驱逐舰B了，但它离得太远，已经来不及阻止敌方护卫舰X轰炸我们的家园了。很明显，对付护卫舰Y的应该是驱逐舰B，护卫舰X则该留给驱逐舰A。

此外，这个简单的算法还会引起其它的问题。来看一下一个更加复杂的场景：

在这个场景里，我们的驱逐舰A因为先前的战斗严重损坏。将其再次遣往战场只是徒劳。将其送回主星球修理才是明智之举。于是就只剩下了驱逐舰B和驱逐舰C来保卫殖民地。但驱逐舰C离（敌人）的护卫舰Y太远了，更好的做法是让它轰炸敌人的殖民地，因为距离上非常接近（更别提剩下的燃料消耗同样重要）。与此同时AI全副武装的殖民舰队也会因此从主要的殖民任务中被调回。

解决方案：资源分配算法
分配记分
为了解决以上这些具体的问题，首先我们要设计一个记分系统。每一项任务都会被分配到一个总体的优先级，如下：

保卫我们的殖民地：1
进攻地方的殖民地：2
殖民（其他）星球：3
进攻地方舰队：4
修理受损舰队：5
开拓未开垦的疆域：6

每一项任务还有一个优先级的加权值，比如防守任务的加权值基于殖民地的价值。（有着生产任务的殖民地有着极高的加权值。）相似地，修理任务会根据受损程度计算加权值，而殖民任务的加权值则来自于行星的适合居住程度。

终于我们要来考虑被舰队的距离了，如下：

当前目标：生成的任务
靠近殖民地的敌舰：保卫殖民地任务
敌舰：进攻敌舰任务
敌殖民地：进攻敌殖民地任务
可居住的行星：殖民化行星任务
受损舰队：修理舰队任务
未开垦的领域：开拓任务

分配得分 = （6 – 整体优先级 + 加权值） / 所分配舰队的距离

因此，在先前的场景中，尽管防守任务拥有较高的优先级，但驱逐舰C离敌方星球实在太近了，所以进攻敌方殖民地的任务得分会更高。

此外，因为驱逐舰A严重受损，所以驱逐舰A的修理任务的优先级加权值也会十分高。再加上它离修理站的距离很近，修理任务的得分就会高过防守任务。

算法概要
整体算法分为4个部分：

收集任务（Gathering Tasks）
AI有一张探测距离之内敌方舰队和行星，以及己方资源的列表。生成其需要完成的任务如下：

可能的分配（Possible Assignments）
问题的另一方面在于如果我们分配任务的次序出错的话，那么就无法做到对资源的最优利用。这可以通过分步分配任务来解决。我们使用两个特殊的类：PossibleAssignment（候选任务）和Task（任务）。PossibleAssignment通过一个任务和一个可能的“任务执行者”联系在一起，并记录“分配得分”。Task记录优先级，优先级加权值和任务。

让我们来快速地看下我们的类结构，把这些都搞清楚：

我们为每个“任务执行者”生成一个PossibleAssignment的组合对象。我们去掉不可能的任务组合。比如一艘未装备的飞船不能执行进攻任务，它如果没有燃料到达某个目的地，那么相应的任务也无法执行。代码是这样的：

// listAsset contains a list of all assets (for instance ships)
for (n = 0; n <>for (f = 0; f <>if (listAsset[f].isTaskSuitable(listTask[n]))
      {
            listPossAssignment.add(new PossibleAssignment(listTaskn]));
               }
      }
}

接下来我们计算每个候选任务的得分，并将列表排序，由高至低。最终，在最后一部，我们实际分配任务。因为列表经过了排序，所以最有效的任务排在首位。一旦任务被分配，便将“任务执行者”标记为“忙碌”，同时将任务标记为“分配”，以免重复分配。

这里是部分的代码：

for (n = 0; n <>public void PossibleAssignment::assign()
{
if (task.isAssigned()) return;
  possibleTaskDoer.assign(this);
}

public void Ship::assign(PossibleAssignment possAssign)
{
if (task != null) return;
  task = possAssign.getTask();
  possAssign.getTask().assign(this);
}

将算法重用于行星生产任务
在现有的飞船不足以打点好所有的任务时，AI应该生产更多的飞船。比如，如果我们发现了一艘敌人的飞船，手头却没有足够的舰队进行攻击，那么我们需要建造一艘新的攻击舰。类似地，如果当前有可以居住的行星，但手头没有殖民飞船，那么我们需要建造一艘新的。

实际上，生产建造的优先级和飞船任务的优先级是完全一样的。正如你在类的图标中所见的一样，飞船（Ship）和行星（Planet）都是继承自星际对象（SpaceObject），所以它们都可以被用在同样的算法中，只需要做很小的修改。这是一个在面向对象的设计中代码重用的很好的例子。

这些都展示在下面的图表中：

简单处事：扔掉旧的任务
因为这是一个回合制的游戏，在每个新的回合开始的时候，所有上个回合的任务都过期了。比如，你的驱逐舰要去攻击的敌护卫舰可能突然撤退，或者你可能——惊恐地——发现，你正要殖民的行星早已被敌人占据。

最简单的处理方法是扔掉所有的任务，在每个回合开始的时候重新调用分配程序。这看起来可能不那么有效率，因为并不是所有的任务都需要更新的，然而它确实可以使得AI代码大大地简单化，你不必在维护之前回合中的任务。

保持代码的简单，对于AI算法来说尤为重要，因为这些算法很容易瞬间就变得过分复杂，让除错和维护变得非常困难。再者，所有的优化都应该在最后阶段，算法全部完成之后来做，而且是在明显感受到是算法一开始就拖慢了游戏的时候才做。

回合中的措手不及
在我们的回合中，我们的一艘飞船可能发现了新的敌人殖民地，或者飞船。我们可以立即分配给这艘飞船新的任务，但这可能会有问题。因为这艘飞船可能已经有了一个非常重要的任务。同样地，自简单和“傻瓜”（fool-proof）的做法是再次调用分配程序，保证选择最优的分配。

结论：这个算法实际的作用如何？
这个AI算法是在一款4X战略游戏的开发过程中设计出来的。（你可能已经通过例子猜到这点了。）实际的情况是人们有一种感觉，似乎在这些敌人的舰队背后隐藏着一种真切的智慧。

飞船会出人意料地改变战术。如果敌方的飞船没有弹药了，它会突然中止战斗，返回基地进行补给。如果它没有足够的燃料回到基地，它会试着去探索未开垦的区域。（这是仅有的有效任务。）新的飞船从船坞中诞生后整个舰队的命令可能都会改变。一些飞船会返回进行修理，让新出炉的战舰展开进攻。

基本上这个算法有着上佳的“性价比”（“bang for buck”），是一个实现和出错都很轻松的，并不太复杂的算法，但仍然造就了具有挑战性的AI对手。

即便这个算法是为某种类型的游戏专门设计的，它还是可以简单移植到其他类型的战略游戏中。

[ 本帖最后由 xat 于 2007-9-7 20:53 编辑 ]

作者: 2047 时间: 2007-9-7 00:38

又是好文一篇

支持

作者: jamesea 时间: 2007-9-7 01:22

这里快变游戏设计综合讨论区了

[ 本帖最后由 jamesea 于 2007-9-7 01:24 编辑 ]

作者: 孟德尔 时间: 2007-9-7 01:33

还好哦会一点点C语言啊

作者: 大头木 时间: 2007-9-7 09:04

回合制战略的AI，一直以来的感受都是很烂的。

不根据敌人的情况生产单位，如高级战争。

不会迂回战术，要是会的话我没法和它玩了

要不就一拥而上，要不就原地静止不动。

回合制游戏的ai要是做得就算只有普通人的一般智商，那我们也没得玩了，这点和rts区别太大。

作者: 卖哥 时间: 2007-9-7 10:34

回合制策略只要建立在对等规则下，人脑优势还是很大的，至少这篇文章提出的AI，完全没有和国际象棋的AI那样计算多步。
即时战略的话则不然，AI可以做到APM再高都完不成的事情，有些单纯不是因为AI高而是操作上的优势就会干掉玩家了。
说起来那个4X游戏是银河文明么？

作者: ffcactus 时间: 2007-9-7 12:17

任务优先级的算法于LINUX的任务优先级算法有点类似。
AI问题确实是有挑战的，要求广，要求准确。

作者: xat 时间: 2007-9-7 16:52

引用:

原帖由卖哥于 2007-9-7 10:34 发表
回合制策略只要建立在对等规则下，人脑优势还是很大的，至少这篇文章提出的AI，完全没有和国际象棋的AI那样计算多步。
即时战略的话则不然，AI可以做到APM再高都完不成的事情，有些单纯不是因为AI高而是操作上 ...

看图似乎应该不是银河文明。

作者: 伊肯 时间: 2007-9-7 17:36

不错，不过感觉最有意义的还是开始的几句：
在回合制战略游戏中，局面却正好相反。速度和命中率已经不再举足轻重了，人类玩家的敏锐和直觉可以轻易地战胜任何AI对手。事实上，要设计出可以打败一名有经验的玩家的AI几乎是不可能的，但毕竟那也不是我们想要的。
挑战在于让AI的攻防策略看上去是聪明的，经过考虑的，保持游戏中挑战的同时，让玩家取得最后的胜利。一旦玩家熟悉了AI的战术之后，游戏很快就会变得无聊起来，因此一定程度上的不可预见性[译注：随机因素]还是很必要的。
另外美式的4ex和日式的srpg感觉还是2种路数，一个偏向模拟，一个偏向解谜。。

作者: 卖哥 时间: 2007-9-7 21:15

作为4X游戏代表的文明系列
这个系列的不可预见性是来自
随机地图

每一盘都是不同的，所以可重复游戏价值还不低。

而日系SRPG的所谓AI，除了脚本因素，其他的也就是对命中情况伤害情况进行加权计算，然后判断攻击谁，也都是只考虑一轮，而且同样的条件也只能得出一个结论的模式。
随机的命中率和甚至随机的伤害值并没有让AI变得随机。

所以，熟悉了AI的战术之后，游戏很快就会变得无聊起来，这两者之间应该是不会有变的。
也就是从S/L或者反复重开之中选择一种新手玩法的区别……

作者: 788414 时间: 2007-9-7 21:58

算法......

具体点吧.......

// listAsset contains a list of all assets (for instance ships)
for (n = 0; n <>for (f = 0; f <>if (listAsset[f].isTaskSuitable(listTask[n]))
      {
            listPossAssignment.add(new PossibleAssignment(listTaskn]));
               }
      }
}

for (n = 0; n <>public void PossibleAssignment::assign()
{
if (task.isAssigned()) return;
  possibleTaskDoer.assign(this);
}

public void Ship::assign(PossibleAssignment possAssign)
{
if (task != null) return;
  task = possAssign.getTask();
  possAssign.getTask().assign(this);
}

收获啊......

谢谢

作者: xat 时间: 2007-9-7 22:12

引用:

原帖由卖哥于 2007-9-7 21:15 发表
作为4X游戏代表的文明系列
这个系列的不可预见性是来自
随机地图

每一盘都是不同的，所以可重复游戏价值还不低。

而日系SRPG的所谓AI，除了脚本因素，其他的也就是对命中情况伤害情况进行加权计算，然后 ...

文明的AI考虑的东西还是很多的，而玩家能左右游戏的方式也太多了。
前两天看到一篇关于游戏中商路的研究，重新玩的兴致又提起来了。

关于日系SRPG的观点非常同意。日系的SRPG中，更多的是玩具性质的AI。
只考虑当前回合这点其实无可厚非，但是其考虑的面非常狭窄。
比如一路按甲乙丙丁的顺序来控制AI。
轮到甲时，当前单位甲考虑当前回合自己怎么行动，接着到乙……很少见到顶楼里提到的让给更合适的单位发动攻击。

作者: md2 时间: 2007-9-7 22:24

引用:

原帖由卖哥于 2007-9-7 21:15 发表

而日系SRPG的所谓AI，除了脚本因素，其他的也就是对命中情况伤害情况进行加权计算，然后 ...

日式SRPG的核心是地形设计，兵力配置而不是AI
火焰文章的AI低得恐怖，很多情况下敌人失败的原因都是移动，如果他们原地不动几乎是不可战胜的
战术几乎没有，全靠设计师放好位置
敌人下一步的行动，很容易就能算出来，真正的变数是命中率
日式战棋里玩家关心的其实只有两点
1 伤害算法
2 命中率
AI？那是什么？好吃吗？

[ 本帖最后由 md2 于 2007-9-7 22:33 编辑 ]

作者: chovosky 时间: 2007-9-8 01:36

不懂啊，还是顶了:D

作者: chinagamemaker 时间: 2007-9-10 22:50 标题: 好文

能看到专业游戏讨论，很开心。楼主加油。

作者: cc0128 时间: 2007-9-15 12:45

收获不小啊

作者: Leny 时间: 2007-9-18 16:28

引用:

原帖由 md2 于 2007-9-7 10:24 PM 发表
火焰文章的AI低得恐怖，很多情况下敌人失败的原因都是移动，如果他们原地不动几乎是不可战胜的

FE 里只要 BOSS 会动，这关的后期都会变得很艰难。
也许习惯了只会守城的BOSS，他们的行动反倒让我方阵脚打乱，而且见到BOSS多为游戏章节的末端，死一个人（晓女里后期BOSS拥有的多数特技以及他们的概率发动更是让这场战争变得扑朔迷离＋提心吊胆，如果他们会自由走动的话……OH MY GOD～）就意味着前面2个小时的努力白瞎……而且终结战绩时显示败1（污点……）。

作者: 红色文化 时间: 2007-9-18 21:08

如果一个战略游戏带有战争迷雾的话计算会更麻烦，cpu每发现一个新的信息都需要重新调整任务的序列和路径的序列。

以前玩某个slg大作的某版本时，在工业时代玩家的地面部队会在签有通行协议的国家的铁路线上做钟摆一样的死循环运动。友方的铁路是不消耗移动力的，所以AI寻路的时候以走铁路格子为最高的优先选择。

这个时候有趣的事情发生了：
当一个成“口”字型的铁路摆在那里的时候，如果玩家的集团军起始点是左上角，而它的目的点是右下角的，那么AI会执行一个路径：左上角－>右上角－>右下角
注意，在这个时候因为战争迷雾的关系AI并不清楚到右上角和左下角上有没有障碍。

玩家的集团军开始往右上角跑，快到右上角的时候它发现那里的铁路被一个治理污染的工人卡住了，比较合理的办法是玩家的大军完全无视一个老俵大咧咧碾过去，但该情况没有发生……。事实上这个单位选择了另外一条文明的路线：“－>左上角－>左下角－>右下角”，反正只要沿着铁路走不消耗移动力的，回头路走多少遍都无所谓。于是这个集团军返头开往左下角，快到的时候它惊讶的发现这个位置上有个同伴的工人傻站在那里（注意这里没有用“又”字），它会很文明地再次选择上次被放弃的路线，是的，因为战争迷雾的关系，它看不到右上角上有什么东西，即使它一秒钟之前已经去过那里，所以它又会选择之前那条路线：“－>左上角－>左下角－>右下角”再跑一次。
悲剧上演了，玩家眼睁睁看着这堆部队在两个工人之间疯狂地打转，并且按任何游戏中设定的按键都于事无补。最后只好打开人物管理器关掉程序。读取上次的档案重来吧。

这个游戏玩下来搞得我染上两个习惯：狂按“Ctrl＋s”和“Ctrl＋Shift＋Q”……

作者: 沉默の狙击手 时间: 2007-9-22 11:55

这篇文章真好。收藏了

欢迎光临 TGFC Lifestyle (http://bbs.tgfcer.com/)