Team: Rhope Burn
Language: Quiche
Members: Michael Pavone, William Morgan

HOW TO BUILD:

To build our Lambda-man AI, you first need to build the lmc compiler. lmc is
written in a WIP language called Quiche. The steps to get a Quiche toolchain
setup are as follows:

1) Make a local clone of hg repo: http://rhope.retrodev.com/repos/tabletprog
2) Make sure the d8 Javascript shell (built from Chrome's v8) is in your path
   -- see this page for instructions on how to build d8: 
		https://developers.google.com/v8/build
3) Install the Boehm GC development package (libgc-dev on Debian derivatives)
3) Install gcc if it is not already present

Please note that there have been some fixes to the standard Quiche libraries
during the contest. If you cloned the repo before the end of the contest (say
for our lightning round entry), please do a fress pull to make sure you have
an up to date copy.

Once you have the toolchain in place, navigate to the Quiche repo clone in a
terminal and execute the following command.

./compile PATH/TO/lmc.tp

If all goes well an executable named lmc will be produced at PATH/TO/lmc. This
program takes a .lm file as an argument and produces "GCC" assembly code on
stdout.

To build our Ghost AIs, you need to build the gqc compiler. gqc is also written
in Quiche. The process for building gqc is similar to building lmc. Once again,
navigate to the Quiche repo clone in a terminal. Then execute the following:

./compile PATH/TO/gqc.tp

This should produce an executable named gqc in the same directory as qgc.tp.
This program takes a .gq file and produces GHC assembly on stdout.

ABOUTE QUICHE:

Quiche (previously called TP) is a language I (Michael Pavone) work on in my
spare time. It draws rather heavily from Smalltalk with a smattering of
influence from other languages. In theory, it's reason for existence is to be
a good target for a structured editor on mobile devices. In practice, I'd
probably be better served targeting an existing language, but that's not nearly
as much fun.

The current implementation is a quick and dirty bootstrap compiler written in
Javascript that produces C code. A self-hosted compiler is in progress.

A Quiche program is made up of one or more modules. At runtime, a module is
just a plain object. Only one module is allowed per source file. The top level
of a Quiche source file is required to either be an object literal or a lambda
that returns an object. After all modules used are initialized, execution
starts in the main method of the main module. Currently, the names of all
available modules occupy the top level of the symbol table; however, this will
change in the self-hosted compiler.

QUICHE SYNTAX:

To make reading lmc's code a bit easier, here is a quick primer on Quiche's
syntax.

line comment: //
block comment: /* */
assignment: foo <- bar
list literal: [1 2 3 4]
array literal: #[1 2 3 4]
string literal "foo bar"
lambda: :arg {
	arg + 1
}
object literal: #{
	foo <- "blah blah"
	bar <- :val {
		foo <- val . " blah"
	}
}
method invokation/function application:
	someval someFunOrMeth
	someFunOrMeth: someval
	some: val1 Fun: val2 OrMeth: val3
	some:Fun:OrMeth: val1 val2 val3
operators:
	+,-,/,* -- basic arithmetic
	=,!=,>=,<= -- comparison 
	and,or,xor -- bitwise
	% -- modulus
	. -- concatenation
	| -- cons
	
ABOUT LMC:

lmc implements a subset of Quiche for the LamCo General Compute Coprocessor. It
uses the parser, ast and symbols modules from the work in progress self-hosted
compiler. Object literals are not supported apart from the top-level object
that represents the module. That object is used to populate the global
environment. Closures are properly supported; however, some elements that are
implemented using closures in the normal Quiche compiler (namely if:else and 
while:do) are instead implemented as special forms that do not introduce a new
scope. Array literals are used for producing tuples as the GCC does not really
support the former and Quiche does not currently support the latter.

Tail call optimization is notcurrently implemented; however, while:do is
implemented using TSEL so we were able to do without.

ABOUT GQC:

gqc implements a sort-of subset of Quiche for the GHC. The subset that is 
supported is quite restrictive. All values are 8-bit integers, recursion is not
supported and control structures only support a single comparison in the
condition argument. It also adds some non-standard features to allow it to be
used as a high level assemlber. All processor registers are mapped to symbols,
instructions are mapped as pseudo-functions and bare names can be used as
labels. Additionally, there are pseudo-functions for all the defined interupt
routines with "magic" variables to deal with multiple return values.

LIGHTNING ROUND SOLUTION:

Our lightning round solution is relatively simple. Each step, we do a breadth
first search for something desirable (pellet, power pellet, fruit or fright
mode ghost). Cells occupied by normal mode ghosts and their immediate neighbors
are marked as walls to provide simple avoidance behavior.

We translate the grid to a tree format to provide more efficient lookup. An
identically dimensioned tree is used for keeping track of visited nodes for our
search.

This seems to work surprisingly well given how simple it is. I'm a bit
concerned about our cycle usage when the nearest "good" thing is far away,
hopefully that will not be an issue.

We noticed that the "undefined" input to main appears to be the ghost code, but
we did not have time to take advantage of it for the lightning round.

MAIN ROUND LAMBDAMAN AI:

Our plan for the main round was to run a simulation of the full game rules and
the individual ghosts so we could use that information for planning our moves.
Substantial progress was made to that end. We wrote a complete interpreter for
the GHC CPU in LM-Quiche  and got quite far along in writing a game rule
simulator. Unfortunately, as the end of the contest drew near it became clear
that even if we finished the simulator in time, we would not be able to
integrate it into our AI before the contest ended.

So we ended up making some last minute tweaks to our lightning round AI. In
fright mode, it now ignores power pellets and chases ghosts exclusively if it
thinks it can catch them. Similarly, it will pursue fruit above pellets and
power pellets if it thinks it can reach the fruit in time.

Our Lambda Man AI remains in dotScanner.lm
The unused GHC interpeter is in ghc.lm
The unused gameState simulator is in gameState.lm

GHOST AI:

We wrote two ghost AI programs in Ghost-Quiche. They are inspired by the
classic Pac Man ghost AI. The first tries to move towards Lambda Man unless
it is in fright mode. The second is similar except that it targets a position
two tiles in front of Lambda Man, much like "Pinky" in Pac Man. Neither ghost
implements a scatter mode and they try to actively flee Pac Man in fright mode
rather than picking a pseudo-random direction.

Together, they perform better than the ghosts on the score server for the
classic map when pitted against our lightning round AI, but worse compared to 
our main round AI.

The code for these is located in ghost0.gq and ghost1.gq

OTHER FILES:

ll.lm - library functions for interacting with linked lists in LM-Quiche
tree.lm - library functions for interacting with a tree of CONS-cells that	
          provide reasonably efficient random access
grid.lm - library functions for interacting with a grid made up of the above
          trees
gcc.tp - An interpeter for GCC assembly written in regular Quiche. The plan was
         to create an entire game simulator based on this interpreter and our
         LM Quiche GHC and game state code. It did provide faster feedback for
         runtime errors in the gameState simulator, but in retrospect the time
         would have been better spent elsewhere.
ghost2.gq - An attempt at writing a 3rd ghost AI. It seemed to worsen the
            performance of our ghost team so it was abandoned.
test.lm - random collection of syntax for exercising parts of the compiler
simple.lm - picks each direction in order every 4 turns
mike00.lm - test program for developing library functions