Пользователь
0,0
рейтинг
15 июля 2008 в 14:20

Разное → ICFPC-2008: первые впечатления

Введение


Есть такой ежегодный программерский конкурс, ICFP Contest — то есть, International Conference on Functional Programming Contest. Конкурс довольно известный, в русскоязычной среде популяризованный отчетами Адепта, так что я очень кратенько изложу его основные принципы.

Конкурс проходит раз в год, игра командная, задания выдаются на сайте конкурса, решения присылаются туда же. Игра идет трое суток, можно прожить их нон-стопом, можно спать и есть, как все нормальные люди. :) Есть так же так называемый lightning round, то есть отдельное призовое место среди решений, присланных в первые сутки игры.

Задания в выгодную сторону отличаются от классических олимпиадных задачек. В 2006м и 2007м годах это были чудесные квесты от программирования, с написанием собственных компиляторов эзотерических языков под эзотерические виртуальные машины; до того, и в этом году, программирование логики поведения объекта в некотором виртуальном мире.

Этот год


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

На марсе есть валуны, от которых ровер отскакивает, теряет скорость и меняет направление движения, есть кратеры, в которые ровер проваливается насмерть, и есть марсиане, с физикой как у ровера, только чуть мельче размером, которые мечтают принести ровер в жертву Богам Барсума (это отсылка к циклу фантастических рассказов о Марсе писателя Эдгара Берроуза). Что они собственно и делают, если догоняют ровер. Ровер высаживают в произвольной точке поверхности карты, задача — добраться на базу, в координаты (0,0). Ровер видит только то, что попадает в его область зрения, которая собой представляет эллипс, в одном из фокусов которого находится ровер.

Информация о том, что видит ровер, поступает в виде пакетов телеметрии примерно раз в 100 миллисекунд.

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

Вот, наверное, и все.

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

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

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

Общее про организацию


Мнения по поводу всего, происходившего в этом году в ICFPC, очень сильно варьируются. Например, подавляющее большинство людей, которые принимали участие в соревнованиях предыдущих лет, почти сразу после опубликования задания высказались о нем резко отрицательно. Мол, раньше было лучше. Я же о подобной задачке мечтал уже давно, поэтому занудствовать не стал. Да и история показывает, что подобные задачи тоже вполне характерны для ICFPC. В общем, мне кажется, высказываться так, это все равно что твердить «а книга была лучше фильма», не понимая принципиальной несравниваемости этих двух видов изложения сюжета.

Но я хотел сказать об организации. Так вот, я видел положительные отзывы. Но мне работа организаторов показалась неудовлетворительной. LiveCD, на котором предполагалось запускать сервер с иксовыми гуями, изначально не стартовал иксов, и потребовалось добавить в официальный FAQ инструкции по настройке. Сам сервер дописывался организаторами прямо по ходу дела, было внесено много багфиксов, хотя по официальным данным, конкурс подготавливался с января — можно было бы успеть написать нормальную реализацию. Например, наша команда собственную простую версию тестового сервера накидала в первые же сутки.

Более того, сам сервер был выложен далеко не сразу после начала контеста. А его статически слинкованная версия для других дистрибутивов Linux и для MacOS X — и вовсе с запозданием в сутки или около того. Так и не появилось версии для Windows, что для как минимум одного члена нашей команды стало фатальным — его машина не тянула виртуалку, как, скажем, моя, и он выбыл из соревнования, поскольку не особо мог тестировать собственный код.

В результате многие команды потратили первые сутки, «играя в линуксовых администраторов», вместо игры в программистов.

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

Собственно игра


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

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

Первые сутки


Первую ночь (ну, это по моему GMT+6 времени) мы потратили на войну с LiveCD и реализацию протокола взаимодействия. В этом месте питон показал всю красоту динамической типизации — когда шаблоны, описывающие парсер протокола, заодно задают и поля классов объектов и событий, это песня! :) Которую, правда, мы переписали в более конвенциальном стиле где-то на исходе вторых суток игры.

Примерно через 10 часов после старта была реализована первая версия Cerebellum («мозжечок») — низкоуровневого контроллера ровера, который принимал в себя команду вроде moveTo(x,y) и уже сам транслировал это в команды поворота и ускорения в протоколе. Примерно тогда же Влад — человек, собственно написавший и Cerebellum, и реализацию протокола — вкоммитил еще и визуализатор происходящего на стороне клиента, написанный с помощью GLUT — питонового апи для OpenGL. Это очень помогло в последствии, так как мы получили возможность всякие промежуточные данные отображать там же на карте и ориентироваться в происходящем. Скажу сильнее — без такого визуализатора отладка логики была бы несоизмеримо более сложной.

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

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

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

В результате мы имели ровер, который на старте разворачивался и по прямой пилил к базе — и все это чисто на уровне мозжечка, «на рефлексах». Ребята в это время занимались модулем сбора статистики — данных о реальной latency, и вычислении на основе данных о latency и телеметрии коэффициентов ускорения и трения. Поэтому я сел и накидал решение выбора пути, которое собственно и осталось в последствии нашим мейнстримом — решение простое, как тапок.

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

Ровер на моем алгоритме навигации успешно справлялся с простыми картами, но уже на spiral (для тех, кто в теме ;)) ему сносило крышу и он справлялся максимум 1 раз из 5. Первый же простой хак улучшил этот показатель до 3 из 5ти.

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

Вторые сутки


Вторые сутки мы, как оказалось позже, просто потеряли. Я ждал, пока ребята реализуют более качественный, учитывающий обстановку вокруг, moveTo, который бы например делал более аккуратные развороты, когда вокруг много препятствий; ребята писали вычислялку неизвестных параметров; Влад собирался сделать систему оптимального, то есть наиболее быстрого и точного, прохождения набора вейпойнтов. Еще нам в копилку добавился алгоритм перемещения «пьяный ровер, возвращающийся домой», который вполне сносно себя вел.

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

Третьи сутки


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

Точнее, сначала я потратил прилично времени на написание логики обработки цепочки кратеров и нахождения крайнего вейпойнта, объезжающего всю их кучу, но этот код так и не заработал как следует. Уже в последние 3-4 часа контеста я понял, что так и не отлажу этот код, и нашел еще один хак для алгоритма, который позволил улучшить результаты до 3 из 5 на этой адской карте. Затем ребятам в голову пришла отличная в своей простоте и гениальности идея — сохраняя кратер в карту, преувеличивать его размер на метр. Это заработало!

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

Еще в общем


В общем, написать какое-то решение для какого-то более-менее вменяемого объезда препятствий не сложно. Я уверен, что реально вопрос о победителе будет решаться в мелочах. Система очков устроена так, что даже одно падение в кратер, одна, пусть и очень маловероятная, встреча с марсианином могут отделять победителей от тех, кто отсеется на карте. Среди же тех, кто научился избегать этих неприятностей со 100%ным результатом, решать все будет скорость прохода трассы. Это и максимально допустимые скорости прохода траектории, и построение кратчайшего, а не просто удовлетворительного пути. Мне очень интересно будет посмотреть на действия и код победителя.

Ах, да, питон больше — никогда. К черту эту динамическую типизацию, которая не выявляет до рантайма даже опечатки. В следующем году буду писать все на Scala — статическая типизация, компилируемость, производительность как у Java, а мощность и выразительность как и бешеной помеси питона с хаскелем.

Обратная связь


Сейчас я собираю отчеты разных команд о том, как это было.

Судя по разным записям в блогах, наше простое решение может оказаться не таким уж и плохим. Вот ребята не успели отправить свое решение, несмотря на активную работу. Я до сих пор благодарен человеку из нашей команды, организовавшему отправку предварительной версии нашего кода. Другие вроде начали, но не понятно, довели ли дело до конца. Провалилась и попытка другой команды использовать Haskell, и они дописали свое предварительное lightning решение на Perl-e. Там как раз наоборот, автор считает тривиальные хаки по месту, как в моем коде или в их перловом решении, злом и собирается реализовать таки красивое обобщенное решение. Еще одна команда, выбравшая простое решение, тоже не очень печалится по этому поводу. :)

С другой стороны, есть сильное решение от ребят на Scheme. Хотя результаты тестовых прогонов, которые они опубликовали, у нас вроде бы и получше, но они успели в последние два часа реализовать очень важную идею, до реализации которой у меня так и не дошли руки — стек стратегий. Я, правда, предполагал реализовывать ее как команды разного приоритета — стратегического, тактического и маневрового — мозжечку ровера.
Ребятам из Харькова на С++ удалось все. И универсальный умный алгоритм, и отдебажиться, и отправить решение в последние минуты.
Кто-то участвовал просто для интереса.
На данный момент еще не опубликовал свой отчет Адепт.

Если у вас есть ссылки на отчеты, не упомянутые здесь — пишите, пожалуйста, я буду добавлять их в список.

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

UPD: создал под эту тему блог и перенес пост туда.

Напоследок


«На сладкое» — адреналин последних десяти минут контеста.
Евгений @EaE
карма
15,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разное

Комментарии (48)

  • +1
    Классно. И написали хорошо. А задача, кто бы там что не говорил, довольно интересная. ждем Адепта, у него тоже всегда хорошо описать получалось:)
    • 0
      Да, мне самому очень интересно, что же у них получилось и как оно было :)
  • 0
    Почаще бы, да побольше таких мероприятий=)

    Участвовал в одиночку, для эмуляции линя и запуска сервера использовал AndLinux для винды...
    Забил на это дело после первой же ночи, но успел реализовать разворот в сторону базы и прямое движение...дальше стало лень...скууучно ;-)
    • +1
      Там же как раз начинается самое интересное после этого! :)
      • –3
        скууууучнооо...
  • 0
    Мне очень понравилась органичность, с которой самоорганизовались задачи и работа в команде.


    "На сладкое" — адреналин последних десяти минут контеста:
    1:50:57 fj.mail: вот вы мудаки что ли
    1:50:58 irusskih: их не тестил никто

    =)

    А в целом молодцы что за такое время реализовали рабочее решение столь интересной задачи. Это неоценимый опыт и новые знания. Насчет хаков тоже интересно было почитать, спасибо за статью!
    • 0
      Вам спасибо, что прочитали :)
  • 0
    отлично написано. я прямо проникся обстановкой :)
    есть скриншоты? :)
    • 0
      Ох... надо было сделать, но как-то не до того было, а сейчас уже поздно. Я спрошу у команды, вдруг у кого-нибудь остались или скриншоты или система настроенная, чтобы их отщелкать.
  • 0
    Извините, за неграмотность, но где я могу почитать официальную информацию о ICFPC? Ссылку или что то подобное....
    Или я слепой или не могу найти.
    • 0
      Я спрятал ее в самом низу топика :) Вам на http://icfpcontest.org/. А ссылку сейчас добавлю сверху, спасибо за замечание.
    • 0
      • +1
        Опоздал .)
  • 0
    Захватывающие мероприятие, жаль что о нем узнал уже после его окончания.

    Было бы хорошо знать о грядущих событиях такого плана зарание :)
    Буду признателен за информацию о подобных конкурсах
  • 0
    Удачи вам!
    • 0
      Спасибо, она нам пригодится. :)
  • 0
    Здорово. Зачет организаторам за задачки.

    Сам я не участвовал, но читал описание прошлогоднего соревнования. Там мне задачки показались интереснее.. (упакованная виртуальная машина).

    Плюс )))
    • 0
      Виртуальная машина, кажется, была в 2006м. Я впервые услышал сейчас, бросился читать отчеты, безумно интересно. Хотелось бы поучаствовать как-нибудь.

      P.S. Молодцы!
      • 0
        упс... это уже 2 года назад было???????? Чёрт, как быстро время летит...
    • 0
      Через чуть больше суток начинается Google Code Jam квалификационный раунд... вот там я думаю поучаствовать :)
  • 0
    Вот мой комрад участвовал, его отчёт http://grep-z.livejournal.com/55979.html
    А вообще спасибо за статью, исчерпывающе. Надеюсь к следующиму году подниму свой левел и тоже подключюсь. Где кстати можно собраться в команду?
    • 0
      Спасибо за ссылку!
      А в команду... да где угодно. Мы вот собрались просто друзьями. Адепт, опять же, набирал людей в команду задолго до начала контеста. В общем, тут каких-то особых технологий нет :)
      • 0
        На следующий год так и поступлю, попробую знакомых сорганизовать. Очень уж это всё увлекательно. Чуть было на работу не забил. :)
        Пока приступал к контесту, подумалось, что гораздо проще было бы выести систему координат отличную от декартовой, где априори забиты такие понятия как b, c, m и h и легче учитывать углы(подобно полярной системе координат), но с ходу вывести не удалось.
        Потом перешёл в систему действующих зарядов, то есть расписывая силы от объектов к роверу, вот оказывается харьковчане почти также поступили. :)
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      спасибо, добавил :)
  • +1
    Немножко забавных картинок про решение задачи
    http://nicity.livejournal.com
    • +1
      Использовалась Джава, алгоритм Дейкстры нахождения кратчайшего пути в графе. Последний удалось сделать неквадратичным от числа вершин только спустя полчаса после окончания :(
      Драйвер ездит хорошо пока наш драйвер успевает сдалать отчёт за ~ 100 миллисекунд
  • 0
    Мы на Ruby писали, алгоритм поиска сделали в виде модуля к Ruby на Си. Катался довольно таки прилично, на спирали не врезался, не врезался и на куда более сложных картах, но на простых ездил достаточно медленно, а на сложных шустренько (см small-08 в мейллисте).
    • 0
      подробнее. отчет! :)
  • 0
    Интересно было почитать!
  • +1
    Если интересно, с удовольствием опубликую на хабре отчет нашей команды (ryba, 4 место ICFP 2007). Будет готов сегодня-завтра.
    • 0
      Конечно интересно, напишите, пожалуйста.
      • 0
        Отчет будет готов завтра. Это первая публикация здесь, надеюсь все получится %)
        • +1
          Да чего там писать, четверо небритых мужиков носятся с безумными глазами и ищут у друг друга ошибки, закусывая на ходу едой из Мака =)) Я потом альтернативный вариант выложу =)) Как говорится, со стороны =))
        • 0
          дело движется медленно, пока есть видео http://www.youtube.com/watch?v=Ee3Bnhm2e…
  • 0
    Действовать полным составом мы начали 12-го в 10:00 GMT, вариант "пьяный ровер невзирая ни на что несется к базе" был написан за 2 часа на перле. В lightning мы попали именно с этим вариантом. Оставшееся время реализовывали различные алгоритмы, каждый свою мысль, иногда черпая идеи друг у друга. Надеюсь, что последним засабмитили достаточно хороший вариант :)
  • 0
    Задание показалось похожим на типичные для Marathon Matches на TopCoder'e. Безусловно, это не делает его не интересным. Просто, по подобным отзывам за прошлые годы, у меня сложилось впечатление, что задания на ICFPC несколько иного рода :)
    • 0
      Квестовые задания, которые сейчас с легкой руки Адепта считаются "классическими для ICPFC" имели место быть в 2006м и 2007м годах. До этого четыре года программировали роботов. Хотя я и сам бы не отказался поиграть в квесты. :)
      • 0
        Спасибо, за разъяснение. Действительно, мое впечатление складывалось по обзорам 2006 и 2007 года, поэтому оно получилось таким однобоким :)
  • 0
    Спасибо. Очень интересно. Был бы рад увидеть пост о всех известных подобных и не подобных соревнованиях по программированию (когда, где, какие условия, сроки, ...) ;))
  • 0
    Горужсь Харьковом!
  • 0
    Интересно написали.
    Мы тоже решили попытать силы в количестве четырех человек, но плохо подготовились, закопались в мелочах и в результате все, что выложили - незамысловатый перловый скрипт, который в кратеры не падал, но и только.
    А вот с марсианами на самом деле непонятно - организаторы писали, что сервер, используемый для проверки результатов, необязательно будет идентичен тестовому, и марсиане могут стать значительно умнее.
  • 0
    Большое спасибо за статью!
  • 0
    Как команда то называется?
  • 0
    Отчет от _adept_: http://users.livejournal.com/_adept_/84592.html (начало)
  • 0
  • 0
    Отчет от team ryba
    neuro159.habrahabr.ru/blog/29137/

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