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 compiler-libs ocamlfind 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.

PS: We spent quite a few hours implementing a simulator (interpreters for Gcc and Ghc, and game rules engine), but we couldn’t make much use of them in the end. Time would probably have been better spent experimenting with the Javascript API directly from the start. On the other hand, we kept the option open to actually simulate other’s ghosts in our lambda-man, which would have made use of our Ghc simulator – written in OCaml; we didn’t have the time budget to make that work, though.

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:

  1. 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.

  2. 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 lists (either 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 (eg. (a,b,c) is (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

    A and B are represented as (tagged) integers, and the heap-allocated blocks are C x (tag 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 3 different if foo has 3 fields, or 4 or 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 directly to car and cdr.

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

Our productions

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:

  • ghosts/genius.g
  • ghosts/genius2.g

The lambda-man source is:

  • mlia/graph_local.ml

Actually running our code

We use

  • ocaml 4.01 (including compilerlibs (+unix +graphics))
  • ocamlfind

In code/

  • 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-exec to 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.native to get our not working own game simulator (you’ll need « cmdliner » to compile it)