21-24 июня 2019 года проходил очередной ICFPContest, в котором наша команда WinterMUTE снова принимала участие.
См. наш отчёт об ICFPContest 2018.
На входе 2D карта лабиринта, по которой перемещается робот с манипуляторами. Цель состоит в посещении всех клеток карты телом робота или манипуляторами за наименьшее время. По карте разбросаны различные booster'ы, позволяющие временно ускоряться, временно обретать способность дрелить препятствия и стены карты или наращивать свои манипуляторы, тем самым увеличивая покрываемую область при движении. Из интересных моментов вспоминается, что при учёте покрытия манипулятором ячейки карты необходимо было учитывать видимость этой ячейки из позиции робота с учётом препятствий, но об этом позже.
В последующих ревизиях спецификации появились бустеры телепортации, а также поддержка клонирования и управления роем роботов и дополнительные наборы карт с новыми бустерами. Итоговый набор всех карт включал 300 карт размером до 400х400 ячеек, как рандомных, так и напоминающих различные страны. Одна из карт была забавным планом USS Enterprise.
Помимо спецификации, наборов карт и примеров решений, организаторы предоставили Web визуализатор и checker карт и решений. Решения от команды отправлялись через API одним архивом с наборами команд для роботов на каждой карте.
Во второй день соревнований организаторами был запущен майнинг lambda coin'ов, которые позволяли покупать бустеры для улучшения времени решения основного набора задач, либо просто увеличивали итоговое число очков команды. Чтобы заработать коины в очередном раунде майнинга необходимо было предоставить решение для текущей задачи раунда и сгенерировать карту, удовлетворяющую заданным в раунде критериям. Впрочем, до этого мы так и не добрались.
В целом, спецификации были лаконичными, понятными и местами забавными.
Мы собрались более-менее устоявшейся командой в офисе JetBrains:
Ещё перед началом соревнований мы приняли решение писать на Kotlin. В итоговом репе только Kotlin и JavaScript. Кроме того, мы решили, что в этот раз участвуем ради фана и не пытаемся изо всех сил попасть в ТОП, поэтому будем экспериментировать с альтернативными подходами к решению задачи.
Почему не Rust, как обещали в прошлый раз -- спросите вы? Никто не подготовился и не попытался освоить этот непростой язык, а после изучения спеки стало понятно, что без подготовки ничего дельного мы не напишем. Была ещё одна безумная идея реализовать свой язык поверх Truffle Framework, но после изучения Truffle Tutorial стало понятно, что подготовки понадобится ещё больше, чем к использованию Rust. Впрочем, в контексте задачи текущего контеста ни Rust, ни Truffle нам бы ничего не дали.
Contest начался 21 июня в 13:00 по Мск. Все засели за спеку, затем мы совместно проговорили её содержание, чтобы выработать общее понимание, и устроили мозговой штурм, чтобы построить граф задач и наметить даже самые упоротые варианты решения. В отличие от предыдущих соревнований мы пытались воздерживаться от нашего классического подхода к решению похожих задач на основе BFS/A* с эвристиками.
В итоге:
К концу дня была готова первая версия развесистой, но чёткой модели предметной области с геометрией, пространством и перемещениями робота, а также сериализацией (и с true-типами для координат X и Y), завели JsVM на основе Nashorn (который Андрей сконвертил с Java в Kotlin) и запустили пример тестового генетического решателя на основе Jenetics. Для ускорения интерпретации JavaScript перешли с Java 11 и Nashorn на GraalVM.
Не обижайтесь на матерные имена функций и комментарии на немецком в JsVM -- полёт мысли при деобфускации было трудно остановить. Кроме того, коммиты Олега в JavaScript часть плохо открываются на Bitbucket в силу своего размера.
Андрей с Олегом заинтегрировали JsVM в качестве scoring-функции в генетический решатель карт, подбирающий минимальную последовательность команд для покрытия всей карты, и занялись улучшением scoring'а, чтобы соптимизировать перебор и сделать его более направленным, а также обеспечить управляемый останов при недостижении решения за ограниченное число итераций. Генетический решатель смог решить первую тривиальную карту (решение было отправлено в lightning round), но все остальные (топологически гораздо более сложные) карты представляли вычислительную проблему. Кроме того, профилирование async-profiler'ом показало, что JsVM исполняется в интерпретаторе и непрерывно перекомпилируется и непонятно было, что с этим делать. Кеширование JavaScript Contextов, чтобы переиспользовать разные инстансы JsVM при генетическом скоринге, не дало эффекта.
Лёша с Димой продолжили работу над развитием модели и интерпретатором решений, попутно реализовав дампилку карт в псевдографике и поддержав телепортацию и клонирование, а также сериализацию форматов и реализацию видимости манипуляторов (с рациональными числами), и начали имплементировать алгоритм обхода карты на основе DFS. К слову, только в этом компоненте были замечены тесты.
Олег продолжил деобфусцировать и оптимизировать Scala.js код checker'а, а также начал работу над альтернативным ручным визуальным и автоматическим жадным решателем карт.
Андрей уехал на конференцию, Вадим занялся инфраструктурой запуска решателей на всех картах и выбором лучших решений для отправки, а после этого попытался формализовать задачу и свести её к SMT, чтобы применить Z3.
DFS-решатель от Лёши и Димы начал успешно обходить карты и, наконец, мы начали отправлять решения. Ручной решатель от Олега завёлся и позволил отлаживать решения, а также строить оптимальные ручные решения для небольших карт.
После просмотра визуализации DFS-решений (сопровождающегося комментариями "ты чё, пёс, куда пошёл?!") стало понятно, что алгоритм на основе простой BFS-эвристики может работать лучше -- на каждом шаге будем идти к ближайшей непосещённой ячейке. Дима и Вадим на коленке запедалили BFS-алгоритм и смогли улучшить результат DFS.
Лёша с Димой внедрили эвристику по приоритетному собиранию booster'ов для расширения манипуляторов, поскольку они позволяют увеличить покрытие ячеек при путешествии робота по карте, что дало профит на большинстве карт.
Попутно всплыли проблемы с некорректной оценкой видимости ячеек под манипуляторами, которые Дима с Олегом героически пофиксили, что позволило отправить решения ко всем задачам.
Олег продолжил улучшать ручной и жадный решатели, но мы успели добиться улучшения лишь по некоторым картам.
У Вадима с Z3 ничего полезного не вышло, поскольку солвер зацикливался из-за использования квантификаторов, и лишь после завершения контеста возникла идея, как можно было сузить область поиска.
В итоговой таблице мы на 73 месте из 142 команд с ненулевыми очками.
Надеюсь, в этом посте я более-менее объективно описал вклад каждого участника и ничего не забыл. Дальше изложен ряд моих собственных мыслей на тему прошедшего контеста.
На этот раз Kotlin показал себя норм, IDEA не крешилась через раз, хотя код пестрел операциями !!.
Наконец-то, мы попробовали альтернативные подходы к решению задачи. К сожалению, это ничем не помогло, но добавило драйва.
Мы рассчитывали на 6 человек, но в итоге full-time участовали только четверо. Наверное, можно было достигнуть большего за счёт распараллеливания.
На мой взгляд, парное программирование снова хорошо показало себя.
Как и всегда, было офигенно. Снова возникло это почти забывшееся за год ощущение, сколько можно сделать всего за 3 дня.
Спасибо Илье Сергею за организацию ICFPContest! Кстати, все исходники инфраструктуры контеста выложены в общий доступ.
Если есть, что сказать, добро пожаловать в комменты!
comments powered by Disqus