================================================
==== Emarhavil Heavy Functional Programming ====
================================================

"ICFPC 2012: Gathering: the Lambdas."

------------------
---- ABOUT US ----
------------------

We're a team based in Mountain View, CA; we unite around the fact that we
wish to try implementing an ICFP challenge in Mozilla's new experimental
language, Rust [1] (version 0.3 of which was released just earlier this
week). Our explicit goals for this iteration of the competition are to
1) have fun, 2) put Rust on the map, and 3) give Rust a serious test by
writing something in it other than the Rust compiler.

We would like to thank the Mozilla Corporation for allowing us the use of
their office space over the weekend (keeping the lights and AC on for us,
and keeping us fed!).

HELP?  Contact:  joshua@joshuawise.com

[1] http://www.rust-lang.org/

----------------------
---- TEAM MEMBERS ----
----------------------

(in no particular order ... just looking around the room)

Joshua Wise (NVIDIA)
Ben Blum (Carnegie Mellon University; Mozilla Corporation)
Paul Stansifer (Northeastern University; Mozilla Corporation)
Josiah Boning (Dropbox)
Kevin Murphy (Carnegie Mellon University; NVIDIA)
Ben Harris (NVIDIA)
Roy Frostig (Stanford University)
Zizhuang Yang (Facebook)
Tony Fernandez (Carnegie Mellon University; Google)
Eric Holk (Indiana University; Mozilla Corporation)
Eric Faust (Carnegie Mellon University; Mozilla Corporation)

and our friendly IRC robots:

Takoyaki Ikayokat
Sourbot Tobruos

----------------------------------------
---- OUR LIGHTNING ROUND SUBMISSION ----
----------------------------------------

We submit some mostly untested pathfinding code that might or might not
work. Actually, we submitted nothing.

------------------------------
---- OUR FINAL SUBMISSION ----
------------------------------

In general, our solution is based on three components: a state space
searcher for trying different possibilities, a pathing engine for getting
from place to place, and a pattern-matching language for identifying how
to get through hard spots.

We have several different searchers and pathers, and we try all of them
on each map, using Rust tasks (the built-in unit of parallelism). An
"octopus" at the top level spawns and collects the results of each
algorithm and chooses the highest-scoring one.

We spent too much time on search and too little time on backend. We have
simulation rules for all of the rules extensions, so the pathing and
search can know what's legal and what isn't, but we have no heuristics
for them, nor any code that knows how to shave.

In the end, the algorithm we chose did not even know how to move boulders
around.

GAME TREE SEARCH
----------------

All of our game tree searches are granular at the level of "paths between
targets". A target is a lambda, an open lambda lift, a razor, a horock,
etc (except we have no strategy code for razors and horocks). In general,
at any search node (i.e., right after we picked something up), we
consider paths to next reachable targets and decide which ones to pursue.

    GREEDY. 

The greedy algorithm always uses the path to the closest lambda. All
other search algorithms are equivalent to it if their branch factor is
set to 1.

    ITERATIVE DEEPENING.

The iterative deepening algorithm iterates depth=1,2,3... until time runs
out, branching at the first 'depth' decision points. When it reaches
'depth', it falls back to greedy to complete the rest of the search.

    TOBRUOS.

Tobruos was named after an IRC bot's Markov-like talk function.  The basic
concept is that it incrementally chooses at each decision point by looking
ahead n steps in the game tree.  It ended up not being as good as Cargomax.

    CARGOMAX.

Cargomax was designed to fix iterative deepening's weakness of only
finding better alternatives at the start of the game (i.e., since it
always does greedy after the horizon, it is unable to fix late-game
greedy mistakes).

The basic idea behind Cargomax is to interleave greedy and branching.
While an iterative deepening tree looks like this:
                  ____________________
                 /\___________________
                /\_________________________
                \  _______________
                 \/ ___________________
                  \/________________
                   \______________

a Cargomax tree should look more like this:
                                         _________
                   _____________________/_____
         _________/___________________
        /         \__________________________
        \          ______________
         \________/           _______________
                  \__________/            ______
                             \___________/_______

Cargomax uses a workqueue model for doing sort-of-breadth-first-search.
Every branch point is a horizon branch point, at which greedy finishes
the game. During greedy, we heuristically evaluate the state at each
target, and cause the next branch point to appear at the maximally
evaluated point (i.e., detect "where it all went wrong" and avoid it).

After finishing searching at each branch point, we compute the average
path length of all greedy-finishes, then trim it by a heuristic constant
(cargomax_munge_avg_depth). Then on each branch we find the maximum point
between the start and that depth, i.e.:

                 _ 1 2 3 4 5* 4 3 2|. . . . .|.         A
                /                  |         |
...(prefix)... /__ 9* 8 7 6 1 0 0 0|. . .    |          B
               \                   |         |
                \_ 1 1 3 5 8 13 21 |* . . . .|. . . . . C
                                trimmed     avg

Here we add three items to the workqueue: {prefix + A's-moves-up-to-5},
{prefix + B's first move only}, {prefix + C's-moves-up-to-trimmed}.

"Cargomax" is a five-way pun.
 - "Cargo" alludes to carrying lambdas around.
 - "Cargo" is Rust's build system (and "crates" are compilation units).
 - "Max", a generic search algorithm name.
 - "Cargofax" is the name of our test arena.
 - "Vargomax" - see https://www.cs.cmu.edu/~tom7/sigbovik/mario3.swf
   (created by a friends over on the Cult of the Bound Variable team)

PATHING
-------

We use a modified A* algorithm to compute paths, regarding spots where we will
definitely die or abort as unpassable.

PATTERNS
--------

We compute how to get around boulders by applying pattern-matches to
areas near the robot while pathing. A pattern is a very small grid of
squares which a known sequence of moves can get past. The pattern
matching language includes items like "eatable", "passable",
"fall-right", "fall-left", "solid", "empty", etc. Patterns also have a
notion of symmetry.

More complicated patterns have lower cost heuristics, because applying
them is more likely to result in success. We can fall back to simpler
patterns, such as "If you're next to a boulder, try pushing it!" or "If
a boulder is above you, try walking under it", which have higher cost.

THIS README
-----------

Will probably be incomplete, since we probably will have run out of time.

CARGOFAX (ARENA)
----------------

We constructed an arena to automatically test a handful of candidates at
once against each other.  It was named CARGOFAX, because a team I previously
played with had arenas named CARFAX (two years ago) and CARDFAX (last year). 
Most of the files for the arena are in etc/, but they are difficult to set
up without already having our infrastructure.  Sample output from the arena
lives in sample.html.  (We are not very good.)