Team Name : Aqua Team Hunger Farce
Members : Jack Diederich [aka jackdied] jack_diederich atthehost email.com

Why Aqua Team Hunger Farce you ask? Because there was one minute left to the lightning submission deadline and it sounds better than anything I could think of for the The Brak Show. My computer wallpaper is Brak Show, so I was looking at it at the time. If you want to know more, here is the Aqua Teen Hunger Force fanpage. Visit the site, the images were 'borrowed' from there. I could have changed the name for the real round, but I didn't

Update. Results out. I'm not in 'em

Tarball is Here
I included compiled C DSO's for my modules. If you aren't on intel/386 recompile them with 'python2 setup.py build'. It assumes that 'python2' is your python 2.2.1+ binary. If this isn't the case change the one-line 'runme' to something else (If you don't have python 2.2.x it won't run at all). By default it will unpack into a directory called icfp_athf/

My ICFP History

Lessons learned this time, get a real friggin team. There are a dozen things I could have done that I just didn't have time for. And I'm sure there are a couple ideas that never crossed my mind. If you look at the bottom of my TODO file, you'll see 'DROP MULTIPLE PACKAGES'. If we're at a location that has multiple deliveries, they'll just have to wait for the next turn. This could be considered a drawback.

Links links links

Every link below here is a link into the pretty-printed HTML version of the source code. Most of it is python, a little C.

Old! Server

Lightning Entry: Meatwad  

Regular Entry: Frylock

Python made it possible,

• Generators, to fine tune the CPU different heuristics get
• Exceptions, to skip over heuristics when they fail
• _VERY CLEAN_ C interface. If you have ever tried to write a C extension to perl you have no idea what you are missing.

The Basic umph of this program is a fast AStar search. Or if you are also in Massachusetts, a wickedfast AStar search. The priority queue was re-written in C with python bindings, the priority queue consumed most of the time, so this made the AStar much much quicker. The map keeping-tracker was also re-written in C. For a 1000x1000 map it consumes 1/10 the memory of the supplied test Server! To limit the AStar from running forever without returning, we use python Generators, which are very powerful. On my development box (I borrowed an Athlon2000+ from work) it can go about 13k continuations on the generators per second. This gives us very fine control over time slices. Python's exception mechanism was also very handy, in non-critical places where I knew the code was buggy or we look for a beneficial but remote possibility we just resume at the next heuristic and purr along.

Bot Heuristics

1. continue_walk() If we are going somewhere, try to pathfind to 7 steps later to allow (the broken?) other player avoidance pathfinding and water avoidance.
2. good_package() If there are packages HERE, try to pick some up
   • find the closeset one, then calculate the closest to the closest to make a delivery route
3. deliver_package() If we are carrying packages, try to deliver the closest one
4. Find a base, and go there in the hope there are packages
   • (Any package dropped from bumping becomes a maybe-base node, any package dropped in the middle of nowhere becomes a doubtful base node. search in that order, delete if we go there and there are no packages)
5. The server hasn't called the game to an end, pick a spot and go there, resume 1)

AStar heurisitics:

• +1 for moving onto a plain square
• +2 if we are 2 steps away from water
• +6 if we are 1 step away from water
• (this next part doesn't work, players never get added?)
• +8 if there is a player on that square
• +4 if the square is next to a player

neighbors: NSEW are calculated at startup and kept in bit fields for fast results

CPU usage heursitics

• 'jiffies' Not true linux jiffies (1/100th of a second) but the number of steps the AStar search can be run. Generators make this possible.
• an Athlon2000+ can do 13k jiffies per CPU second
• start with 100k, on our first turn we have to try harder because we don't know anything
• cap available of 1 million (so they won't kill our process if it runs for 30 minutes)
• each turn add INC jiffies to available, defaults to 10k
• if our average CPU time is > 1, lower INC by 1k
• if our average CPU time is < 0.8, raise INC by 1k (max 100k)

FindClose

find = FindClose(start, list of destinations)
answer = find.try_weakly()
if (still need an answer or have spare CPU time)
  answer = find.try_harder()
if (no answer and DESPERATELY need a solution)
  asnwer = find.try_hardest()

FindClose heuristics

• sort the list with the standard heuristic abs(startX - destX) + abs(startY - destY)

• guess that it will take 200 jiffies per destination to find the answer (GUESS = 200)
• take the N first destinations from the list, where N = Available Jiffies / Guess
• If the board width * height > 5000, only use the first two
  (This is to limit memory usage, not CPU)
  This may be a severe limitation of the program on big boards, but we don't want to get disqualified
  
• for each item in the list, new() an AStar object
• while (Jiffies.available > 0)
  

        foreach gen in generator:
          gen.next()
          if (gen.has_answer)
            add the answer to the list
  	  remove gen from the generator list
  

try_hardest()

• pick the two best from try_weakly()
• set available jiffies to 200000
• then do everything that try_harder() does

FindPackage

  run FindClose.try_harder()
  if (Jiffies.available has lots of time left)
    pick the best package
    do a FindPackage with the Start coords being the DESTINATION of this package
      recurse while we have lots of time left

Bidding Heuristics

• Default, bid 1
• If we are close to another player or water, Bid 1
• All other conditions, bid 1

The Map object is written using C array, which cuts the memory usage by an ugodly amount (4M vs 40M)
Each space is represented by two bytes
Byte 1, how close are we to a player
Byte 2

• bits 1-4 NSEW do can we move to the square NSEW of us
• bit 5 WARN_H2O are we two squares away from water
• bit 6 DANGER_H20 are we right next to water
• bit 7 GOOT_SQ is the square open/move-onto-able
• bit 8 BAD_SQ is the square a wall or water

The neighbors function used in the AStar search calls the Map object to find its neighbors, the routine examines the bitmap and returns Python tuples for each of the coordinates.

Bugs

• 'bid 1' is not always the optimal strategy
• I keep track of how close other players are in order to avoid them. That routine never gets called.
• The bot is only capable of dropping one package at a time
• The bot is capable of picking up many packages at once, but I've never seen him do it (7 packages == 7 turns)
• There are some glaring typos in the submitted source that are hidden by try/catch blocks. These heuristics are basically skipped if they hit the wrong code path (which might be never, I don't keep track)
• The Unknown, always the unknown