Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Categories:

In Soviet Union, the rover moons you! -- отчет о ICFPC'08, часть 1

Несколько дней тому назад закончился ICFPC'08, и, пока свежи воспоминания, я тороплюсь их записать.

Перво-наперво,
Результаты и впечатления

Результаты:
========
* Мы, скорее всего, попадем в верхние 50%. Мы явно не победим, и даже не приблизимся к десятке
* Мы получили фан
* Я получил кучу (без)полезных сведений о том, как осуществляется управление технологическими процессами, роботами и т.п.
* Я получил удовольствие от игры в замечательной русскоязычной команде

Что понравилось:
===========
* Мы начали готовится загодя, и со стартом соревнования почти не тормозили
* Мы старались по максиму использовать выбранные технические средства
* У нас было очень немного проблем с коммуникациями

Что не понравилось:
=============
* Задание и провтыки организаторов (хотя лично нас они и не коснулись)
* То, насколько сильно я забыл физику и тригонометрию
* То, что мы в какой-то момент все-таки попали в творческий кризис и разброд и шатание

А теперь - детали и подробности.

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

В этом году примерно за месяц до ICFPC я начал совершать какие-то телодвижения в этом направлении, в результате чего на просторах jabber-конференций образовалось некое количество народу, которое было бы не против организоваться в одну команду. Мы даже успели позубоскалить по поводу того, что нас, мол, уже 9 человек желающих и 3 определяющихся, и еще чуть-чуть -- и мы будем давить если не умением, так числом. Но тут организаторы объявили правила, в которых было указано, что в этом году размер команды ограничен 5-ю участниками.

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

В результате я в этом году я участвовал в 100% русскоязычной команде, в которой было целых три Дмитрия (включая меня):
* Dmitry Astapov (_adept_)
* Dimitri Timofeev (dtim)
* Dmitry Antonyuk (lomeo)
* Gleb Alexeyev (palm_mute)
* alar (nealar), оставшийся инкогнито :)

Благодаря тому, что готовится мы начали загодя, к моменту начала соревнования у нас уже были настроены и проверены средства коммуникации и совместной работы:
* darcs-репозиторий (для хранения исходников)
* gobby-сервер (для совместного редактирования текстов)
* приватная jabber-конференция (общий чат)
* skype (для голосового общения)
* бот, оповещающий в чате о новых коммитах в центральный репозиторий

Мы даже сделали вид, что тренируемся, и часть из нас по отдельности порешала по одной задачке из прошлогоднего Google Code Jam :)

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

Старт! День первый, 11 июля
Участники нашей команды находились в соседних временных зонах и в пересчете на наше время соревнование начиналось в 22:00/23:00. Мы предполагали, что в первый вечер мы просто прочитаем задачу, обсудим подходы к реализации и разойдемся спать, чтобы с утра со свежими силами ринуться в атаку.

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

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

Сам LiveCD появился за день до начала. Еще до его появления в официальном списке рассылки неоднократно спрашивали: "правда, вы выложите его с помощью bittorrent?", на что организаторы отвечали: "не извольте волноваться, у нас такой канал - всем каналам канал. Хватит на всех желающих". Естественно, что через 20 минут после появления письма с ссылкой на LiveCD их канал забили под завязку ... Поняв, что спасение утопающих - дело рук самих утопающих, кто-то из участников, успевших выкачать LiveCD до начала давки и толчеи, сделал bittorrent, которым активно пользовались все желающие. На этом злоключения с LiveCD не закончились, а только начались - очень быстро выяснилось, что часть софта, находящегося на LiveCD, не работоспособна без приложения напильника. В частности, находящиеся на нем реализации Scheme (mzscheme) и C++ (g++) - "из коробки" не работают (не находят какие-то файлы), а для Haskell не положили никаких библиотек, кроме тех, что идут вместе с компилятором (этот факт еще сыграет свою роковую роль позже). Забегая вперед, скажу, что организаторы еще несколько раз обновляли LiveCD, и последняя версия, если мне не изменяет память, имела номер 1.5 ...

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

Впрочем, вернемся к заданию

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

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

Поворот ручки приводит к тому, что марсоход начинает разгоняться (тормозить, поворачивать) с каким-то определенным, нам неизвестным, ускорением. Кроме того, на марсоход действует сила трения (с неизвестным коэффициентом), а его линейная и угловая скорости ограничены сверху известными нам значениям. (полностью текст задания доступен по адресу http://smlnj.org/icfp08-contest/task.html).

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

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

Лирическое отступление второе, про задание и организацию
Если внимательно просмотреть задания ICFPC начиная с самого первого 1998-го года, можно увидеть, что задания с "управлением роботами" попадаются на соревновании достаточно часто. В 1998-м году роботы играли друг против друга в "N в ряд", в 2002-м -- роботы играли друг против друга в Socoban, в 2003-м -- участники контролировали гоночную машину на трассе, стараясь привести ее к финишу за минимальное время. В 2005-м году задача заключалась в написании "кибер-вора" и "кибер-полицейского", которые противостояли друг другу в маленьком городке с большим количеством банков.

У всех этих заданий были некие общие черты:
* участники писали и подавали в качестве результатов своей работы некий программный код на произвольном языке (а не, скажем, результаты его работы, как это было в 2004-м году), и, соответственно, должны были подстраиваться под специфицированный организаторами runtime environment.
* оценка решений проводилась по качественным (не количественным) критериям вида "ваши реализации будут соревноваться друг с другом, и победитель будет определяться так: ....". Соответственно, в процессе разработки у участника нет четкого критерия проверки того, насколько успешна его программа.
* для оценки решения требовалось какое-то (возможно, существенное) время, поэтому результаты не были доступны сразу после окончания соревнования. Более того, они обычно не были доступны и через неделю, и даже через месяц. Победителей обычно объявляли на конференции ICFP, которая традиционно проводится в сентябре, а до этого времени все участники изводили себя ожиданием.

Потом пришел 2006-ой год и памятный ICFPC с задание про Cult Of Bound Variable. В том году все было по-другому. Интерактивный scoreboard, который сразу показывал все результаты (ну, почти все - за час до окончания соревнования обновления результатов отключались). Программы на псевдо-языках, которые не надо было компилировать в бинарник (такое было и раньше, но нечасто). Много мелких задач вместо одной большой (такого раньше не было никогда). Разноплановые задачи, которые, в основном, сводились к алгоритмике и творческому программированию.

Соревнование 2006-го года было настоящим прорывом, и еще тогда многие справедливо замечали, что теперь любое следующее ICFPC будут сравнивать именно с 2006-м годом. Именно так все и произошло. Уже следующий 2007-й год ругали за отсутствие множества разноплановых задач, а интерактивную доску с результатами, предоставленную организаторами, уже воспринимали, как само собой разумеющееся.

Вы уже поняли, к чему я веду, да? Организаторов 2008-го года, решивших сделать соревнование в стиле "back to basics" (сравните, например, стиль страниц http://web.cecs.pdx.edu/%7Esheard/2002IcfpContest/task.html и http://smlnj.org/icfp08-contest/task.html) совершенно ожидаемо облили грязью. Во-первых, scoreboard-а нет. Во-вторых, результата ждать аж до сентября. В третьих, бинарник под Linux им подавай, или исходники, которые соберутся в условиях LiveCD. Ну, и так далее ... Если поискать в интернете отзывы о ICFPC'08, то легко убедиться, что ооочень редкий автор не пнул организаторов по этому поводу.

Я, как видите, не исключение :) Ну, организаторов пнули - можно возвращаться к заданию

Задание (продолжение)

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

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

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

Meeting 1, 23:00 EEST
... но нам эта задача казалась достаточно простой. По крайней мере, на первом общем сборе мы уделили физике достаточно мало внимания. Глеб вскользь упомянул ПИД-регулятор (о котором тогда, кажется, кроме него вообще никто раньше не слышал), и мы сразу принялись обсуждать детали реализации и разделение задач.

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

В результате мы сошлись на таком разделении:
0)сообща в gobby: общие типы данных (карта, команды сервера и клиента)
1)adept: Парсинг протокола
2)dtim: Структуры данных для хранения карты, какие-то средства их обновления
3)lomeo: Визуализация карты (структуры данных)
4)adept: Билдовая система для быстрой пересборки проекта
5)gleb:Двухстрочная логика ровера, плюющаяся одной командной, затем - более сложное управление.

Вписаный мною в начала совещания вопрос:"Надо ли делать research в сети по поводу физики/формул, используемых при решении подобных задач?" собрал два противоположных ответа (к сожалению, уже не помню, чьих): "надо обязательно" и "не надо, физика тут игрушечная".

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

Линк на продолжение.
Tags: icfpc
Subscribe

Recent Posts from This Journal

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 6 comments