Previous year's contest tasks have ranged from a 3D Ray Tracer to playing a board game in a round-robin tournament against the other entries.
The intention before the contest was that Alex and Bruce would form the core of the team, working for all three days, from midday Saturday (NZ time) until midday Tuesday. Keith could help during the weekend, but had to work Monday and Tuesday. We were also expecting to have Andreas Bogk, but unfortunately technical problems kept Andreas out of communication until the last six hours of the contest.
As suggested by the name of the team, we used Dylan as our primary programming language. Dylan is a high level compiled dynamic language that is well suited to rapid prototyping of complex algorithms while also offering performance comparable to C in the parts of the program where that is critical. Andreas and Bruce previously formed the core of a team that used Dylan to take 2nd place in the ICFP 2001 contest.
The supplied tracks were all laid out on bitmap images of 1024x768 pixels. Pseudo-code was supplied for the physics model to use to calculate the position and velocity of the car at a particular time step, given the position and velocity at the previous time step, and the control inputs.
The distance and time units were arbitrary, but in order to make things more concrete in his mind Bruce attempted to reverse-engineer the mathematics based on the physics model given and the dimension-independent observation that rubber on road friction is usually good for approximately 1G of cornering acceleration. The conclusion was that probably one pixel represented 1m, and each time step was 1/100th of a second.
This selection of units gave the car a top speed of around 250 km/h and acceleration at normal speeds comparable to a typical four cylinder 2l family car -- but unlike a real car the acceleration force was independent of speed, so it was more like a rocket- or jet-powered car than like a normal wheel-driven car. The brakes were also rather poor, perhaps something like drum brakes rather than modern disk brakes.
While waiting for the contest start at noon we drive to the supermarket to stock up on junk food and also borrow a 1.5 GHz Athlon (1800+ to marketers) in case a little more firepower will be useful.
Once the task is announced Bruce sets about writing low-level Dylan classes to represent tracks, strings of commands, the state of the car and so forth in order to provide a foundation for optimization algorithms. Keith does the same in C++ in order to write an OpenGL program to animate the car driving around the track. Alex has missed a lot of sleep the previous night so goes home to bed.
Despite the duplication of effort, both Bruce and Keith complete and debug their code by midnight -- 12 hours after contest start -- and call it a night.
Alex arrives after having some sleep to pick up the work and spends the night trying various approaches to optimizing the tracks or finding a solution automatically. Lots of paper is wasted with not much progress, apart from understanding. :-)
Keith adds to his OpenGL program a simple ability to drive the car interactively around the track. It is easy to at least take a reasonable path, but proves to be very very difficult to do it quickly, as it is hard to judge how tightly the car will turn, or how far it will take to stop -- and the brakes are quite useless so that if you are overcooking a turn then braking just makes it worse, not better (and according to the rules you can't turn while braking). A projection line showing where the car would stop under continuous braking is added, which helps a little and also gives some idea how tightly you might be able to turn.
Bruce succeeds in driving the car rather badly around several of the tracks and a lightning entry is contemplated, but rejected.
Alex starts writing a post-optimizer that will (hopefully) take a badly-driven track and improve it.
Bruce continues to scribble on paper and write experimental code for global optimization, without success.
The contest rules provide a tenth racetrack, with different physics allowing sliding as in rally driving, as a tie-breaker. With each track taking anything from 3,000 to 15,000 time units, there seems to be essentially zero chance of two teams getting the same total for nine tracks, so we ignore the tie-breaker task.
The program now shows six different things:
A partnership is born, with the computer doing the grunt work of modeling the physics, and the Mk 1 eyeball doing the pattern recognition to enable the right driver commands to be given at the right times.
Bruce abandons the global optimizer effort and starts driving the different tracks in earnest.
Keith continues to add more features to the simulator:
Alex's post-optimizer is working. Typically over multiple runs it can eventually improve Bruce's manually-driven tracks by a hundred units or so, sometimes more, sometimes less. Alex continues to tweak it.
Bruce continues to re-drive tracks. Alex's optimizer might be able to improve any given attempt by fifty time steps, but sucessive manual attempts can easily vary by several hundred time steps or a lot more if a drastically different track is found!
Eventually there are good attempts for all the tracks except 4_EatYouAlive and 9_PhilAndSimon. Long sucessions of S-turns strung tightly together are defeating the manual driving approach. A small mistake on one corner quickly magnifies into a very bad racing line and slow speeds a few corners along.
Just before the contest is finished (in the last two hours), our total goes from just over 88,000 to 81,000 or so (with a big improvement made on 9_PhilAndSimon), Alex's optimizer pushes down 9_PhilAndSimon to our final total of 79,682 and we decide that we don't have any more time to find a new eyeballed path in the ten minutes remaining. :-)
It's time to submit our entry. We're happy with seven tracks, unhappy with two, but nothing can be done about it now. We triple-check our best traces, write a README, package everything up and submit our entry nearly ten minutes early.
We include a not-very-good solution for the rally track, using normal physics (which is OK, as Rally physics doesn't apply unless you brake while turning...).
We feel we've done better than last year, when we placed 35th. We think we've done well against others who drove manually, and have probably beaten 95% of people who wrote optimizers, but if anyone managed to actually get a global optimizer to work well then we're surely toast.
Hudson's entry is quite interesting. It remains the best of which we are aware, prior to the official announcement of the winners. A few random observations on Us vs Hudson:
Our entry proved to be a real team effort. Without Keith's OpenGL simulator we wouldn't have had an entry at all. Bruce's driving seems to have been good enough to get us into the same ballpark with good automated approaches. In many cases those extra fifty or more time steps gained by Alex's post-optimizer may prove to be critical in determining whether we are in the top few or not -- on the four tracks on which we beat Hudson, the margin was between three and forty nine time steps!
It's just a pity we sucked so badly on two of the tracks :-(
