ICFP 2002 Contest Entry Description - Bernd Paysan

I heard about the ICFP contest last year on EuroFORTH 2001, and decided to team up with Anton Ertl, so that ICFP gets a Forth entry, too. I planned to take some days off, to be relaxed and well-prepared.

However, things went differently. My current project at work is close to tape-out (I make money by designing chips), so "some days off" are not in question. After reading the task description, I decided first to help Ian Osgood (Anton in the meantime joined a team of Ocaml programmers), and after the first pieces of code went well, while Ian had a few problems with Gforth, sockets, and Mac OS X, I decided to finish and submit my entry. Start it with

./busy-bee <host> <port> [-v]

Good points: The task was interesting, and implementing a solution was fun. The algorithm for the shortest path search works well with an imperative language.

Bad points: The judges' server is ways too slow to check for larger maps, and I hadn't time to write my own server. Since the server has much less to do than the client, I think this shows that functional programming languages (Haskell in this case) are not always a good idea ;-).

The scores are out

And wow, I'm rank 10 out of 168. My bot seemed to have a problem with the large map, but otherwise was fairly good. I decide to claim that Forth is a cool language for a lone programmer with lack of time.

How the bot works

• The distances over the map are computed using a modified flood-fill (or wave propagation) algorithm. The modification allows different path length depending on the ground, and remembers the direction(s) that lead to this particular point. This algorithm is O(reachable locations), and apart from the map itself, it needs an array to represent the distances of every point. Bug: I misremembered the upper bound for the buffer size. A complicated enough map can cause the program to hang.
• I annotate the map with "difficult ground", ground that's close to water, narrow channels, enemies that can be pushed (a detour around the enemy is cheaper most the time), cornered enemies (cannot be passed), and packages the enemy dropped (pathes over this ground will be cheaper). This modification isn't complete, since it would require to change the wave propagation algorithm, which I didn't. It however works quite well when there are several equivalent pathes.
• The robot strategy is the following:
1. First drop packages that are at their destination
2. Then pick packages shortest-path first (no attempt is made to get a maximum load, just pick packages as long as possible)
3. Try to deliver the cheapest picked package
4. Search for the nearest package with known destination (may be one at the home location, or one dropped by another robot). This is only half-hearted, becase what I really want is the package with the cheapest path for pick up and delivery.
5. Search for the next home
6. If there's nothing to do, kill myself with an illegal bid. There's no point into continuing the game, since the score will count.
7. What I forgot to put here last is to search for the nearest package with unknown destination. However, when the bots go to the same home base, there's a good chance that I get knowledge of the destinations before the other bot can "hide" too many of them. After all, I'm notified of other bots dropping packages, and I know where this happens.
• No attempt at fighting is made. Also, no attempt is made at calculating bids. Bids are randomly -1 or 1.
• When there's more than one direction to go at equal costs, choose one randomly.

: play ( -- )
    drop-packs ?dup IF  <bid> drop" command  EXIT  THEN
    pick-packs ?dup IF  <bid> pick" command  EXIT  THEN
    my-p $@len  IF  cheapest-package <bid> move" command  EXIT  THEN
    count-packs IF  nearest-package <bid> move" command  EXIT  THEN
    homes $@len IF  cheapest-home <bid> move" command  EXIT  THEN
    cr ." Don't know what to do, killing myself" 0 0 drop" command ;

I spent about 10 programming hours totally on the contest; as said above, I hadn't prepared time to participate. However, I got a working bot, so I submitted it. I'm more interested how my bot scores against lightning entries, because if I had the time, this would have been one. I had to work again on monday, which would be a full working day on the contest, given that I'm sitting in Europe, and 12:00 PDST is 21:00 MDST. And as listed above, I had several good ideas afterwards. That's life.

Forth isn't a safe language, and it doesn't have abstract data types. It's ok for parsing simple languages (and the language used here was close to ideal). Data types for lists of packages and such can be implemeted ad hoc, and so I did. libc bindings are available, so the non-standard stuff such as talking to sockets is not difficult.

Since the contest reference machine runs x86 Linux, I could use my own native code Forth for Linux, bigFORTH.

About Forth

You can read why I use Forth here.

Origianlly, Forth was a language for embedded control. However, Forth is a general purpose language. It doesn't provide high level data types, but it provides ways to extend the language. The inventor of Forth, Chuck Moore, did know about Lisp, and so some influence can be seen. Forth eliminates the parenthesis of Lisp by being reverse polish. Instead of binding arguments to variables, arguments are passed anonymous on the stack. Stack manipulators allow to access variables. The computation principle is called "concatenative", and there are concatenative functional languages, like Joy. The most widely used concatenative language however is Postscript.

Like Lisp, Forth is an interactive language. Testing programs by using the interpreter is very common when developing in Forth, and it helps to create working programs fast. I use the interpreter to parse the server's response.

: N  1 y +! ;
: S -1 y +! ;
: E  1 x +! ;
: W -1 x +! ;
: X get# x ! ;
: Y get# y ! ;
: P get# robot id = IF sp@ cell my-p $+!  THEN  mark-robot ;
: D get# id robot = IF dup my-p delete-p THEN  mark-pos ;

Like Lisp, Forth is extensible, and extensions become first-class elements of the language. Metaprogramming is possible, though in this application, it wasn't necessary. It's possible to define own data types with DOES>, and even that was used only at one place, for robot-specific variables (position and alife status).

: robvar ( -- )  Create 0 , DOES>
    dup @ 0= IF  dup >r s" " r> $!  THEN  $@ drop robot cells + ;

robvar alife
robvar x
robvar y

I used my string package for all the dynamically sized arrays. For the next contest, I'll prepare a number of data types:

• Integer Hash: a integer indexed structural data type (the basics of a in-memory relational data base)
• Hash: a dynamic associative array, indexed by a string
• S-expr: a structured data type capable of storing and evaluating XML and S-exprs

Here, only the integer hash would have been useful. Also, using dynamically expanding data structures for everything would have been a good idea. Just counting on assumed upper bounds wasn't wise.

My toolset includes an object oriented extension to Forth, which was useless here, and a GUI library with everything, including a 3D turtle graphics. I didn't feel that creating a special display was necessary, since the ASCII output worked well enough. It might have impressed the judges, though (using the 3D turtle graphics to render a perspectific view of the map with animated water, and the robots walking through).

This document is certainly not written in HTML, but in a Wiki-like language, and processed by a Forth Program.