вторник, 17 июля 2012 г.

ICFPC-2012: отчёт

О том, что такое ICFPC - см. пост от 2009 года.

TL;DR: https://bitbucket.org/xa4a/icfpc12/src (python)

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


По сложившейся традиции, ещё до начала самого контеста, организаторы выдали некоторые намёки (как оказалось в последствии) на суть задания: упоминались холмы (из категории breast-shaped hills) с шахтами, проливные дожди, летающие по улицам батуты.



День первый: пятница,  13-е


~13:00: Заправившись обедом, залогинившись в соответствуюшие #icfp-contest на irc.freenode.net и icfpc@conference.jabber.ru, ожидаю задание.
13:00 с промежутком в несколько секунд в разных уголках мира становится доступным задание.

В этом году задание начинается с предыстории, повествующей о нелёгкой судьбе шахтёров из Шотландии, которые, не покладая рук, день и ночь работают на шахтах под упомянутыми холмами, чтобы обеспечить мировые потребности в лямбдах (λ). Тем не менее, не смотря на все их старания, прогнозы говорят, что запасов хватит лишь до октября этого года, а значит функциональное программирование в опасности! 
Участникам предлагается заменить малопроизводительных шахтёров на настоящих железных роботов, а именно – написать управляющее ПО для этих роботов.


При более детальном рассмотрении, оказывается, что от нас всего лишь хотят получить бота для игры, аналогичной Boulderdash. На первый взгляд, задание, соответствующее больше Google AI Challenge. Там же в задании сразу обещают до четырёх измений/дополнений к заданию в процессе контеста. Примечательно, что в этом году задание было довольно четкое и содержало всего одну ошибку, которую, после замечания в irc, быстро исправили (порядок обработки условий конца игры). 


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




#######
#..***#
#..\\\#
#...**#
#.*.*\#
LR....#
#######

где # - стены, \ - лямбды, R - управляемый персонаж, L - закрытый выход, открывающийся после сбора всех лямбд, * - толкаемые/падающие/расплющивающие робота камни. Цель робота: собрать все лямбды и выйти через открывшуюся дверь лифта, при этом не быть раздавленным камнями. Цель участника - для заданной карты сгенерировать последовательность команд (Up/Right/Left/Down) для прохождения этой карты. Задание понятно, как и то, что начинать надо с симулятора/реализации игрового движка, на котором собственно решения можно будет проверять и оценивать. 

16:04 Закомичена первая работающая версия симулятора, умеющая по заданной карте и последовательности команд считать и рисовать результат, а в 16:34 симулятор уже вполне правильно работает и даже считает очки.

16:59 Симулятор в репозитории умеет вывполнять программы пошагово.

С готовым симулятором стало можно приступать к реализации накопившихся мыслей по поводу решения. Первой итерацией было решено делать простой А*, искавший лямбды, а если их нет – выход, и ходивший по всем доступным ячейкам. С самого начала я не стремился сильно оптимизировать работу решателя + учитывать изменения карты по ходу А* не хотелось, поэтому путь до ближайшей цели пересчитывался на каждом шагу, симулировался первый шаг этого пути и снова искался путь. Это повторялось, пока поиск не заводил робота в тупик (избежать попадания под камни удалось довольно просто, приравняв ячейки приводящие к этому к стенам). 

19:34 Simple solver, that works – решатель решает, и даже доходит некоторые карты до конца!



19:44 Объявлено первое дополнение к заданию: из-за ливней шахты может со временем заливать водой, а робот не особо водоустойчивый – может находиться под водой не больше некоторого заданного количества времени подряд. 
После этого в первый день меня хватило только на исправление нескольких багов, а обработку воды перенёс на субботу.

День второй: суббота

К 13:15 был готов комит с говорящим сообщением "lala", который добавлял обработку воды в симулятор, а так же решатель на уровне "если утонули - отменить последний ход и вернуть результат". Думаю, этот код попал в lightning submission и, возможно, не совсем меня опозорит.

тут справа виден уровень воды

14:39 Усовершенствования А*, в частности метод подсчёта стоимости переходов: вместо статических очков каждой ячейки в карте, каждый переход оценивается в зависимости от направления, то есть камни с некоторых сторон толкать нельзя -> стомость перехода как на стену, а с других можно - входить дешевле.

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

Наблюдения за ботом показали, что часто, следуя по А*, он блокирует себя камнями и сдаётся. Примечательно, что блокирует он себя за последних несколько ходов. Решение? Если застряли – откатить несколько ходов назад и попробовать вместо "оптимального" А* рандомно перебрать возможные исходы и посмотреть, не застрянем ли в каком-то из них. Идея оказалась довольно действенной, хоть и была доведена до ума только к концу третьего дня.

17:33 Объявлено второе дополнение к заданию: на картах могут присутствовать одноразовые трамплины-телепорты.

Конец субботы. 
А, нет, ещё не конец: в 22:47 новое дополнение к задаию: посреди шахт бывает растёт борода (W), которую можно (и нужно) брить бритвами (!). С мыслью о предстоящем сновидении бороды иду спать.

День третий: воскресенье

11:01 Простое изменение в скоринге карты для А*: путь через бритву стоит 1, через землю – 3 и робот непроизвольно собирает бритвы, встречающиеся по пути.
11:49 Если путь упирается в бороду – стричь!





12:30 Новое дополнение к заданию: кроме обычных камней и обычных лямбд, добавлены яйцекамни (@), которые являются камнями, пока не разбиты, а потом становятся лямбдами, которые тоже надо собирать.

Тут уже нужно было активнее толкать камни, а значит искать к ним подход. Стало понятно, что изначальный метод описания того, как подойти к камню, чтобы толкнуть, вышел слишком избыточным, и нужно было что-то проще. 
В 14:05 Ответом стал метод поиска целей на карте паттерн-матчингом, например:

    targets = find_cells(map, '\\')

    # break horocks
    # dig under
    pattern = ["@",
               "."][::-1]
    targets += find_pattern(pattern, [0,0], map)

    # dig to the down-right
    pattern = ["@ ",
               "r."][::-1]
    mapping = {'r': 'R*@\\'}
    targets += find_pattern(pattern, [0,1], map, mapping)


То есть цели задаются паттерном, который ищется на карте и координатами в этом паттерне. Это позволило сократить кучи кода для описания возможных ситуаций и, собственно, описать побольше этих ситуаций. Ещё немного рефакторинга и в 14:33:

если не осталось лямбд, подходим к толкаемым камням:

if not targets:
        pattern = [" @e",
                   "-w-"][::-1]
        mapping = {'w': '#W',
                   'e': ' .'}
        targets += find_pattern(pattern, [1,2], map, mapping)


и толкаем: 

        pattern = [" @R",
                   "-w-"][::-1]
        mapping = {'w': '#W'}
        targets += find_pattern(pattern, [1,1], map, mapping)


14:57 Целям были добавлены приоритеты так, что до подкапывания камней доходило только если больше делать ничего не оставалось.
19:55 Закомичено последнее существенное изменение кода: доведён до ума брутфорсер окончания маршрута + добавлен оптимизатор готового пути, обрезающий ненужные ходы из середины и с конца программы. 
21:18 Исправлены мелкие баги + решение ускорено в ~два раза путём простого:


- #!/usr/bin/env python

+ #!/usr/bin/env pypy

Немного потренировался упаковывать решение для сабмита и пошёл спать.

День последний: понедельник

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

Что было хорошо:
  1. Это было, как обычно, увлекательно!
  2. Организаторы хорошо постарались с заданием, его описанием и оранизацией. Хорошо отвечали на вопросы в irc, избежали проблем с лежащими серверами.
  3. С удовольствием просидел три дня и, думаю, получил неплохой резльтат. 
Что могло бы быть лучше:
  1. Если кто-то рядом тоже пишет, то это придаёт мотивации, не говоря о том, что кодить в четыре руки быстрее.
  2. Не хватало онлайн скорборды, духа соревнования.
Вот так.

UPD: поднял неофициальную скорборду для всех желающих. Присоединяйтесь.

1 комментарий:

  1. Ну круто же! Жаль, что не смог даже попробовать себя. Хотя, сомневаюсь, что чем-то смог бы быть полезным >_<

    ОтветитьУдалить