Отчёт об ICFP Contest 2015

Настало время отчитаться по результатам ICFP Contest 2015.

В этом году мы выступали традиционным составом: я, rexim, portnov, а также примкнувший к нам Minoru. "Вторым составом" у нас была также команда из grouzen и ulidtko.

Так вышло, что за несколько дней до контеста мы случайно собрались вчетвером в programming@ и выбрали Scala в качестве основного языка, который мы будем использовать на соревновании. До этого использовали в основном Haskell, но на этот раз решили попробовать что-нибудь новенькое (поскольку, честно признаться, лично я весьма недоволен своими успехами в Haskell, и мне кажется, что у меня пока на нём получается программировать недостаточно хорошо и быстро).

В этом году авторы контеста решили немного пошутить, и заранее выложили описание сюжета с участием потусторонних сил, спецслужб и учёных. Я сразу отметил, что описание получается в духе серии The Atrocity Archives Чарльза Стросса, и, как выяснилось позднее, авторы именно им и вдохновлялись (а я даже взялся в итоге читать его в оригинале).

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

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

Для прохождения квалификационного раунда нужно было решить все задачи из тестовой подборки, и сделать это лучше большинства остальных участников (был ещё lighting division, но наша команда слоупоков на него традиционно забила).

Стоит упомянуть архитектуру уровней: они были интересными. На некоторых полях были написаны волшебные слова (так что первоначальный текстовый визуализатор, а затем — графический визуализатор rexim'а нам очень помогли найти первые слова); на одном уровне была пентаграмма, на некоторых были просто смешные фигуры в форме ктулхов или букв "ICFPC-2015", ну а на последнем уровне был пейзаж какого-то города.

Для меня эти три дня (пятница-суббота-воскресенье) пролетели достаточно стремительно. Вот кратенько список достижений (или этапов работы):

1. Я сделал шаблон проекта на Scala, а также заранее организовал проект на github и приватный чатик на jabber.ru, в который было очень сложно пригласить сотоварищей по команде (поскольку я в присущем мне стиле не желал сообщать им адрес чата явным образом, и всячески намекал проверить почту и прочитать readme в репозитории на github; в следующем году надо будет придумать загадки).
2. portnov написал годный эмулятор происходящего в игре. В дальнейшем эмулятор использовали для поиска оптимальных стратегий действия.
3. rexim написал замечательный визуализатор, который очень помог нам в отладке и ручном решении некоторых задач. К сожалению, на исходе второго дня соревнования домашние дела взяли верх и больше он участвовать не смог.
4. Minoru провозился довольно долго с решением задачи по повороту фигур на гексагональном поле (не спорю, задача довольно нетривиальная).
5. Совершенно неожиданно (кажется, на второй день соревнования) к нам присоединились grouzen и ulidtko. Как оказалось несколько позднее — они писали совершенно отдельную программу на Haskell (но всё равно остались нашими товарищами, делились соображениями, и вообще мы друг другу неплохо помогли).
6. ulidtko в течение всей субботы занимался той же задачей вычисления поворотов. Фраза "улитка делает повороты" стала на эти несколько дней нашим локальным мемом. И когда улитка их таки доделала вперёд Minoru — это был успех; правда почему-то решение получилось... на JS. Это нас не остановило: я быстренько портировал решение на Scala, дополнив также работой с разворотами по часовой стрелке (т.к. в оригинале был только поворот против часовой).
7. Что делал grouzen в программе на Haskell — я не знаю, т.к. особо не всматривался. Похоже, что ребята, к сожалению, не успели дописать программу в срок. Ну что ж, попытка всё равно была неплохой!

Пару слов об архитектуре решения. Изначально мы сошлись во мнении, что нужно два отдельных солвера — один для глобальной стратегии (где и как размещать фигуры), а второй — для локальных движений (т.е. для продвижения фигуры к целевой точке поля).

Я в течение дня наваял нечто невнятное на алгоритме A* и назвал это просто Solver. Предполагалось, что это будет глобальный солвер, который бы должен искать самые "широкие" ряды (которые нам проще всего будет разрушить) и старался бы вставлять в них дополнительные фигуры. Однако в итоге оказалось, что эта идея — не самая лучшая: алгоритм A* всё-таки больше рассчитан на движение к известной точке, а я предполагал просто движение к максимуму оценочной функции.

В общем, что-то с этим солвером у меня вообще не заладилось, я запутался и решил его выкинуть. Написал новый "наивный" солвер, который назвал Solver2, а впоследствии переименовал в BottomSolver (да уж, лучше название не придумаешь). Идея была проста: ищем самое нижнее место, куда можно воткнуть фигуру без учёта поворотов, и втыкаем. Получилось даже не очень плохо, хоть и не без нюансов (учитывать фигуры сложной формы этот солвер так и не научился).

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

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

Контест вышел достаточно весёлый, и в целом мне всё понравилось. Однако же, результатом я недоволен: хотелось бы достигнуть большего.

Что бы могло нам помочь? Что мы сделали неправильно? Вот некоторый список пунктов, которые могут нам помочь подготовиться в следующий раз получше.

1. Хорошая идея — сразу делать автоматизированный скрипт, который будет заливать решения на сервер. Так можно будет быстро проверять гипотезы, и всё такое.
2. Юнит-тесты — это хорошо.
3. Иммутабельность — это замечательно, давайте её использовать!
4. Положительного опыта со Scala не получилось. Отрицательного, на мой взгляд, тоже, но раз уж наши "тяжеловесы" чувствуют себя лучше с Haskell — хорошая идея использовать именно его. Ну или, как на памятном russian-winter-icfpc, применять какое-то гибридное решение. В частности, Scala показала себя хорошо с точки зрения отладки и визуализации результата.
5. У нас в коде очень много багов. Причём как в этом, так и в прошлых контестах. Надо что-то делать :(
6. Обязательно нужно хоть немножко изучить теорию — все эти солверы, алгоритмы, машинное обучение.
7. Желательно, чтобы все участники подготовились и подтянули знания используемого языка программирования (если это будет Haskell — то подтягиваться придётся как раз мне).
8. Может, действительно использовать алгоритмы машинного обучения? Судя по тегам других участников, генетические алгоритмы достаточно неплохо показали себя на данном контесте.

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