Team name: Frictionless Bananas
Team members: Jeremy Sawicki (jeremy at sawicki dot us)
Language: C++
Lightning submission:
lightning.zip
Full contest submission:
full.zip
Source code:
source.zip
The Frictionless Bananas had only one team member this year. This page describes my 2019 ICFP Programming Contest entry.
This year’s contest continued the story of lambda mining from the 2012 and 2017 contests. The task was to program robots to wrap empty lambda mines with insulation to prepare them for waste storage. Robots must navigate a 2D grid representing a mine and “wrap” every square in the grid. Robots are equipped with manipulator arms that can reach nearby squares, and whenever a square is within reach of a manipulator arm, the square is automatically wrapped. Thus the task is to find an efficient path to pass near every square in the map.
Mines also contained “boosters”—power-ups that give robots additional capabilities:
Teleport and Clone boosters were introduced as spec changes during the lightning round.
My strategy can be described as hill climbing or a genetic algorithm: repeatedly make random changes to a solution, keeping those changes that decrease the solution’s time and discarding those that increase it.
Rather than operating on a solution (a sequence of actions) directly, I use a more abstract representation of a solution called a “plan.” Random changes are made to the plan, and then the plan is executed to create a concrete solution. Plans are executed by a basic solver that implements a default greedy behavior and can produce somewhat reasonable solutions without any input from the plan. The plan tweaks the default behavior to produce better solutions. This is an approach that I used successfully in the 2012 contest, and I decided to try it again.
My basic solver performs breadth first searches from the robot’s location to find the fewest number of moves to reach a location where the robot can do something interesting, like wrapping squares, picking up a booster, or creating a clone. When multiple such locations can be reached in the same number of moves, the highest priority is given to special actions like creating a clone or picking up a booster, and after that, higher priority is given to locations where more squares can be wrapped. Boosters are activated as soon as possible, independent of the search.
Clones are supported by performing the search for all robots simultaneously, one time step at a time. At any time step in the search, each robot has a set of locations that it may reach at that time step. When a robot’s location set includes a desirable destination, its past moves are retroactively specified to be those needed to reach that location, and its location set is reduced to just that location so it can begin a new search.
To support fast wheels, a small change to the search process was needed due to the fact that not all destinations are reachable when traveling at double speed. When a robot’s fast wheels wear off, its location set is replaced with all locations reached since the last destination, effectively allowing it to wait at any of those locations until the fast wheels wear off if necessary.
My lightning round submission used only the basic solver. It supported manipulator boosters but not much else—no clones, no fast wheels, not even turning. My final submission still did not support drills or teleports.
My plan representation tweaks the behavior of the basic solver by altering the priorities for wrapping different squares. Each square is given an integer noise value from 0 to 255 and an integer bias value from -1 to +1. The noise value is used to break ties: when the solver has a choice between multiple locations where the same number of squares can be wrapped, the location with the largest sum of noise values is preferred. The bias values override the usual rule that favors locations where more square can be wrapped. If the sum of the bias values is larger in one location that another, the larger sum will be preferred even if fewer squares are wrapped in that location. By tweaking those values, it is possible to force a robot to enter a dead end when it passes nearby rather than needing to return later, for example.
My program starts out by initializing 16 plans with random noise values and all-zero bias values. It then tries to improve the plans in five stages: first working on 16 plans, then 8, then 4, then 2, then 1, each time discarding the worse half of the plans before proceeding to the next stage. The final version of my program allocates 5% of the available time to each of the first four stages, and the remaining 80% to the final stage.
My plan representation is reasonably effective at making local changes, but it is not as well suited to making global changes. For example, it may be desirable for a robot to immediately create clones or pick up boosters before doing anything else because those actions can improve the performance of the rest of the solution.
I tried to address global changes by enhancing the plan representation with the concept of “missions.” A mission consists of a pair of squares: a source and a destination. Whenever a robot wraps a source square, it receives the mission to travel directly to the destination square. In theory, missions should be able to guide robots to create clones early, for example. In practice, the number of possible missions is quadratic and it seems too hard to randomly choose a good one.
Instead, I added some hard-coded rules to force the first robot to collect and activate clone boosters first, and manipulator boosters second, before proceeding with the regular search strategy. I was able to reuse the code for completing missions—I just replaced the code for assigning missions with hard-coded logic.
After the lightning round, another part of the task was introduced: mining blocks on a blockchain to earn coins which can then be used to buy additional boosters in the main task problems. The coin mining process involves solving ordinary mine-wrapping problems as well as creating new mine-wrapping problems that meet certain requirements.
I generate mine-wrapping problems as follows:
I managed to mine 400142 coins, which I used to purchase 200 clone boosters for 200 problems. The problems were chosen to maximize the likely score improvement based on the ratio of solution times and the number of points available for the problem.
When the rankings were frozen three hours before the end of the contest, I was in sixth place. It is possible that I will pass some of the teams in second to fifth place, which are somewhat close together in score. It is not likely that I will pass the first place team, Unagi, which is considerably higher than everyone else.
This was a fun task and a well-run contest. I found the creation of problems for coin mining to be less interesting than other parts of the contest, mainly because it only mattered whether you satisfied the requirements or not—there was no meaningful notion of better or worse solutions. The use of coins to purchase boosters added an interesting twist to the main contest though.
Thank you to the organizers for all your hard work!