psi_storm (psi_storm) wrote,
psi_storm
psi_storm

ICFP 2008 или как я провёл выходные

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

Задание 2008 года было про марсоход, который должен доехать до базы из разных точек карты. По пути ему встречаются кратеры, валуны и марсиане. Марсиане стремятся познакомится поближе. Всё круглое, включая марсоход и препятствия строго рекомендуется объезжать, ибо об них можно умереть. Марсоход оборудован комфортабельным джойстиком который можно давить во все четыре стороны, и приборами (по которым идут), сообщающими раз в 100 миллисекунд ситуацию с текущей скоростью и препятствиями вокруг. Общение с Марсом происходит через TCP поверх гиперпространственной связи. Чем быстрее и живее доедешь до финиша тем лучше.



В команде cw образца 2008 года в сухом остатке набралось 2 человека: я и Дима. Причём Дима был на отдыхе с семьёй и строго дозированным интернетом, а я имел планы на вечер и ночь субботы. SVN мы не подняли, канал на IRC не завели и даже не решили на чём будем писать в надежде что работу можно будет разделить на независимые куски. С такой вот вводной мы начали читать задание вечером в пятницу.

Собственно задание меня разочаровало - я рассчитывал на кусок программно-активных данных, которые придётся увлечённо препарировать (как это было в последние 2 года), а вместо этого получил турнир роботов. Но команда была уже собрана и отступать было некуда.

Очень быстро выяснилось что сразу приступить к решению задачи не получится, потому что тестовый сервер в начале контеста был недоступен. А когда его выложили через 3 часа, то оказалось что его нужно запускать в очень конкретной среде - LiveCD. Образ полагалось скачать (650 мегабайт) и загрузится с него или шаманить с виртуальной машиной (VMWare 300 мегабайт, или VirtualPC на котором не работала графика). Обещали выложить версии сервера под другие системы. В ожидании сервера мы решили что Дима будет писать визуализатор на Джаве, а я попробую писать мозги на C++. Но мозги без тестирования писать было невыносимо и я убил первую ночь на попытки поднять LiveCD и чтото туда записать. Злой, но очень... расстроенный я лёг спать.

Хмурое утро принесло нам версии сервера под Линукс, Макос, новую редакцию правил и туманное обещание, что Windows сервера не будет. Nice... Мозговой штурм в скайпе (чтоб вы понимали Дима сидел в переговорном пункте и на фоне доносились крики "Алло! Алло!") дал нам метод настройки сети VMWare "host only" и метод передачи файлов в вирутальную машину через веб сервер поднятый на хосте и wget. Очень удобно! К этому времени первый день контеста для меня почти закончился, но за оставшиеся пару часов я набросал клиент на MSVC++ который позволял управлять ровером с клавиатуры. Это уже был какой-то фан - довольно быстро я научился объезжать кратеры руками и понял чего я примерно хочу от ИИ.

Здесь в повествовании случается Fast Forward примерно на 24 часа, по рябящему экрану идут полосы и быстро бегают смешные фигурки. Сеанс связи с Димой дал нам симпатичную программку на Джаве, которая умела сама всё рисовать и умела довольно неплохо думать. Дима придумал мат. модель происходящего по которой на ровер действуют разные силы: притяжения к базе и отталкивания от препятствий. Все эти силы, складываясь, давали вектор направления куда надо ехать. Ура! - у нас была программа которая могла доехать до финиша. Другое дело что делала она это ой не всегда, проблемы предлагалось решать хаками. Поделив 3 перспективных хака между собой мы пошли спать (Дима) и программировать (я).

Сеанс кодирования я начал с того, что выбросил свои наработки на С++ и установил Eclipse: Java-версия настолько далеко продвинулась вперёд, что было глупо догонять. Начать я решил не с договоренных хаков, а с небольшого исследования на тему проверки своих идей о том как ровер должен думать. Эта проверка вылилась в то, что я полностью переписал ему мозги. Идея простая но мощная - мы строим предполагаемую траекторию движения для каждого направления при движении вперёд. Те траектории которые выводят нас ближе к центру оцениваем выше, те которые пересекаются с препятствиями штрафуем. Штраф тем больше, чем раньше мы врезаемся. Среди всех траекторий выбираем набравшую больше всего очков и едем туда. Усталый но довольный я лёг спать, предварительно написав Диме завещание.

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

Приняв пост я довёл архив до ума, на что ушёл час, засабмитил первую версию и решил немножко полирнуть алгоритм за оставшиеся 3 часа. Полировать было решено основательно - дополнив физическую модель до осознания понятий "тормоз" и "ускорение" ("сила трения" была нечаянно упущена, что впрочем не очень страшно, т.к. она прибавлялась к вычисленным ускорениям и незримо присутствовала). Значения мы вычисляем по ходу дела, когда пользуемся газом и тормозом, получается не очень точно, но достаточно для практических применений. Пока мы ничего не знаем, мы используем значения с тестовой карты (я знаю, что это не очень хорошо). Имея в руках ускорения можно пытаться предугадать куда мы поедем если отпустим газ или нажмём на тормоз. После добавления этих 8 новых путей в анализатор ровер автомагически научился притормаживать. Теперь траектории объезда препятствий стали очень экономными - ровер буквально облизывал кратеры. Как побочный результат скоростные показатели сильно ухудшились. Побочный результат удалось частично забороть штрафами на очки тормозных путей.

Тут подошло время сабмита и мы начали сравнивать то что уже засабмитили и новую тормозящую версию. Результаты у нас получались противоречивые, причём сильно варьирующиеся от запуска к запуска. Несмотря на противоречивость послали новую версию, т.к. там был немного улучшен объезд марсиан и в целом более экономичные пути давали меньшее время.

Подведём итоги. За 3 дня нам удалось сделать довольно неплохого тактического водителя марсохода, ещё б денёк и посадили бы рядом с ним штурмана с картой. Несмотря на то что удовольствие я получил, организатором выше тройки поставить не могу. Задание такого плана можно было придумать за неделю и ещё за неделю написать инструменты. Судя по всему так оно и было, потому что всё спешно дописывалось уже после начала контеста. Если сравнить это с трудом, вложенным оргами в предыдущие 2 контеста, то получится отношение яблока к горе Фудзи. Наши шансы оцениваю выше среднего (то есть мы должны быть в первой половине таблицы результатов ;-). Ждём сентября и ICFPC 2009!
Tags: tech
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

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