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!
Задание 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!