ICFP 2012

Подготовка.

В этом году наша команда ShallowEndians пополнилась новыми людьми. Как и в прошлом году участвовали Джей, Пол, Кирилл Т., Кирилл М. и я. Но к нам ещё присоединились Гена и Млош. Также было решено работать в офисе, но в этом году не было свободных офисов и мы поселились в небольшом конференц зале.

Кирилл Т. создал образ дебиана, а Кирилл М. настроил меркуриал на своем амазоновском сервере. В этом году решили попробовать писать на одном языке. И им должен был стать C++.

До этого самого события мы ещё просто встретились что бы познакомится и просто обсудить предстоящее событие. На встречу я тоже опоздал;)

В пятницу мы договорились собраться в 5 утра в офисе и обсудить задачу. Среди нас только Джей был готов взять отгул на пятницу, что бы посвятить время icfp. Так что по плану мы должны были собраться после работы в 5 вечера.

В этом году я подошел к icfp не совсем в форме. Хоть и приехал с отпуска за две недели до, но ха это время эффект отпуска как рукой сняло. К тому же в четверг меня подняли в 5 утра - у нас были проблемы в одном из кластеров. Хоть фронтэнд и переключился на запасной кластер, но это надо было расследовать. В итоге весь четверг убил на это. А в пятницу в 3 утра опять подняли. На этот раз - это было ложное срабатывание вызванное инцидентом в четверг.

День первый.

По вышеизложенным причинам я не смог присоединится к комрадам в 5 утра. Но я успел прочесть задачу и отослать несколько идей которые появились:

• важно сохранять текущий лучший результат и по SIGINT выводить его в консоль и выходить. Лучше не ждать ещё 10 секунд, так можно схлопотать SIGKILL.
• большие карты решить будет сложно, надо собрать все лямбды локально идти к следующей далекой лямбде.
• A* кажется хорошим строительным блоком для других стратегий.
• интерактивная тулза будет очень важна для анализа решений и отладки алгоритма
• Что бы определить регионы которые надо посещать надо воспользоваться алгоритмом кластеризации

Написав это я лег спать. А Кирилл М. с Джеем за пару часов до работы успели написать почти полный симулятор карты. Джей продолжил работать над симулятором, а Кирилл М. начал работу над BFS ака полный перебор. У комрадов была идея разбить карту на регионы и на каждом запустить BFS что бы найти оптимальные ходы для сбора всех лямбд.

Я присоединился к команде в 5 вечера. Милоша не было, а остальные уже были в зале. Работа кипела и по началу я даже не знал чем заняться. Скачал репу и скомпилил проект. Почитал уже написанный код. Почитал ещё раз задание. В общем все были в работе. И особо отрываться не хотели.

В данный этап в основном кодили Кирил М. и Джей. Кирил работал над BFS, Джей над симулятором. Остальные обдумывали задачу. Придумывали разные сложные карты, пытались определить алгоритмы которые могут пригодится.

Над идеями типа нейронных сетей мы посмеялись, но не приняли всерьёз. Камрады сказали что отказались от A* потому что, по описанию, он плохо работает на динамических картах. Была хорошая идея заключавшаяся в том, что бы разбить алгоритм на множество простых решений - набор предикат-решение опрашивался бы на каждом ходу. Если бы предикат возвращал true, выполнялось бы решение. В этом случае мы могли бы иметь общий алгоритм, который работал бы в большинстве случаев и набор захардкоженых решений для очень сложных случаев.

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

Про молниеносный раунд никто даже и не заикался. Участие в нем не представлялось возможным.

В общем помозговали немного. Идей было море, но вот времени на их реализацию не очень. Я был уже готов писать код. Не хотел пересекаться с тем что уже идет в разработке. Я задал вопрос комрадам - "что делать то?". На что получил ответ, что когда будет готов BFS, надо будет как то ходить от региона к региону. Вот этим я и занялся.

Я ещё раз прочитал статьи про BFS и A* в википедии. Все же верил, что на динамических картах A* должен работать. И я решил его реализовать. Основная идея была в том, что бы хранить в каждой ячейке карты саму карту, которая бы предоставляла состояние которое будет после того как мы туда доберемся. Эвристика была простой - расстояние + прохождение по земле - пенальти +1, иначе - пенальти 0.

В общем около 11 вечера у меня уже был алгоритм почти готов - путь находился, но в бектрекинге у меня был баг. Кирилл М. решил пойти домой, ну и я тоже пошел спать. Правда придя домой решил добить A*. Нашел багу и за минут 10 сделал dummysolver, программу которая берет лямбды, сортирует по удалению, пытается пройти к одной лямбде (сперва ближней, потом далее по расстоянию), дальше повторяется. В общем я обрадовался. До конца молниеносного раунда оставалось 4 часа и был шанс засабмитить. Но потом я нашел баг, что робот не умерает если по нему шарахнет камень. С таким багом алгоритм поиска пути выдавал фатальный вариант и робот умерал. Я огорчился и лег спать.

День второй.

Утро субботы началось не очень приятно. Оказалось что мой код не компилируется у большинства людей. Я использовал gcc 4.6, а некоторые - gcc 4.4 в котором не было поддержки auto, некоторые Visual Studio, в которой не было поддержки новому for (for(auto & i : container) {}), у некоторых были проблемы с std::unique_ptr. Немного подумали и самым простым было выпилить новый стандарт со всего кода. На это ушло около часа. Неблагодарная работа. Код стал менее читабельным.

Я объяснил как сделал A*. Рассказал, что хочу ввести более сложные эвристики. Например пенальти за сдвиг камня. Гена проявил сомнения что он будет работать с эвристиками отличными от расстояния. Мы немного подискутировали на эту тему и я сел и написал новые эвристики. Теперь за проходжение сквозь лямбду не было пенальти, пустая ячейка - +1, земля - +3, земля, которая находится под камнем, давала +7 пенальти. И оно заработало. Причем очень даже неплохо.

Дальше я попросил Джея сделать статистику по падению камней. Каждый раз, когда один камень падал, она увеличивалась на 1. Я интегрировал в A* и он стал ещё лучше. Теперь к примеру если был короткий путь, но который сдвинет камень и он упадет на 10 клеточек вниз, получал более низкий приоритет, чем обходной путь, который не тронет камни. Но если выхода не было, то камни двигались.

У Кирилла уже почти был готов BFS, он работал над тем что бы вырезать куски карты и перебирать варианты на меньшем участке. Джею организаторы не давали скучать своими обновлениями - водой, трамплинами и подобными пакостями. Милош работал над редактором, а Пол, Кирилл и Гена над исследованием алгоритмов. Они нашли статьи по сокобану и прочие алгоритмы и анализировали как их можно применить.

Я нашел проблему в моем алгоритме, робот загонял себя в тупик. Если над ним был камень, а по бокам стены - то он не мог продолжать двигаться. Я по началу начал запрещать двигаться к таким лямбдам, но это не дало ожидаемого результата. Алгоритм стал работать медленно, хотя и работал лучше.

Мне пришла идея использовать симуляцию отжига. Алгоритм был таков - находим первое решение. Запоминаем его. Дальше отрезаем 80% пути и делаем рандомное движение к любой лямбде. Дальше включаем алгоритм найти решение до конца. Получив несколько решений - выбираем лучшие. От них отрезаем 60% пути и продолжаем. Дойдя до 20%-го отрезания - возвращаемся к 80%. В общем этот алгоритм реализовывал некое подобие бектрекинга. Не настоящей бектрекинг, который мы хотели сделать, но первая быстрая версия. Стыдно говорить, но в начале я реализовал неправильно алгоритм. Делал по памяти. В начале отрезал 20%, потом 60%, потом 80%. То есть делал наоборот. Но быстро исправился.

Гена начал работать над высокоуровневыми стратегиями. А у Кирила был готов алгоритм и мы его начали комбинировать с моим. Идея была такова - если в округе есть лямбда - включать BFS, если нету - выбирать ближайшую лямбду и двигаться к ней, а дальше повторить. К тому же в качестве рандомного действия в симуляции отжига - мог включится BFS.

С одной стороны BFS давал хорошие результаты, но как и любой полный перебор - он был не очень быстр - что замедляло симуляцию отжига и уменьшало число популяций алгоритмов которые прорабатывались. Я немного уменьшил размер популяции что бы компенсировать. Результат был уже очень даже ничего.

Кирилл Т. нашел народные карты. Аж 1000 штук. И залил их в репозиторий. На очень больших картах наш dummysolver не очень шустро работал. На самой огромной я не дождался результата за одну минуту. Было над чем поработать.

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

День третий.

Гена занялся реализацией кластеризации карты. Нашел библиотеку с кодом для Lin–Kernighan, и прикручевал её. Пол, хотя он и не знает C++, помогал реализовывать последние изменения от организаторов. Джей допилил интерфейс карты и оказалось, что мой A* не надо менять для поддержки трамплинов. Я надеялся на это, но все же было приятным сюрпризом. Кирилл Т. начал работу над тестами.

Кирилл М. оптимизировал BFS. Он придумал способ ускорить его получая лучший результат. На этапе когда память подходила к лимиту он отбрасывал часть решений. В итоге обрабатывалось больше хороших цепочек и получался лучше результат.

Я нашел проблему с тем, что A* не умеет двигаться назад. То есть ему не под силу подойти под камень убрав землю, отойти и подождать пока он упадет, а потом пойти дальше. Хотел решить эту проблему. Даже почти придумали как - убрать все камни, пройти к желаемой лямбде, дальше найти последний камень который мешает, предположить, что мы туда дойдем и включить там BFS, что бы найти путь сквозь камень. Дальше найти предыдущий камень и тд. Но к сожалению я так и не успел реализовать это.

Нам надо было ещё реализовать финальную программу, которую будем отсылать организаторам. Я начал с того, что заменил все std::cout на std::cerr, что бы если мы забудем закомментировать какой то логгинг, это не испортило нам решение. Также сделал хранитель решений, который бы обновлялся последний лучшим решением, а по SIGINT выводил его на экран и завершал программу. Также поддержал SIGABRT и SIGSEGV, на случай если произойдет ошибка, которую не сможем обработать. В этом случае тоже выводился лучший результат и завершалась программа.

Часам к 5 вечера и Пол и Милош нас покинули. А мы остались допиливать решение, исправлять краши, тестировать на разных картах.

Я также внес ещё рандомности в симуляцию отжига отрезая не 80%, а от 80 до 100, а потом не 60%, а от 60 до 80 и тд. Это тоже улучшило результаты.

Часов в 7 мы провели презентацию нашего решения. Не зря же мы поселились в конференц зале с проектором;) Каждый рассказал о том, что сделал и как это внутри работает.

К этому моменту я уже достаточно вымотался. Да и остальные тоже. Джей так вообще без сна был. Никаких кардинальных решений мы не планировали сделать. Только допиливали текущее решения. Только Гена работал над кластерингом, который должен был значительно улучшить результат собирая лямбды в оптимальной последовательности.

Вскоре нас покинул и Кирилл Т. Честно говоря мы так и не успели применить его тесты. Оценить новый алгоритм мы по достоинству не могли, оценивали на глаз и на результат с тестовых карт.

По Джею видно было, что он был ужасно измотан и мы сказали ему, что бы он шел спать. Он немного посопротивлялся и все же пошел. Для него работы много уже не было. После этого нашли два бага в симуляторе, но их смогли исправить сами.

А Кирилл, Гена и я остались до победного конца. Я занялся регистрацией и созданием финального бинарника. Кирилл скачал образ с сайта организаторов, а я установил его в Virtual Box и отработал создание архива с исходниками и финальным исполнительным файлом.

Кирилл успел сделать механихм отталкивания камня от лифта и мы игтегрировали его в финальное решение. Часа в 2 ночи, Гена был начал интеграцию кластеризации и приоретизации кластеров в осноной алгоритм. Я все ещё хотел сделать решение с проходом сквозь камни, но руки не дошли. Ещё пришлось повозится с Кириллом над интеграцией LKH библиотеки. Гена писал на виндовсе и хотя библиотека и была на C, у нас ушло достаточно времени что бы её скомпилить и слинковать с нашим решением на C++. К тому же там было много printf-ов. Я то думал что вычистил все std::cout, а про printf не подумал. Пришлось их комментировать или перенаправлять в STDERR. А дальше мы с Кириллом продолжили текстировать и исправлять баги.

Хоть Гена и старался успеть к 5 утра, но если бы и успел, было бы очень рискованно выкладывать не протестированное решение. Так что к сожалению не успели. А последний час шел очень быстро.

В 4:30 мы уже почти были готовы к заливке финальной версии. Где то в 4:45 я начал финальный билд. Кирилл ещё хотел включить небольшое изменение - включать BFS на всей карте если она не очень большая, а не на окне. Но получить билд уже было нереально. К тому же мы заметили регресию на одной из карте, где камень должен был быть отодвинут роботом, но этого не происходило. Но решено было заливать как есть.

Но я был на мобильном интернете. Остальные подключились к корпоративному интернету, но я не стал заморачиваться - для разработки хватало. Но тут интернет начал тупить. Было уже где то 4:55. Я плюнул - скинул билд на телефон и понес к Кириллу. Но почему то его ubunta не хотела монтировать телефон. Гена побежал на свой этаж за флешкой. Пришел где то в 4:58. Я быстро скинул файл. Кирилл открыл флешку, залил в google docs. Все вздохнули с облегчением. Но там надо было ещё нажать разшарить. Кирилл добавил организаторов, но не нажал на финальную кнопку. Мы это заметили - он нажал, все - файл ушел. За последние 5 минут получил не маленькую дозу адреналина;)

Послесловие.

Мне этот год понравился. Может даже больше чем предыдущий. Мы смогли писать на одном языке. И очень продуктивно взаимодействовали. Кирилл М. к примеру считает, что прошлый год был лучше. Но они немного разные были. В ICFP 2012 нам надо было именно реализовывать алгоритмы, а в прошлом году - придумывать их, а сама программа не была очень сложной.

Некоторые проблем мы решили с прошлого года, но все же было много и ошибок. К примеру вот несколько. Джей потратил много времени на мержи кода. У него не было нормальной утилиты как у других - KDiff3. По началу он использовал vimdiff, пока не перелез на винду. Нам надо было больше времени потратить на тесты и использовать их для нахождения оптимального алгоритма. Мы делали это на глазок. Так же мы не успели сделать много что хотели. Некоторые алгоритмы возможно были бы очень кстати, но руки не дошли до них.

Не смотря на проблемы, я все же считаю что мы молодцы. И неважно какое место мы получим. Мы уже получили массу удовольствия. Хотя это немного извращенное удовольствие. После окончания мы были изнеможены полностью. А в понедельник я ещё и пошел на работу, так как не мог пропустить этот день.

Всего было 270 команд. После первого раунда должно остаться 135. Я надеялся что мы попадем в 80, а может и в 60-ку. Кирилл М. дал прогноз, что мы все же пройдем в 2-й раунд, но еле-еле. После мы прочитали, что команда _adept_-а набрала свыше 6 миллионов на народных картах. Уже после окончания мы протестировали наш алгоритм, он набрал всего 1.3M.

К нашему удивлению в первом раунде мы, ShallowEndians, заняли 19-е место набрав 9877 очков. Я крайне обрадовался этому результату. Я все таки верил в нас. Но на 19 место даже не рассчитывал. Но посмотрим на 2-й раунд. Может это была случайности и среди 135 команд мы не попадем и в первые пол сотни. Кто знает.