Memetix:
Enjoyed reading more details from your code write-up on your homepage (
http://www.blackmoor.org.uk/AI.htm). I also used a a tile-scoring system that required maximizing total score across all ant-destination pairs, while not allowing ants to collide.
This is an example of the assignment problem:
http://en.wikipedia.org/wiki/Assignment_problemAn exact optimal solution to the assignment problem can be found in O(n^3) with the Hungarian algorithm (which I used in my bot, but it turns out to too demanding with 150+ ants for a language as slow as Python or even pypy, but may be fine in compiled languages -- but anyway my bot is susceptible to timing out as a result). Googling will also find some faster, approximation algorithms; I considered the auction algorithm and "deep greedy switching". Finally, there is simply plain-old greedy algo, which most people probably used, but I was finding the number of colliding ants (when in tightly packed space) to be too onerous -- in fact, when I corrected for collisions, my performance improved materially.
Anyway, the heuristics the you describe for solving the problem were pretty bright, and I never considered a solution of that type. I think I was mentally boxed-in, because I had prior experience with the Hungarian algo. I'd be curious to know how your heuristics compared to optimal solutions, if you ever studied that.
Your writeup is really enjoyable to read -- I had many "oh!!" moments, where a solution you describe seems so obvious after you tell it to me that I feel I should have been able to think of it myself -- but I didn't. So, thanks for the write-up. Since I won't be competitive with the very top bots -- I'm rooting for you.
