# HG changeset patch # User William Morgan # Date 1406547690 25200 # Node ID 23d74104e51570950956902a8052bac5e35ad5b2 # Parent 3e5de539a676e650385e375ec86088e710aa72a1# Parent ea6a0709373f166de35203a2f38fe76229a06d6a merge diff -r 3e5de539a676 -r 23d74104e515 code/README --- a/code/README Mon Jul 28 04:39:30 2014 -0700 +++ b/code/README Mon Jul 28 04:41:30 2014 -0700 @@ -15,6 +15,11 @@ 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. @@ -24,6 +29,15 @@ 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 @@ -92,6 +106,17 @@ 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 @@ -110,10 +135,52 @@ 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. -The code for this AI is located in dotScanner.lm +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. 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 diff -r 3e5de539a676 -r 23d74104e515 code/dotScanner.lm --- a/code/dotScanner.lm Mon Jul 28 04:39:30 2014 -0700 +++ b/code/dotScanner.lm Mon Jul 28 04:41:30 2014 -0700 @@ -103,6 +103,9 @@ ret } } + + fruitX <- 0 + fruitY <- 0 step <- :myState world { lmState <- (world tail) value @@ -112,16 +115,6 @@ fruitState <- ((world tail) tail) tail grid <- makeTree: (map: (world value) :row { - if: fruitState >= 127 { - } else: { - row <- map: row :el { - //remove fruit if it is not enabled - if: el = 4 { - el <- 1 - } else: {} - el - } - } makeTree: row }) badGhostCount <- 0 @@ -177,7 +170,12 @@ //default behavior, target all yummy things target0 <- 2 target1 <- 3 - target2 <- 4 + if: fruitState > 0 { + //only target fruit when it is actually present + target2 <- 4 + } else: { + target2 <- 2 + } target3 <- 7 if: badGhostCount > 0 { } else: { @@ -192,6 +190,26 @@ } else: {} } else: {} } + fruitDist <- 0 + if: target2 = 4 { + if: (myLoc value) > fruitX { + fruitDist <- (myLoc value) - fruitX + } else: { + fruitDist <- fruitX - (myLoc value) + } + if: (myLoc tail) > fruitY { + fruitDist <- fruitDist + (myLoc tail) - fruitY + } else: { + fruitDist <- fruitDist + fruitY - (myLoc tail) + } + if: fruitState > (fruitDist * 127) { + //go straight for the fruit if we can make it in time + target0 <- 4 + target1 <- 4 + target2 <- 4 + target3 <- 4 + } else: {} + } else: {} //make sure my location is marked clear even if there is a ghost nearby grid <- grid: grid set: myLoc to: 1 visited <- treeMap: grid :row { @@ -206,6 +224,17 @@ } main <- :initWorld ghostCode { + grid <- (initWorld) value + fold: grid 0 with: :y row { + fold: row 0 with: :x el { + if: el = 4 { + fruitX <- x + fruitY <- y + } else: {} + x + 1 + } + y + 1 + } /* print: (step: 0 #[ //grid