这个问题是指谷歌赞助的人工智能挑战 http://aichallenge.org/,每隔几个月举行一次的竞赛,参赛者需要提交一个能够自主与其他机器人玩家玩游戏的机器人。刚刚结束的比赛名为“蚂蚁”,您可以阅读其所有规范here http://aichallenge.org/specification.php, 如果你感兴趣。
我的问题是针对某一方面的ants: 作战策略 http://aichallenge.org/specification_battle.php.
问题
给定一个离散坐标网格[如棋盘],并假设每个玩家都有一定数量的蚂蚁,它们在每个回合可以:
- 保持静止
- 向东/向北/向西/向南移动,
...如果范围内的敌方蚂蚁周围的敌人数量少于(或相同),则蚂蚁将被敌方蚂蚁杀死[相当于:“如果敌方蚂蚁在范围内,则蚂蚁将杀死敌方蚂蚁”范围被比目标更多(或相同)的敌人包围”]
一个直观的例子:
在这种情况下,黄色蚂蚁将向西移动,而橙色蚂蚁无法移开[蓝色瓷砖被阻挡],将有两只黄色蚂蚁“在范围内”并会死亡(如果解释仍然不清楚,我邀请您参观上面的链接 http://aichallenge.org/specification_battle.php查看更多示例和解释场景)。
问题
我的问题主要是关于复杂性。我对这个问题进行了广泛的思考,但我仍然无法想出一种可接受的方法来在合理的时间内计算最佳的一组动作。在我看来,为了为我的蚂蚁找到最佳的可能动作集,我应该评估每种可能情况的结果,但由于战斗可能非常拥挤,这意味着计算时间将呈指数级增长(5^n
,其中 n 是涉及的蚂蚁数量)。
这种方法的另一个限制是正在研究的解决方案并没有提高其有效性按比例计算所花费的时间,因此,任意中断其执行可能会给您带来不可接受的解决方案.
我怀疑通过一些几何考虑可以找到一个好的解决方案结合线性代数,(也许计算蚂蚁群的一些“重心”?)但我无法通过这方面的“直觉”水平......
所以,我的问题实际上可以归结为:
应该如何解决这个问题,以便在现代机器上在大约 50-100 毫秒的计算时间内找到[接近]最佳解决方案(该数字是根据官方竞赛规则得出的)?
如果您对这个问题感兴趣并且需要一些灵感,我强烈建议您观看一些可用的内容比赛重播 http://aichallenge.org/games.php.