ICFPC-2012: Время собирать лямбды и разбрасывать камни

Предыстория

Начать это повествование стоит с того, что после феерического участия в ICFPC-2010 мы с Лёхой на ровном месте продолбали ICFPC-2011 (а какие отчёты народ делает...).
Нет, мы не были ни в разъездах, ни в отпусках, и вообще - не имели никаких уважительных причин. Просто прочитали задание и решили, что... ну скучно же. Нет online-скоринга?! Нет необходимости разгадывать какие-нибудь адские ребусы с адскими кодировками?! А в чём прикол тогда? Где драйв? Что будет поддерживать в нас высокий боевой дух в течение трёх суток?
В общем, пожали плечами и занялись своими делами. И только к вечеру субботы, вчитавшись в интернет и обнаружив дуэльный сервер, я стал проникаться идеей Lambda Gathering и спамить Лёху смс'ками. Утром в воскресенье проснулся с чётким пониманием, что нужно было участвовать. В панике написал на коленке интерпретатор, но в итоге никаких содержательных стратегий мы реализовать не успели и ничего не сабмитили...
Главным результатом этого фейла стало то, что в этот раз мы договорись всё-таки начать решать задачу, а там видно будет.
Организаторы слегка подогревали интерес, периодически публикуя что-нибудь наподобие видео про батут. Отчего я заставил Лёху прочитать про Trampolining a monad computation зачем-то...
Для тренировки порешали задачки с ICPC-2012. Правда Лёха их больше сводил к задачам матпрога и решал с помощью промышленных солверов за какие-то микросекунды. Но я честно повозился с переборными алгоритмами на хаскеле и руку поднабил. Отчасти это сыграло свою злую роль в будущем. Но не будем забегать вперёд.
Еще я поставил правильный Debian на два сервака, которые символизировали собой наш "вычислительный кластер". Деятельность эта закончилась в аккурат в момент публикации задания, так что даже дух перевести было некогда.

Пятница, 13, 16:00

По плану мы должны были осмыслить задание и через два часа встретиться дома у Лёхи в Ближнем Замкадье, где и провести время до утра понедельника. В процессе осмысления я даже проехал нужную станцию метро.
Ну ладно, встретились, стали разбираться, что к чему... Итак, как мы все знаем, в связи с огромным ростом популярности функционального программирования, в мире стало жёстко не хватать лямбд. Однако оказалось, что нехилый запас имеется в шахтах Шотландии (нет ли тут, кстати, какого-нибудь коррупционного совпадения, что в этом году организаторы как раз из этих мест?) и вопрос только в том, как их добыть. Оказалось также, что добывающий робот имеется в наличии, карты шахт тоже есть, нужно лишь составить последовательность команд для робота.
По сути, задача сводилась к написанию программы, которая получает на вход описание лабиринта, а на выходе формирует последовательность команд для его прохождения роботом. Команды могут быть L (влево), R (вправо), D (вниз), U (вверх), W (пропустить ход).
Самый простой лабиринт, из предложенных организаторами выглядел так:

######
#. *R#
#  \.#
#\ * #
L  .\#
######

R - робот, которым мы управляем
# - стенки, через них пройти нельзя
. - земля, её можно сгрызть, тогда она превращается пустую клетку
\ - лямбда... её надо собирать
L - лифт, выход из лабиринта, который откроется после сбора всех лямбд
* - камень...
Камни - это самое интересное. Камни можно двигать, камни могут упасть на голову и убить, они могут завалить проход или наоборот - открыть его. Камни скатываются с других камней и с лямбд направо и налево по определённым правилам. И даже могут сколлапситься друг в друга (rocks crash, yeah...).
Всё это должно звучать более или менее знакомо для любого, кто играл в digger, boulderdash, supaplex или любой из их клонов.
Кому хочется формальных подробностей - вот задание. Есть официальный validator, где можно попробовать свои силы на предложенных организаторами простых картах. Или вот тут вариант повеселее, тем более, что там почти 2000 "народных" карт. По слухам, там на ваших решениях люди какую-то нейросеть пытаются натаскивать... Ну не знаю...
Кстати, на упомянутой простейшей карте максимум можно набрать 212 очков и возможная программа прохождения такая: LDRDDUULLLDDL.
Организаторы обещали еще до 4 дополнений к заданию, поэтому было понятно, что наши "алгоритмы и структуры данных" должны быть "достаточно общими".
Всё это мы довольно быстро осмыслили, повозмущались опять отсутствию online-скоринга и взялись за дело. Я вооружился спецификацией и стал писать интерпретатор, который по данной карте и последовательности шагов робота вычисляет новое состояние карты и положение робота, а также количество набранных им очков. Лёха стал ковырять официальный валидатор. Периодически у меня возникали вопросы по спецификации и Лёха выяснял ответы путём эксперимента.
Интерпретатор был готов уже где-то к 11 вечера в пятницу. Он работал чертовски медленно, потому что представлял всю карту как один большой немутабельный двумерный массив, который целиком копировался на каждый чих. И он не был покрыт тестами совершенно. Но работал.
Примерно в то же время, как у нас появился интерпретатор, организаторы опубликовали первое дополнение к заданию. Им стали наводнения. Ну понятное дело, погода в Шотландии плохая, шахты подтапливает. В принципе робот обладает некоторым запасом водостойкости, но увлекаться не следует - периодически надо выныривать из воды, глотнуть свежего воздуха лямбда-шахт.
На дополнения мы сразу забили, решив в субботу сосредоточиться на главном: на алгоритме поиска решения. При этом еще зачем-то часа два ночью проспорили о том, будет ли на этой задаче работать метод динамического программирования или нет. Я считал, что будет, Лёха считал, что нет. В конечном итоге он оказался прав, но меня в тот момент не убедил.
Главным Лёхиным аргументом была мощность фазового пространства, неподъёмная даже на маленьких картах. Я же считал, что поскольку все карты подобраны вручную организаторами, то там будет очень мало содержательных траекторий робота, т.е. что нас будет интересовать ничтожное подмножество этого фазового пространства. Кроме того, была идея, что многие формально различные состояния игры легко отождествляются. Например если некоторый камень уже пролетел мимо робота, то можно смело считать, что он уже упал до самого низа. Догнать его роботом и изменить его траекторию уже невозможно. Из этой идеи должен был появиться "интерпретатор с большим шагом", но так и не появился...

Суббота

Если проигнорировать некоторое количество коммитов с комментариями, содержащими словосочетание "evil eclipse" (да, Лёха использует EclipseFP, а я - emacs), то первое, что было сделано в субботу, - это генератор случайных карт. Он быстро позволил нам выяснить, что интерпретатор никуда не годится. Точные цифры не помню, но большие карты он интерпретировал просто неприлично медленно. С одной стороны, мы рассчитывали переписать конечное решение на C/C++, но с другой стороны даже для исследовательской работы интерпретатор был признан малопригодным (и наверное зря...). Возникла задача его оптимизации. С ней я справился только к трём часам дня. Очень подвело отсутствие тестов. Параллельно Лёха написал вариант интерпретатора на C#. Он работал еще раз в 10 быстрее, чем моя оптимизированная реализация, но оказался нежизнеспособен: баги, мутабельные структуры данных итп. Даже Лёха признал, что C# не рулит.
Но главной моей ошибкой было то, что новый интерпретатор я делал, имея в виду конкретный алгоритм поиска решения, а именно упомянутый выше метод динамического программирования, и все структуры данных интерпретатора были неудачно заточены под него. В частности, меня очень интересовала скорость сравнения двух "состояний игры". Эх, Лёха, что же ты меня за руку в этот момент не поймал...
Наверное правильнее было бы оставить медленный "референсный" интерпретатор и сделать к нему набор тестов. А уже потом, определившись с алгоритмом поиска пути, переписать всё еще разок. Может быть даже и на C/C++.
Пока я возился с интерпретатором, Лёха не терял времени и исследовал содержательную часть задачи. Видимо он хорошо понимал, что несмотря на моё сопротивление, нам нужны будут приближённые или вероятностные методы поиска решения. Периодически на его мониторе я мельком видел страницы википедии типа Ant colony optimization algorithms и еще что-то на ту же тему с wolfram'а итп. К вечеру я уже и сам осознал, что динпрог в чистом виде здесь не сработает. Мы просто не сможем придумать и реализовать достаточное количество "тонких" оптимизаций, чтобы не перебирать всё фазовое пространство. Именно так к 11 вечера появилась первая версия алгоритма с муравьиной колонией. И - чёрт возьми! - некоторые маленькие карты муравьи проходили вообще оптимально, а на больших картах жрали хоть какие-то лямбды. Еще несколько часов ушло на допиливание и изучение алгоритма. Последний коммит в субботу был сделан в районе 3 часов ночи. Кстати, это был очень содержательный коммит. В нём был алгоритм "естественного отбора" (т.е. поддержания размера колонии муравьёв в заданных пределах), алгоритм присваивания цели муравьям ("иди к той лямбде"), куча исправлений и оптимизаций. Короче, вечер пропал не зря.

Воскресенье

Утром вставать было совсем тяжко. А впереди было море работы. Стало ясно, что переписать всё на C/C++ - это утопия. Поэтому пришлось улучшать и чистить то, что есть.
Лёха взялся за эвристику, позволяющую муравьям идти по градиенту потенциальной энергии к цели. Я же стал внедрять дополнения. Кроме наводнений к тому времени уже были известны те самые трамплины (чтобы роботу было проще перемещаться по карте, ага) и бороды Водлера. А в четыре дня стало известно, что лямбд гораздо больше, чем мы полагали раньше. Просто нужно уметь добывать их из камней высших порядков.
Все дополнения были реализованы только в первом часу ночи. Я сейчас даже не помню, почему это было так долго. Но ясно, что тесты на интерпретатор спасли бы отца русской демократии... Потому что значительную часть времени он ловил какие-то изумительные баги. То лямбды, вывалившиеся из камней, продолжали свободное падение. То камни с лямбдами не убивали робота. То бороды отказывались нормально расти. То лифт отказывался открываться после съедания всех лямбд. Весь день я как мантру повторял одну и ту же фразу: "Алгоритмы и структуры данных". Тяжелое наследие несостоявшегося метода динамического программирования сквозило в каждой строчке кода...
По моим ощущениям, Лёха тоже день провёл крайне "плодотворно". Он свёл задачу к какой-то задаче линейного целочисленного программирования и попытался заставить какой-то matlab'овский солвер её решать. Я не вникал, чем дело кончилось, но помню, что робот долго ходил по стенам, потому что штрафы от этого ему казались пренебрежимо малыми по сравнению с мучениями по честному сбору лямбд... Но расчёт потенциальной энергии Лёха всё-таки сделал к вечеру, и муравьёв вроде как стало притягивать к лямбдам "более лучше".
Короче, Лёха успел в этот день изрядно порефлексировать над тем, что мы на самом деле сделали, и озвучил интересный прогноз, что мы пройдём первый тур и завалимся во втором. Я же весь день прозанимался какими-то частностями, поэтому не сразу понял, откуда такая уверенность.
А потом понял и согласился. Первый раунд по замыслу организаторов должен проводиться на картах небольшого размера. На таких картах наши муравьи могут перебрать практически все варианты ходов, поэтому вопрос о прохождении во второй тур сводится к вопросу о корректности интерпретатора. Так что первая часть Лёхиного прогноза - это просто его оценка моих способностей кодировать по спецификации :-) А вторая часть прогноза - это оценка способностей нашей муравьиной колонии решать поставленные перед ней задачи...
Во втором часу ночи мы занялись подготовкой пакета для отправки организаторам, потому что возможности по продолжению банкета в понедельник были сильно ограничены.

Понедельник

В понедельник я проснулся полон сил и энергии улучшать мир. Хотя бы малую его часть. Хотя бы один муравейник. Лёха, наоборот, сказал, что ужасно не выспался и делать что-либо не в состоянии.
Но добравшись до работы он всё-таки сделал очень полезное исправление, научив потенциальную энергию лямбды распространяться через трамплины.
А я успел классифицировать ходы муравьёв на "интересные" (съел лямбду, залез в трамплин итп) и "неинтересные" (ничего не случилось), рандомизировал неинтересные ходы, исправил кучу багов итп.
В итоге финальная сборка готовилась за 15 минут до дедлайна, как оно обычно и бывает. И вот тут уже драйва было выше крыши...
...В ночь с понедельника на вторник я спал сном младенца. Часов 12, не меньше.

Результаты

Пока я неспешно готовил этот пост, организаторы столь же неспешно провели первый раунд. Как и говорил Лёха, этот барьер мы взяли, заняв со своими муравьями 80-ое место (в полном соответствии с результатами 2010-го года...). Всего во второй раунд прошло 117 команд. Немного напрягает то, что на третьей карте мы набрали -14 очков, что как бы намекает, что некоторые баги в интерпретаторе всё-таки остались.
Ждём результатов второго раунда... Upd. Ну вот, всё по плану...

Некая рефлексия aka Выводы

Хочется отметить некоторые особенности задания.
Во-первых, уже не первый год обязательной частью задачи для ICFPC становится программирование по спецификации. Не знаю, в чём тут великая идея, но похоже, что это играет роль порога вхождения. Хотя мне, если честно, больше нравится, как это было устроено в 2010-ом году с разгадыванием префикса. Причём в отличие от прошлого года, в этот раз еще были 4 дополнения к спеку, чтобы жизнь не казалась мёдом.
Во-вторых, в который раз отмечу отсутствие online-скоринга. Узнавать свои результаты через несколько недель - это очень уныло и демотивирует чертовски. В прошлом году хотя бы дуэльный сервер был... В общем, это тоже становится печальной традицией.
В-третьих, тенденцией становится использование "игровой" модели соревнования, а не "квестовой". Наверное одним из самых ярких квестов в истории ICFPC был про Endo. А в последние годы организаторы всё чаще предлагают самим участникам побороться друг с другом. В 2010-ом это была возможность сабмитить свои машинки. В 2011 - это вообще были дуэли программ, т.е. игра в чистом виде. В нынешнем году была возможность засабмитить набор своих карт. Организаторы намекали, что самые интересные карты могут включить в состав официальных.
Что касается непосредственно нашей команды IKS, то все выводы 2010-го года остаются в силе :-) Хотя готовы мы вроде были чуть лучше, но на результате это визуально не сказалось. Главным же достижением я считаю то, что мы всё от и до сделали на хаскеле - языке, с которым профессионально практически не работаем, но который нравится и взрывает мозги своей красотой и сложностью.

Отчёты

Классика жанра - отчёт _adept_'а
И еще: отчёт sergeif'a, отчёт undefined.org.ua, отчёт 7-12, мини-отчёт yantayga, атчод sorhed, отчёт xoposhiy.