created 02sep2002
wf icfp.html "ICFP 2002 Contest Entry Description - Bernd Paysan"
--
* ICFP 2002 Contest Entry Description - Bernd Paysan
I heard about the [ICFP contest|http://icfpcontest.cse.ogi.edu/] last
year on [EuroFORTH 2001|http://dec.bournemouth.ac.uk/forth/euro/ef01.html],
and decided to team up with
[Anton Ertl|http://www.complang.tuwien.ac.at/anton/home.html], 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|%bernd.paysan.tar.gz]. Start it with
#./busy-bee# __ __ _[_#-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|http://icfpcontest.cse.ogi.edu/scoring/] 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|%tree.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:
<<
+ First drop packages that are at their destination
+ Then pick packages shortest-path first (no attempt is made to get a
maximum load, just pick packages as long as possible)
+ Try to deliver the cheapest picked package
+ 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.
+ Search for the next home
+ 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.
+ 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.
>>
:code
: play ( -- )
drop-packs ?dup IF drop" command EXIT THEN
pick-packs ?dup IF pick" command EXIT THEN
my-p $@len IF cheapest-package move" command EXIT THEN
count-packs IF nearest-package move" command EXIT THEN
homes $@len IF cheapest-home move" command EXIT THEN
cr ." Don't know what to do, killing myself" 0 0 drop" command ;
:endcode
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|bigforth.html].
** About Forth
You can read [why I use Forth|why-forth.html] 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.
:code
: 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 ;
:endcode
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).
:code
: robvar ( -- ) Create 0 , DOES>
dup @ 0= IF dup >r s" " r> $! THEN $@ drop robot cells + ;
robvar alife
robvar x
robvar y
:endcode
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|icfp.wf] is certainly not written in HTML, but in a
Wiki-like language, and processed by a [Forth Program|%wf.fs].
---
.