As people give the descriptions and code of their bots, I will do something similar. Maybe more of a story than description, because clearly there's a lot of better bots to look at. Mine is ranked around 180 at the moment.
I learned about the competition quite late - registered on November 23rd. I decided to go with Python, because it's an elegant, simple language and I had known it a bit from before. I entertained a thought of learning Clojure, but decided it would be too difficult to learn a new language and code a bot at the same time.
Early on, it became clear that there might be some performance problems with Python. Most top ranking bots were written in C or Java, and dynamically typed languages (Python, PHP, Ruby) seem to run about thirty times slower.
First I did the tutorial and improved on tutorial bot. This version just moved randomly or in straight lines, and when it had food in sight, it went for it. It worked surprisingly well, althought wasn't that great in mazes.
Overall, there were two main breakthroughs in the development of my bot. First had to do with navigating the map and gathering food, second with combat.
Then first one was when I read about a collaborative diffusion. I liked it right away, because it offered a unified way of dealing with all kinds of movement.
Implementing diffusion was easy and it worked right away. My diffusing bot ranked around 650 at one time - and it was ignoring enemy ants completely, that is, just went where the scent was coming from. And the scent was coming from food, invisible areas, unexplored areas, enemy hills and later from enemy ants.
The main thing left was combat. I wasn't sure how to approach this. Fortunately, first a1k0n and then Memetix wrote about their methods. At first, I had trouble understanding them. Then I tried a1k0n's version, but it didn't work for me and I suspected Python would be too slow to do this. I decided I better go implement Memetix' approach, which was very common sense. It was quite easy once I understood the idea.
The method is simplified in that it only sees own and enemy ants, without paying attention if there's more than one enemy. I suppose it gives worse results when multiple parties are involved, but one may say it works well enough. I run out of time to write a full version.
Finally, my ants were behaving! They were forming lines, and regrouping, something that looked at least vaguely like what top bots were doing. This version managed to reach about 180th place before the finals.
One other important moment was when I learned about PyPy, which is basically a Python with JIT compiler - runs muuuuuch faster. Suddenly, the same code was running several times quicker, and performance stopped being a major bottleneck.
So here's the agent_smith, in case you want to take a look or match your bot against it.
The thing is based on starter pack and rather short: basically less than 1200 lines of code, including whitespace and scarce commments. There's also some AI visualization stuff that I enclose for completeness.
The bot runs on two simple ideas:
1. Each ant decides which direction to go, based on the strength of scent coming from each direction - towards the strongest scent. Of course, scent map must be prepared earlier. This is diffusion part.
2. If there's an enemy around, each ant checks own and enemy strenght (influence), as described by Memetix. If it's safe to go, it goes, if not, it doesn't (with some exceptions).
Main problem with combat is "lazy friends", that is, ants are unsynchronized, so it may happen that one goes one way and the other one some other way when they both need to go in the same direction to defeat an enemy ant.
To overcome this, in a week before the final I tried writing a combat simulator which took all ants close to enemy and aimed to find optimal combination of movements. It was quite frustrating, because I pushed myself hard to do this, but the effect was underwhelming. I got it to work in my third attempt, but it was inferior to my best bot and there was no time left to work on it further, so I went with the previous, simple version.
Just before the deadline I slapped a few quick hacks to improve areas that needed improvement, namely defending own hills and attacking enemy hills. Maybe it helped a little.
So here you go, a version which is currently in competition.
- (10.21 KiB) Downloaded 211 times