Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Source code:
submission.tar.gz
Repository:
https://github.com/jeremysawicki/icfp2020
The Frictionless Bananas had only one team member this year. This page describes my 2020 ICFP Programming Contest entry.
The task this year was quite elaborate. First there were two weeks of teasers: daily messages from space defining alien notation for numbers and basic mathematical operations. During the contest, the notation was expanded to a full programming language. After implementing the language, you can use it to run a large alien program. The program presents a graphical user interface that contains tutorials for a game involving a battle between ships orbiting a planet. In the final stage of the contest, participants write programs to play that game against each other.
The contest was an amazing achievement on the part of the organizers. That said, I didn’t personally find the format to be as enjoyable as a more traditional format. I prefer to receive a clear and precise specification up front. One of the reasons I like the ICFP contest is that three days is enough time to come up with a quite sophisticated strategy and implementation. There is always a certain amount of “busy work”—implementing the mechanics of a game, simulation, virtual machine, etc.—before you can get to the real competitive part of the contest. It’s fine for that to take six hours, but when it takes a day or two it doesn’t leave enough time to develop an advanced solution. A precise spec is also more enjoyable to work with. Some years the spec has been more vague and incomplete, requiring experiments with a reference implementation to figure out some of the details. This year’s spec was intentionally vague and incomplete, and the organizers intentionally did not provide answers or clarifications. It made perfect sense given the theme of the contest, but reverse engineering a problem is not as much fun as solving it.
Still, it was an incredible contest. The organizers clearly put a huge amount of effort into it. The story was amazing, and the infrastructure worked flawlessly. Despite some misgivings about the long buildup to the main task, I had a lot of fun. I think this will be one of the most memorable contests for years to come.
This year’s teasers were more elaborate and contest-relevant than most. The organizers typically try to avoid revealing too much before the contest begins, but this year I wasn’t so sure. While most of the notation in the teasers was for simple numbers and math, the function application operator revealed that we were dealing with a programming language with curried functions. I was convinced that the organizers gave away their language with that detail.
I expected the language to be extended with single-argument lambdas. For example, \ x \ y ap ap add x ap ap mul y 2 would define the function f(x, y) = x + y * 2. To make the language useful, it would also need something like if and integer comparisons. After the introduction of add, mul, and div, I correctly guessed that comparison functions would be coming next. I incorrectly guessed that the final two days would introduce if and lambdas, but I still thought they would come during the contest.
When a contest introduces a programming language or virtual machine, it usually means one of two things: we will have to evaluate the language to run code provided by the organizers, or we will have to write a compiler targeting the language so the organizers can run code provided by us. I decided to prepare for both.
I started with a representation of a program as a sequence of tokens, with functions to convert between text and tokens. (I intended that tokens could also be converted to and from images if necessary, but I never implemented that.) I then introduced another representation as a tree of expressions, with functions to convert between tokens and expressions.
To implement a more friendly language that can be translated into the alien language, my approach was to convert text to expressions, perform a series of desugaring steps, and then convert back to text. I implemented let expressions, parentheses for function calls, boolean operations, and some extra mathematical and comparison functions:
| Syntactic sugar | Desugared equivalent |
|---|---|
let variable = value body |
ap \ variable body value |
let function x y z = definition body |
let function = \ x \ y \ z definition body |
(f x) (f x y) (f x y z) |
ap f x ap ap f x y ap ap ap f x y z |
(and x y) (or x y) (not x) |
if x y false if x true y if x false true |
(neg x) (sub x y) (gt x y) (le x y) (ge x y) (ne x y) |
(mul x -1) (add x (neg y)) (lt y x) (not (lt y x)) (not (lt x y)) (not (eq x y)) |
For example, here is a recursive function to compute Fibonacci numbers:
let fib_ fib_ n = if (lt n 2) n (add (fib_ fib_ (sub n 1))
(fib_ fib_ (sub n 2)))
let fib = (fib_ fib_)
(fib 35)
To evaluate the language, my approach was to convert text to expressions, perform a series of optimizations, and then convert to a sequence of instructions that execute on a stack machine. For example, a call to a curried function like ap ap add 1 2 is turned into a built-in version that requires all its arguments to be present, like add_ 1 2, which then becomes the sequence of instructions push 1; push 2; add. If a function doesn’t have all its arguments, it is turned into a lambda: add becomes \ x \ y add_ x y.
As it turns out, my guesses about the language were wrong. First, instead of lambdas there were combinators. That broke my syntactic sugar for let expressions, but it didn’t matter because the contest didn’t involve writing code in the language anyway. I probably could have adapted my stack-based evaluator to deal with combinators. A bigger problem was that instead of a built-in if construct, true and false were two-argument functions that returned one or the other of their arguments. That meant we were dealing with a lazy language, and a stack machine wasn’t going to work. Instead, I had to put all values into objects on the heap and add support for a not-yet-evaluated state. The first time a value is needed, it is evaluated and updated in place so that any other references to the same value will not need to evaluate it again.
I had a few subtle bugs related to the sharing of values. When evaluating a not-yet-evaluated value, I sometimes made the mistake of creating a new object on the heap rather than updating the existing one with the computed value. I also had an issue where I initially assumed that every name in galaxy.txt would correspond to a separate value object, but it turns out there are definitions like :1352 = :1343 where two names should ideally refer to the same object. I solved that one by introducing a call to the identity function, but I would have to think more deeply about the correct solution.
It took me a while to understand how the interaction protocol was supposed to work. I started out manually invoking the galaxy function with state and vector arguments, and displaying the resulting images as text. One it clicked that I was dealing with a GUI, it was clear what needed to be done.
I have a homegrown graphical display library—basically a thin wrapper around xlib and the Windows API—that I sometimes use for visualization during the contest. I quickly added support for mouse clicks and was able to see and interact with the galaxy. Unfortunately, I had to chase down some of the evaluator bugs mentioned above before I could successfully run the tutorials.
It took me long enough to implement the galaxy evaluator and get an understanding of the game that I didn’t have as much time as I would have liked to develop a good strategy. There were about 18 hours left in the contest when I submitted my first bot that did nothing. Still, I was able to implement a few good ideas by the end of the contest.
At the beginning of a game, four numbers must be specified to define the ship’s parameters. The documentation hinted that the last number cannot be zero and that the numbers cannot be too large. I worked out that there is a total amount of “money” that can be spent, and that the four resources have costs of 1, 4, 12, and 2. Without knowing what the resources were yet, I initially spent an equal amount on each.
Later, as I learned more about what the resources did, I called them fuel, guns, cooling, and ships. The fourth resource was only needed when you “clone” or deploy additional ships, which I was not yet doing, so I decreased that resource to 1. I tweaked the other resources further as my strategy developed.
The first important task is to avoid crashing into the planet. This is a case where I had good success reverse engineering the rules of the game. I was able to fully determine the effects of acceleration and gravity on a ship’s position from one time step to the next. Gravity accelerates the ship one unit horizontally or vertically depending on which side of the square planet it is closest to, unless it is exactly on a diagonal in which case the acceleration is diagonal. With that knowledge, I was able to search for a good trajectory and precompute the ship’s acceleration commands for the entire game on the first turn.
My goal was to find a sequence of accelerations that avoid crashing for the entire game while using the minimum amount of fuel. I start out by evaluating how many turns I would survive with no acceleration at all. Then I try a single acceleration command at every possible time step and in every possible direction to see how much longer it is possible to survive using just one unit of fuel. Starting with whichever acceleration command produces the longest survival, I continue to add additional acceleration commands one at a time until the ship lasts the entire game or the available fuel is exhausted.
That approach worked reasonably well some of the time. The ship would often enter a nice orbit around the planet, or an unusual back-and-forth pattern on only one side—clipping through a corner of the planet in the process. But other times the ship would travel to a corner of the playing field and hover there, burning fuel until there is none left and then crashing. To deal with that problem, I improved my search to try not just one acceleration command at a time, but bursts of 1, 2, 4, or 8 time steps in a row of the same acceleration. With that change, I was typically able to enter a stable orbit using only 3-5 units of fuel. I adjusted my resource allocation to spend only 1/16 of the available money on fuel, leaving the rest for shooting and survival.
My offensive strategy was shooting—I did not use detonation. I was only able to get a rudimentary understanding of the rules for shooting. I determined that the damage was greatest when firing horizontally, vertically, or diagonally, and it decreased significantly in other directions. It also seemed important to hit the target precisely. So, I carefully determined the expected next position of each ship based on its current position, velocity, gravity, and my own acceleration (the enemy’s acceleration was unknown). When an enemy ship was within some margin of one of the correct angles, and when my own ship’s temperature was low enough, I would fire. I didn’t have a separate defensive strategy. Whether playing as attacker or defender, I would attempt to shoot at and destroy enemy ships.
I spent some time trying to optimize the ship’s parameters. I didn’t use extra ships, and I needed very little fuel, so the main question was how to allocate between shooting and cooling. I tried to keep at least 8 units of cooling to counteract the effects of acceleration, as well as to recover from shooting and being shot at. After that, I favored putting more resources into guns. I would only increase the cooling further once the guns reached the sum of the maximum temperature and the cooling, since at that point it was not possible to use more guns without sustaining damage.
I noticed that in some games against other teams, the opposing team’s ships would have a maximum temperature of 128, whereas mine was always 64. Another unknown number was always 1 for me but would be 2 for other teams. Having a higher temperature limit seemed crucial for doing well in the contest. I checked the chat and found someone asking about it and receiving a cryptic reply. I studied the messages at the start of the game and found that the JOIN message would accept an unknown list of integers, which was also hinted at in the documentation, but I didn’t know what to put there.
Looking at the main galaxy screen, I realized that there were two mystery games that could relate to the two unknown bonuses. The games included the symbols for temperature and acceleration, telling me that I was on the right track, so I set to work on the memory-like game that corresponded to temperature. I found a couple matching pairs by hand, but it was tedious. Instead, I wrote a quick program to click all possible pairs. Once I completed the game, the interaction protocol state included a number that could be included in the JOIN message to unlock the higher temperature limit.
I did not bother trying to unlock the other bonus related to acceleration, since my strategy required very little acceleration.
From watching games against other teams, it became clear that an effective defensive strategy would involve using many clone ships. I made a rudimentary implementation that would create clones, but it needed more work. At a minimum, I needed a way to make the ships follow different trajectories. One idea was to have each ship choose a random point and search for a trajectory that passes as close to that point as possible. I didn’t have time to finish it, so I didn’t use it it my submission.
A big thank you to the organizers for all the hard work putting this contest together. I know you have received some negative feedback, but there was also a lot to love about the contest. The ICFP contest is a little different each year, and this year continues that trend. I am looking forward to exploring the task more without the time pressure of the contest.