20-23 июля 2018 года проходил очередной ICFPContest, где наша команда WinterMUTE снова принимала участие.
Окончательные результаты соревнований ещё не опубликованы, но мы отчётливо понимаем, что не заняли никаких топовых мест. Тем не менее, это было интересно, и я просто хочу описать по свежим следам, как это было, чтобы сподвигнуть кого-нибудь ещё поучаствовать в таком крутейшем ежегодном мероприятии.
Итак, на входе алгоритма дискретная 3D модель (матрица) размером до 250х250х250 вокселей (см. анимацию), представленная в виде вектора битов. Необходимо предоставить трассу из набора команд для управления наноботами, которые построят указанную модель.
Наноботы могут:
Симуляция системы осуществляется в дискретном времени. Всё начинается и заканчивается единственным наноботом, который стоит в начале координат. На каждом такте симуляции каждый нанобот выполняет ровно одну команду.
В lightning round (заканчивается через одни сутки с момента старта соревнований) Nanobot Matter Manipulation System поддерживала до 20 наноботов и требовалось строить модели, начиная с пустого пространства.
В full round Deluxe Nanobot Matter Manipulation System позволяла использовать до 40 наноботов и поддерживала операции групповой заливки/уничтожения вокселей. При этом появились два новых типа заданий:
В системе задана нетривиальная целевая функция расчёта потраченной энергии, которая зависит от выполняемых наноботами команд (создание/расщепление материи, перемещение и др.) и количества наноботов, а также количества шагов симуляции в двух режимах "резонансного поля":
High режим гораздо дороже с точки зрения энергии и между режимами можно переключаться (если выполняется условие groundedness).
Разумеется, на каждом такте работы системы проверяется отсутствие коллизий при перемещении наноботов (между собой и со стенами).
Участникам для каждой проблемы предоставляется пример решения, где один нанобот "змейкой" строит модель, находясь всё время в режиме High.
Модели и трассы (команды) упакованы в компактные битовые представления. Организаторы выдали client-side визуализацию моделей и симулятор трасс на WebGL.
Для каждой проблемы (сборка/разборка/пересборка модели) предложить наилучшее решение (трассу из набора команд для наноботов) с точки зрения потраченной энергии.
Мы собрались более-менее устоявшейся командой в офисе Одноклассников:
Ещё перед началом соревнований мы спонтанно приняли решение писать на связке Java и Python. В итоговом репе только Java и JavaScript.
Contest начался 20 июля в 19:00 по Мск, поэтому мы посвятили несколько часов разбору задания, генерации идей по его решению и рассмотрению извращённых примеров 2D моделей на доске, а затем разошлись по домам думать.
Собрались пораньше и начали писать код. Олег заинтересовался JS кодом симулятора/визуализатора от организаторов и занялся его изучением и деобфускацией (чем и продолжил заниматься оставшиеся дни). Остальные члены команды разбились по парам и отправились кодить обязательные части: наше внутреннее представление состояния системы наноботов в матрице, координаты, десериализаторы входных моделей и сериализаторы выходных трасс. При этом всё обильно покрывали тестами.
Решили пойти по пути создания детерминированных стратегий решения задач и реализовать следующую архитектуру (сверху вниз):
К концу дня Саша, Дима и Вадим дописали основную обвязку и реализовали SwitchVM. Тем временем Олег сократил код JS с 30К до 14К строк. Антон с Алексеем занимался кодом "парковки" в начале координат после построения модели, а затем начал пилить простейшую стратегию, которая собирает модель одним наноботом, но более эффективно, чем дефолтные трассы от организаторов.
Тем временем, lightning round закончился, мы ничего не отправили. Организаторы опубликовали условия Full Round, где были добавлены групповые команды заливки и уничтожения вокселей (к слову, Олег обнаружил их в коде JS загодя), увеличено максимальное количество наноботов, а также опубликованы новые проблемы сборки, разборки и пересборки моделей.
Собрались пораньше, посокрушались, что не успели ничего доделать до окончания lightning round, и продолжили кодить. Нас осталось четверо.
Первым делом Дима поддержал групповые GFill/GVoid и переключился на создание стратегии послойной разборки моделей сверху-вниз. Вадим занялся автоматизацией прогона и отправки решений, а затем начал разрабатывать утильные примитивы горизонтальных плоскостей и проверки groundness с помощью BFS. Олег продолжил разбирать JS организаторов на части, чтобы переиспользовать в качестве валидатора и оценщика энергии. Антон существенно развил стратегию сборки моделей MothershipStrategy, использующую рой наноботов, и доотлаживал её. MothershipStrategy распределяла строки каждой горизонтальной плоскости между ботами, которые строили свою часть снизу вверх.
Мы начали сабмитить наши решения для набора задач по сборке моделей, используя MothershipStrategy, хотя и не поднимались выше 37 места в таблице. Нужно было научиться решать оставшиеся задачи (благодаря будущей DisassemblyStrategy), а также улучшать существующие стратегии.
Тем не менее, к концу дня драйв нарастал, поскольку всё это уже работало.
Олег запустил перепиленый JS-симулятор организаторов под Nashorn, научился подавать ему входные данные извне, а также перехватывать callbackи ошибок и успеха, и начал интегрировать его в наш CI. Дима продолжил возводить DisassemblyStrategy, а Антон -- улучшать MothershipStrategy. Вадим вылавливал баги, добавил поддержку решения оставшихся проблем, запилил простейшую статистику и занялся изучением моделей из новых проблем.
Ближе к дедлайну заработала DisassemblyStrategy, которая работала как утюг на основе GVoid, что дало возможность решать задачи разборки и пересборки моделей. Впрочем некоторые задачи решить не удалось из-за оставшихся багов, но мы засабмитили то, что успели решить.
Надеюсь, в этом посте я более-менее объективно описал вклад каждого участника и ничего не забыл. Дальше изложен ряд моих собственных мыслей на тему прошедшего контеста.
IMHO, Java не подходит для решения подобных задач в сжатые сроки -- слишком много boilerplate кода и невыразительная система типов. Не хватало функций высших порядков, data/case classes, pattern matching и т.д. (чего стоят постоянные преобразования (short) 1 и отладка перепутанных координат). Впрочем, код на Java предельно "тупой", что позволяло быстро разбираться в чужом коде. При этом написание нетривиальных стратегий вызывало боль и страдание.
В следующий раз мы предварительно договорились попробовать язык Rust.
С одной стороны, фиксированный набор готовых вариантов проблем от организаторов упрощал разработку и CI. Client-side визуализаторы и симуляторы устраняли необходимость дёргать какой-либо API. С другой стороны, это теоретически позволяло отправить для каждой проблемы какое-то кастомное решение. Возможно, было бы "честнее", если бы окончательная оценка решений осуществлялась запуском бинарников участников на отдельном оценивающем наборе задач (как когда-то в ICFPC про Pacman).
В этом раз (как и в предыдущие) мы применили классический инженерный подход к решению задачи. Было бы интересно взглянуть на проблему с принципиально иной точки зрения, например, попытаться свести задачу к известной, попробовать SAT-солверы, генетические/рандомизированные подходы или что-нибудь ещё.
На мой взгляд, было хорошей идеей программировать парно. Кроме того, неплохое покрытие тестами позволяло бесстрашно наносить улучшения чужому коду. Тем не менее, на второй день все почувствовали, что при большем количестве участников мы смогли бы сделать больше. Мы не успели полностью реализовать проверку возможных коллизий и расчёт энергии для текущей трассы, использовать GFill в MothershipStrategy. Впрочем, стратегии по построению избегали коллизий.
В целом, это было чертовски круто! Трудно объяснить, почему круто. Это можно только почувствовать на собственном примере. Лично у меня после каждого ICFPC возникает ощущение, что нет ничего невозможного и за 3 дня можно подобраться к какому-никакому решению любой задачи.
Огромное спасибо организаторам за проделанную работу! Мне трудно представить, сколько усилий было потрачено на разработку, отладку и тестирование всей этой машинерии.
В корне проекта лежит README для организаторов.
Если есть, что сказать, добро пожаловать в комменты!
comments powered by Disqus