Due to real-life issues, I’ve had less time to devote to the contest that I’d expected so my progress has been slow. I should have more time from here on out so hopefully I’ll be able to do better. Most people haven’t been as lazy as me however and more people have entered than I expected. As of the time of the writing, there are over 6,600 entrants. The contestant count for last year’s contest peaked at less than 5,000.
As a rough gauge of the quality of the competition, I recently climbed to the first place for Malaysians, but my overall ranking is only 800+. By contrast, the user named Jacks who self-identifies as from TM Berhad held the Malaysian top spot for over a month but in the overall rankings he peaked in the 500s and has since gradually declined to the 1,400s. This suggests a combination of very good new entrants and users who have been actively improving their bots.
Getting into the top 1,000 and staying there with a bot of my own design proved to be far harder than expected. I read up on pathfinding algorithms and wrote implementations of both breadth-first search (BFS) and A-star. That wasn’t so hard. What was hard was doing that and still stay within the 500 millisecond time limit, especially since the server seems to run slower than my home PC so tests that run fine at home times out miserably on the live server. I’ve since learned that traditional pathfinding algorithms can work only if combined with heavy use of caching to vastly reduce the number of searches necessary. It’s a good thing that the servers allow each bot to use up to 2Gb of RAM!
The new hotness that I’m now experimenting with are diffusion techniques. A user started a thread about this on the official forums and my own tests indicate that it’s a lot less computationally intensive than repeatedly making BFS and A* calls. This approach also plain makes sense. The metaphor here is exactly similar to the scent trails used in Maxis’ old SimAnt game. Instead of using pathfinding to generate a valid path from an ant to an objective, use scents that diffuse automatically from high density zones to lower density ones. Then each ant simply has to head in the direction of the strongest scent values.
I have no illusions about getting into the top 100 this year. Even getting into the top 500 will be an achievement. From what I can see, even the bots in the 600s have tactical AIs that is capable of judging when to advance and when to retreat when enemy ants are nearby. Currently, I have no idea how to go about implementing something like that. For now, my near-term goals are to test diffusion with food gathering, which I now currently do wit h BFS, and to institute some sort of static defense mechanism for my anthills. I’ve lost far too many matches in which a single lucky enemy ant wandered up to my completely undefended hill.
Anyway, for those interested in this contest, you still have time to write and submit a bot. Submissions end on 18th December and I’d love to see more Malaysians give me some competition for the top spot in the local rankings.