I've attached my C++0x code, it is pretty big, around 3.3k lines of code (5.1k including whitespace & comments), but quite well structured, so it shouldn't be too hard to find things. Included in the archive is a Makefile, so just run make to compile everything. There are a lot of leftover comments all over, unused functions everywhere and glaring inefficiencies throughout. Feel free to point them out if you feel like it .
So, with all that said, here is an overview of how my bot works.
My bot uses for everything except combat. My State class keeps track of the diffusion values for: food, exploration, enemy ants & enemy hills. I assign a fixed potential to food, tiles just beyond the edge of vision, enemy ants & enemy hills. Food is scored higher earlier in the game, while unseen tiles are scored higher the longer they have been unseen. Both food & enemy hills get a lower potential the longer it has been since my ants have seen them. Enemy ants get a higher value the closer they get to one of my hills, limited to a minimum value. All potentials are calculated using functions.
The spread of potential values is diminished if one of my ants is on a square. Depending on the type of field, this diminishing is high or low. When calculating the food potential field for example, an ant will block 99.99% of the potential, while for the enemy hills field this is only 10%.
One problem with diffusion is that it doesn't work too well when there are a lot of small passages. So to fix this, while diffusing, the value of a square is multiplied by 4 / (4 - numberOfWaterSquaresAsNeighbors). This increased the potential value of squares that have water squares as neighbors. This fix improved my bot quite a lot on maps with narrow tunnels. Before putting this in, the bot would ignore food in these small tunnels, since their potentials couldn't spread out.
Initially I had a combat routine that modified potential field values locally depending on the number of nearby friendly & enemy ants, which worked OK. However, when Memetix posted on the forum, I implemented that instead and noticed a great increase in combat skill. I did however apply a few tweaks to it.
First of all, after I actually output the move for an ant, I fix this ant at its new position in my CombatManager. Then, I update the combat resolution. This helps when the success of a move is dependent on where nearby ants move to. Doing this improved combat quite a bit, since ants will accidentally suicide a lot less often.
What I also did was detecting when my ants that are trying to raze an enemy hill are blocked. If at least 70% of them are blocked, I allow them to die as long as they kill at least 1 enemy ant. To calculate this correctly however, you need to know not how strong the strongest nearby enemy is, but how weak the weakest one is.
Now a problem arises when fixing an ant at its position. Without knowing how many enemies each enemy ant has on a square, you can not correctly update the strongest & weakest enemy values without recalculating everything. To fix that, instead of storing just the best & worst values per square, I keep a priority queue for each square in a combat zone to keep track of how many enemies each enemy ant has to fight in that square.
Finally, I also detect stationary enemies. An enemy is regarded as stationary if he hasn't moved for at least 10 turns in a row. When this happens, that enemy's position is fixed for the combat evaluation. This helps to detect good moves during stalemates and for suiciding my ants efficiently during a raze.
Before outputting any move, I check to see if I have seen an enemy hill. If so, I go over each of my ants and check the value of the enemy hill potential field at their location. The 50% of my ants with the highest value are then used as attack ants. I tried coming up with better ways to select attack ants, but this very dumb approach seems to work well enough, although it will use way too few ants to attack when I have a large number of ants on a small map.
Then, for every ant, for every direction + its current location, I get the sum of potentials of either (food + exploration + enemy ant) if it's a normal ant or (food + enemy ant + enemy hill) in case it's an attack ant.
I also got an idea while reading delineate's : reduce the score of squares that border water squares. I had noticed that often, when running away from enemies, my ants would get themselves stuck near water. So, for every neighboring water tile, the sum of potentials of a square is reduced by 5%.
Lastly, I distinguish between SAFE squares (where my ants are certain to kill an enemy) and NOCOMBAT squares (where no combat can take place). The potential sum of a NOCOMBAT square is only 20% of it's true potential sum value, so ants will prefer moving to SAFE squares. This has the effect that they prefer killing an enemy over running away, if possible.
Once I have the score for each direction, I sort them by their potential sum value, then loop over every ant and check if the best unchecked move so far is safe to execute according to my CombatManager (i.e. the ant won't die when it moves there, unless it's allowed to suicide). If an ant wants to move to the location of another ant, I push the first ant on a stack to evaluate later and check the 2nd ant first. This ensures that I can not have any collisions.
One aspect I implemented early on, before I had any decent combat evaluation, was static defenses. Depending on the number of ants I had, I would place ants next to my hill as long as at least 2 directions where free to move to from on top of the hill. This helped a great deal against bots without combat intelligence, but was useless against bots in the top 100.
However, the day of the deadline, I removed this and instead give enemy ants a higher potential the closer they come to my hills. On top of that, I define "suicide zones" at my hills, meaning that if any enemy ant get into these zones, my ants are allowed to suicide to kill them.
The net effect is that I have more ants early game to explore and gather food. And due to the increased potential of enemy ants near my hill, attackers are pushed away. Less sophisticated bots aren't even able to get close enough to see my hill. All the tests I ran the last day seemed to indicate that my bot with these changes did a lot better than the previous version without, so I kept them in.
One last thing I do is symmetry evaluation. I do not detect all possible types of symmetry however, only tilings (so no rotations or reflections). I wanted to add detection of all possible symmetries, but didn't have enough time left.
Whenever I do not see an enemy hill, but have seen/razed one in the past, and have detected a valid symmetry, I add an "artificial" hill at the correct location. As soon as an actual hill has been seen, this artificial hill is removed again. This ensures that, assuming a symmetry is found, as soon as I raze a hill (or an enemy razes a hill I've seen), my ants will move on to the next enemy hill using the shortest path, even if they have not seen it yet.
I wait to add "artificial" hills until I've seen one myself to make sure that I actually have enough ants to start attacking hills. If I add the "artificial" hills as soon as I detect symmetry, I often only have around 10-20 ants and attacking then would kill too many ants that could be gathering food.
Even though I code in C++, which is regarded as one of the fastest languages, I still need speedups to ensure I do not time out. There's 2 cases where this helps a great deal.
The most important thing when optimizing is definitely to use some kind of profiling tool. I found cachegrind in combination with KCachegrind to be amazing for this, much better & clearer than the text-based gprof. Just wanted to get that out in case people don't know about it .
So, first of all, the diffusion. One of the things about diffusion is that, in general, the more you can do it, the better your ants will behave. So I cached lots of non-changing variables, removed all function calls, changed branches to tertiary operators, minimized number of mathematical operators by reordering & grouping calculations and split up my diffusion loop in such a way that I didn't have to take into account wrapping coordinates anymore. This made my diffusion function go from +-15 lines to a +-250 lines monster, but gave me a 50x speedup. To give you an idea, doing 200 diffusions on a common 50x175 map takes around 130ms and on a 196x196 map it takes around 310ms.
The other part of the bot that was slow was the combat evaluation. In itself, it was super fast, somewhere around 3ms, but due to the fact that I completely recalculated everything after moving every single one of my ants in combat, it was not unusual that the bot needed 200ms to get the final positions for all ants in combat.
First of all, instead of completely recalculating the combat resolution, I only did so for ants that could have their combat evaluation results altered due to the move of the ant which position I fixed. This was quite involved, but basically came down to: store lots and lots of extra information.
I also implemented a bucketed priority queue for keeping track of enemy strengths. It seems this type of queue is also used in some OS schedulers, path finding algorithms, etc, but I had a hard time finding any real info on it. Instead of a heap-based priority queue, such as the C++ standard one (which is very, very limited in its functionality), you use a hash map, mapping priority -> hash set, and store all objects for a certain priority in the hash set. Almost any function you can imagine will have (in general, not worst case!) a run time of O(1): getting min & max priority, updating object priorities, inserting & removing objects, ...! Be sure to do lazy initialization though, so only create a hash set for a certain priority if you actually have an object with that priority. If you don't, you'll notice huge setup times for your queue. I'm quite amazed that it is so hard to find information about this type of priority queues before, they're amazing!
The combined effect of doing only local updates & using the lazy initialized, bucketed priority queue is that my combat resolution times went down from 200ms to 5-10ms.
In case you want to run my bot on your PC, note that there is at least one bug in it. When the bot plays on a map where no water tiles are visible, it will move its only ant north, even if there is food nearby in other directions. After this one move north, if still no water tile is visible, the single ant will just stay where it is. No timeout, no crash, nothing...
I only noticed this 2 hours before the deadline and didn't want to risk breaking something else by fixing it, so it's still in there. I've got no idea what is causing it, because I haven't tried to debug it yet.
Luckily there are very few maps where this can actually happen, I'm keeping my fingers crossed I won't have to play on them.
I want to thank to organizers for this wonderful competition. It has cost me a LOT of sleep, but I wouldn't hesitate to partake again. It had been quite a while since I did anything AI related and this was a great way to refresh that knowledge and learn loads of new things. I'm already looking forward to the next competition!
I also would like to thank Memetix, a1k0n, delineate, icefox, mathiasds & Nefbrethilion for all their shared ideas. Without them, my bot would not have had anywhere near the skill that it has now.
Statistics: Posted by Darhuuk — Tue Dec 20, 2011 1:13 am