Edit Question - KnowledgeHub

Title Body

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 . The problem 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: stay still move east / north / west / south, ...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"] A visual example: 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). The question 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 shoul

Tags (comma-separated) Cancel