ICFPC 2008

It seems that I've got the second place in ICFPC 2008. I'm really appreciated this result. I think I was very lucky. I don't think my program was excellent. For example, my rover would run poorly if there are difficult maps, like complicated maze.

I'd like to put some notes on my implementation. My rover had three parts:

Calculate geometry informations: Just like other teams, my rover guessed some parameters using the information. Since there are some latency between server and client, my rover calculates the future position using the log of commands sent to the server.

Macroscopic planning: All obstacles are memorized. If some of them are near enough each other, they are considered as a cluster. If there is a obstacle between the rover and the home, my rover decides left or right using some heuristics. The heuristics was like 1. if my rover is far from the obstacle, choose the way which makes the path after the obstacle easier (with this logic, my rover could solve easy mazes) 2. otherwise, consider safety first, then consider distance. Hmm... actually, I forgot the detail.

Avoid risk: Suppose that the state of my rover is "accel and right turn". Simulate a second using the current state. If it turns out that my rover will die, my rover considers that the current state is risky. In this case, my rover tries 8 simulations with other states. If there is a state which can avoid the risk, my rover sends the commands to be the safe state, ignoring the macroscopic decision. If all states is risky, choose the state which can alive as long as possible.

I wrote a visualizer. It was important for me to fix many bugs. It shows the macroscopic plan using line. Also, it changes the color if my rover considers it's risky.

http://shinh.skr.jp/dat_dir/icfp08.png

After the contest, I wrote some scripts to show statistics.

http://shinh.skr.jp/icfp08/

Anyway, it was fun and I feel happy. Thanks for organizers!