|
Отчет об ICFP Contest 2008 (updates - see thirteen.kharkov.ru) Харьков, 2008. Tags: kharkov, functional,programming,contest,sannysanoff,Rst7,sas,Харьков,функциональное программирование,haskell. (я понимаю, что дальше речь не о хаскеле и не об ФП, но я по этим словам гуглил команду, и не нашел. А место ведь пусто!).
(Этот текст прокомментирован мною, Rst7/CBSIE, т.к. писать свой отчет было лень, но некоторые моменты хотелось уточнить) Команду начал я собирать за 2 месяца. Было неожиданно, что много хороших людей отказалось принять участие вместе со мной. У одних работа, и они не могут, у других отдых, и они отдыхают. Третьи сказали, что они уже старые, и вовсе сложно им будет решать такие задачи, и что вообще компьютер за много лет уже вот где сидит. (Rst7: Я тоже сначала думал, что моя деятельность давно переместилась из плоскости академической в плоскость прикладную. Однако, поразмыслив, я подумал, что терять мне нечего, и, возможно, мой взгляд на проблему со стороны прикладных вещей будет полезен) Но постепенно собрались два моих старых товарища, Rst7 и SAS. Rst7 любит и уважает компьютеры, а SAS любит и уважает задачи над которыми надо подумать. Затем еще через дальнего знакомого нашелся некоторый человек Souldump, который славился тем, что участвовал в соревнованиях на топкодере. Он привел своего товарища, и стало нас пятеро. Четверо из нас встретились за неделю накануне старта у меня на работе. Были рассмотрены задания по ICFP прошлых годов. Порешали микрозадачки из Google Treasure Hunt. Разработали план заезда, что брать. Поехали посмотрели на место действия — была выбрана новая квартира Surge9, он в нее еще не переехал, но там оставалась некоторая мебель старого хозяина — было просторно и светло. Увидели также, например, что не хватает немного стульев и столов. Где-то в четверг организаторы выложилили Live CD с тестовым environment-ом. Дома я его скачал и запустил под QEMU. Посмотрев, что там в графическом режиме ничего полезного нету, умудрился запустить и под VirtualBox. Исследование показало совершенно бездарно настроенный диск — g++ не находил STL includes, Haskell стоял без network libraries. Так как в комментариях не было намека на то, что используется сеть, а было только то, что программа будет запускаться с параметрами, то мы все предположили, что никаких сокетов. Мы глубоко ошиблись, это просто организаторы оказались такими нехорошими и обидели хаскеллистов. Еще там была Java - много Jav-ы, и еще было 2 варианта ML, а вот LISP не влез. Ну, еще было по мелочам языков. Кроме меня все четверо педалили на С++, один я на Java. Я думал распараллелить работу и как-то разделиться, но оказалось, что программа в результате должна много и хорошо работать, и быть монолитной, поэтому пришлось писать тоже на С++. (Rst7: я вообще к плюсам отрицательно отношусь (обычно пользую Plain C), так что я тоже испытывал некоторый дискомфорт ) В пятницу вечером завезли все компы — вывезли из конторы где я работаю полтора компа. Ноутбук, который я взял для SAS-а, не завелся (no boot record) — то ли что-то с ним стало во время пути (?) то ли я после переинсталляции винды не бутился (бутился). Поэтому в один из рейсов пришлось привезти ему свой домашний компьютер. В это время Rst7 раскладывал сеть, подключал УПС-ы и устанавливал завезенное железо по столам, и много курил. Вечером позвонил Souldump и сказал, что они приедут утром. А задание уже вот-вот должны были дать. Мы сказали, что ну ладно, завтра так завтра. И вот выложили задание. Там написано, что будет эмулятор физического мира, там ездит марсоход и говорит нам по сокету, что видит. Надо им управлять и доехать до базы. Нашей программе приходит информация про круглые кратера, в которые не нужно падать, круглые горы, от которых отскакиваешь, если на них налетаешь, и еще на марсе есть марсиане, которые вокруг бегают и могут скушать. Кратеры видно только в определенном радиусе (эллипсоидной формы зачем-то). А управлять марсоходом нужно командами: влево, сильно влево, вправо, сильно вправо, нажать газ, нажать тормоз. И всё. У марсохода инерция, и инерция вращения тоже. И есть еще формула расчета горизонтальной скорости с квадратом в ней, а формулы расчета скорости вращения нету, и говорят, что надо добыть ее экспериментально. Потом еще дали сервер, на котором мы все тренировались. Сервер работал только под линухом (и еще макосом), чем очень сильно обидел виндузеров. Как только мы прочитали задание, сразу у всех возникла куча идей. Мы сразу стали их друг другу говорить. И такие были наполеоновские планы, что хоть на нобелевскую подавай. Тем не менее, чем ближе к конце забега, тем мы более приземлялись, и очень хорошие и правильные идеи куда-то удалялись, по причине их нереализуемости в указанных рамках времени нашими силами. Потому что думать-то и трепаться - все горазды, а вот собственно педалинг нас уже выставляет простыми кодерами. Поэтому чем ближе к третьему дню, тем больше появлялось четкое понимание, что нужно хотя бы что-то сделать из первой четверти основной части необходимых фич. До полудня следующего дня мы все еще трепались. Надо сказать, что «заземление» посредством педалинга вещь полезная, и всё-таки когда педалишь, то мысли приходят тебе более правильные, чем когда ты еще не начал. И дискуссия в следующие дни ведется уже на более конкретном уровне и больше соответствует нашим возможностям, чем витание в облаках в первые часы с фломастером у доски. Тем не менее, у доски были разработаны несколько основных концепций:
И много еще чего было написано (всего 15 очень важных пунктов), из которых выстрелили только эти, а остальные остались на доске. (Rst7: На самом деле, изначально мы планировали посвятить вечер пятницы исключительно разговорам, потом лечь спать и утром приступить уже к кодингу. Однако, из-за того, что двое участников появились только утром в субботу, пришлось повториться. Хотя, часам к 12 субботы я (предварительно посидев в гугле) внес предложение - "Давайте я реализую сейчас поиск пути", и не встретив возражений, приступил. SAS прокомментировал мое предложение примерно так - "Ты решил сесть и делать хоть что-то?", на что я ответил "Да." Некоторое время разговоры еще разговаривались, а затем все начали педалить...) Наконец, приступили к педалингу. Поставили недостающие VisualC++, и начали кодить. Написали первые строки — общую структуру данных. Дело это было на лаптопе у Souldump-а. Они пришли утром, а теперь было время прикрутить svn к их ноутбуку и залить первый коммит. После того как набросок структуры данных был сделан, нам внезапно было сказано Souldump-ом и его другом, что дальше педалить они будут дома. Они уехали и связь с ними была очень редкой. Впоследствии от Souldump-а мы получили opengl код для отрисовки внутреннего состояния мира, где-то в первой половине вторых суток, а также заглушку для работы без сети, а от его товарища немножко парсенья входных данных через strstream и изменение внутренного состояние, строк 150 общим числом. Позднее я потратил еще пару-тройку часов для того чтобы перевести opengl под линукс, оказалось познавательно. А сначала я приступил к общему фреймворку, пока Rst7 начал делать стратегию, а SAS начал ковыряться с «ногами». Моим ошибочным предположением было, что многие алгоритмы будут проще, если у каждого будет внутренний loop, где они смогут делать что хотят, хранить состояние в локальных переменных итд. Для этого я решил сделать мультитаскинг, да не простой, а кооперативный, в одном потоке с переключением стеков. Я рассчитывал потратить на это несколько часов, чтобы разогнаться, и потратил их! Мультитаск заработал, и был закоммичен в 1700 субботы, что означает на 19 часу соревнований. Всё это время я ждал сетевого парсера от пятого товарища, но от него не было ни слуху ни духу. В 1800, устав от ожидания, я написал слово gethostbyname и еще одно слово socket. Заглянув в наш канал, где мы держали с товарищами связь, я почувствовал сильную необходимость писать дальше на ту же тему. Что и было сделано. Тряхнув стариной, я достал из старого загашника ntohs, select, connect, FD_SET и еще несколько инструментов, и довел дело до void parseLine(char *line). В это время объявился пятый и сообщил, что он собирается начать писать select. Я его срочно затормозил и вручил данный код ему. Отсюда он написал парсилку строк, упомянутую выше, к 23:00, и пропал. Я в это время делал тему градиента. Через градиент планировалось делать тактическую часть марсохода. Для этого писалась специальная функция, которая вычисляла равнодействующую привлекательности в произвольной точке неким образом, и кроме всего прочего обладала экстремумом в том месте, куда надо было идти (путь посчитанный стратегом). Так как в виндозе с графикой (визуализация) совсем туго, особенно на голом С++ (а больше к нему я ничего не знаю, разве что MFC, но нуего), то визуализация происходила в массиве, который потом записывался в формате BMP на диск (включая прикручивание заголовка). Градиент был бы хорошей идеей, если бы SAS согласился написать ноги, которые будут использовать его, а не путевые точки. Но он писал обычные ноги, а написать ноги, работающие с градиентом, я думал как-то чуть позже, налицо ошибка планирования, и градиент в конечном итоге был выкинут. Градиентом я мучался до 2 часов ночи, когда внезапно объявился Souldump и залил GL-ный визуализатор для мира. После этого я переключился на прикручивание визуализатора для сети и прикрутил. В это время Rst7 сделал на Borland C++ Builder инструмент для расчета пути. Он нашел где-то у себя теорию трассировки печатных плат. (Rst7: собственно говоря, идея прокладки пути и идея трассировки плат суть одна фигня, и, тем более, что все время на слуху бессеточные (топологические) трассировщики, то я решил, что для мира, в котором изначально неизвестны параметры объектов, реализовать алгоритм подобного плана будет самое то. Немного погуглив и обнаружив подходящую картинку, описывающую алгоритм, я счел возможным приступить к делу и завершить болтовню ;) ) Там было про разбивку на треугольники и нахождение пути. Rst7 сделал всю структуру и побил на треугольники и находил путь, только он был корявый. Где-то в час ночи он сказал что он замучался, и надо что-то делать, но в то же время был полон идей как улучшить разбивку. Мы посмотрели на его треугольники, и я стал настаивать, что оно побито как-то не очень красиво, треугольники получаются вытянутыми, потому что его реализация при добавлении новой точки всегда делит треугольник на три новых, и так каждый раз, оставляя первоначальные треугольники, которые были вытянутыми, и плодя еще более вытянутые. Потому и путь кривой, а если бы были ровные, то он был бы более красивым. SAS стал рисовать на доске приблизительные картинки, оценивая мои слова. Когда Rst7 ушел спать, а SAS пошел домой, я взялся поделить на треугольники более красиво. Была ночь, и надо было спать, но я полез по инету, и тропинка привела меня к методу Делонэ, он как раз инкрементальный, и ничего пересчитывать много не надо. Еще какое-то время ушло на поиск подходящей реализации на жабе, и вот уже ночь идет вовсю, а я портирую с жабы на STL, не особо веря в успех. Когда закончил перебивать, работало оно с трудом, пришлось вникать в матчасть, и еще ковыряться в сети, покуда я не нашел несколько лаконичных картинок, где неизвестный художник доходчиво нарисовал. Я понял всё! Метод заработал и ввел меня в полную радость. Теперь между марсианскими камнями пролегали edges, а сами камни были nodes. Осталось инвертировать граф, но у Rst7 в структуре были указан сосед для каждой грани произвольного треугольника, и инвертировать граф не понадобилось, он уже поддерживался. Вторым шагом надо было сделать поиск. Снова гугл вывел меня на Википедию , где на псевдокоде был расписан поиск методом A*, самый быстрый и хороший, конечно же. Снова портирование с псевдокода на STL, и к 6 часам утра все заработало. Borland C++ Builder показывал граф, далее юзер тыкал мышой, добавлял нод, далее тыкал другой мышой, находил маршрут. Так юзер тыкал мышой до 8 часов, когда проснулся Rst7 и вышел, почесываясь, и уставился на меня. Я подтвердил, что я сидел всю ночь, и дал тоже потыкать мышой. Rst7 сказал, что я сделал за него самое интересное, и пошел варить себе кофе. Но картинка, которая таки работала и придавала мне своим видом силы педалить всю ночь, взяла свое и мы с Rst7 сели посмотрели код, ознакомились с указанными творениями неизвестного художника, и Rst7 сел прикручивать всё это к сетевым нотификациям, так, чтобы из телеметрии данные попадали прямо в граф. Где-то на этом этапе умерло Borland C++ (Rst7 задолбался выкусывать код #define-ами), и дальнейшее визуальное развитие алгоритма застопорилось (ошибка). Я пошел спать, и проснулся в 14 часов. В это время SAS делал ноги. Выяснилось, что SAS что-то написал, отчего программа падает (access violation). Выяснилось, что в результате переключания стеков и использования longjmp что-то портится. Час или полтора ковыряния в попытках реанимировать идею показали, что longjmp из глубокой вложенности не просто переходит на новое место, а при этом еще честно уничтожает локальные переменные во всем старом стеке. Когда потом входишь, получается беда, а частенько беда и при выходе (не поняли, отчего). Попытались запретить ему это делать посредством хитрых забиваний нулем в jmpbuf (17:45), но оно не замучалось. При мысли о том, что это надо будет портировать на линух, у меня грустнели пальцы. Было принято волевое решение, что для сохранения существующей структуры переведем всё на нативные потоки. Будет сделан один BIG LOCK, и всё будет минимизировать его использование. Что и было сделано (18:21). (Rst7: На самом деле, надо было вынести многозадачку в файл .c и собрать его без всяких плюсов, тогда setjmp и longjmp ничего не знали бы об объектах на стеках, и все бы работало. А, соответственно, в cpp-шном инклуде объявить yield() как extern "C". Но эта мысль пришла уже потом...) В это время Rst7 переключился в помощь SAS-у на ноги — стал вычислять параметры марса, чтобы сделать симуляцию. Надо сказать, что в позже, какой-то момент времени я услышал краем уха, что мы умеем предсказывать наше положение на несколько ходов вперед. SAS даже написал симулятор, который ехал в особом, отдельном мире, и реагировал на команды, которые наш контроллер отправлял официальному симуляционному серверу. Надо сказать, очень неплохо ехал (!!). Я опять поднял вопрос, что надо просчитывать на несколько ходов вперед (используя симуляцию), чтобы правильно ехало. SAS стал настаивать, что дерево вариантов достаточно велико, и что мы замучаемся. Я не остановился, не подумал, как это лучше написать (моя ошибка), и идея была оставлена. А ведь достаточно было просчитать несколько веток (ехать как если бы и ехал, ехать как если поворачиваешь в сторону, ехать как если тормозишь), чтобы хотя бы избежать коллизий с ямами! Посредством симуляции можно было бы ответить, что «все коллизии от незнания» но «существует путь, который избавит нас от них, и путь этот — нажать сейчас влево и тормоз» В это время я занимался разделением глобального лока на 2 мелких лока и вообще уменьшением lock collisions, портированием лока на линукс и твиканием чтобы он позволял рекурсивный заход, как и винда со своей CriticalSection (ушло еще пару часов, включая ознакомление с pthreads). Вообще, я пошел спать, а в 9 утра на третий день залил это все в svn. На третий день написали генератор карт, сгенерили красивую карту с огромным количеством объектов, на ней стала вылетать ошибка, больно похожая на случайное повреждение данных в результате совместного доступа. В результате в третий день я все перевел на однозадачность, поломав везде циклы «while true», что оказалось легче чем я ожидал. Я с радостью убил все локи и оно стало работать не хуже, но только ошибка не прошла 8-(. Это была ошибка в данных, когда у двух смежных треугольников в определенный момент времени указатели не показывают друг на друга. Я не знаю, чем она была вызвана. Rst7 настаивал что это оттого, что мы используем float а не double, а я махал на это рукой. От отчаяния, за несколько часов до окончания я начал переводить весь расчет маршрута на новые рельсы, более оптимизированные и по скорости в том числе. Час я переводил, внутренне страдая от заранее видной бесплодности затеи, потом ко мне подошел благословенный Rst7 и сказал, что перевод на double проблему решил. Я не верил своим глазам, но времени оставалось мало, и слава Аллаху. (15:00) (Rst7: на самом деле, даже double не спасал. Но глобально переделать всю математику на +,-,* с целыми числами я был неготов) Следующей моей задачей было то, что SAS, который делал ноги, сообщил, что, в результате моей однозадачной программы, на нашей большой карте расчет маршрута занимает слишком долго, и его команды поздно приходят на симуляционный сервер. Было предложено вынести считалку в отдельный thread. Чем я и занялся, здравствуйте, закомментированные имплементации локов, закончил около 17:00. В это время Rst7 мучал свою версию ног, довольно простую, приделывая к ней всякие эвристики. Но все равно, никакие эвристики не могли учесть, что в результате смены глобального маршрута, по причине большой скорости робот может залететь в яму. Что он и делает до сего дня. Тем не менее, из комнаты SAS-а доносились матюки вперемешку с обнадеживающими возгласами, и чем дальше, тем больше матюков. А дело было к вечеру. Пора было уже что-то коммитить. Мы взяли из Rst7-шного branch-a код, и стали его оформлять в виде, требуемом для сабмита. Проверили, компилится ли он на LiveCD, он не компилился. Решили выкачать новую версию CD, и она качалась полтора часа. А пока что написали комментарий «у нас всё компилится нормально, а новый CD еще не приехал», и залили. Мы еще не знали, что у некоторых участников были проблемы с сабмитом, но у нас всё залилось нормально (1.2Мб с бинарником). Нервы, тем не менее, уже были порядком напряжены. Остаток времени прошел в твикании эвристик для более правильного проезда. Например, на большой карте асинхронный расчет маршрута притормаживал, и очередную точку марсоход проезжал, а маршрута еще не было. Марсоход продолжал держать на нее направление, и тормозил и возвращался, а потом вдруг от стратега приходил правильный маршрут, и марсоход дергался снова. Было предложено ехать всегда к точке, которая дальше всего от марсохода по вычисленному маршруту, и в то же время видна по прямой линии. Заимплементили, оказалось, что где-то лучше, а где-то хуже: накладываясь на внесенный баг, в результате которого стратегический маршрут был кривоват, новая фича скорее ухудшала результат. Убрали. Потом еще было варьирование данными, используемыми для расчета стратегического маршрута. Большие ямы у нас могли моделироваться круглой цепочкой маленьких, что в первое время давало неплохой результат. Сейчас мы отключили это для достаточно маленьких размеров, и похоже стало получше. Потом еще была идея более правильного сглаживания маршрута. Дело в том, что сейчас найденный маршрут представлял собой путь по очень маленьким треугольникам, от грани к грани. И хотя треугольники были маленькие, все равно получалась по-мелкому изломанная кривая, которую я спрямлял, проверяя каждую пару дуг в маршруте на спрямление, если спрямленная не пересекала препятствие. Я проверял каждую пару: 1+2, 3+4, 5+6, а потом еще раз и еще раз сначала, но существовал другой алгоритм, дававший более плавное решение: спрямлять сначала самые крутые изломы. Я его не успел реализовать. Постепенно приехал диск с версией 1.6, и мы помучали сборку на нем, всё собиралось прямо в кноппиксе, и это радовало. Разница состояла в #include <unistd.h> для выполненения базовых операций, которые на ubuntu отчего-то работали прямо так. Наверняка была другая версия gcc. Когда мы заливали в третий раз, а это было за 10 минут до окончания соревнования, было решено проверить, как оно компилится, и оно откомпилилось. Потом совершенно чудом Rst7 сказал что надо проверить как работает распакованная версия из нашего сабмит-файла, если ее собрать на месте. Собрали, запустили на кноппиксе, а оно не едет, в смысле что марсоход стоит на месте!! А до окончания осталось уже 8 минут. Около 5 минут дикого адреналина, в результате синхронизация SVN, возвращение на Windows компилятор, компиляция, и наконец удалось воспроизвести баг. Дикий поиск по коду, и оказалось, что в результате последнего svn update пришли персональные #ifdef которые обрамляют код для конкретного разработчика. Там стоял #if RST_HERE, а у меня в директории лежал (неверсифицируемый по определению!) #define SAN_HERE, таким образом финально собранный код не содержал в себе Rst7 бродилку. Обратно коммиты из windows в svn, из svn в linux основной development, оттуда упаковка, заливка на кноппикс, распаковка, проверка — РАБОТАЕТ. Срочно отправляемся на сайт, вносим token, оно мучительно долго аплоадит, и в 57 минут файл залит. Начинается релакс. Мы лезем на сайт icfpcontest.org и с ехидством наблюдаем, что сабмит форма доступна еще минут 20 после окончания (спасибо оргам). Читаем почту и видим, что народ меряется письками и выставляет свои scores, которые генерит официальный симулятор. Там же лежат некоторые карты, и если в них нормальная физика, то мы их кое-как проходим, а если ненормальная, то не проходим вовсе. Некто залил карту с 80 марсианами, и они скопом бросаются на тебя и разрывают в куски. Постепенно Rst7 уходит домой, и SAS тоже. На icfpc@conference.jabber.ru происходит разбор полетов: кто-то не залил, у кого-то тормозит расчет, кто-то посчитал дифуры и оно классно ездит. (Rst7: В этом месте вынужден посыпать голову пеплом... Почему я не применил свои знания в области тех же PID-регуляторов, я понять не могу до сих пор. Видимо полное затмение...) Делимся подробностями реализаций. Adept дает линк на свой darcs repository, и народ исследует meeting notes, а я потихоньку листаю ихний haskell implementation, видит око... P.S. 1) Наверняка, если послушать Rst7 и SAS-а, у них истории тоже полны метаний, трагедий и радостей. Но они их фиг напишут. (Rst7: Писать действительно лень, но я нашел в себе силы откаментить этот текст :) ) 2) Адепту респект. 3) VAG, нам тебя ОЧЕНЬ НЕ ХВАТАЛО. О результатах: наша программа ездит как пьяная, но по правильному маршруту в лабиринте, и постепенно выезжает. Это средний результат. Многие не осилили постройку маршрута. У некоторых работает и то и то. Так что результаты средние.
Что не забыть на следующий раз: Отлаживать и писать отдельные алгоритмы отдельно, как было с поиском пути и триангуляцией на Borland C++ Builder вначале. Структуризация кода — на Ц очень тяжело. Например, еще, мелкий кусочек — управлением робота, написать микро-клиент, который содержит в себе хороший и правильный алгоритм, который приходит в заданную точку вовремя. Показать на экране крупным планом. Выучить boost, stl итд. На всякий случай. Беда, что нету джавистов.... Поменьше трепаться вначале, а ровно столько сколько надо чтобы поделиться и начать кодить пока тривиальные версии. Трепаться лучше в середине, когда набиты шишки и разговор идет более конструктивный. Unit tests для критичных кусков — лучше больше чем лучше, но если нету времени, то ничего страшного. Научить пользоваться subversion всех. (Rst7: и заставлять писать вменяемые каменты к комитам, а не "1" или "aaa", как некоторые ;) ) Больше времени на настройку компов. То, что можно сделать потом, делать потом (читать: мультитаск) Доводить свои идеи до людей, даже если они спорят насмерть. Либо они примут, либо ты поймешь ошибку. Не оставлять на потом (его не будет). Если не принимают, то попробовать еще 1 раз, потом забить. Договариваться с новыми людьми о более devoted отношении к делу. Может быть я доросту до понимания, что лучше было бы всё-таки выйти погулять часок по улице (не хотелось). И есть не хотелось. |