Настало время составить ежегодный отчёт о ежегодном же соревновании. Да, я знаю, что в прошлом году составить отчёт почему-то не получилось, так что отчёт получается не совсем ежегодным. Да, и в позапрошлом году тоже не получилось, хватит об этом >_<

Мы заранее собрались и договорились выступать стандартным составом: я, Minoru, Портнов, Akon32 и примкнувший к нам Hagane. В этом году, как ни странно, мы опять решили программировать на Scala (хотя в прошлый раз, когда мы этим занимались, понравилось не всем).

С самого начала соревнования я начал записывать заметки в отдельный файлик, так что отредактированную и дополненную версию этих заметок тут сейчас и приведу.

Описание задания

Организацией соревнования в этом году занимался Илья Сергей, но было оно, как ни странно, не про формальную верификацию чего-нибудь эдакого, а про вещи достаточно приземлённые: мы управляем роботом, который осуществляет навигацию по пещере, и должен закрасить все свободные клетки пола в этой пещере с помощью манипуляторов. Чем-то это было похоже на то, что мы видели в 2012 году (ух, как давно это было).

У робота есть несколько манипуляторов (и он может добавить себе ещё), а на игровых полях щедро разбросаны бонусы, которые он может собирать и применять, когда захочет.

В течение последующих дней публикуются дополнения к заданию и новые карты для решения. Кто на тестовых картах сделает наиболее быстрые решения — тот и молодец.

День 1

Соревнование в моём часовом поясе началось в вечер пятницы (2019-06-21). Как обычно, первый день мы потратили на чтение задачи и обсуждение возможных идей, как её решать.

С самого начала Hagane нам выдал идею, которой мы следовали в течение почти что всего соревнования: мы будем возможные варианты игрового поля обходить с помощью алгоритма A* (который мы за эти годы уже научились реализовывать так, что почти не стыдно).

За вечер первого дня мы сделали парсер задач и обрисовали базовые типы, которыми будем в дальнейшем описывать игровое поле, а также простенький симулятор.

Помимо этого, обнаружилась очень неприятная проблема на машине у Портнова: у него возникли какие-то мутные проблемы с сертификатами в JVM, и из-за этого он очень долго не мог скачать зависимости для проекта. Для справки: проблема починилась повторным импортом системных сертификатов в cacerts, который можно выполнить вот таким скриптом:

$ sudo /var/lib/dpkg/info/ca-certificates-java.postinst configure

День 2

Я решил, что, если получится ускорить наш код, то это принесёт очень большую выгоду в стратегическом плане, поэтому с воодушевлением взялся за профайлер, и не выпускал его из рук до самого конца соревнования. И оптимизации действительно получались не очень плохо, некоторые куски я ускорил существенно.

Помимо этого, придумал одно интересное решение: в качестве оценочной функции в A* я использую отношение закрашенных клеток к длине решения, получается эдакая «скорость закрашивания», измеряемая в квадратах в единицу времени. На одном из решений это дало хороший результат, но на других работало слишком уж долго.

Хотел было запустить наше решение ночью в многопоточном режиме на своей машине, но в JVM обнаружились какие-то баги под нагрузкой, и GC разваливался, поэтому план многомудрый не удался :(

Ночью мы неплохо так нагнули сервер организаторов, залив им туда 300 мегабайт каких-то рандомно сгенерированных решений от Minoru. Они написали нам по почте и попросили больше так не делать :)

День 3

Забавная история из жизни робота:

Minoru: гыгы, бот оставил незакрашенной клетку посреди большой закрашенной области, а когда приехал её закрашивать — не может, потому что новая ЦФ включает пенальти за расстояние до незакрашенной, и стоять рядом с незакрашенной выгоднее, чем закрасить и внезапно оказаться в десятке шагов от ближайшей незакрашенной

В этот день я занимался в основном багфиксами, а также написал более-менее удобный отладчик для нашего алгоритма. Жаль, что сделал я это лишь ближе к вечеру, так что, похоже, никто, кроме меня, так и не смог этим отладчиком воспользоваться. Охотился за нехорошим багом, который проявлялся на одной из карт; понял, в чём проявляется проблема, но так и не смог её исправить. Где-то в нашем коде до сих пор сидит ошибка на единицу :(

День 4

Это был уже рабочий день, поэтому я особенного участия в соревновании уже не принимал. Разве что смержил решения, которые получились у меня на сервере, с основным репозиторием — на некоторых задачах они были чуть лучше имеющихся у нас.

Заключение

Во время соревнования публиковали несколько обновлений спецификации, но мы за ними особо не следили – разве что ближе к концу соревнования научились натравливать нашего бота на новые карты, чтобы предложить хоть какие-то решения для них. Забавно, что одно из обновлений предполагало, что мы должны присоединиться к какому-то местному наколеночному блокчейну, майнить в нём свою валюту, а потом за неё покупать дополнительные бонусы, которыми можно пользоваться при прохождении уровней. К сожалению, у нас совершенно не хватило рабочих рук, чтобы всё это реализовать.

Упомяну одну интересную механику (которую мы реализовать также не успели): это клонирование роботов (и, да, она отсылает нас к задаче прошлого года). В качестве одного из бонусов можно было создавать клонов, и рулить уже несколькими роботами, что в теории могло бы позволить значительно сократить время прохождения уровней.

Официально мы заняли 86-е место, а спецификацию задания, примеры задач и код нашего решения можно посмотреть в репозитории.

Я могу сделать несколько выводов по результатам.

1. До начала соревнования (в понедельник той же недели, скажем) стоит проверить окружение у всех участников: попробовать собрать и запустить какую-нибудь простенькую программу (но с зависимостями!) на выбранном стеке.
2. У меня появился план на каникулы между соревнованиями: надо взять ту же команду, и попробовать решить russian-winter-icfpc 2012 года на разных языках. Вдруг нам понравится что-то ещё, кроме Scala и Haskell.
3. В этот раз, мне кажется, Scala зашла довольно неплохо. Во всяком случае, каких-то крупных проблем с окружением не возникло почти ни у кого, а те, что возникли, мы быстро решили. Мне лично на Scala программируется намного комфортнее, чем на Haskell.
4. Очень правильная мысль — сразу настраивать окружение так, чтобы можно было заливать решения в Git, а также автоматически выбирать лучшие, и поддерживать в какой-нибудь ветке базу самых хороших решений. Это помогает на ходу оценивать алгоритмы, а также позволяет в конце соревнования быстро собрать и отправить все наработанные решения.
5. Очень хорошая идея — составлять путевые заметки по мере хода соревнования. Это помогает составить хоть какой-то отчёт в конце. Без заметок я бы никогда не упомнил столько подробностей.