I was delighted to receive the judge’s prize for the ICFP programming
contest 2014 as part of “Team gagallium”  for being, in words of the judges, an “extremely cool bunch of hackers”. This post describes the secrets of our submission.
The main goal of this year’s International Conference on Functional Programming competition was to implement an AI for a variant of Pac-man running on an arcane architecture — a variant of a lisp machine, ironically coined GCC by the organizers. The second goal was to implement an AI for the ghosts running on a completely different architecture — an 8-bit micro controller coined GHC. The organizers scored the submissions by pitting the contestants against each other.
Our performance was decent, but not enough to reach the top of the leader board. So why did we win the jury prize? According to the judges, it was for two reasons: first, our ghost was apparently the best one (more on that in a mo); second, we re-targeted the OCaml compiler itself to produce the code for the Lambda-man, earning massive kudos (see the video here.)
We wrote our ghost in assembly, using a thin assembler to have labels and constants. The main feat of our ghost is his ability to follow a corridor to check whether it is a dead-end before entering it. Sounds simple, sure, but implement it using an 8-bit assembly language and it becomes much harder. This feat makes it possible for the ghost to pick the right direction at intersections, avoiding dead-ends (unless the lambda-man is trapped in it) and moving in the general direction of the target (or in the general direction opposite to the target in fright mode).
We had other perks like a timer implemented on two bytes of memory (wow) to make it possible to synchronize ghosts between “scatter mode” and “chase mode”, and a fancy convention for function calls. Playing with an 8-bit micro controller is surprisingly exciting.
For the Lambda-man AI, we wrote a compiler from OCaml to the Lisp machine. Specifically, we used the OCaml compiler to get one of its intermediate representations (the one just after type checking), and plumbed it into a code generator for the Lisp machine. Our compiler does not support all of OCaml, but it was sufficient to implement a decent AI. The AI performs a depth-first search to find a path that maximizes a value function (which takes into account good things like eating a pill, and bad things like being eaten by ghosts). This DFS was informed by an approximation of the ghosts’ positions for the next few steps, which often made it possible to avoid dying. If no good path exists in the neighborhood of the Lambda-man, it tries to find a path to a single pill further away (as a last resort). There were a few bad ideas in this code, but it performed quite well in the end!
Last but not least: we had some good fun over the week-end and some great food (my team mates were gourmets like myself, which is always good). The code of our submission is available here. It contains our AIs, the sources of our compilers and also our implementation of the game engine with a fancy GUI.
Enjoy! François Bobot, Pierre Boutillier, Thomas Braibant, Damien Doligez, and Gabriel Scherer