How did you gather food?

[McLeopold]

To try and efficiently gather food, I did a breadth first search from every food at the same time. I setup some python generators to look for targets (my ants) 1 step at a time. When I found a target, I committed to the move and added a new target ant at the time it would be at the new spot. This allowed me to schedule 1 ant to pick up several foods if it was the closest to each one, freeing up the other ants to do something else. I also added a future ant at the hill so the first ant would tend to collect in 1 direction and the new ant would have orders waiting for him.

Food gathering happened after combat so an ant wouldn't flee the front lines. Targeting enemy hills and ants was done afterwards, which caused ants to not raze a hill and gather food instead.

My bfs code only recorded the first and last direction for each target, not the full path, so I could search from ants to food or food to ants. I wrote a second bfs that just recorded distances that I used for exploration and was faster, but never got around to using it for food. That means I redid the calculations each turn without caching.

Playing on TCP, there were only a few bots that gathered faster than my bot, and usually by luck of exploring a better area first.

I thought about trying to get a few ants to ignore food and look for and steal food closer to the enemy, but never got there. Sort of a dodge ball rush at the start. I also thought about trying to collect all food I saw in the shortest amount of time, but figured a few ants sooner would be better, as I would always find more food.

https://gist.github.com/1507173

For the python experts, you'll notice my generators are producing and collecting values, a big no-no in python land.

[Parasprites]

I guess I'm one of the rare bots that didn't attempt to do any scheduling of targets at all, though I probably should have. I use a pure influence based approach.

I also combined food gathering, collision avoidance, and combat into a single solver, which is also probably unique.

[tictac]

at some point my harvesting was not good at all so i switch more or less to what you describe : compute the closest ant to a food, start by assigning the ant the min distance to a food, then consider it will be there in n turns.
someting i started but did not included for lack of time , and i think it would have been useful, is taking into account the extra dist to goal for exploring ants at start / ie its better to have an ant continue toward the unknown and let another take a food even if its cost 1-2 turns (but not 10-15 obviouly so ther was tuning to do) to discover new ground quicker, at the very start of the game (before turn 50 or 100); Someting i would have doen too is to try to go for food even when ennemies where nearby: nin my code when i switch to combat mode food does not exists anymore (but i still think that is harvestd so i do not dispatch a new ant); I think food gathering at start of games is still one my bigger weakness compare to stronger bots

[McLeopold]

My thought for solving the explorer or gather problem (which I didn't implement) would be to score each ant as distance from hill. What ever solution gave the highest score for some horizon would be the best solution. So, going sideways or backward to a food would lower the score, going from the hill to the food would increase the score. So at some point it should prevent an ant from going backwards.

I'd like to implement that and see how it does.

[analyst74]

I used a influence map based approach, it's quite accurate, probably the only part of my bot that doesn't suck. :p

An influence map is created for each food, using linear diffusion, then they are combined into a single food_influence map, by using the best(highest) influence + sum(all other influences) * 0.001.

[BenJackson]

I found individual scheduling was most important in the initial expansion. Later a few turns of difference taking food in your safe interior isn't a big deal.

Someone on IRC mentioned the idea of solving the travelling salesman problem at the start for initial food. As long as you work in the future ants you will get I think this is a good idea. You can turn that off when your expansion hits a certain point.

[Parasprites]

I thought of doing TSP style scheduling for the first few turns, but I wasn't sure how useful it would be and never got around to implementing it.

[Manwe56]

In early versions I used a global BFS on all the foods all over the map, then assigned one ant per food considering the euclidian distance to go to the nearest food.
But it tends to make ants going into the same direction without respecting the assignment I did previously.

So I tryed to assign the pair food/ant using a BFS on each food until an ant is found. It was a little better, but I enhanced the pairing system by allowing the ants to be assigned to a list of food. Typically, I take into consideration the distance to reach the first food, then to go from the first food to the second etc...

It gives good results. Check the following couple images :

My ant are in grey. They already moved (so lines start from the previous positions). The red line represent the food the ant should collect. The white line reprensent the order I gave them