|
36
|
1 Team: Rhope Burn
|
|
|
2 Language: Quiche
|
|
|
3 Members: Michael Pavone, William Morgan
|
|
|
4
|
|
|
5 HOW TO BUILD:
|
|
|
6
|
|
|
7 To build our Lambda-man AI, you first need to build the lmc compiler. lmc is
|
|
|
8 written in a WIP language called Quiche. The steps to get a Quiche toolchain
|
|
|
9 setup are as follows:
|
|
|
10
|
|
|
11 1) Make a local clone of hg repo: http://rhope.retrodev.com/repos/tabletprog
|
|
|
12 2) Make sure the d8 Javascript shell (built from Chrome's v8) is in your path
|
|
|
13 -- see this page for instructions on how to build d8:
|
|
|
14 https://developers.google.com/v8/build
|
|
|
15 3) Install the Boehm GC development package (libgc-dev on Debian derivatives)
|
|
|
16 3) Install gcc if it is not already present
|
|
|
17
|
|
82
|
18 Please note that there have been some fixes to the standard Quiche libraries
|
|
|
19 during the contest. If you cloned the repo before the end of the contest (say
|
|
|
20 for our lightning round entry), please do a fress pull to make sure you have
|
|
|
21 an up to date copy.
|
|
|
22
|
|
36
|
23 Once you have the toolchain in place, navigate to the Quiche repo clone in a
|
|
|
24 terminal and execute the following command.
|
|
|
25
|
|
|
26 ./compile PATH/TO/lmc.tp
|
|
|
27
|
|
|
28 If all goes well an executable named lmc will be produced at PATH/TO/lmc. This
|
|
|
29 program takes a .lm file as an argument and produces "GCC" assembly code on
|
|
|
30 stdout.
|
|
|
31
|
|
82
|
32 To build our Ghost AIs, you need to build the gqc compiler. gqc is also written
|
|
|
33 in Quiche. The process for building gqc is similar to building lmc. Once again,
|
|
|
34 navigate to the Quiche repo clone in a terminal. Then execute the following:
|
|
|
35
|
|
|
36 ./compile PATH/TO/gqc.tp
|
|
|
37
|
|
|
38 This should produce an executable named gqc in the same directory as qgc.tp.
|
|
|
39 This program takes a .gq file and produces GHC assembly on stdout.
|
|
|
40
|
|
36
|
41 ABOUTE QUICHE:
|
|
|
42
|
|
|
43 Quiche (previously called TP) is a language I (Michael Pavone) work on in my
|
|
|
44 spare time. It draws rather heavily from Smalltalk with a smattering of
|
|
|
45 influence from other languages. In theory, it's reason for existence is to be
|
|
|
46 a good target for a structured editor on mobile devices. In practice, I'd
|
|
|
47 probably be better served targeting an existing language, but that's not nearly
|
|
|
48 as much fun.
|
|
|
49
|
|
|
50 The current implementation is a quick and dirty bootstrap compiler written in
|
|
|
51 Javascript that produces C code. A self-hosted compiler is in progress.
|
|
|
52
|
|
|
53 A Quiche program is made up of one or more modules. At runtime, a module is
|
|
|
54 just a plain object. Only one module is allowed per source file. The top level
|
|
|
55 of a Quiche source file is required to either be an object literal or a lambda
|
|
|
56 that returns an object. After all modules used are initialized, execution
|
|
|
57 starts in the main method of the main module. Currently, the names of all
|
|
|
58 available modules occupy the top level of the symbol table; however, this will
|
|
|
59 change in the self-hosted compiler.
|
|
|
60
|
|
|
61 QUICHE SYNTAX:
|
|
|
62
|
|
|
63 To make reading lmc's code a bit easier, here is a quick primer on Quiche's
|
|
|
64 syntax.
|
|
|
65
|
|
|
66 line comment: //
|
|
|
67 block comment: /* */
|
|
|
68 assignment: foo <- bar
|
|
|
69 list literal: [1 2 3 4]
|
|
|
70 array literal: #[1 2 3 4]
|
|
|
71 string literal "foo bar"
|
|
|
72 lambda: :arg {
|
|
|
73 arg + 1
|
|
|
74 }
|
|
|
75 object literal: #{
|
|
|
76 foo <- "blah blah"
|
|
|
77 bar <- :val {
|
|
|
78 foo <- val . " blah"
|
|
|
79 }
|
|
|
80 }
|
|
|
81 method invokation/function application:
|
|
|
82 someval someFunOrMeth
|
|
|
83 someFunOrMeth: someval
|
|
|
84 some: val1 Fun: val2 OrMeth: val3
|
|
|
85 some:Fun:OrMeth: val1 val2 val3
|
|
|
86 operators:
|
|
|
87 +,-,/,* -- basic arithmetic
|
|
|
88 =,!=,>=,<= -- comparison
|
|
|
89 and,or,xor -- bitwise
|
|
|
90 % -- modulus
|
|
|
91 . -- concatenation
|
|
|
92 | -- cons
|
|
|
93
|
|
|
94 ABOUT LMC:
|
|
|
95
|
|
|
96 lmc implements a subset of Quiche for the LamCo General Compute Coprocessor. It
|
|
|
97 uses the parser, ast and symbols modules from the work in progress self-hosted
|
|
|
98 compiler. Object literals are not supported apart from the top-level object
|
|
|
99 that represents the module. That object is used to populate the global
|
|
|
100 environment. Closures are properly supported; however, some elements that are
|
|
|
101 implemented using closures in the normal Quiche compiler (namely if:else and
|
|
|
102 while:do) are instead implemented as special forms that do not introduce a new
|
|
|
103 scope. Array literals are used for producing tuples as the GCC does not really
|
|
|
104 support the former and Quiche does not currently support the latter.
|
|
|
105
|
|
|
106 Tail call optimization is notcurrently implemented; however, while:do is
|
|
|
107 implemented using TSEL so we were able to do without.
|
|
|
108
|
|
82
|
109 ABOUT GQC:
|
|
|
110
|
|
|
111 gqc implements a sort-of subset of Quiche for the GHC. The subset that is
|
|
|
112 supported is quite restrictive. All values are 8-bit integers, recursion is not
|
|
|
113 supported and control structures only support a single comparison in the
|
|
|
114 condition argument. It also adds some non-standard features to allow it to be
|
|
|
115 used as a high level assemlber. All processor registers are mapped to symbols,
|
|
|
116 instructions are mapped as pseudo-functions and bare names can be used as
|
|
|
117 labels. Additionally, there are pseudo-functions for all the defined interupt
|
|
|
118 routines with "magic" variables to deal with multiple return values.
|
|
|
119
|
|
36
|
120 LIGHTNING ROUND SOLUTION:
|
|
|
121
|
|
|
122 Our lightning round solution is relatively simple. Each step, we do a breadth
|
|
|
123 first search for something desirable (pellet, power pellet, fruit or fright
|
|
|
124 mode ghost). Cells occupied by normal mode ghosts and their immediate neighbors
|
|
|
125 are marked as walls to provide simple avoidance behavior.
|
|
|
126
|
|
|
127 We translate the grid to a tree format to provide more efficient lookup. An
|
|
|
128 identically dimensioned tree is used for keeping track of visited nodes for our
|
|
|
129 search.
|
|
|
130
|
|
|
131 This seems to work surprisingly well given how simple it is. I'm a bit
|
|
|
132 concerned about our cycle usage when the nearest "good" thing is far away,
|
|
|
133 hopefully that will not be an issue.
|
|
|
134
|
|
|
135 We noticed that the "undefined" input to main appears to be the ghost code, but
|
|
|
136 we did not have time to take advantage of it for the lightning round.
|
|
|
137
|
|
82
|
138 MAIN ROUND LAMBDAMAN AI:
|
|
|
139
|
|
|
140 Our plan for the main round was to run a simulation of the full game rules and
|
|
|
141 the individual ghosts so we could use that information for planning our moves.
|
|
|
142 Substantial progress was made to that end. We wrote a complete interpreter for
|
|
|
143 the GHC CPU in LM-Quiche and got quite far along in writing a game rule
|
|
|
144 simulator. Unfortunately, as the end of the contest drew near it became clear
|
|
|
145 that even if we finished the simulator in time, we would not be able to
|
|
|
146 integrate it into our AI before the contest ended.
|
|
|
147
|
|
|
148 So we ended up making some last minute tweaks to our lightning round AI. In
|
|
|
149 fright mode, it now ignores power pellets and chases ghosts exclusively if it
|
|
|
150 thinks it can catch them. Similarly, it will pursue fruit above pellets and
|
|
|
151 power pellets if it thinks it can reach the fruit in time.
|
|
|
152
|
|
|
153 Our Lambda Man AI remains in dotScanner.lm
|
|
|
154 The unused GHC interpeter is in ghc.lm
|
|
|
155 The unused gameState simulator is in gameState.lm
|
|
|
156
|
|
|
157 GHOST AI:
|
|
|
158
|
|
|
159 We wrote two ghost AI programs in Ghost-Quiche. They are inspired by the
|
|
|
160 classic Pac Man ghost AI. The first tries to move towards Lambda Man unless
|
|
|
161 it is in fright mode. The second is similar except that it targets a position
|
|
|
162 two tiles in front of Lambda Man, much like "Pinky" in Pac Man. Neither ghost
|
|
|
163 implements a scatter mode and they try to actively flee Pac Man in fright mode
|
|
|
164 rather than picking a pseudo-random direction.
|
|
|
165
|
|
|
166 Together, they perform better than the ghosts on the score server for the
|
|
|
167 classic map when pitted against our lightning round AI, but worse compared to
|
|
|
168 our main round AI.
|
|
|
169
|
|
|
170 The code for these is located in ghost0.gq and ghost1.gq
|
|
36
|
171
|
|
|
172 OTHER FILES:
|
|
|
173
|
|
82
|
174 ll.lm - library functions for interacting with linked lists in LM-Quiche
|
|
|
175 tree.lm - library functions for interacting with a tree of CONS-cells that
|
|
|
176 provide reasonably efficient random access
|
|
|
177 grid.lm - library functions for interacting with a grid made up of the above
|
|
|
178 trees
|
|
|
179 gcc.tp - An interpeter for GCC assembly written in regular Quiche. The plan was
|
|
|
180 to create an entire game simulator based on this interpreter and our
|
|
|
181 LM Quiche GHC and game state code. It did provide faster feedback for
|
|
|
182 runtime errors in the gameState simulator, but in retrospect the time
|
|
|
183 would have been better spent elsewhere.
|
|
85
|
184 ghost2.gq - An attempt at writing a 3rd ghost AI. It seemed to worsen the
|
|
|
185 performance of our ghost team so it was abandoned.
|
|
36
|
186 test.lm - random collection of syntax for exercising parts of the compiler
|
|
|
187 simple.lm - picks each direction in order every 4 turns
|
|
|
188 mike00.lm - test program for developing library functions
|
