Tuesday, July 15, 2008

ICFP 2008 programming contest

It's been about a week since our team (myself, Pieter Holtzhausen, Loftie Ellis and Albert Swart) completed the ICFP programming contest. I think I've had enough sleep now for a little writeup.

The most important problem was that the provided sample maps and server was not necessarily representative of what we will be judged against. Assuming martians are not a threat (either not smart or too few), the optimal strategy is to ignore them, keep accelerating and dodge craters and boulders on the way to the home base. If a map contains martians of significant intelligence, they will have to be avoided.

Our approach was to continuously switch between 2 modes:

1. Given a goal position (initially the home base), move towards that goal. If there is an object in the path towards the goal, set the goal to be directly to the side of the obstacle. Once we arrive at a goal, reset the goal to the home base and repeat.

2. If our strategy is to take martians into account, predict if we will collide with a martian on our current velocity and path. If we will collide, change the goal position to be somewhere else.

We decide on our mode based on what was learned about the map. By default we start in the first mode. If we were killed by a martian or have observed more than 4 martians at once in a previous run, start the next run in martian avoidance mode. If we ran into a crater, ignore the martians by next time starting in the first mode.

We wrote everything in Python. We spent most of the time on tweaking the goal following code, keeping the server communication stable and fighting with the lack of a Windows version of the server. Towards the end we tried A* path finding to hook into the goal following system, but decided not to include it in our final version. We also have an alternative visualization system based on OpenCV.

I'm quite proud of our entry. We never collide with any craters or boulders if enemies are ignored. If enemies are taken into account we effectively make running away from them our short term mission. I'm a bit worried they will test our code against maps with dead ends, or that our martian avoidance code fails (because it hasn't been thoroughly tested).

I predict the first few places will be taken by entries that can characterize the type of map quickly.