My AI: 4 days worth of work

[Morloth]

Hi everybody!

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.git

Strategy
I'm using a diffusion map to guide ants towards food and unexplored territories [1]. 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!

Retreat:
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 .

Other notes
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!

Bram

[1] viewtopic.php?f=24&t=1746

[Darhuuk]

Wow, you got all that working in 4 days? Amazing, nicely done !

[KonaEarth]

Diffusion maps certainly seemed to be a popular solution for this contest. For many things, such as emitting pheromones to attract reinforcements to a battle, collaborative diffusion can work great. However, I ended up not using any diffusion maps.

For food collection, I felt that A* presented a more optimal solution because I could ensure a 1 food:1 ant ratio. Of course the computation time of A* can get out of control. I added a maxDist limiter so A* would give up if the food was too far away (i.e. maxDist = distance of closest ant so far). For most maps there are usually either a lot of ants and little food or a lot of food and few ants. So it balances out and I never had a problem with food collection taking a significant proportion of time. Still, I may have used collaborative diffusion except that I had already implemented A* first and in the end I think it worked well.

I did start using diffusion for map exploration then I backed off of that too. I decided that exploring the entire map just wasn't very important. Killing enemy hills and defending your own is the only thing that matters. I spent way too much time trying to get my ants to spread out better until I reminded myself that there are no points for efficient map exploration.

Instead of diffusion, I used simple distance maps to find my way to targets. For example, an enemy hill would be at distance zero, adjacent squares were distance one, then distance two and so on. Similar to diffusion but a simple breadth-first flood fill can fill even the largest, most complex maps in a single pass. Then the ants simply follow the scent to the target. Works great for simple targets. Of course not so great if the ants blindly march into danger.

Neither A* nor BFS will handle battle situations elegantly. I like how you divided it into attack/retreat scenarios then handle them differently. I wish I had considered that. The simple starter bots always "attack" because they're oblivious to combat. Many other bots always "retreat" and you can use that to your advantage by pushing an enemy around. Only the most advanced bots can choose intelligently between attacking and retreating.

[Darhuuk]

snip...

I decided that exploring the entire map just wasn't very important. Killing enemy hills and defending your own is the only thing that matters. I spent way too much time trying to get my ants to spread out better until I reminded myself that there are no points for efficient map exploration.

snip...

Actually, I would say that to get into the top 100, you need some decent combat, but to get in the top 20-30, you need good exploration.

The reason is simple: more exploration -> more food found -> more ants -> more power to kill your opponents. If you manage to explore fast in the beginning of the game, you can have a huge lead on your opponents. Just watch the best bots, you will notice that they have excellent exploration behavior.

[zaphod]

I fully agree! Exploration seems too important to be ignored. An average combat, but very good exploration seems to make a bot much stronger than a good fighter but average explorer. I have watched a lot of games where this has happened. I myself have spent most of my time (over 80%) in implementing efficient exploration, but my bot still seems to be lagging far behind bots ranked within the top 200 (even before the combat comes into the picture). By the time I get to 30 ants, the top bots would get to over 40! I am waiting to see how the top bots have implemented their explore strategy...

[BenJackson]

I fully agree! Exploration seems too important to be ignored. An average combat, but very good exploration seems to make a bot much stronger than a good fighter but average explorer. I have watched a lot of games where this has happened. I myself have spent most of my time (over 80%) in implementing efficient exploration, but my bot still seems to be lagging far behind bots ranked within the top 200 (even before the combat comes into the picture). By the time I get to 30 ants, the top bots would get to over 40! I am waiting to see how the top bots have implemented their explore strategy...

I think the key to growth that early is efficient use of ants for picking up food. Late in the game if you have a lot of ants it hardly matters who gets the food or if it's inefficient. But at the beginning sending too many ants to a food or having to backtrack (away from exploration) to get food will slow you down.

[KonaEarth]

I think the key is early versus late strategy. Early in the game, or on a crowded map, efficient exploration and food gathering definitely makes a difference. My problem is that I spent too much time worrying about that then underperformed on the large maps and later in the game.

One of my test bots was pure aggression. It pretty much ignored exploration and food gathering. It did surprisingly well because it attacked so early that most bots were busy trying to explore the map and not ready for a fast assault. That strategy doesn't work so well against high-end bots but my final "improved" bot still loses against the earlier pure-aggression bot in many cases. Of course that may be a reflection on my programming skill rather than the strength of the strategy.

[Morloth]

Exploration and food gathering is key in the beginning, I agree. This is one of the weaknesses of my bot in random_walk maps - exploration is overvalued and it favours exploring over food if the food is more than say 5 pixels away. This is no problem on other types of maps because the corridors are narrow enough to avoid this behaviour. So usually the enemy bots gains more ants in the beginning of the game and I have to rely on combat to get back into the game. So far it hasn't proven to be an issue, but I fear it will be a problem against higher ranked bots.

For example see: http://aichallenge.org/visualizer.php?g ... user=13789