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