回合制战略游戏的AI算法设计
原文载于游戏设计研究室转载请注明出处，并保留原文链接译自Ed Welch《Designing AI Algorithms For Turn-Based Strategy Games》
在动作游戏里由电脑控制的对手总是有着先天的优势：完美的命中率，快如闪电的反应，所以为这类游戏设计AI的挑战在于使其更“人性化”，可以被玩家打败。
在回合制战略游戏中，局面却正好相反。速度和命中率已经不再举足轻重了，人类玩家的敏锐和直觉可以轻易地战胜任何AI对手。事实上，要设计出可以打败一名有经验的玩家的AI几乎是不可能的，但毕竟那也不是我们想要的。
挑战在于让AI的攻防策略看上去是聪明的，经过考虑的，保持游戏中挑战的同时，让玩家取得最后的胜利。一旦玩家熟悉了AI的战术之后，游戏很快就会变得无聊起来，因此一定程度上的不可预见性[译注：随机因素]还是很必要的。
面临的挑战：一款典型的战略游戏分析
引用实际的例子是理解AI设计问题最容易的方法。在这里我们来看一款太空战题材的游戏。
我们的例子是一款俗称“4X”的游戏。[译注：4X游戏，战略游戏的一种，其主要的四个游戏目的分别是：eXplore（探索），eXpand（扩张），eXploit（掠夺），eXterminate（毁灭）]在这款游戏里，你必须扩张并征服整个星系。每个玩家都拥有战舰以及殖民舰，始于己方行星，能够殖民化适合居住的行星。
http://www.gamasutra.com/db_area/images/feature/1535/ai_1.jpg
为其设计AI的最初尝试可能只是一个简单的算法，分派针对各资源（如行星，或舰队）的任务，从最重要的任务开始执行。守卫正在生产的行星具有最高的优先级，因为它们最有价值。
第二重要的是守卫没有生产任务的殖民地，接着是进攻敌人的主行星，之后是殖民能居住的行星，再是进攻敌人的舰队，然后修理受损的飞船，最后是探索尚未开垦的领域。总之，我们从最高优先级的任务做起，检查在离我们的行星附近是否有敌人舰队存在。
正如你在图片中所看到的，敌方护卫舰X，Y威胁到AI的基地和殖民地。于是，我们找到最近的驱逐舰，分配进攻任务。你可能已经留意到我们的算法在这里的漏洞。如果碰巧，护卫舰Y先行动，距离最近的是驱逐舰A，它会被分派去作攻击。而此时护卫舰X又行动了，剩下能进攻的只有驱逐舰B了，但它离得太远，已经来不及阻止敌方护卫舰X轰炸我们的家园了。很明显，对付护卫舰Y的应该是驱逐舰B，护卫舰X则该留给驱逐舰A。
此外，这个简单的算法还会引起其它的问题。来看一下一个更加复杂的场景：
http://www.gamasutra.com/db_area/images/feature/1535/ai_2.jpg
在这个场景里，我们的驱逐舰A因为先前的战斗严重损坏。将其再次遣往战场只是徒劳。将其送回主星球修理才是明智之举。于是就只剩下了驱逐舰B和驱逐舰C来保卫殖民地。但驱逐舰C离（敌人）的护卫舰Y太远了，更好的做法是让它轰炸敌人的殖民地，因为距离上非常接近（更别提剩下的燃料消耗同样重要）。与此同时AI全副武装的殖民舰队也会因此从主要的殖民任务中被调回。
解决方案：资源分配算法
分配记分
为了解决以上这些具体的问题，首先我们要设计一个记分系统。每一项任务都会被分配到一个总体的优先级，如下：
保卫我们的殖民地：1
进攻地方的殖民地：2
殖民（其他）星球：3
进攻地方舰队：4
修理受损舰队：5
开拓未开垦的疆域：6
每一项任务还有一个优先级的加权值，比如防守任务的加权值基于殖民地的价值。（有着生产任务的殖民地有着极高的加权值。）相似地，修理任务会根据受损程度计算加权值，而殖民任务的加权值则来自于行星的适合居住程度。
终于我们要来考虑被舰队的距离了，如下：
当前目标：生成的任务
靠近殖民地的敌舰：保卫殖民地任务
敌舰：进攻敌舰任务
敌殖民地：进攻敌殖民地任务
可居住的行星：殖民化行星任务
受损舰队：修理舰队任务
未开垦的领域：开拓任务
分配得分 = （6 – 整体优先级 + 加权值） / 所分配舰队的距离
因此，在先前的场景中，尽管防守任务拥有较高的优先级，但驱逐舰C离敌方星球实在太近了，所以进攻敌方殖民地的任务得分会更高。
此外，因为驱逐舰A严重受损，所以驱逐舰A的修理任务的优先级加权值也会十分高。再加上它离修理站的距离很近，修理任务的得分就会高过防守任务。
算法概要
整体算法分为4个部分：
http://www.gamasutra.com/db_area/images/feature/1535/ai_3.jpg
收集任务（Gathering Tasks）
AI有一张探测距离之内敌方舰队和行星，以及己方资源的列表。生成其需要完成的任务如下：
可能的分配（Possible Assignments）
问题的另一方面在于如果我们分配任务的次序出错的话，那么就无法做到对资源的最优利用。这可以通过分步分配任务来解决。我们使用两个特殊的类：PossibleAssignment（候选任务）和Task（任务）。PossibleAssignment通过一个任务和一个可能的“任务执行者”联系在一起，并记录“分配得分”。Task记录优先级，优先级加权值和任务。
http://www.gamasutra.com/db_area/images/feature/1535/ai_4.jpg
让我们来快速地看下我们的类结构，把这些都搞清楚：
我们为每个“任务执行者”生成一个PossibleAssignment的组合对象。我们去掉不可能的任务组合。比如一艘未装备的飞船不能执行进攻任务，它如果没有燃料到达某个目的地，那么相应的任务也无法执行。代码是这样的：
// listAsset contains a list of all assets (for instance ships)
for (n = 0; n <>for (f = 0; f <>if (listAsset.isTaskSuitable(listTask))
{
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），所以它们都可以被用在同样的算法中，只需要做很小的修改。这是一个在面向对象的设计中代码重用的很好的例子。
这些都展示在下面的图表中：
http://www.gamasutra.com/db_area/images/feature/1535/ai_5.jpg
简单处事：扔掉旧的任务
因为这是一个回合制的游戏，在每个新的回合开始的时候，所有上个回合的任务都过期了。比如，你的驱逐舰要去攻击的敌护卫舰可能突然撤退，或者你可能——惊恐地——发现，你正要殖民的行星早已被敌人占据。
最简单的处理方法是扔掉所有的任务，在每个回合开始的时候重新调用分配程序。这看起来可能不那么有效率，因为并不是所有的任务都需要更新的，然而它确实可以使得AI代码大大地简单化，你不必在维护之前回合中的任务。
保持代码的简单，对于AI算法来说尤为重要，因为这些算法很容易瞬间就变得过分复杂，让除错和维护变得非常困难。再者，所有的优化都应该在最后阶段，算法全部完成之后来做，而且是在明显感受到是算法一开始就拖慢了游戏的时候才做。
回合中的措手不及
在我们的回合中，我们的一艘飞船可能发现了新的敌人殖民地，或者飞船。我们可以立即分配给这艘飞船新的任务，但这可能会有问题。因为这艘飞船可能已经有了一个非常重要的任务。同样地，自简单和“傻瓜”（fool-proof）的做法是再次调用分配程序，保证选择最优的分配。
结论：这个算法实际的作用如何？
这个AI算法是在一款4X战略游戏的开发过程中设计出来的。（你可能已经通过例子猜到这点了。）实际的情况是人们有一种感觉，似乎在这些敌人的舰队背后隐藏着一种真切的智慧。
飞船会出人意料地改变战术。如果敌方的飞船没有弹药了，它会突然中止战斗，返回基地进行补给。如果它没有足够的燃料回到基地，它会试着去探索未开垦的区域。（这是仅有的有效任务。）新的飞船从船坞中诞生后整个舰队的命令可能都会改变。一些飞船会返回进行修理，让新出炉的战舰展开进攻。
基本上这个算法有着上佳的“性价比”（“bang for buck”），是一个实现和出错都很轻松的，并不太复杂的算法，但仍然造就了具有挑战性的AI对手。
即便这个算法是为某种类型的游戏专门设计的，它还是可以简单移植到其他类型的战略游戏中。
[ 本帖最后由 xat 于 2007-9-7 20:58 编辑 ] 好帖,收了
AI做得好，游戏才有意思 好深奥，对作者崇拜ing…… AI学习比较重要。记不得那个SLG了。同一战术3次没达到效果就换....... :sweat: 看不懂………… 真变态！连程序都给出了。原码被盗了？ 好贴
其实AMAI也是类似的算法 原帖由 muzimuzhen 于 2007-9-7 11:08 发表 http://bbs.stage1st.com/images/common/back.gif
真变态！连程序都给出了。原码被盗了？
这点示例代码也能叫程序。。。 技术帖来支持下，虽然还没看完 看成了“回合制战棋游戏的AI算法设计” :awkward: 感觉这个的AI更象是即时战略用的AI 嘿嘿 原帖由 tonyunreal 于 2007-9-7 11:50 发表 http://bbs.stage1st.com/images/common/back.gif
看成了“回合制战棋游戏的AI算法设计” :awkward:
+1
看不懂，溜～～ 学术贴，MARK一下 顶技术贴:) 原帖由 tonyunreal 于 2007-9-7 11:50 发表 http://bbs.stage1st.com/images/common/back.gif
看成了“回合制战棋游戏的AI算法设计” :awkward:
更晕，看成了‘回合制战略游戏AI没法设计’。。。 :glasses1: 原创? 第二张图下第二行，有个错字
“于是就只剩下了驱逐舰B和驱逐舰B来保卫殖民地。”应该是“于是就只剩下了驱逐舰B和驱逐舰C来保卫殖民地。” 原帖由 test 于 2007-9-7 18:53 发表 http://bbs.stage1st.com/images/common/back.gif
:glasses1: 原创?
翻译。 原帖由 hagger 于 2007-9-7 19:11 发表 http://bbs.stage1st.com/images/common/back.gif
第二张图下第二行，有个错字
“于是就只剩下了驱逐舰B和驱逐舰B来保卫殖民地。”应该是“于是就只剩下了驱逐舰B和驱逐舰C来保卫殖民地。”
多谢，已改。 想起来手头还有本原版的programming game AI by example，当初一老师让我帮忙买的最后又不想要了，三百多的原版书啊…… :awkward: 原帖由 godzillaqqq 于 2007-9-7 10:53 发表 http://bbs.stage1st.com/images/common/back.gif
AI学习比较重要。记不得那个SLG了。同一战术3次没达到效果就换.......
有学习能力的AI好强大
页:
[1]