changeset 84:23d74104e515

merge
author William Morgan <billjunk@mrgn.org>
date Mon, 28 Jul 2014 04:41:30 -0700
parents 3e5de539a676 (current diff) ea6a0709373f (diff)
children f420fabd0e44
files
diffstat 2 files changed, 108 insertions(+), 12 deletions(-) [+]
line wrap: on
line diff
--- 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
--- 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