Mercurial > repos > icfp2014

comparison code/README @ 82:ea6a0709373f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Updated README
author Michael Pavone <pavone@retrodev.com>
date Mon, 28 Jul 2014 04:38:29 -0700
parents c0b3922646d8
children f420fabd0e44
comparison
equal deleted inserted replaced
81:4251797af36b 82:ea6a0709373f
13 -- see this page for instructions on how to build d8: 13 -- see this page for instructions on how to build d8:
14 https://developers.google.com/v8/build 14 https://developers.google.com/v8/build
15 3) Install the Boehm GC development package (libgc-dev on Debian derivatives) 15 3) Install the Boehm GC development package (libgc-dev on Debian derivatives)
16 3) Install gcc if it is not already present 16 3) Install gcc if it is not already present
17 17
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
18 Once you have the toolchain in place, navigate to the Quiche repo clone in a 23 Once you have the toolchain in place, navigate to the Quiche repo clone in a
19 terminal and execute the following command. 24 terminal and execute the following command.
20 25
21 ./compile PATH/TO/lmc.tp 26 ./compile PATH/TO/lmc.tp
22 27
23 If all goes well an executable named lmc will be produced at PATH/TO/lmc. This 28 If all goes well an executable named lmc will be produced at PATH/TO/lmc. This
24 program takes a .lm file as an argument and produces "GCC" assembly code on 29 program takes a .lm file as an argument and produces "GCC" assembly code on
25 stdout. 30 stdout.
31
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.
26 40
27 ABOUTE QUICHE: 41 ABOUTE QUICHE:
28 42
29 Quiche (previously called TP) is a language I (Michael Pavone) work on in my 43 Quiche (previously called TP) is a language I (Michael Pavone) work on in my
30 spare time. It draws rather heavily from Smalltalk with a smattering of 44 spare time. It draws rather heavily from Smalltalk with a smattering of
90 support the former and Quiche does not currently support the latter. 104 support the former and Quiche does not currently support the latter.
91 105
92 Tail call optimization is notcurrently implemented; however, while:do is 106 Tail call optimization is notcurrently implemented; however, while:do is
93 implemented using TSEL so we were able to do without. 107 implemented using TSEL so we were able to do without.
94 108
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
95 LIGHTNING ROUND SOLUTION: 120 LIGHTNING ROUND SOLUTION:
96 121
97 Our lightning round solution is relatively simple. Each step, we do a breadth 122 Our lightning round solution is relatively simple. Each step, we do a breadth
98 first search for something desirable (pellet, power pellet, fruit or fright 123 first search for something desirable (pellet, power pellet, fruit or fright
99 mode ghost). Cells occupied by normal mode ghosts and their immediate neighbors 124 mode ghost). Cells occupied by normal mode ghosts and their immediate neighbors
108 hopefully that will not be an issue. 133 hopefully that will not be an issue.
109 134
110 We noticed that the "undefined" input to main appears to be the ghost code, but 135 We noticed that the "undefined" input to main appears to be the ghost code, but
111 we did not have time to take advantage of it for the lightning round. 136 we did not have time to take advantage of it for the lightning round.
112 137
113 The code for this AI is located in dotScanner.lm 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
114 171
115 OTHER FILES: 172 OTHER FILES:
116 173
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.
117 test.lm - random collection of syntax for exercising parts of the compiler 184 test.lm - random collection of syntax for exercising parts of the compiler
118 simple.lm - picks each direction in order every 4 turns 185 simple.lm - picks each direction in order every 4 turns
119 mike00.lm - test program for developing library functions 186 mike00.lm - test program for developing library functions