Mercurial > repos > icfp2014
view code/README @ 85:f420fabd0e44 default tip
One last README change
author | Michael Pavone <pavone@retrodev.com> |
---|---|
date | Mon, 28 Jul 2014 04:42:24 -0700 |
parents | ea6a0709373f |
children |
line wrap: on
line source
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