Well, the Google AI Challenge is over, and I ended up as the second best Clojure bot. My skill rating was 53.23, which put me in 1,335^th place. I never expected to be so high, but it turns out there weren’t a lot of Clojure entries. I was beaten, by a large margin, by thobel. He did a great job. With the contest over, I thought I’d post a little postmortem of how my bot worked.

Global State & Exploration

My bot really doesn’t keep any global state, which is one of the reasons it didn’t do better. I planned to start adding some, but I never got around to it as I got distracted by work and other things. Here is the only global state that really matters:

(def ^{:dynamic true} *current-defense* (atom nil))
(def ^{:dynamic true} *positions-to-fill* (atom #{}))
(def ^{:dynamic true} *positions-unfilled* (atom {}))

(def ^{:dynamic true} *ant-last-moves* (atom {}))

The first three variables keep track of bot’s defenses, which is the only form of coordination between the ants. *ants-last-moves* keeps track of the last move each ant made so they can be prevented from backtracking.

In fact, the backtracking prevention is the only form of exploration in the code. Each ant sets out when spawned in a random direction, and ants have a 90% chance of continuing in the direction they were already traveling.

Core Logic

The core of the bot is a function called process-ants-for-moves. It is called once for each ant and is responsible for determining what that individual ant will do. In the last set of changes I uploaded, I added some code to keep track of how long the turns were taking and abort processing if it hit the 90% mark. It runs the process-ant function for each ant, building up a list of where the ants new positions are so they can be sent to the server at the end of processing.

The process-ant has a list of individual functions it can apply to the world state to find the best move for the ant. Cleaning things up with some pseudo code, it looks like this:

(defn find-move-through-functions
  "Run each function, return the first valid non-nil direction"
  [ant valid-directions valid-directions-with-back ants-last-move]
  (when (not-empty valid-directions))
    (loop [functions-to-run {move-to-defend-our-hills :defense
                            move-to-emergency-defense :e-defense
                            move-to-capture-hill :capture
                            move-away-from-enemy :run-away
                            move-towards-food-classic :food
                            move-in-random-direction :random}]
      (if (not-empty functions-to-run)   ; Still functions to check
        (let [the-function-stuff (first functions-to-run)
              the-function (key the-function-stuff)
              the-function-purpose (val the-function-stuff)
              result (apply the-function ...)]
          (if (= :none result)
            nil     ; The answer is 'don't move'
            (if (empty? result)
              (recur (rest functions-to-run)) ; No answer, try next
              (random direction from result))))))))

This works quite well. It runs each function in turn for the ant. If the function returns nil, the next function is run. Otherwise a random direction for the list of possibilities the function returns is chosen as the ant’s move.

The Move Functions

There are quite a few of these, including some from experimentation that don’t actually get run. Here is the description of those that are in use, in priority order. They all tend to follow the same pattern. I never put it into a macro or function, but that would have been smart. Here is the basic template:

(defn some-move-function
  [ant _ _]
  (cond
    (check that that function applies, such as if we see enemies)
      nil  ; It doesn't

    :else
      (let [distances (calculate distances to things of interest)
            spots (sort distances and filter out things too far away)
            visible-spots (stuff in spots that's line-of-site of ant)
            closest-spot (first (first visible-spots))]
        (when closest-spot    ; If something matches the criteria
          ; Some additional processing may be done here
          (utilities/direction ant closest-spot)))))

The line-of-sight code was a pretty big improvement. It meant that ants no longer got stuck against water trying to get to a piece of food on the other side. The function is basically Bresenham’s line algorithm. It’s not perfect, but it worked well enough and was pretty fast. As it walks along the line, it checks for water. If it doesn’t find any, the line-of-sight is clear.

Each function returns a set of directions the ant should move in, and the code picks one randomly. The selection is weighted so the ants tend to move in straight lines.

move-to-defend-our-hills

This is the function that uses up most of the global state. The global variable *current-defense* is checked to see what kind of defense we should be running. This is set at the start of each turn based on the number of ants we have per hill.

This is the code that sets up the little formations around my hills. First the ant is checked against the list of defense positions. If the ant is already on one of the spots, the answer is the keyword :none, meaning “don’t move from that spot.”

If the ant isn’t in a good position, it checks to see if it’s within visual range of a spot that does need filling. If so, it goes straight to it. This has the effect that newly spawned ants first action is to move into any holes in the defensive positions. Because of the way the defenses are setup (and since ants can’t move diagonally), attackers have to come in from a corner or two-abreast if they don’t want to lose their ants. This was remarkably effective.

move-to-emergency-defense

Once the defensive positions are filled, the next thing to do is to run emergency defenses. The code finds the closest visible hill to the ant, and then checks if any enemy ants are too close.

If they are, any ants that can see that hill rush back to try to stand on top of it. This floods the hill with defenders, hopefully allowing it to survive the onslaught. Since there is no real state on the ants, as soon as the danger is passed (the enemies are gone), they go straight back to normal behavior.

move-to-capture-hill

Whenever my ants see an enemy hill, they go straight for it. There is no hesitation, no strategy, just suicide charges. As a result of the next function (move-away-from-enemy), my ants don’t tend to get near enemy hills unless the area is not well defended. I’ll often lose ants this way, but it’s amazingly effective at grabbing hills people leave undefended. If an enemy moves so much as moves a square or two off a hill, my ants have a good chance at taking it.

move-away-from-enemy

This function is my bot’s entire survival instinct. My ants run in the other direction from the closest enemy that’s within 8 squares. This does hamper food gathering, but it prevents my ants from getting roundly slaughtered during movement. Note that this function doesn’t apply if the ant is in one of the defense modes (since this function wouldn’t get run), or when the ant is within view distance of one of my hills (an old condition from before defense mode so my ants wouldn’t give up their home bases).

move-towards-food-classic

It’s called “classic” because I came up with a better function for finding food, but it was never turned on due to performance problems. This function simply moves the ant towards the nearest piece of food they can see (with the line-of-sight check). In practice, having multiple ants go after the same piece of food wasn’t a problem.

moves-in-random-direction

If nothing else came up with a move, the ant would go in a random direction. This caused (limited) exploration.

Things I Meant To Do

If you look through the code, you can find commented out sections from some of my experiments. One of the early ones was move-towards-food-res. It would find the closest ant to each piece of food and record a reservation. This prevented multiple ants from going towards one piece of food. When I turned this on, my ants picked up much less food. The simpler method seemed to work better.

The better method of finding food was diffusion. There are globals and functions to take the food that the bot knows about and diffuse their influence, producing a gradient that the ants could follow to the areas with the most food (see influence mapping).

It turned out that this was much too slow. Others got it working (quite well), but I didn’t. Data structures were (I think) a big part of this. I was using a pseudo queue made out of a vector, and it wasn’t that fast. As it turns out Clojure has a queue that simply has no syntax yet which was very fast, but I didn’t get around to converting my code. The other thing that would have helped was not recalculating everything each turn. I started planning this but never got around to it either.

Many people used some form of this to explore the maps, which would have also been a smart thing to do.

Debugging

One thing I learned a fair bit about was debugging. It’s something difficult to do in Clojure (since there aren’t any native debuggers that I know about), so I had to invent some. I started debugging by sprinkling my code with statements like this:

(utilities/debug-log "Ant at " ant " doing " the-function-purpose ", going " dir)

The actual function looked like this:

(defn debug-log
  "Log something to the console for us to go through later"
  [& message]
  (when defines/logging-enabled
    (binding [*out* (if (nil? defines/*log-file*)
                        *err*
                        defines/*log-file*)]
      (apply println message)
      (flush))))

First the function checked to see if logging was enabled. If it was the *log-file* global variable was checked. When defined, the code would write the log message out to a file (which I would use to follow what my bot was doing). If the file wasn’t defined, it would just spit the message to standard error (which would cause the ants server to mark my bot as crashed for producing unexpected output).

Later I started using the visualizer that was available in the forums, but I had to be careful. I found the python server wouldn’t terminate if I produced too much visualization output.

Summary

That’s basically it. I’ve put my bot’s source up on my GitHub account if you want to take a look at it. The Clojure code is in the src/ directory, and it’s pretty clear that it was under active development when I stopped. Code is still commented out in places from debugging.

My ants had already learned courage, and now they know the importance of cowardice. It’s been about two weeks since I uploaded a new bot, and this new version is much improved. The last real version of my bot was able to play 63 games, and ended with a skill rating of about 58.

Today’s intelligence level: real swarm.

It took a couple of deploys to get the newest version of my bot up, but after only a few games it’s now rated at almost 69. At the moment I’m typing this, my bot is once again the best Clojure bot in the content, and is on the edge of the top 500 (although I expect to fall out shortly).

After doing some simple work on my bot (such as using the random seed the content provides to let you run game replays correctly), I found and fixed the bugs I had mentioned last time. The biggest problem the last version of my bot was having (besides stupid behavior due to bugs) was defense. Since the ants didn’t care too much about enemy ants (and sometimes actively avoid them) under the right circumstances it was possible to walk in and take one of my hills without too much effort. The bug fixes made this worse as the ants spread out better so there were fewer to act as defense.

This was fixed by implementing a strategy that I thought of a while ago, but was remedied of when I saw a competitor using it. By strategically placing ants around my hills I can raise the bar for anyone trying to attack. In the picture at the top of this post you can see my 2^nd level arrangement (out of three). This simple defense works great against single file streams of ants. Combined with new code that causes all nearby ants to run home if the hill gets attacked my hills have been able to survive much longer than they ever would have before. In some games, an enemy loses all their extra resources unsuccessfully trying to take my hill.

Things aren’t perfect. A side effect of the way things work is getting an ant near one of my hills can, under circumstances that aren’t nearly rare enough, prevent my bot from doing any further work. My colony may survive, but it’s not out gathering food or razing other hills. This in combination with a large number of opponent ants means that my bot can be shut down and eliminated by a correct show of force.

The last thing I had to do was fix a problem I didn’t expect to have: my bot times out. In easy games (especially the initial “does the bot crash” game bots run through when first uploaded) my bot can generate so many ants that it actually goes over it’s turn time. I added a little code so skip processing ants when my bot is about to run out of time, and I have seen it in action in production. Due to some quirk of the Python server implementation the order of ants to the bots being tested in is a discernible pattern. So when ants stop moving (because I ran out of time and didn’t get to issue them any orders) it makes a very obvious pattern on the field.

While the code seems to work very well, it does still fail on the ultra-small test map for some reason. I’m going to have to keep an eye on my bot to see if it happens in any other games. I may have to make it more aggressive.

My bot is getting better. After taking a little time off, I spent a few hours last night making updates. While I haven’t deployed them, my current bot has continued to test it’s potential. It’s been playing a lot of random_walk maps (which it handles better than the maze maps), and my rank is now in the top 1200.

Current intelligence level: stupid swarm.

While spending a bunch of time yesterday, I uncovered a couple of bugs in my code that explained some of the odd behavior I’ve seen (such as ants getting stuck together in small features). It turns out that I was using contains on a list, which does nothing. This is actually rather odd. contains checks to see if a key is in a collection, but doesn’t raise an exception in this circumstance. keys shows the behavior that I was expecting:

user=> (contains? (list 1 2 3 4) 3)
false
user=> (keys (list 1 2 3 4))
ClassCastException java.lang.Long cannot be cast to [...]

So because of this, some of the tests I had in my code were useless, essentially always returning false. On top of that, I found another bug. I was checking to see if collections were empty like this:

(if (empty my-collection) [...]

That’s a mistake too. empty is a new function in Clojure 1.3 which returns an empty version of the collection passed to it (so it will give you an empty set if you pass it a set). This also caused subtle bugs. The correct function was empty?, but I wasn’t looking that closely at autocomplete.

With that fixed, my bot looks quite a bit better. The ants don’t get stuck and they spread out better on all maps, even though there isn’t any code specifically instructing them to do that. When testing, I noticed that this means it’s much easier to take my hills because there are fewer ants milling about now. I added some code to have everyone rush home when an enemy approaches, but I haven’t given it any real test yet. It looked like it might have kicked in during  test game, but I was tired of working by then and decided to do the real testing later.

So as it is, I don’t want to post my updated version until I can test better. If I post what I have at this moment I’m pretty sure my rating will drop more than a few points. But I now know that my bot can handle over 600 ants without timing out. Before it almost never got above ~250 because the ants ended up blocking the hills.