战斗策略蚂蚁 [英] Combat strategy for ants

问题描述

这个问题指的是谷歌发起 AI挑战，比赛出现这种情况每隔几个月，并在其中的竞争者需要提交能够与其他机器人玩家自主打一个机器人。刚刚结束的比赛被称为蚂蚁，你可以阅读其说明书此处，如果你有兴趣

This question refers to the Google-sponsored AI Challenge, a contest that happens every few months and in which the contenders need to submit a bot able to autonomously play a game against other robotic players. The competition that just closed was called "ants" and you can read all its specification here, if you are interested.

我的问题是特定于的蚂蚁的一个方面：作战策略。

My question is specific to one aspect of ants: combat strategy.

鉴于离散坐标网格[如棋盘]，并给予每个​​玩家有许多蚂蚁在每回合可以：

Given a grid of discrete coordinates [like a chessboard] and given that each player has a number of ants that at each turn can either:

1. 仍然停留
2. 将东/南/西/北，

...一只蚂蚁会被敌人蚂蚁被杀死，如果在范围内的敌人蚂蚁包围了自己的敌人少（或相同），比蚂蚁[等同于一只蚂蚁会杀死一个敌人蚂蚁，如果在范围内的敌人是由比其目标]

...an ant will be killed by an enemy ant if an enemy ant in range is surrounded by less (or the same) of its own enemies than the ant [equivalent to: "An ant will kill an enemy ant if an enemy in range is surrounded by more (or the same) enemies than its target"]

有一个直观的例子：

在这种情况下，黄蚂蚁要偏西方向移动，并橙色蚂蚁，不能够离开[蓝色的瓷砖被阻挡]将在范围内两黄蚂蚁，会死（如果该解释依然是不明确的，我邀请您来参观上述的链接查看更多示例和解释的情况）。

In this case the yellow ants are going to move west, and the orange ant, not being able to move away [blue tiles are blocking] will have two yellow ants "in range" and will die (if the explanation is still not clear, I invite you to visit the link above to see more examples and explained scenarios).

我的问题基本是复杂性。我想这个问题广泛，但我仍然不能拿出来计算的移动优化设置在合理的时间一个可以接受的方式。在我看来，对于寻找最好的一套动作让我的蚂蚁，我应该评估每一个可能的情况下的结果，但由于战斗可能是pretty的挤满了蚂蚁，这将意味着计算时间将成倍增长（ 5 ^ N ，其中n是参与蚂蚁的数量）。

My question is substantially about complexity. I thought to this problem extensively, but I still couldn't come up with an acceptable way to calculate the optimal set of moves in a reasonable time. It seems to me that for finding the best possible set of moves for my ants, I should evaluate the outcome for every possible scenario, but since battles can be pretty crowded with ants, this would mean that computation time would grow exponentially (5^n, with n being the number of ants involved).

这个方法的另一个限制是，该解决方案正在处理不提高其效率的比例的与花费的时间计算，这样随意打断其执行可能会离开你与非可接受的解决方案

Another limitation of this approach is that the solution being worked on doesn't improve its effectiveness proportionally to the time spent computing, so arbitrarily interrupting its execution might leave you with a non-acceptable solution.

我怀疑是一个很好的解决方案可能是通过一些几何考虑与线性代数组合可以发现，（也许计算一些的重心蚂蚁？组），但我过不了在这种直觉......

I suspect that a good solution might be found via some geometrical considerations in combination with linear algebra, (maybe calculating some "centres of gravity" for groups of ants?) but I could not pass the level of "intuition" on this...

所以，我的问题其实可以归结为：

So, my question really boils down to:

应该如何这个问题上前找[近]在一个计算时间的最佳解决方案〜50-100毫秒的现代化的机器上（这个数字是由正式比赛规则派生）？

How should this problem be approached to find [nearly] optimal solutions in a computation time of ~50-100 ms on a modern machine (this figure is derived by the official contest rules)?

如果你有兴趣的问题，需要一些灵感，我强烈建议看一些可用的游戏重播<的/ A>。

If you are interested by the problem and need some inspiration, I highly recommend to watch some of the available game replays.

推荐答案

编辑从OP：

我选择这个答案，因为接受了大赛的获奖者发表了他的code进行事后​​分析，而事实上他跟着这个答案的作者提出的办法。你可以阅读href="http://xathis.com/posts/ai-challenge-2011-ants.html" rel="nofollow">这里赢家的博客文章

I'm selecting this answer as accepted as the winner of the contest published a post-mortem analysis of his code, and indeed he followed the approach suggested by the author of this answer. You can read the winner's blog entry here.

有关这类问题，极大极小算法，提供的α+β剪枝通常使用。 （*）的最小最大和ALPA测试prunning简单的解释就是底，但对于更多的细节，维基百科页面也应该阅读。

For these kind of problems, MinMax algorithm with alpha beta pruning is usually used. (*) [simple explanation for minmax and alpa beta prunning is at the end, but for more details, the wikipedia page should also be read].

为了克服你所提到的有关非常大量的可能的行动问题，一个共同的改进反复做极小极大算法。起初你浏览的所有节点，直至深度为1，并找到最佳的解决方案。如果您还有一段时间：探讨所有节点，直到深度2，现在选择了一个新的更明智最好的解决方案，等等...
当出来的时候：提供最佳的解决方案，你会发现，在过去的水平，你探索

In order to overcome the problem you have mentioned about extremely large number of possible moves, a common improvement is doing the minmax algorithm iteratively. At first you explore all nodes until depth 1, and find the best solution. If you still have some time: explore all nodes until depth 2, and now chose a new more informed best solution, and so on...
When out of time: gives the best solution you could find, at the last level you explored.

要进一步提高您的解决方案，你可能要重新排序您开发的节点：迭代我，（I-1）通过为每个顶点的启发式值]排序在迭代的节点，探索按照顺序各种可能性。其背后的想法是，你更有可能PRUN更多的顶点，如果你先查最佳的解决方案。

To further improve your solution, you might want to reorder the nodes you develop: for iteration i, sort the nodes in iteration (i-1) [by their heuristical value for each vertex] and explore each possibility according the order. The idea behind it is that you are more likely to prun more vertices, if you first investigate the "best" solutions.

这里的问题仍然是找到一个很好的启发式功能，它评估多么好的一个状态是

The problem here remains finding a good heuristical function, which evaluates "how good a state is"

（*）的极小极大算法很简单：你探索游戏树，并决定你会做的每一个状态，你有什么oponent是最有可能做的每一个动作。这样做，直到深度 K ，其中k是考虑到该算法。

(*)The MinMax algorithm is simple: You explore the game tree, and decide what will you do for each state, and what is your oponent is most likely to do for each action. This is done until depth k, where k is given to the algorithm.

在α+βprunning是除了最小最大，它告诉你哪些节点不应再探讨，因为任何方式，我不会选择他们，是因为我有一个更好的解决方案

The alpha beta prunning is an addition to minmax, which tells you "which nodes should not be explored anymore, since any way I am not going to chose them, because I have a better solution"

这篇关于战斗策略蚂蚁的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！