dastapov: (Default)
[personal profile] dastapov
Несколько дней тому назад закончился ICFPC'08, и, пока свежи воспоминания, я тороплюсь их записать.

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

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

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

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

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

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

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

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

В результате я в этом году я участвовал в 100% русскоязычной команде, в которой было целых три Дмитрия (включая меня):
* Dmitry Astapov ([livejournal.com profile] _adept_)
* Dimitri Timofeev ([livejournal.com profile] dtim)
* Dmitry Antonyuk ([livejournal.com profile] lomeo)
* Gleb Alexeyev ([livejournal.com profile] palm_mute)
* alar ([livejournal.com profile] 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 в сети по поводу физики/формул, используемых при решении подобных задач?" собрал два противоположных ответа (к сожалению, уже не помню, чьих): "надо обязательно" и "не надо, физика тут игрушечная".

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

Линк на продолжение.
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

dastapov: (Default)
Dmitry Astapov

April 2017

M T W T F S S
     12
3 45 6789
10111213141516
17181920212223
24252627282930

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags