There were 8 members in team tech.kontur.ru at ICFP Contest 2019, and here's what we've done.
In this 72-hour contest, we had to solve tasks by creating an AI for robots which wrap (i.e., paint) 2-dimensional maps. After 24-hours, we also could solve puzzles in a team-contributed "blockchain".
Shared domain code. lib/Models contains the code used by task solvers to represent tasks and AI state as well as some utility code. tests helped to chase bugs in this code.
Task solvers. lib/Solvers includes a number of task solvers which were good enough to make it to the end of the contest:
- Greedy, Stupid. Fast and non-optimal solvers which were able to compute solutions for all provided maps in reasonable time. These solvers enabled us to submit solutions for all problems early in the Lightning Round
- Palka. A promising solver which used map features (so called "boosters") to make the robot grow in particular direction (i.e., to grow a stick, a "palka" in Russian) and then wrap the map efficiently
- RandomWalk, DeepWalk, ParallelDeepWalk. Single- and multi-robot ("parallel") solvers which construct solutions by computing a number of suboptimal random moves and selecting the best ones. They use B/F/C-boosters and estimate moves in such way that a robot sequentially wraps partially unwrapped closely connected parts of a map. These solvers enabled us to take the lead in the Lightning Round
- Plan & Paraplan. Single- and multi-robot solvers which wrap the map according to an optimal plan suggested by a clusterization algorithm. See clusterization code in MishaResearch, results in clusters.v1 and clusters.v2
- Postprocessor. The ultimate solver which significantly improves the quality of other solvers' solutions via the rearrangement of AI moves. We've completed this solver during the last hours of the Full Round
Compare results of a second-best algorithm and the postprocessor:
| Task 42 | Task 139 |
|---|---|
 |
 |
Puzzle solver. lib/Puzzles contains the code which solves puzzles in the "blockchain".
Computing infrastructure. console-runner was used to run the following tasks on our laptops and workstations, on multi-core virtual machines, and on a GitLab CI server:
- compute a solution for a particular task (or tasks) using a particular solver (or solvers)
- compute solutions for all task-solver combinations (if not computed before)
- compute a solution for the most recent task in the "blockchain"
- verify solution correctness via the "online checker" provided by organizers
- pack and submit best solutions to organizers
- verify that submitted solutions are accepted by organizers, show quality improvements
Here's a screenshot of CI jobs during the contest:
pipeline code was used to store/retrieve solutions from MongoDB and use an "online checker" provided by organizers via Selenium WebDriver.
parallelepiped is a dirty CLI tool that runs many solvers in parallel on a multicore machine.
Visualisation. visualizer contains a modified version of the "online visualizer" provided by organizers. Its obfuscated ScalaJS code was reverse-engineered and altered to implement features required to efficiently debug our solutions: loading tasks and solutions by their ids (bypassing the file selection dialog), step-by-step execution, time travel, etc.
A web dashboard was used to monitor the progress of solution computation and compare the performance of different task solvers. (See the last snapshot of the dashboard.)
We've also generated bitmap images for all maps to efficiently explore them bypassing the "online visualizer".
There also was a Grafana dashboard to track the blockhain mining process.
| Task 59 | Task 101 | Task 134 | Task 190 |
|---|---|---|---|
 |
 |
 |
 |
Submissions. submission-grades contains the results of every submission we've made during the contest.
Dependencies:
- .NET Core 2.2
- NodeJS 10.0 — visualizer
- Python 3 — clusterization
Run dotnet run --project console-runner/console-runner.csproj -- -h to see all available commands.
Run dotnet run --project console-runner/console-runner.csproj -- solve [-p x..y] [-s solver-name-prefix] to run any solver registered in lib/Solvers/RunnableSolvers.cs on problems with ids from x to y.
An even better way to run the solvers is to use the StupidOne1 test in tests/Solvers/SolversTests.cs.
- Alexey Kungurtsev — algorithms, task solvers, puzzle solver
- Andrew Kostousov, Ivan Dashkevich — algorithms, task solvers, shared domain code
- Pavel Egorov — algorithms, task solvers, visualisation
- Michael Khrushchev — data science for task solvers
- Alexey Kirpichnikov — computing infrastructure, mining automation, submission quality assurance, visualisation
- Veronika Samokhina — visualisation, photography
- Igor Lukanin — computing infrastructure, visualisation, catering, gonzo journalism
This contest should be marked for paying tribute to a number of previous contests. We were glad to notice the legacy of many renowned contests in this contest.
Also, kudos to organizers for making all contest infrastructure work super-smoothly as well as for frequent and clear communications with participants. The best organizers of a few recent years!
We hope somebody likes the idea behind our "postprocessor" solver (see above).
It's also worth mentioning that we were making some field notes during the contest and broadcasting them to ~1k followers of our Telegram channel. It's in Russian but has some nice pics and animated images. Here's the start of the broadcast: https://t.me/KonturTech/416
More on our more-than-10-year history of participation in the ICFP Contest here: https://tech.kontur.ru/contests/icfpc