dastapov | ICFPC 2012: от Lambda The Gathering к Gathering The Lambdas

Обязательное вступление: что это вообще такое?

Каждый год случается международная конференция ICFP - International Conference on Functional Programming. К этой конференции приурочен програмерский конкурс под названием ICFPC. Несмотря на название конференции, участвовать в контесте может любой желающий, и пользоваться можно любыми языками, не только функциональными, кроме того - участники могут объединяться в команды. ICFPC отличается от соревнований типа ACM и topcoder тем, что он менее "заточен" под какие-то конкретные языки или наборы навыков, а задачи в нем прикольные и позволяют получить удовольствие не только от победы, но и от участия.

Я стараюсь принимать участие во всех ICFPC, и о том, как это было в прошлые годы, можно почитать в этом журнале по тэгу icfpc.

Подготовка

В этом году я заранее вписал даты в календарик, взял на работе отгул, и договорился с Женей

antilamer и Ваней

_navi_ о том, что мы будем выступать одной командой и писать на Haskell.

Моя жена собиралась где-то в это же время поехать с детьми на историческую родину, и мы подгадали поездку так, что на время ICFPC я остался один-совсем-один. Если быть точным, за 4 часа до старта я был в аэропорту и провожал их на самолет, и вернулся домой за 5 минут до начала.

Подготовка, таким образом, свелась к заливанию ssh-ключей на bitbucket (где у нас был git-репозиторий) и обмену контактами с остальными участниками команды :)

Старт и условие

Локальное время: 13:00

Когда соревнование началось, у Жени и Вани было 5 часов утра, поэтому я читал задание самостоятельно. Соревнование в этом году называлось "Lambda Lifting", хотя можно было бы переставить слова в прошлогоднем названии (Lambda The Gathering) и получить Gathering The Lambdas - вышло бы вернее.

Я думаю, многие из вас играли в детстве в Supaplex, Rocks'n'diamonds или Boulderdash или в какой-то из бесчисленных клонов этих игр, в котором надо бегать по лабиринту и собирать алмазы, уворачиваясь от падающих камней:

Watch on YouTube

В этом году участникам ICFPC предлагалось написать решатель уровней для подобной игры, который будет брать с stdin описание карты, и выдавать на stdout последовательность из команд Up, Down, Left, Right, Wait, которая позволит роботу собрать в подземной шахте все сокровища (лямбды), после чего откроется выход (называемый Lambda Lift), и робот сможет подняться на поверхность.

(Тут надо заметить, что организаторы в этом году не поскупились на pun-ы и шутки для тех, кто в теме. В частности, название конкурса одновременно является известной техникой реализации интерпретаторов или компиляторов функциональных языков: Lambda lifting)

Конечно, условия для конкурса были попроще, чем в реальных играх: из объектов в лабиринте были только камни и лямбды, робот не мог обогнать падающий камень и падающие камни не разбивали/уничтожали сокровища.

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

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

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

Учитывая опыт прошлых лет, все найденные баги снабжались тестами - либо HUnit+TestRunner прямо в коде, либо shelltestrunner для black-box тестирования. Забегая наперед скажу, что всего у нас было 34 теста для shelltestrunner ("скорми вот эту карту и эту программу в симулятор, проверь, что получился такой результат" или "реши карту такую-то, проверь, что получилась такая программа") и 26 тестов в коде ("сделай update такой-то карте, сравни, что вышло") и они нам здорово помогли во второй части соревнования, когда мы стали радикально менять нашу реализацию.

Учитывая, опять же, опыт прошлых лет, который убедительно доказал, что визуализация - это все, я быстро сделал две утилитки, которыми мы потом пользовались постоянно и постоянно же дорабатывали:
1)"play", которая позволяла поиграть на выбранной карте, двигая робота клавишами a,s,d,w
2)"run", которая позволяла посчитать очки, набранные роботом и, при желании, показать пошагово состояние карты после каждого хода

Реализация была максимально простой: карта хранилась как Array (Int,Int) Cell, все обновления/движения робота делались как list comprehensions по всей карте. Про скорость я в этот момент не думал вообще.

Вечер первого дня - dummy solver

Где-то в 18:00 прорезались мои товарищи по команде, сказали, что они уже прочитали задание, но будут еще недоступны несколько часов. В процессе они будут изучать, что же придумали другие люди в области решения подобных головоломок. Оказалось, что bouderdash как-то незаслужено обойден вниманием, зато про sokoban пишут статьи и даже master thesises:

* http://webdocs.cs.ualberta.ca/~games/Sokoban/program.html
* http://stackoverflow.com/questions/4237462/sokoban-solver-tips (тут ссылка на тезис)
* http://pavel.klavik.cz/projekty/solver/solver.pdf
* http://sokobano.de/wiki/index.php?title=Links#Sokoban_Solvers
* http://webdocs.cs.ualberta.ca/~games/Sokoban/papers.html

Беглый просмотр показал, что везде упоминается знаменитый алгоритм поиска A*, а cabal list сказал, что вот как раз есть готовый пакет astar для этих целей.

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

На базе этого был сделан тупой солвер (забегая наперед скажу, что название dummy.hs просуществовало до конца соревнования, и именно эта программа и была сдана). Солвер делал две простые вещи:
1)Находил координаты ближайшей (по прямой) лямбды и шел к ней. Если ему это удавалось, шел к следующей. Если нет - позорно завершал работу
2)Если в какой-то момент открывался лифт, он шел в него (если ему это удавалось).

Ура, на 10 картах, предложенных организаторами, этот солвер даже что-то нарешал!

В 21:00 появились мои товарищи по команде и мы стали обмениваться мыслями и читать мой код.

Где-то в это же время организаторы опубликовали первое дополнение к правилам (а всего их было обещано до 5 штук): в шахте может быть вода, уровень которой поднимается на 1 клеточку каждые N ходов. Робот обладает "водоустойчивостью" в M ходов - он может "заныривать" под воду, но после M ходов, проведенных под водой, он тонет. Чтобы не утонуть, роботу надо периодически подниматься выше уровня воды.

Мы подумали, что любой достаточно общий алгоритм поиска пути без труда будет отсекать те варианты, в которых робот тонет, и временно отложили реализацию этого изменения. О том, чтобы сдавать свое решение в lightning round-е (после первых 24 часов) мы даже не заикались :)

Дальше в течении пары часов мы гоняли тупой солвер на имеющихся картах, смотрели на его поведение, нашли и пофиксили пару багов, нагенерили кучу идей (и больше половины из них, как оказалось было дельными :)

Стало очевидно, что на "больших" картах (больше 10x10 :) решалка почему-то тормозит и, похоже, многократно перебирает похожие пути движения. А если выбранная цель недостижима, то у нее наступает ступор, и она никак не может сообразить, что выход завален камнем, и перебирает и перебирает все возможные способы сделать 2-3-4-5 ходов в нужном направлении.

Пока я что-то кодил, мои коллеги (сидящие в одной комнате) читали и спорили про travelling salesman problem, branch-and-bounds и breadth-first search и их применимость к проблеме в общем и к отдельным ее аспектам.

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

Второй день - ускоряемся!

Проснувшись часиков в 10, и почитав сообщения, оставленные мне Женей и Ваней, я узнал, что наш A* не только тупит над недостижимыми состояниями, но и вообще сильно тормозит. Женя переписал часть кода, чтобы это исправить - например, для определения того, являются ли два игровых состояния идентичными, сравнивалась не вся карта, а только координаты робота и камней, и превратил карту в IntMap (IntMap Cell) но радикально проблему это не решало.

Кроме того, часть тестов начала FAIL-ится после ряда изменений в коде, и у них не хватило времени понять, отчего и почему.

После завтрака я сначала пофиксил все баги (тесты - это наше все, я уже говорил это?), причем самый тяжело ловимый баг оказался в результате вот чем:


-inMine (x,y) m = x>0 && x<=maxRow m && y>0 && y<=maxCol m
+inMine (x,y) m = x>0 && x<=maxCol m && y>0 && y<=maxRow m

После этого я собрал код с профайлингом и стал смотреть, где же он тормозит. Тормозил он в очевидных местах (неэффективное внутренне представление карты и ее обновление), поэтому я по совету Вани стал паковать координаты в один Int (путем x<<16+y), превратил карту в IntMap Cell, переписал части функций обновления карты и движения робота менее "в лоб" и код ускорился в 20-25 раз :)

Самым большим тормозом было неуемное употребление функций вида "возьмем все клетки карты, отфильтруем те, на которых стоит лифт, возьмем ее координаты". Поскольку лифт всегда был всего один, разумнее было просто хранить его координаты в состоянии мира отдельно :) Аналогично стали хранится координаты камней и лямбд. Т.к. карта у нас была абстрактным типом с достаточно простым интерфейсом, все эти изменения были достаточно безболезненными.

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

Народные карты

Неотъемлимой частью ICFPC является треп на IRC и в Jabber. Читать его не только интересно, но и полезно - в середине второго дня кто-то упомянул, что на хабре появилась ссылка на сайт с crowdsourced картами и я быстренько скачал их все.

Карт оказалось 1000 штук, и некоторые из них были большими и/или заковыристыми. Я тут же запустил нашу решалку на всех картах подряд и получил в сумме 80К очков.

Радости моей не было предела, пока aleksey (который, к слову, занимал на ICFPC призовые места и вообще олимпиадник и мозг) не сказал мне, что у него на этих же картах результат свыше одного миллиона. Однако ...

Тут же на IRC показали еще один набор заковыристых карт, сделанных вручную: http://icfp.stbuehler.de/icfp2012/ , и на большинстве из них наша решалка тупо сдавалась сразу.

Трамплины

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

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

Пока я этим занимался, появился Женя (у которого были идеи про стратегии) и стал их реализовывать. В частности, A* теперь использовал более реалистичную оценку расстояний до целей. Для того, чтобы считать эти расстояния (которое мы стали называть "статический роутинг"), Женя использовал тот же A*, но не обновлял карту (не двигал камни, и т.п.). Таким образом, у нас получился A*, использующий A* :)

В процессе переделок, правда, было традиционно поломано и починено N тест-кейсов, на что ушло какое-то время. После того, как тесты стали зелененькими и решалка снова стала что-то решать, обнаружилось, что ей, вопреки ожиданиям, сильно поплохело.

То статический роутинг не мог понять, что некоторые камни можно подвинуть и выдавал чушь, то A* уходил в себя и начинал перебирать кучу вариантов путей из пункта А в пункт B в, казалось бы, тривиальных случаях, где можно было брать и идти напролом.

А тут еще и aleksey сказал, что у него текущий результат на "народных" картах - 6 миллионов очков. А у нас - по-прежнему 70 тысяч. Было от чего расстроится.

После недолгих совещаний мы решили выкинуть имеющий вариант A* (который шел к лямбдам "вообще", а не к какой-то конкретной в частности), и заменить его на другой - который будет четко идти к ближайшей достижимой, а когда достижимых не осталось - к выходу (если он открыт). Мы использовали такой подход в самом начале, и он работал плохо, т.к. у нас не было определения "достижимости" целей. Теперь она у нас была (пресловутый "статический роутинг") и дело пошло на лад.

Следом мы добавили в наш статический роутинг поддержку трамплинов, и - ура! - стали получать какие-то результаты на картах с трамплинами. Да и на народных картах результат улучшился до 180К. Мы еще немного покрутили имеющуюся стратегию так и сяк, потом вернулся с велогонки Ваня, а я пошел спать

Комбинируем стратегии

Пока я спал, Женя и Ваня сделали кучу изменений и улучшений в нашей реализации А*, в статическом роутинге и добавили определение ситуаций, в которых возникает deadlock (пошли за лямбдами, а выход завалило камнями). Счет на народе вырос до 600К, так что все изменения явно были полезными. Ребята даже написали мне в скайпе комментариев и пожеланий, но, увы, половина из них была мною не понята (или понята не до конца), т.к. я не был настолько сильно погружен в контекст, как они, когда это писали.

С утра пораньше я обнаружил карту, на которой робот должен первым делом подождать, пока мимо него пролетят падающие камни, а потом уже идти собирать, что получится. Наша же решалка сразу говорила "ничего не могу" и завершалась. Это было странно, т.к. наш А* явно должен был ументь рассматривать Wait в качестве потенциально команды. Ошибка, похоже, была где-то в коде "статического роутинга", но я ее не мог найти. Я покрутил код и так и сяк, и ничего не добился. Я стал вчитываться в комментарии в скайпе и в коммиты, сделанные за ночь.

Чтобы проверить парочку своих предположений, я быстро на колене слепил альтернативную решалку (на базе все того же А*), в которой эвристикой была сумма расстояний до всех лямбд (по прямой), а целевой функцией - получить больше заданного числа баллов. Дальше я вызывал этот А* в цикле. Первый раз он искал путь с кол-вом очков, больших нуля. Потому - больше уже найденного, и так далее. Кода в ней было строк 50, но неожиданно оказалось, что она умеет правильно ждать и вообще на мелких картах очень часто обгоняет имеющийся у нас алгорим (по очкам), но проигрывает ему по скорости.

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

Окрыленный успехом, я сделал комбинированный решатель, который гонял три стратегии параллельно:
1)Идем к ближайшей лямбде, и так по очереди (то, что мы использовали повсеместно до недавнего времени)
2)В цикле гоняем мой тупой A* от первоначальной позиции, задавая ему в качестве цели (которую надо улучшить) счет текущего наилучшего решения
3)В цикле гоняем мой тупой А* от позиции текущего наилучшего решения, пытаясь набрать еще больше баллов.

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

Кроме того, организаторы выдали еще одно обновление правил. Теперь в шахтах могла расти растительность (называемая "Wadlers beard", в честь вот этого), и ее можно было убирать "бритвой Хаттона" (а вот и сам Хаттон). Кроме того, "бритвой Хаттона" по аналогии с "бритвой Окамла" называют простой формальный язык из одной операции, который служит хорошим тестом на тьюринг-полноту языка -- если на нем нельзя реализовать "бритву Хаттона", то о чем-то более серьезном и заикаться не стоит. Я не нашел хорошей ссылки, но вот тут есть дельное описание).

Я добавил рудиментарную поддержку этого в наш код - растительность росла, робот собирал бритвы, но брить растительность не умел и не пытался.

В 16:00 появились Ваня и Женя, и я продемонстрировал им свои успехи, после чего Женя стал отлаживать свою реализацию IDA* и поиска deadlock-ов, и раз за разом улучшать и ускорять их. Например, вместо сравнений координат камней мы стали считать и сравнивать сумму хэшей всех координат. Кроме того, мы стали сообща рассматривать карты, на которых робот заходил в тупик, тупил или сдавался в неожиданно простых ситуациях и допиливать нашу стратегию напильником.

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

Самый замечательный фикс этого вечера:


-move (x,y) Wait = (x,x)
+move (x,y) Wait = (x,y)

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

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

Финишная прямая

Проснулся я за четыре часа до окончания конкурса, думая что осталось всего делов-то - протестировать все, спаковать, и отослать организаторам. Но не тут-то было.

Выяснилось, что Женя и Ваня довели наш суммарный счет на народных картах до 6.2 миллионов(!) и не собираются останавливаться на достигнутом. Более того, они до сих пор не спят. Следующие два часа у них прошли в отчаянных попытка выжать ну еще хоть чуть-чуть из того, что есть, а я тем временем поднимал в VirtualBox образ вирт. машины, предоставленный организаторами, чтобы проверить, что наше решение там без проблем заработает.

Женя в процессе изменил "play" так, чтобы он мог работать в паре с решалкой и показывать движения робота в режиме реального времени (см. видео ниже), и это очень сильно помогло с внесением/отладкой последних изменений.

В какой-то момент я понял, что Ваня и Женя вообще не используют комбинированный решатель, и попробовал проверить, нет ли от него каких-то улучшений. Оказалось, что на ряде карт он находит более хитрые пути и набирает больше очков. Тут я попытался его воскресить и мы даже в какой-то момент решили, что сдавать будем именно его, но в конце-концов я забоялся того, что при out-ouf-memory комбинированный решатель набирает 0 очков, и мы сдали более простой, с одной стратегией.

Как обычно, времени хватило в обрез, за 30 минут до финиша мы еще что-то меняли в коде, за 10 минут до конца я еще компилировал Самый Последний Самый Правильный бинарник, и заливали мы его за 5 минут до финала.

Но успели :)

Уфф. Несмотря на относительную простоту, этот ICFPC мне понравился. Задание было простым, и в то же время без единственного верного решения. У нас не было затыков, когда мы сидели и не знали, что делать - скорее наоборот, всегда было море идей, и сложно было решить, какую же имено реализовывать. Обновления к правилам не давали скучать.

Жалко, что не было глобального scoreboard-а и не было элемента соревновательноси ("а вот мы закоммитили вот это и обогнали команду X!"), но и без этого я получил море удовольствия.

Организаторы сказали, что оценивать решения будут путем нескольких раундов с выбыванием (что бы это не значило), и я не думаю, что наше решение дотянет до четверть-финалов. Но это не главное. ICPFC is where you have fun failing :)

Женя и Ваня, большое спасибо!

Демонстрация

Вот, как работает наше решение: прямая ссылка на видео, так как iframe вставляться не захотел.

Вот наш репозиторий: https://bitbucket.org/jkff/icfp2012

Чуть подробнее про наши алгоритмы: http://antilamer.livejournal.com/438034.html

А вот репозитории других команд (без всякого определенного порядка):

* https://bitbucket.org/gltronred/ncplug-icfpc-2012/
* https://github.com/popiel/icfp-2012
* https://bitbucket.org/xa4a/icfpc12/src
* https://github.com/latticetower/icfp2012_submission
* https://github.com/jld/icfpc12 (Celestial dire badger!)
* https://github.com/leastfixed/icfp2012
* https://github.com/emarhavilicfp/icfp
* http://pastebin.com/JahadZjU (Паскаль!)
* https://bitbucket.org/rmathew/icfpc
* https://github.com/amogil/icfpcontest2012 (Quad-trees!)
* http://re.jabber.ru/~alexey/icfpc-2012/icfpc2012.tar.gz (тот самый aleksey)
* http://www.ugcs.caltech.edu/~stansife/icfp2012/
* https://github.com/fferreira/ICFP2012 (C++ и шаблоны, все решается в compile time!)

А вот как мы коммитили код:

По авторам

По дням

По часам в сутках

А еще я получил свои 5 минут славы :)

(13:25:22) savask: adept: Just in case, aren't you that famous adept which wrote fascinating ICFP diaries? :-P
(13:26:11) adept: savask: the same. why? :)
(13:27:29) savask: adept: Just your ICFP2006 article made me form a team and try current ICFP
(13:27:29) savask: adept: :-P Thanks to your articles, without them I would never try that.
(13:27:46) adept: savask: wow, thanks :)
(13:28:24) ems_: oh, I am curious; how did people here get started with icfpc?
(13:29:10) ilya: adept: the same as savask. thanks
(13:29:31) jsn-: adept, yeah, +1, thank you
(13:30:21) [nofate]: we've read adept's diaries too and started last year )
(13:30:30) mietek: Where can I find those diaries?
(13:30:50) jsn-: mietek, it's all in russian
(13:31:04) mietek: Wsio rawno
(13:31:15) [nofate]: http://users.livejournal.com/_adept_/tag/icfpc
(13:37:09) aliher: +1 for adept's diaries few years ago :)
(13:37:45) snauts: so many people can read adept here

Flat | Top-Level Comments Only

From:

jerom.livejournal.com

Жалко, что не было scoreboard.

Но тебе с такой славой можно совсем ничего не писать. Да, и я тоже узнал о ICFPC отсюда :)

From:

spamsink.livejournal.com

Оно, конечно, cute использовать компилятор C++ в качестве интерпретатора функционального языка с бешеным синтаксисом, но хотелось бы увидеть статистику по языкам среди первой пары дюжин участников в турнирной таблице.

From:

http://users.livejournal.com/_navi_/

Обычно примерно так (в порядке убывания успешности): C++, Ocaml, Haskell, Java, Python, ну и чаще всего команды на смеси языков разные тулы пишут. У нас в этом году как-то так получилось, что только Haskell (плюс совсем мелочи в bash и Makefile).

Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов

Обязательное вступление: что это вообще такое?

Подготовка

Старт и условие

Вечер первого дня - dummy solver

Второй день - ускоряемся!

Народные карты

Трамплины

Комбинируем стратегии

Финишная прямая

Демонстрация

Page Summary

Style Credit

Expand Cut Tags