ICFP 2003 Contest Entry Description - Bernd Paysan

I've already participated in last year's ICFP contest, see description. 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:

You can also download my submission, 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, 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. Since this program needs more RAM than usually reserved, start bigFORTH with

xbigforth -m 64M racer.fs

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:

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

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:

race1 init-genes 200 mutations

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

$20 to population#

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 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 is certainly not written in HTML, but in a Wiki-like language, and processed by a Forth Program.