created 06jul2003
wf icfp2003.html "ICFP 2003 Contest Entry Description - Bernd Paysan"

--

* ICFP 2003 Contest Entry Description - Bernd Paysan

I've already participated in last year's
[ICFP contest|http://icfpcontest.org/], see
[description|icfp.html]. Since I scored rather well (10th), I was
quite motivated to participate this year, too. Also, I took the third
day off, since last year, having only two days weren't enough.

This year, other obstacles kept me away from working full-time. First,
the weather in Munich was wonderful, and I left the computer to go
swimming on the afternoons. Second, my father's birthday barBQ cut off
most of saturday evening. And my sister needed my help to lift a 70kg
flower pot into the fourth floor... But enough lame excuses, here's
how far I got:

<| <> 1
+| *Track* | *Score* |+
-| [1_Simple.trc|%tracks/1_Simple.png] | 10639 |-
-| [2_Hairpins.trc|%tracks/2_Hairpins.png] | 18683 |-
-| [3_Sepang.trc|%tracks/3_Sepang.png] | 19978 |-
-| [4_EatYouAlive.trc|%tracks/4_EatYouAlive.png] | 22137 |-
-| [5_Car.trc|%tracks/5_Car.png] | 6725 |-
-| [6_IcfpContest.trc|%tracks/6_IcfpContest.png] | 5777 |-
-| [7_Gothenburg.trc|%tracks/7_Gothenburg.png] | 4902 |-
-| [8_ManyWays.trc|%tracks/8_ManyWays.png] | 10614 |-
-| [9_PhilAndSimon.trc|%tracks/9_PhilAndSimon.png] | 15642 |-
-| Sum | 115097 |-
-| [X_Rally.trc|%tracks/X_Rally.png] | 51696 |-
|>

You can also download [my submission|xmen-racer.zip], written in Forth.

** How my bot works

Two things were clear immediately: First, this was a task that
requires visualization. And second, this was a task where an optimal
solution is very likely NP complete.

For the visualization, I choose [MINOS|bigforth.html#MINOS], my GUI
extension to Forth. It provides a turtle graphics, which is the only
widget I need in this case. I use only a very limited subset of this
turtle graphics: paint an icon at (0,0), and draw x,y paths. The
obvious color for the car was yellow (don't know why it is so obvious,
but a lot of other teams decided to use the same color ;-), and red
after it crashed (it never should paint red, but you can't know...).

Since I've made some changes to my Forth since I last put an official
distribution, anyone who wants to run my program needs to download the
[current snapshot of bigFORTH|%bigforth-2.0.10.tar.bz2]. Since this
program needs more RAM than usually reserved, start bigFORTH with

:code
xbigforth -m 64M racer.fs
:endcode

The first step thus was writing a simulator and the visualization. I
also wrote a file interpreter to see how the sample track works
out. Run the sample track with the following command from the bigFORTH
dialog window:

:code
raceEen s" Een.trc" run-file dist ? step# ?
:endcode

BTW: spaces matter in Forth. The output should be #0 9479 ok#, meaning
that the distance to the goal is 0 (reached it), and the number of
steps executed is 9479.

The next task is the internal representation of the track: I choose a
simple 2D array with three values: 0 for road, 2 for goal, 1 for the
rest. A second array then is computed that contains nearly-euclidean
distance to the goal (starting from the left side of the goal, with
the goal itself being impassable). I use the same flood-fill approach
I used in last year's contest for the robot, modified to
pseudo-eclidean coordinates (diagonals are weighted sqrt(2), and there
are three arrays for updating; this flood fills the field with an
octagonal growing rule).

To evaluate how good a path is, I check how many steps it took, and
how far it is still to the goal. Steps weight more than distance to
goal (since there are several steps per pixel necessary). Pathes that
actually hit the goal get a favour. Generally, the lower the score,
the better.

For the actual path search, I use something that remotely resembles a
genetic algorithm. A "gene" is a command that contains a fractional
accelleration, a fractional turn, and deltas for these fractions, and
a number. The execution of such a command dithers accelleration and
turns. On the top node of each path, I "conventionally" search for a
good continuation by going 500 steps with a number of random path
commands (limits reasonable set). The steps number the best path
managed to drive before crashing (or ending on the road) is then
reduced by a random amount (at least to 60%) before appending it as
gene. Non-crashing paths and paths that hit the goal get preferrence.

There's a population (default 16, I used 32 and finally 64 for running
the actual game - the higher the population, the better. Twice the
population gives a better result than the best of two runs). After
each run, the population is sorted by score, and the lower half is
killed and replaced by mutations of the upper half. Since "good" paths
tend to duplicate, I also mutate them, so that there's only one unique
path in the population. There's no sexual interbreeding. The
population has to be as large as posible, since competition is global,
when the goal is reached. The path stabilize on the start first. The
populations are there to avoid being stuck in local minima.

Paths can mutate in a number of ways: First, parameters can change
randomly. This is restricted to the last few genes, since changes in
earlier ones will quite likely throw the path off road. Paths can also
mutate by reducing the last command length to half, and by dropping a
few genes, and mutating a bit further.

Due to the shorting of the path, it takes quite a while to have the
best path actually finish. Therefore, I added another step that uses
the best-path search, but doesn't reduce the path length at the end of
the game. This finalizes the path.

I also added skidding for the racing contest; I didn't invest a lot of
time to get it good, especially since it's only a tie braker. It does
reach the goal in the simulator, and it does use skidding (don't know
if it actually helps ;-).

This sort of heuristic random solution can in fact make use of an
infinite amount of computation, and still won't give an optimal
solution. I only have a single Athlon 600. Tuning the algorithm took
quite some time, and an important part of tuning was to get it solving
as many tracks as possible by itself (without adjustment of the
constants). I have some ideas to improve speed (e.g. caching the
result of the unchanged part of the path), but didn't implement these
ideas. As always, there have to be some compromises between meeting
the deadline and the quality of the implementation. I later got a
significantly better result for track 9, by growing the population to
128.

A race is played with the following command from the xbigforth dialog
prompt:

:code
race1 init-genes 200 mutations
:endcode

Hit Esc to stop (when you think that it's "good enough"). Each race
(race1 to race9 and raceX) know where to save the result. You should
give a big enough number for the mutations, since this program stops
after this many rounds. If you want to increase the population, do

:code
$20 to population#
:endcode

right at the start (definitely before "init-genes"). For the
completely unnecessary tiebraker, do #x: on# before to enable
skidding.

The program crashes occasionally with an "Invalid Handle" message
short after startup, which I didn't care to fix (it's sufficient to
get results, the likelyhood of crashing increases with the
population). In any case, just kill xbigforth, and start it anew.

** Ideas that didn't get in

One problematic point is that I examine paths with rolls. That's not
optimal - you can always do better with accellerating and breaking
afterwards. A roll is only acceptable if you turn all the time.

I spent some time at tuning the genetic algorithm, but it was for sure
not enough. One problem is the score of the appended genes: It is
measured at the end of the path. A better way would have been to
remember the maximum score it reaches on the way.

Another problem is the interpolating parameter: It is too large for
long paths, but good for smaller ones. It would have been better to
store this parameter independent of the actual path length.

** 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.

I used my string package for all the dynamically sized arrays.

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 wanted to write a 3D animated racer to impress the jury,
but tuning and running the algorithm took too long.

[This document|icfp2003.wf] is certainly not written in HTML, but in a
Wiki-like language, and processed by a [Forth Program|%wf.fs].

---

.

bye