The Lumberjacks are Winning

I’m still working on ForestryService. I spent two hours last night trying to convert it to using a mutable vector instead of a list to keep track of the forest, but I couldn’t get all the monad stuff sorted out.

Tonight I switched to a non-mutable vector and had it running in about 10 minutes. When I turned optimization on the program flew until it got to image generation, which is still an issue. So with that solved I decided to try to track down my lumberjack bug.

It didn’t take too long. I added printouts to see how many lumberjacks there were at the start and end of each turn and quickly found the culprit. When a bear and a lumberjack collided and a mauling occurred I had the test backwards. I was removing the non-mauled lumberjacks and keeping the one who was supposed to be removed due to injury. One character change.

But that led to another issue, one which I thought might be a problem. We can end up with a couple of bears, but the number of lumberjacks quickly explodes. Within 25 years I have 1400 lumberjacks. At that size the list operations on lumberjacks (specifically finding if a square if free of other lumberjacks) absolutely dwarfs all other calculations in the program. I need to store them (and while I’m at it the bears) in sets. That would change my search from linear to log and should fix the issue. It will also make some of the tests cleaner since I don’t have to find intersections manually.

After that it’s back to the image code. I’m not sure if the problem is my pixel generation or the image library it’s self. I think it may be the integer division I’m doing to implement a basic scaling algorithm, but I haven’t profiled it since I switched to vectors.

Also I fixed all the spelling errors in the file. I can’t spell “forest.” I fixed it in the file and repo name before I first pushed ‘em to github, but I didn’t touch all the variables and methods before.

A Week of Haskell. Also… Ruby

Over the last week and a half I’ve spent quite a bit of time writing Haskell programs. I needed ideas for what to do so I started giving some of the challenges in /r/dailyprogrammer a try.

First Challenge – Lines

The first one was LineIntersections.hs, which I posted as a GitHub Gist. It was for the #163 – Hard challenge. This was mostly practice since it didn’t require much in the way of new skills compared to my WordLadders program. It took me a few tries to find a good line intersection algorithm that would tell me where the lines intersected and to get that implemented.

Second Challenge – Termites

Things got much more complex with #163 – Intermediate, my solution is called BunkerMaster. You’re given a little map and you have to help humans build walls around their living area to keep out giant killer termites that come out of a nest.

Most people were doing an A* algorithm repeatedly to keep closing off the paths that the termites could taken. This often minimized the number of walls used but also tended to minimize the human’s area due to the way people implemented it. I’ve written A* algorithms before, in a way that’s what WordLadders used. I wanted to try something different so after a while I came up with the idea of flood-filling the map from both endpoints and putting walls wherever things met.

To do this I marked two boolean bits on each square of the map to note if the humans or termites has reached that square. As soon as both bits were set we knew we reached a place that needed a wall. I would end up with more walls than necessary but the humans and termites has similar amounts of territory on ‘fair’ maps.

The biggest problem I had once my solution was done was that because I was processing both opponents each turn if they met in the middle you can end up with double walls. It could be fixed but it didn’t seem worth it.

Third Challenge – Befunge

I really had to press myself for the third challenge. #164 – Hard was a challenge to create a Befunge 93 interpreter. If you’ve never heard of it before it’s an esoteric language designed to be nearly impossible to compile by using a 2D grid of mutable characters as instructions and non-stack storage. Here’s an example that prints 99 Bottles of Beer:

v v0\1:\1:{CODE}{CODE}\!:p15-<     Bottles of Beer for Befunge
0 \ {befunge} >" ekaT">v   written by Brian Raiter, 5/97
0>>.0"llaw eht no "v<#,:   breadbox@muppetlabs.com
"\,     >"eno"^>0 #"^1^_v
c1,>51g#^_"ti"^. >vr :  $
"::^" down, pass "<e    5
>^|\*25,<^     # i e ^g1< 
  ,>052*":dnuor t"vbv:<
v0_^    .      , ^< " "
>52*".ll"v   >,^   fb e
v<v<v_$!|>"aw eht no r"v
""" ,:  >" ;"^      f ^<@
meo >^"bottle"<    "o   $
o m^"re:"<v  _^#g15<  v_^
s""  >52*^>"s"^v"les"<,:
"^<  ^"99 bott"<    >^>^<
>" yub ,erots eht ot oG"^

Yeah.

So if writing an interpreter (which I’ve never done) for an odd language (which I didn’t know) wasn’t enough, I pushed myself by using the State monad (actually StateT stacked on IO) to keep track of and modify the interpreter state.

My interpreter is called BefungeIt and ran the test programs I found. It’s not 100% compatible since I don’t limit the size of the stack and I don’t think Befunge is supposed to have 32 bit stack values.

Figuring out the state stuff took quite a few tries. My worst bug took me maybe 20% of the total programming time to fix. When I was supposed to pop two values off the stack and then save the result in a memory cell I was accidentally *restoring* the stack values at the end of the function because of the way I modified the state. This caused any program that used the ‘p’ instruction to go haywire, but after stepping through things (and learning a fair amount of Befunge along the way) I figured it out. In the end the state monad was quite useful.

Fourth Challenge – Forestry

Now I’m working on ForestryService, which I started for #165 – Hard which asked for an ecology simulator.

I started this using the StateT stuff from my interpreter to carry the state of the world. I’m learning quite a bit here as I’m using things like sequence, mapM_, and more.

I went crazy with this too, because what fun is a step-by-step ecology simulator if it doesn’t output graphics? So I’m doing something I’ve never done in any programing language: output an animated gif of the world changing over time.

In fact that’s the slowest part of the program by far. Having to get the state of each of the 10k cells each frame is where most of the time (and memory) are being spent in my program. At the moment I’m doing the easy thing and using lists of lists to store everything and that’s not nearly performant enough. I plant to try replacing that stuff with a mutable Vector, but I haven’t gotten to that yet.

I’ve had to fix quite a few bugs. Things are supposed to be able to move to any of the 8 neighboring cells, but a mistake in my list comprehension meant they would only walk diagonally. That was harder to find that it should have been because I forgot to call the functions that reset how far characters could walk each turn so they would only walk once ever.

Right now I know of one bug (besides performance): something is causing a plague to kill my Lumberjacks. I haven’t figured out what’s happening but over the course of a year I can lose hundreds of ‘em when no more than 1 should disappear. This is probably a test somewhere that’s not restoring values correctly, but it needs to be debugged.

When I’m done with this (or at least further through it) I think I’m going to ask /r/haskell about it. All the state transformation code looks way too imperative to me. I know that’s supposed to be a benefit of the state monad but I’m worried that I may have taken it too far.

I ran a quick profile on the code to see what was slow (any other hotspots are currently dwarfed by the gif creation, which was pretty obvious just from running it), but I was surprised how much faster the code got when compiled with -O2. Since I spent so much time in Java I’m not used to thinking about having to turn on a special optimization mode, that’s done automatically by the JRE. It’s been a while since I worked with a compiled language (well the Objective-C stuff I did didn’t need that kind of performance tuning).

Then There’s Ruby

Playing with Haskell has had quite an effect on my brain. I enjoy strongly type languages and have been LOVING ghc’s ability to find errors and suggest solutions. I’ve found myself doing things in Java at work and thinking “Haskell would have caught that”.

Well in the last few days I’ve been working on a little Ruby program/set of scripts at work and… it’s different. After my little Haskell immersion week going to an ultra-loosely typed language like Ruby is a huge swing of the pendulum. Besides simple parameter checking Ruby doesn’t seem to be too sharp at parsing. As an example I was missing an “end” in my file and instead of indicating the problem at the end of the file or in the actual problem area it indicated a problem with a requires statement at the top of the file (which was a total red-herring).

I’ve looked at Ruby before but I’m not very familiar with it and I keep getting surprised at how many options there are to do some things. Often there are multiple methods that are just aliases for each other (such as Array.length, Array.size, and Array.count), which makes me wonder a bit. I’m also having problems with documentation I’m finding online. While the core documentation is pretty good 3rd party gems often have highly questionable documentation that was clearly auto-generated and doesn’t provide any information that’s not in the method signature. I already know that a method takes 2 parameters and returns an Object; I want to know if that’s a String or a MyStruct or a whatever.

Bits of Ruby style are also getting to me. I’m so used to camelCase that I keep having to catch myself to match the use_of_underscores that seems to be the common Ruby style. I’m not sure about some other stylistic points, such as when I should use parenthesis in method calls or if people put “then”s on their “if”s.

I was quite happy to see characters on the end of method names to indicate if they’e a predicate (such as .nil?) or if they have side effects (such as .map!). I was really impressed with that pattern when I first saw it in Lisp/Scheme and it’s nice to see another language use it.

I’m having problems finding advice on Ruby online though. For example I wanted to print a number in Hex and did a quick Google search. Numerous sources told me that num.to_s(16) would do it, but Ruby complained that to_s didn’t take parameters. I’m not sure if that’s a version issue (I’m using 2.0, but 1.9.x and 2.1.x both seem to say they support it) or what. I’ve also run into a few things questions the solutions are clearly poor and a library found in a later answer is a much better solution. I ran into this finding people suggesting rolling your own command line option parser instead of something in the standard library. I get the feeling this is because of the number of people writing Ruby without much programming experience not knowing how many libraries are out there, much like I remember seeing in PHP.

Despite all this I’m having fun. I love playing around in new languages and I’m getting work done.

But I want to get back to playing with Haskell. I want to help my Lumberjacks.

WordLadders in Haskell

Over the weekend I wrote my first Haskell program. It’s called WordLadders and I’ve spent a total of about 5.5 hours on it.

I’ve been interested in functional programing for quite a while. Last year I started reading about Haskell more heavily, including all of Learn You a Haskell and Real World Haskell. I’d been trying to find a small program that I thought I could actually make on my first try, but I hadn’t come up with any really good answers.

Then on Friday Nathan Smith posted I wrote a Go program for solving “doublets” (AKA word ladders) using A* search algorithm on /r/golang. It uses a dictionary and the A* algorithm to try to connect two words through a list of real words, changing only one letter at a time. So if you entered “goat” and “toad”, the path might be goat -> goad -> toad.

Well that seemed simple enough to me. There are only four parts to the program:

  1. Reading in the dictionary file
  2. Creating a graph that links the words together
  3. Finding the shortest path between two words with A*
  4. Handling user IO (getting words, showing answers)

That’s the order I ended up writing the program in. Haskell has a reputation that “If the code compiles, it works (almost all the time)“, and that was my experience. My program contained only a single bug that the compiler didn’t find. When doing recursion within my A* implementation I was forgetting to remove the node I just processed from the open set, leading to an infinite loop. There’s no way for the compiler to catch that, but it caught everything else.

The actual process of writing the program was a little rough. I use IntelliJ all day at work and wanted to continue to use it, but the Haskell plugin doesn’t work right now. Development just picked back up after a two year hiatus and the old plugin doesn’t work with my (much newer) version of IntellJ. In the end I ended up using TextWrangler with a simple syntax highlighter and the ghci REPL.

My program works correctly as far as I can tell. It can find the longest word ladder (between ‘charge’ and ‘comedo’) in 8.5s on my 2010 MacBook Pro. It also correctly handles words that can’t be linked (such as ‘apples’ and ‘spoons’).

I’ve posted it to /r/haskell to get some advice on improving my program. There are a few things that I felt I stumbled on. There were also some issues I didn’t fully understand, but as often happens the solutions came to me while I was writing out the questions. Rubber duck debugging strikes again.

Building and Running My Polargraph SD

Complex print (better picture)

Once I received the kit, it didn’t take me too long to build. I used RJ-11 jacks and cables to connect the motors and gondola to the controller board. I started to print out the Polargraph SD’s case after it was posted to Thingiverse this morning. It’s going to take some time, the bottom of the case is just a little too big for my Thing-o-Matic, so I had to slice it into two pieces.

It certainly takes a long time to print, so I’m glad I waited to get a version that could run without a computer attached (although I suppose that could have been my Raspberry Pi’s job). Since nothing is being heated over 220° C, I don’t worry about leaving it alone. I’ve been starting prints before I leave for work in the morning, so they’re ready when I get home. That didn’t work out perfectly today, when this happened:

Solid square GameBoy

It had been going for about 7 hours. I’ve been trying the different printing styles, and this was called “solid square wave”. That seems to mean that every pixel that isn’t blank is solid black. Since it wasn’t turning out to be much of a drawing, I stopped the print.

Polargraph brownout

I’ve had other adventures too. We had a summer storm last week that caused two very short brownouts. They were long enough to trigger the alarm on my UPS, but not long enough to cause problems with my TV, XBox 360 or other electronics. The capacitor’s in the Arduino’s power supply kept it running, it never missed a step.

On the other hand, the steppers didn’t fare as well. It looks like when the brownouts occurred, there wasn’t enough current to keep the stepper motor’s locked in position, the pen fell down the paper. That caused the neat little mistake above. I’m using a giant linear wall-wart for a power supply, and I guess it doesn’t have enough output filtering to be able to supply the motors during those fractions of a second.

I’ve had a few other adventures. At one point I accidentally changed the pen width to be much too wide. This caused drawings to look too sparse (first attempt), instead of having the contrast it should.

I also had a positioning problem caused by running firmware that was too bleeding-edge out of the SVN tree. It meant I got to help debug the problem, which Sandy quickly fixed. When I tried the Norwegian drawing style, I ran into an issue with the way The Gimp made the headers on PGM files, which I fixed myself. That meant I wrote and submitted my first patch to an open source project.

What To Do With A Raspberry Pi?

Raspberry Pi case

Earlier this year when my number came up in the queue, I put in my order for a Raspberry Pi. It arrived in the last week or so, and I printed out HansH’s case to give it some protection and style. The print took surprisingly little time even though it wasn’t accelerated.

The only problem is I haven’t figured out what to do with it yet. I use Rogue Ameoba’s Radioshift (which apparently is no longer developed) to record two radio shows, but they don’t show up as podcasts in iTunes. I’ve been thinking of using the Pi to server up those files to iTunes so they would show up correctly.

Second Best Clojure Bot, Postmortem

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,335th 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.

AI Challenge Entries Closed

Aside

The entry period for the AI Challenge has closed, and they’re doing the final games. I really haven’t updated my bot in two weeks or so. I had some more ideas to do and optimizations, but I never got around to it. In the end, it looks like I’ll be the 2nd place Clojure bot as one of the other that was more actively developed took a giant leap above me. I’ll be happy to try again next year.

Courage is Better With Cowardice

 

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 2nd 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.

Less Bugs In My Clojure Means More Ants

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.

Now With Line of Sight

Over the weekend I updated my bot to use a line of sight to decide on what to do for each ant. This fixes some of the worst behaviors my ants had, but it’s not perfect. The ants no longer crowd up trying to get to food or a hill they can’t reach, but they’re still not terribly bright. I had to turn off the food reservation system because it wasn’t intelligent enough and the side effects were worse than the benefits.

So how smart is my bot now? I’m not sure. It should be better, but the AI Challenge keeps having server problems. My bot had to wait most of the weekend for games to start being played again, and they seemed to have another problem today. Because of this games aren’t happening very fast at all so my bot hasn’t had the chance to move up to it’s true rank. The AI Challenge forms have posts about alternate servers you can test you bot on, I may have to go to that.

I’m a little tired of working on the bot at this point, even though I can think of quite a few things I should do. After all the time I’ve put in lately, it would be nice to see my bot reach it’s potential (or at least where it was before the last change). The slow game rate was very demotivating.