蚂蚁的战斗策略
mac*_*mac 14 language-agnostic algorithm complexity-theory
这个问题涉及谷歌赞助的人工智能挑战赛,这是一个每隔几个月发生一次的比赛,其中竞争者需要提交一个能够自主地与其他机器人玩家玩游戏的机器人.刚关闭的比赛被称为"蚂蚁" ,如果您有兴趣,可以在这里阅读所有规格.
我的问题是针对蚂蚁的一个方面:战斗策略.
问题
给定一个离散坐标网格[就像一个棋盘],并给出每个玩家有一些蚂蚁,每个转弯可以:
- 保持不动
- 向东/北/西/南移动,
......如果一只敌人的蚂蚁被蚂蚁包围的敌人少于(或相同)自己的敌人,那么一只蚂蚁就会被敌人的蚂蚁杀死[相当于:"如果一个敌人在范围被更多(或相同)的敌人包围而不是其目标"]
一个直观的例子:
在这种情况下,黄色的蚂蚁将向西移动,橙色的蚂蚁,无法移动[蓝色瓷砖阻挡]将有两个黄色蚂蚁"在范围内"并将死亡(如果解释仍然不清楚,我邀请您访问上面的链接,查看更多示例并解释方案).
这个问题
我的问题主要是关于复杂性.我对这个问题进行了广泛的思考,但我仍然无法想出一个可以接受的方法来在合理的时间内计算出最佳的动作组合.在我看来,对于找到最佳的可能设置为我的蚂蚁的动作,我应该评估每一个可能的场景的结果,但由于战斗可以用蚂蚁会相当拥挤,这将意味着计算时间将成倍增长(5^n,其中n是蚂蚁的数量).
这种方法的另一个限制是,正在处理的解决方案并没有与计算所花费的时间成比例地提高其有效性,因此任意中断其执行可能会给您留下不可接受的解决方案.
我怀疑通过一些几何考虑结合线性代数可以找到一个好的解决方案,(也许可以为蚂蚁群计算一些"重心"？)但是我无法通过这个"直觉"的水平......
所以,我的问题归结为:
如何在现代机器上以约50-100毫秒的计算时间找到[近似]最优解的问题(这个数字是由官方竞赛规则得出的)？
如果您对这个问题感兴趣并需要一些灵感,我强烈建议您观看一些可用的游戏回放.
从OP编辑：
我选择这个答案作为比赛获胜者发布的对其代码的事后分析，事实上他遵循了这个答案的作者建议的方法。您可以在此处阅读获胜者的博客文章。
对于这类问题，通常使用带有alpha beta 剪枝的MinMax 算法。(*) [minmax 和 alpa beta 剪枝的简单解释在最后，但要了解更多详细信息，还应该阅读维基百科页面]。
为了克服您提到的有关极大量可能移动的问题，一个常见的改进是迭代执行最小最大算法。首先，您探索所有节点直到深度 1，并找到最佳解决方案。如果您还有时间：探索所有节点直到深度 2，然后选择一个新的更明智的最佳解决方案，依此类推...
当时间不够时：在您探索的最后一个级别提供您可以找到的最佳解决方案。
为了进一步改进您的解决方案，您可能需要重新排序您开发的节点：对于迭代 i，对迭代 (i-1) 中的节点进行排序 [按每个顶点的启发值]，并根据顺序探索每种可能性。其背后的想法是，如果您首先研究“最佳”解决方案，则更有可能修剪更多顶点。
这里的问题仍然是找到一个好的启发式函数，它可以评估“状态有多好”
(*)MinMax 算法很简单：您探索游戏树，并决定您将为每个状态做什么，以及您的对手对于每个动作最有可能做什么。这样做直到深度k，其中 k 被赋予算法。
alpha beta 剪枝是 minmax 的补充，它告诉你“哪些节点不应该再被探索，因为无论如何我都不会选择它们，因为我有更好的解决方案”