The dates for the 2015 ICFP programming contest have been announced on the contest webpage. This is a good occasion to dig out a summary of our 2014 participation, that had been written over the span of several months (mostly right after the contest), and that we had unexplainably failed to publish before.
In 2013, some Gallium members (Thibaut Balabonski, Thomas Braibant, Jacques-Henri Jourdan and Gabriel Scherer) participated to the ICFP programming contest, and it was a lot of fun. We participated again in 2014, with a bit less gallium in the team (blame the precarity of post-docs, and some badly-chosen dates for a honeymoon) and a skewed alphabetic distribution: François Bobot, Pierre Boutillier, Thomas Braibant, Damien Doligez and Gabriel Scherer.
This (double) blog post was written over the course of the last ~5 months by three different persons. With hindsigth, we could probably have phrased some of the post differently. We believe that this blog post is best enjoyed as a pot-pourri of our thoughts, much like our ragtag submission.
The subject of the 2014 contest was the following: a computer game called Lambda-Man, a variation on Pacman, running on an arcane (simulated) computer architecture with heterogeneous processors. We were asked to implement a Lambda-man AI (the player character) on a Lisp-machine-inspired processor architecture, using a functional but relatively low-level programming language, and to write ghost programs (the attackers) on very low-level co-processors, using a low-level assembly-like language. The organizers funnily enough called the functional low-level language “Gcc”, and the Ghost language “Ghc”.
Because it would be too long to be read comfortably in one shot, we split the document in two posts: we will now mostly focus on the Lambda-Man AI, and describe the ghost in a later post.
Our broad design
We wrote a Ghost in ghost machine code, using a very thin assembler to have named labels and simple constants. The ghost AI, due to Damien and Thomas, is relatively elaborate and is probably the best part of our submission (Editor’s note: the judges specifically refered to our ghost as the best of the competition. See the annoucement.).
For the Lambda-man AI, we wrote a compiler from OCaml (what else?) to
the Lisp machine. Specifically, we use the OCaml compiler API (as
exposed in the not-well-documented
package) to get the “lambda” representation to the Lisp machine.
“Lambda” is the representation used just after the compilation of
pattern-matching, the choice of data representation, and a couple of
very simple type-directed specializations; it is an untyped
representation that is rather close to Lisp, and was thus a fitting
choice. In particular, lower-level representations (bytecode or Cmm)
have already performed closure conversion, which was unnecessary as our
backend supports closures. You can inspect the lambda-representation of
an OCaml module
foo.ml by running
ocamlc -dlambda -c foo.ml.
We then wrote the Lambda-man AI using OCaml, in the subset that our compiler supports (more on this in the “# Compiler limitations” section). The AI is rather simple; a problem in our team (and I guess many other teams) is that everyone was quite excited at writing a compiler, but nobody was really fond of writing AIs, so we delayed this part to the very last day of the contest.
In retrospect, I think that reusing/porting/hacking an existing language (OCaml) was a great choice, because it allowed us to test our IA code not only on the organizers’ simulator, but also by compiling it as an usual OCaml program with the usual OCaml toolchain, which has less bugs (than our own compiler backend) and is much more efficient. This saved our sanity of mind many times.
The lambda-man AI
We iterated quite a lot on the lambda-man AI in the last few hours of the contest. One problem is that we had a lot of fun with the ghosts and the compiler, and we delayed working on the main part of the contest till the end. Here are the main features of our lambda-man, which was mostly implemented by Thomas with help from Gabriel:
at initialisation time, it computes the graph structure of the map (seen as a vector of vector of possible directions); this makes it possible to have a more efficient main loop in the time constrained part of the game.
our main loop is a depth-first search that computes the best possible path of a given length, based on a few heuristics. Broadly speaking, the value of a path is the sum of the value of the pills that are eaten along the way, plus an approximation of the value of the ghosts that are eaten, minus a huge value in case our lambda-man gets eaten. One nice thing is that Gabriel implemented a function that predicts the possible positions of the ghosts in the next few steps, which helps take good decisions in tight situations (rather than flee blindly if a ghost comes nearby).
since this DFS is quite costly and cannot be used to find a long path, we had to put a failsafe mechanism in place that tries to find a pill if no “good” path is available.
finally, our lambda-man “remembers” its decisions and try to keep its path, unless its path is blocked by a ghost or a ghost is too close.
There are quite a few problems with this basic solution. For instance, our lambda-man will quite often let a pill alone (because its AI forbids backtracking). Then, it does not try to maximise the use of power pills (and does not even give the proper value to the ghosts eaten in succession). Also, it does not computes the proper timing of the moves of the ghosts – each ghost move at its own pace, and keeping track of this situation might be useful in tight situations.
Finally, in the heat of the last fifteen minutes, Thomas added (amond
other changes) the
Fruit line in the part of our code that
computes the value of a path:
let content = get2 map pos in let value, fright = match content with | Pill -> value + 10, fright | Power_pill -> value + 50, fright + 20 | Fruit -> value + 15, fright (* Blunder *) | _ -> value, fright in ...
This is a real bad idea, and it was obvious soon enough. Problem is
we ran out of time to correct it (“Never try to update your submission
in the last 120 seconds of the contest”). The problem is that
Fruit indicates a cell of the map where the fruit
may be, not the position of the fruit updated in real-time. It
turns out that this single line makes our lambda-man perform quite
badly, because it might try to run in circle around the Fruit cell.
There are plenty of one-line changes that could solve or mitigate this
issue: e.g., removing the line, or changing this 15 value into 5, or
just checking that the fruit is indeed present at the time of the
evaluation. Too bad.
The OCaml-to-Lisp-machine compiler
The compiler, written mainly by François (which first experimented the backend by hacking on the miniML compiler of Andrej Bauer’s PL zoo, thanks Andrej!), only implements the bare minimum we need to write our AIs. We made two design choices:
We would only implement the minimum needed; so we have no modules, no polymorphic variants (or at least we didn’t check that they were supported), and even our compilation of pattern-matching was a bit lousy: the OCaml compiler will generate various kind of code depending on whether it thinks, for example, that binary tests or jump tables are the best way to test something, and we only added support for the various lambda-code instruction as our AI examples revealed a need for. It’s a compiler that is meant to be used in tandem with a backend hacker, implementing (or fixing) the features as your need evolve.
We wanted the OCaml datatypes to be compiled in such a way that we would need no separate FFI layer to talk with the values given to us, in Lisp-land, by the game engine. At the beginning of each turn the lambda-man AI is passed a big tuple of linked lists that represents the map, each, and we wanted those to fit exactly the representation of some OCaml datatype. Another option would be to represent the OCaml datatypes however we like, and add the FFI types as primitives that can only be inspected through special compiler primitives.
Those two choices are inter-linked: representing OCaml records as Lisp tuples (our goal) is harder than as Lisp lists or Lisp closures (did you notice how frame environments are the only memory structure in this Lisp machine that allows reasonably compact storage of data?), because the access pattern for the very last element is not the same as the others. We ended up without records, but with good support for OCaml tuples (implemented as Lisp tuples).
Another OCaml-using team (the OCamlpro guys) made the different design choice of having the FFI as compiler primitives, and also implemented a more complete support for the rest of the OCaml language – we’ll let them describe their solution if they want to.
Data representation tricks
We initially wished to have a valid OCaml representation for Lisp
0 for the empty list or a cons-cell
(x . xs) for… a cons cell
x::xsq), and arrange
our compilation of OCaml tuples and records to be exactly Lisp tuples
(a . (b . c)), note how there
is no end-marker). This is all that was needed to talk natively with the
world representation passed to our Lambda-AI. We ended up with no
records, OCaml tuples that were exactly Lisp tuples and, surprisingly,
OCaml lists that mapped directly to Lisp lists (we would have
been happy with having to define a hand-made OCaml datatype).
Focusing on tuples for now, we faced two independent issues:
Constructor tags: OCaml variants (sums) and tuples/records (products) come with a header word that contains some GC-specific information and a “constructor tag”; it always is 0 for tuples and records, and for variants it indicates the constructor. For example with the datatype
type foo = | A | B | C of foo | D of bar * baz
Bare represented as (tagged) integers, and the heap-allocated blocks are
0, one parameter) and
D (y, z)(tag
1, two parameters).
Directly translating this to cons-cells would give to the OCaml tuple
(a, b, c)the representation
(0 . (a . (b . c))), which is not good to talk to the FFI (of course we could convert first, but constraints sometime provoke creativity).
Irregular access: with the Lisp representation, the access pattern for the third-element of a triplet is distinct from the first or second. Unfortunately, the lambda-representation of field access in the OCaml compiler tells us which field to access, but not the total length of the structure (when it is statically known; the same field-access instruction is used for arrays and strings). We would need to compile
getfield foo 3different if
4or more, and we don’t know which it is.
Solving the irregular access
Thomas had a cool idea to solve the irregular access problem: let’s
preprocess the OCaml source-code to replace each n-tuple by a
composition of 2-tuples, just as in the Lisp representation:
(a, b, c) becomes
(a, (b, c)), and we gain the
invariant that field accesses are always to index 0 and 1, which map
In theory this also works for records: translate record types to tuples and, on record field selection, use the type information associated to the field to know which field number it is, and translate that accordingly. (OCaml 4.00 supports distinct record types sharing field names, so you really need typing information here.) It works in theory, but processing the OCaml typedtree is painful enough in practice to be worth it; so we did not implement this for records.
The preprocessing for tuples is amazingly easy to do using Alain Frisch’s visitor-pattern Ast_mapper library.
Solving the constructor tags
The two data structures we care about the most are linked lists and tuples; in both case the tag is 0. Gabriel suggested that we make that a rule: let’s forbid non-0 tags, that is, sum types with strictly more than one non-constant constructor. We can then never include the tag and get exactly the Lisp tuple representation.
That may seem like an awful limitation, but as PhD students (or, for the most part, former PhD students), we get paid to know about arcane type-system tricks we would never hope to suggest in a serious discussion, but can use in situations like that: you can translate any OCaml type declaration into an isomorphic one respecting this condition (at most one non-constant constructor), using GADTs to simulate sigma-types. The type declaration above gets rewritten as:
type foo = | Foo : 'a foo_tag * 'a -> foo and foo_tag = | A : unit foo_tag | B : unit foo_tag | C : foo foo_tag | D : (bar * baz) foo_tag
And we used this trick in our AI implementation, in this rushed implementation of logarithmic-access immutable arrays (we didn’t implement any support for mutation, as pure and strict is clearly the way to go):
type 'a vect_tree = Tree : ('a, 'b) vect_tag * 'b -> 'a vect_tree and ('a, _) vect_tag = | Leaf : ('a, 'a) vect_tag | Node : ('a, 'a vect_tree * 'a vect_tree) vect_tag type 'a vect = 'a vect_tree * int let get_vect (t, n) i = let rec find : type a . int -> int -> a vect_tree -> a = fun i n -> function | Tree (Leaf, v) -> v | Tree (Node, (left, right)) -> let mid = n / 2 in if i < mid then find i mid left else find (i - mid) (n - mid) right in find i n t let rec vect_of_list li = let rec consume li n = if n = 1 then begin match li with |  -> assert false | x::xs -> (Tree (Leaf, x), xs) end else begin let mid = n / 2 in let left, li = consume li mid in let right, li = consume li (n - mid) in Tree (Node, (left, right)), li end in let len = list_length li in match consume li len with | tree,  -> (tree, len) | _, _::_ -> assert false
For reference, we uploaded the sorry state of our code at the very end of the contest as this archive. (This is not an open-source release, because it would be work to prepare one.)
The ghost (readable) assembly are in:
The lambda-man source is:
Actually running our code
- ocaml 4.01 (including compilerlibs (+unix +graphics))
gcc/ contains compiler ./ocamlgcc.native from OCaml (minus records, references, exceptions) to gcc. « make » compiles it.
mlia/ is the AI of lambda man written in OCaml. In this directory do
../gcc/ocamlgcc.native « an_ia.ml » --print --no-execto get some gcc code
ghc/ contains an assembler ./asm.byte of ghc. « make » compiles it.
ghosts/*.g contains the assembly of our ghost AI. It must go though ../ghc/asm.byte « an_ia.g » to give correct ghc code.
At top-level you can try
ocamlbuild -use-ocamlfind main.nativeto get our not working own game simulator (you’ll need « cmdliner » to compile it)