I only found out about this side 4 days ago and have been working franticly to get an AI together. Hopefully I'll be aware a little earlier next time
. I'll discuss my strategy and give credit where credit's due.
First of all the source code is on a git repository, execute the following command to get it:
git clone git://git.assembla.com/killerants.gitStrategy
I'm using a diffusion map to guide ants towards food and unexplored territories . The longer a territory remains unexplored the stronger the pulls gets towards that area. Eventually the ants will spread out evenly across the map such that everything (except the water tiles) is visible. The only problem with this approach is that once everything is explored, or the unexplored bits are far away from the ant hills, the ants will cluster around the ant hills.Combat
For combat I use a different method. I cluster together ants which are close enough to be able to enter combat the next round and solve these "scenarios" separately. We simulate the following options:
We attack - Enemy attacks too.
We attack - Enemy holds the line.
We hold the line - Enemy attacks.
We retreat - Enemy attacks.
To qualify: Attack means move the ants towards the enemy; Hold the line means get all the ants in position such than when the enemy attacks they will be in range to engage - basically form a defensive barrier; Retreat speaks for itself
We simulate these approaches multiple times, trying different movements to get the ants into as good a position as possible. The heuristic is reported as the pair (#my ants die, #enemy ants die), we want to limit the number of dead allied ants and increase the number of enemy casualties. When both numbers are equal though, we check if we have overwhelming forces compared to the enemy ants in combat. If this is the case we will start pushing to break any deadlock situation and maximise casualties, otherwise we want to minimise casualties. If the heuristic is otherwise the same we prefer attacking over holding the line and holding the line over retreating.Pheromones
Depending how combat plays out, ants might call for backup to help them out.
Hold the line:
When ants decide to hold the line, but they do not have overwhelming forces they call in for backup. This is done as follows, they put a marker on all enemy ants in combat with them which will show up in the diffusion map and also put a negative value on the tile they stand on. This will give incentive for nearby ants to go around the defensive barriers and fill in the missing holes or - when a line is fully formed - to go around for some flanking action!
When an ant actually retreats it'll release a "panic" pheromone - effectively add a positive value on the diffusion map - so ants who are nearby will go there to help their brethren out. To make sure they don't block the retreat path, the ant will put a negative value on the tile it wishes to retreat to, this way the ants will go around the retreating ants and form the new flanks! Which is pretty sweet
We also detect enemy ant hills and use the diffusion map to send ants there to destroy it. Similarly if an enemy is close to one of our ants hills we put markers on the attacking ants to defend our ant hills.Conclusion
While competent I don't expect this AI to make it into the top10 (hopefully the top100
), there are still major issues which I would have resolved given more time. Most notably:
Clustering around ant hills.
Combat isn't perfect yet - sampling approach is totally random and does not guide towards a good solution.
Many ants doing the same task, for example food collection is due through the diffusion map which means that sometimes a whole hoard of ants moves towards a single food piece as it shivers in fear. It would be better to use - as many people on the forum have suggested - a hive mind approach where a single ant is selected to select said food piece.
All in all I would like to congratulate the organisers as they did a bloody good job! And cheers are going out to all the other competitors, see you at the next challenge!