Cult of the Bound Variable
ICFP 2011 Programming Contest


Cult of the Bound Variable, the descendants of the CMU-affiliated team that ran
the 2006 ICFP Programming Contest, is usually a rather large team. This year,
we were not only large but had active participants in five different cities on 
three separate continents (Pittsburgh, New York City, Boston, Paris, and
Bangalore). 

In order to allow many people to participate together and have fun, in many
recent years our overall design has been "arena" based - we allow different
subgroups to explore many different solutions during the contest, but all the
code is pulled into a shared sources.cm file. This greatly facilitates sharing
and means that people can either work on finished submissions or shared 
libraries throughout the contest. We tag everything with revision numbers
with the knowledge that sometimes progress goes backwards, and the code
at the end of the contest is not always the code we want to use to build our
final submission.

We describe several aspects of our submission, from roughly the highest to the
lowest levels: the Kompiler (a compiler), DOS (a scheduler), the individual
candidate players, the Demonic Tutor (a match server), and CARDFAX (a web 
tracking system).


== The Kompiler == 

Because we like writing functional programs, not SKI combinator terms, we wrote
a compiler to cards, the Kompiler, which allowed LTG programs to be written in
a higher-level abstract syntax using a lambda-like combinator library (with a
convenient integer building combinator).  The Kompiler translates lambda-terms
to card-combinator terms using a call-by-value variant of Curry's "optimized"
bracket abstraction algorithm which takes into account whether the variable to
be abstracted over occurs in the body of the abstraction or not:

    [x] x = I
    [x] V = K V  (if x not free in V and V value)
    [x] V x = V  (if x not free in V and V value)
    [x] M1 M2 = S ([x] M1) ([x] M2)

This algorithm produces *vastly* smaller terms than the naive approach given
in the contest task description in many common cases by omitting needless
applications of S.  (An interesting bug in an early version of the Kompiler
omitted the value checks, causing effects to happen too early, or worse, to be
discarded entirely -- including the effect of non-termination!)

After producing a combinator term, the Kompiler "linearizes" a term, turning it
into an equivalent term that can be created by only left- and right-applications
to constant cards.  Two of our team members had dramatically different ideas for
linearization, both based on the core idea of eliminating parentheses using S
and K:

        t (u v)
    === (K t v) (u v)
    === S (K t) u v

In the case that either u or v is a card, the last term is "more linear" now
than the given one, and linearization can proceed on the remainder, either v
or u.

Each linearization strategy produced smaller terms in different cases, so in
the end, we decided to just run both and pick the smaller output.  We
recognized early on that producing small terms is paramount, since every left-
or right- application spent building a large term costs an entire turn of play.


== Dominators and the Dominator Operating System ==

The Dominator Operating System is a response to the competing demands of 
needing to do several things (defense, short-term offense, long-term offense)
well. It allows a contestant to be made of several Dominators, the aggressively
named thread abstraction in DOS. The main role of DOS is to handle memory
partitioning and scheduling for the scarce resource of plays.

Individual dominators can use the operating system to reserve slots for their
processes, fork, block for certain events, and manipulate their running
priority. There is no memory protection, so dominators have to be careful not
to execute functions that write into the slots of other dominators. Slot are
divided into those that are easily addressable and those that are not.
Addressable slots are those whose number can be quickly computed in the
combinators language. Allocated slots are automatically cleaned up on process
exit, and if a process was created with a parent process, it will also be
killed with the parent exits.

At every turn, DOS runs the "preview" function of every dominator so that the
dominators can look at the state (possibly changing its priority in response)
and update their internal memory. Then, DOS selects a single process and runs a
"taketurn" function that allows a single dominator, as determined by the
scheduler, to either run or yield its slot to another process.  Each process is
created with a priority that controls how often it runs relative to other
processes.  This priority may be changed dynamically.

In addition to dominators, the "userland" of DOS also provides several other
services which dominators may use. For example, "EmitProgram" allows a dominator
to spawn (and optionally block on) a child thread which, given a program, will
make the program appear in a specified slot.

Underlying DOS are two abstraction levels that we created as we understood 
the problem better. At various points, we wrote contestants against each of
these interfaces. At the bottom is the PLAYER abstraction, which is used by the
code that talks to and from standard output, and knows nothing else. Next is 
the LAYER abstraction, which abstracts away maintnence of the game state. 
(There is an alternate CORO_LAYER on top of PLAYER that allows contestants to 
be coded as coroutines.) 


== Individual Players and Strategies == 

A player differentiated itself from the global infrastructure based on the
content of a file player-*.sml in the root of the repository. Some of these
were very simple, and relied entirely on capabilities built into the shared
infrastructure.

Our submitted strategy uses the tried and true Team Fortress 2 class
composition, which is known to maximize teamwork.  Three members of the Team
formed our submission:

  Scout. The purpose of the scout is to get us into the long game.  It
  is only place during the first 85 or so turns of a game. It builds
  an option to either heal our slot 255 or attack their slot 0, in
  either case sacrifice our 0 and 1 slots.  The idea behind attacking
  slot 0 is that it's often part of naive programs, setup phases, or
  super-short fixed strategies. If it's dead, these often fail.  When
  this option is ready, we decide to take the disruptive aggressive
  strategy or the disruptive conservative strategy.

  Sniper. The sniper creates a weapon that can kill an unhealed
  opponent in a single turn. It reads its target from a separate slot.
  The weapon is rather large (it takes about 700 slots to build), but
  once it's built, we can dispatch the entire field in an average of
  about 2 moves per opponent slot. It targets high-value opponent
  slots first (based on how often the opponent uses those slots, reads
  from them, how much damage they've done, etc.). The gun strategy is
  to use an auxiliary slot with at least 8192 vitality. We self-heal
  on that slot 21 times, which guarantees that we have enough to do
  two Attacks of magnitude 8192, with a net benefit to the vitality of
  the attacker. When it moves between slots, it uses the optimal path
  for updating its target number; for example, if the previous target
  was 63 and the new one is 128, then it just applies Succ to the
  target slot and then Dbl.

  Medic. The medic finds high-value targets on its own team and heals
  them. It builds a one-off program to do each round of healing (which
  minimizes the start-up time) which just uses Revive target; Help
  (src, target); Help (target, src) for a net benefit of about 11%. It
  does some fancy stuff to try to estimate the magnitude of healing,
  and to reuse old medics that happen to have been abandoned, and
  interrupt in-progress medic building to heal or revive critical
  slots.

  The other six Team Fortress 2 characters were never implemented. :)

As of 10 hours before the end of the contest, dozens and dozens of players
had been created, 39 had been registered with the CARDFAX arena (see below),
and 22 were currently being tracked in the arena as potential candidates for
submission.

Descriptions of other strategies that did not make it into the final strategy
follow.

The timecube is a combinator which generates an arbitrary number 0-255 in four
card plays. We considered that, once all the important programs for a strategy
were built, a lot of the game's remaining work would in generating numbers. The
idea that each of the general combinators I, S, K, and Put could represent 2
bits of an 8-bit number, and in four turns, all 8 bits could be specified,
motivated the following:

    a = S (K Succ)
    b = S (K (S (K Succ) Succ))
    four x = x Put I (x (K a) b I)

'four' maps x in [K, I, Put, S] to [(+0),(+1),(+2),(+3)], and:

    quad x = Dbl (Dbl x)
    timecube x y z w =
        four x (quad (four y (quad (four z (quad (four w Zero))))))

performs a series of "shift and add"s to generate all 8 bits. (for example,
"timecube S S K K" builds the number 15.)

Other "system services" for DOS were also developed, some of which helped some
of our auxiliary strategies. "Backup" allows a dominator to maintain a
copy of an important program in another slot, to reduce the risk of having to
build something from scratch if a slot gets killed. "RobustEmit" is a
version of EmitProgram which maintains incremental backups and automatically
restores from them when under attack. "NumberGenerator" provides numbers in
slots, sometimes more cheaply than building the number from scratch. It looks
for a slot that already have the desired number or something close to it, and
could also be extended to make use of a timecube.

Ideas were thrown around, but never implemented, for a 'watchdog' dominator which
would (using the "preview" phase of DOS) examine what the opponent is doing and
spawn and manipulate priorities for particular dominators tuned to counter
certain openings.

We also implemented an abstract evaluator that allows us to determine
possible effects of our opponent's code. For example, given a game
state in which the opponent has value 12288 in slot 2 and this piece
of code in another slot:

(S (K (S (K (S (K (S (K (S (K (S (K (S 
   (K I) (S (S (Attack 7) (S (K Get) (K 2)))))) 
   (S Zombie))))) S)))) S)) K),

the abstract evaluator can determine that two possible effects which
the opponent can achieve are (Zombie unknown unknown) and (Attack
12288 unknown 7). (Note that argument order is reversed here and
immediately above, due to a quirk of our implementaion. Sorry.) From
this information we might conclude that we should attack our
opponent's slot 7 to reduce its vitality below 12288.


== The Demonic Tutor ==

The Demonic Tutor (named after a Magic: The Gathering card --
http://sales.starcitygames.com/cardsearch.php?singlesearch=Demonic%20Tutor)
was our clone of the judges' interactive LTG clients. It allowed players
to be run against each other at the head of the repository. Based on our 
reading of the rules, it differed from the judges' version in allowing
each player 100000 turns.

./tutor leviathan killer

And it allowed matches to be played relative to particular revisions of the
repository. Below, we would make player-leviathan.sml in version 162 of the
repository, player-killer.sml in version 193 of the repository, and allow
them to complete.

./tutor leviathan:162 killer:193

If these two name:revision combinations are registered with CARDFAX (see
below), then the results of the match will be recorded by a simple RPC
interface (the ML code would 1) invoke wget to 2) visit a webpage that 3) was
a php file that stored things in CARDFAX's database.) In order to facilitate
this kind of play, the tutor essentially had Makefile-like capabaility: it
checked for the existence of player-leviathan-162.exe, and then built it
if it did not exist.

The demonic tutor also had a mode where it would query the database for some 
under-tested pair of players and automatically run a test ("autotutor").


== CARDFAX ==

CARDFAX is the 2011 arena; it mimics the unofficial duel server provided by
the organizers (though it uses the official 6/2/1/0 contest scoring and keeps
the scores of everyone against everyone else). It is the descendant of the
2010 CARFAX, the 2009 Orbiting Arena, and the 2004 Arena Eternal. CARDFAX
stored and reported the results of all matches, and had a view of all the 
matchups for each player.

CARDFAX can be seen for a limited time (probably until the end of July) at 
http://R_E_D_A_C_T_E_D/arena.