Quiche is a language I work on in my spare time. It borrows heavily from SmallTalk, but has some features to make functional approaches a bit more pleasant. A quick overview of the syntax is present in the README to make it a bit easier to read the code behind our entry.
LM-Quiche is mostly a subest of regular Quiche limited to the features that map well to the Lamco GCC (and presumably the real world SECD virtual machine). The biggest ommission from the full language is objects. I briefly considered trying to implement them using closures, but it didn't seem worth it given the lack of an efficient way to do method dispatch. Since there are no objects, if:else, while:do and a number of other operations are implemented as compiler built-ins rather than methods. Array literals were repurposed to provide a convenient syntax for creating tuples encoded as CONS cells. In retrospect, this was probably a mistake as it made LM-Quiche incompatiple with regular Quiche.
Ghost-Quiche is less of a proper subset of regular Quiche and more of a primitive language that uses Quiche syntax. 8-bit unsigned integers provide the only values. Functions are supported, but not closures or recursion. There are compiler builtins provided for all the interrupt routines defined in the spec as well as basic flow control in the form of if:else, if and while:do. Unlike in LM-Quiche (or normal Quiche), the condition argument to those flow constructs is limited to a single comparison. Additionally, there are predefined variables and functions for direct access to registers and instructions. Combined with the ability to define labels by putting a label by itself on a line (except for the last line of a function as that indicates what to return), it can effectively be used as an assembler. Combining the assembly mode with higher level code is possible, but some care is required as the compiler makes no effort to avoid clobbering registers used by low-level code.
The H register is reserved for use as a stack pointer. A function call is implemented with the following instruction sequence:
DEC H
MOVE [H], after_call
MOVE PC, function_address
after_call:
INC H
And function return is implemented like this:
MOVE PC, [H]
Since there is no register-relative addressing on the GHC, local variables are located at fixed addresses. For this reason, recursion is not supported though the compiler does not make any effort to stop you from trying. Arguments to function calls are passed in registers C-G. Unused registers in this set are also used as temporaries. Any of those registers considered in use by the compiler at function call time are automatically saved to the stack with DEC/MOV pairs by the caller.
Global variables are only initialized on the first run. This allows state to be carried over between turns.
After skimming the task spec it became clear that the first order of business was to write some sort of compiler for the Lamco GCC. Since one of my goals in ICFP each year is to use my current language project as much as possible I decided to write a compiler for a dialect of Quiche instead of a more natural choice like something in the Lisp family. I've been working on a self hosted compiler for the language so I already had a parser as part of Quiche's standard library we could use. For once, it seemed that using my goofy pet language might actually work in our favor rather than making things more difficult.
I started in on the compiler while Bill spent some more time fully digesting the spec. By 4PM PDT we had a working version of the LM-Quiche compiler. Bill went to work on the core of our pathfinding while I started on some library functions for working with linked lists and tries constructed from CONS cells. Once I had run out of library functions to write, we pair programmed the rest of our lightning round AI. By about 1AM PDT, we had a basic AI that found a path to the nearest pill or power pill ignoring ghosts. By about 3:15, ghosts were treated as a pill when in fright mode and ignored when in invisible mode. The 4 tiles adjacent to a ghost were marked as walls to give us some measure of ghost avoidance. After writing a README and submitting our tarball, we called it a night.
I'm quite happy with our lightning round performance. Our AI was far from perfect, but it seemed like a good effort for the first day of the contest. It also happens to be our first lightning round submission since 2009 and our first lightning round submission since we switched to Quiche (previously we used an older project of mine called Rhope).
I'd actually figured out that the undefined second parameter was the ghost code in some form during the lightning round. Once it was officially announced for the main round, I found it hard to resist trying to incorporate an interpeter for the GHC into our solution. Writing AIs to play games is not one of my strongest suits, but I have a fair bit of experience writing CPU emulators. We guessed (correctly based on the initial round of writeups), that not many teams would attempt to go this route and figured it could be a big competitive advantage if it worked. It was a high-risk strategy, but after the lightning round I felt we could pull it off.
By itself though, the GHC simulator would not be that helpful. We also needed a proper game state simulator both to better inform our planning and to feed the ghost AIs with appropriate information. I was also concerned about our resoure usage. The online simulator seemed to provide no feedback and according to the organizer I asked in IRC, it did not even check the cycle limit. Between that concern and a desire to have a better environment for debugging our game state simulator I decided we also needed a simulator for the GCC. Combined with the GHC simulator and game state simulator, it would give us a complete implementation of the game to test with. The main round also added the task of writing Ghost AIs so I figured we would need some kind of toolchain for targeting the GHC as well.
In summary, the tasks we set out for ourselves were the as follows:
Due to our late night on Friday, we did not get going on the contest again until after lunch. Bill got started on the game state simulator and I started working on an import mechanism for our LM-Quiche compiler so we could share code between programs. Around 3:30 PM PDT, I moved on to working on the GHC emulator. By 7:45 it seemed to be working correctly and so I moved on to the GCC emulator. I called it quits for the night around 1:50, but Bill kept going past 2:30.
I don't remember exactly when we started on Sunday. I had trouble sleeping in and I had gone to bed earlier so I started the day off solo and Bill joined me a bit later. By 1:30 PM PDT, our GCC emulator could run our GHC emulator so I decided it was time to turn my attention to a toolchain for writing ghost AIs. Since our first compiler went pretty well, I decided to pick a smaller subset of Quiche to compile to the GHC. The initial work went relatively quickly as I was able to reuse some code from the LM-Quiche compiler as a starting point. By 4:30, it could compile basic expressions.
Unfortunately, things started to go less well at this point. Fatigue and feature creap slowed my progress. I didn't have a useable version of the compiler until around 8 PM. It was becoming increasingly clear we had a problem as Bill still didn't have a working game simulator and there was still a fair amount of other work to be done. I was not ready to face reality and started work on our first ghost AI. A bit over 2 hours and some compiler bugfixes later we had our first ghost AI, a "chaser" inspired by "Blinky" in Pac Man. It would head directly towards Lambda man when in normal or invisible mode and would try to get as far away as possible when in fright mode. Unlike, Pac Man ghosts, there was no scatter mode.
Since we had one usable ghost at that point, the sensible thing to do would have been to help Bill finish the game state simulator. Instead, I started work on more ghost AIs. I added an "interceptor" based on "Pinky" and did some work on 2 more AIs that were supposed to surround Lambda Man on his left and right flanks. They never really worked out though. I stopped messing with ghosts at 1 AM with only 4 hours left in the contest. At this point, we finally faced the music. There was no way we had enough time to finish our original strategy and we needed to switch to plan B.
We started work on a revised version of our lightning round AI. The version we submitted for the main round has the following the earlier version:
For estimating whether we had enough time to catch a ghost or eat fruit, we used the Manhattan distance multiplied by roughly the number of ticks we though it would take to close the gap by 1 tile. The multipliers were rough guesses since we were short on time, but they seemed to work well enough.
As I said before, I'm quite happy with our lightning round performance. Unfortunately, that's tempered somewhat by how things went in the main round. I did a poor job of prioritizing tasks and didn't intervene in the game state simulator when I should have. Unlike me, Bill only writes Quiche once a year and while he had done some warmup this time it mainly focused on the OO parts of the language which were unavailable in LM-Quiche. This put him at a distinct disadvantage productivity wise and I did not properly account for that in my planning.
On the whole, we had fun. The organizers did a great job with the task this year. It's probably my favorite so far. As a bonus, all the compiler work during the contest has inspired me to get back to work on the self hosted Quiche compiler.
Writing the path finding was pretty fun. I wanted it to be breadth first so that we could stop at any point, check if we were approaching the turn resource limits, and still know that at least nearby things had been accounted for. With that in mind, I thought it would be pretty natural to return a list of continuation closures that, if called later, would keep searching one more level. When they reach a fork in the road, they could branch by returning a list with more closures. When they find what they are looking for, a visited spot, or a dead end, they could return an empty list of closures (or set a flag to say what they found and the accumulated path to it). The hope was to get us up and running quickly for the lightning round and still have a useful part for the final solution.
For the simulator, I took great care to structure the simulation events so that it would have allowed us to switch to a priority queue for scheduling later on, which seems like the natural and best way to do this. So even though I did not waste time writing an LM-Quiche priority queue before we needed it, it still took time to structure events this way. Perhaps just having a flat fixed set of variables to for each possible event would have saved time and allowed us to get something correct earlier, even if it meant not getting something fast later. Going that route would have been more obvious if the number of ghosts was statically known. But it turned out we need an efficient way to access the ghosts outside of when their event had triggered anyway, so maybe I could have stuck the next ghost event time in there and moved on.
We placed 2nd in the Lightning Round and 8th in the Main Round. The full resulst are available here. This is our best result by a wide margin and quite a bit better than I expected (especially in the main round).