ICFP '08 Contest

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

Preambula

Про ICFP contest я узнал начитавшись отчетов и сразуже захотел попробовать. Этот контест выгодно отличается от ненавистных мне «академических» олимпиад и их идиотскими заданиями, не имеющими ни малейшего отношения к реальности. Поскольку по одним субъективными отчетам трудно достоверно оценить явление было решено потрогать воду лапкой прежде чем готовиться к участвовать всерьез. Что и было проделано с величайшим удовольствием. Однако, некоторую подготовку я все же провел: настроил NetBeans с Ruby, создал необходимую структуру папок для проекта, поднял на всякий случай Linux под виртуальной машиной, скачал и запустил LiveCD

Day 0. Landing

За час до начала вылезаю на канал #icfp-contest и наблюдаю там больше 200 человек. С трудом дожидаюсь публикации задания. Большого смысла в этом нет, но хочется уже прочесть его, составить план штурма и отправится спать. Время из-за разницы во времени довольно позднее. В час «X» вся эта толпа, коей набралось уже за 300 человек радостно тянется качать задание и на несколько минут роняет сервер. Наконец я добираюсь до нужного документа и погружаюсь в чтение. Итак, задача этого года, в моем кратком изложении

Есть квадратное поле заданных размеров, представляющее поверхность Марса. На поверхности имеются:

1. кратеры, в которые можно упасть, насмерть, много;
2. валуны, о которые можно стукнуться, больно, тоже много;
3. марсиане, которые норовят сожрать, самоходные, много;
4. база, дружественная, одна;
5. марсоход, свой, один.

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

Прочитав задание, понимаю, что Ruby тут не при делах. Марсоход — железка глупая, не станет ждать пока досчитается, укатится к черту на рога. Решаю применить запасной вариант и использовать Java. Пока разворачивается IDE, лезу качать симулятор, но его ещё не выложили. Основных проблем в задании видится три: 1) Сетевой протокол; 2) Алгоритм управления; 3) Визуализатор для отладки. За пару часов реализую сетевой протокол, описываю необходимые структуры данных и с чистой совестью отправляюсь спать

Day 1. Doctrine: Mobility

Пока я спал, организаторы выложили симулятор, а участники в чате и рассылке развели невообразимый флейм. Быстро скачав симулятор, проверяю свой код. Сетевой протокол работает без отладки. В симуляторе оказывается встроенный визуализатор, так что от одной задачи я на некоторое время избавлен. Несколько часов уходит на то, чтобы научить марсоход ехать в заданную точку. Дело продвигается медленно, потому как тригонометрию я напрочь забыл, уж слишком давно не делал ничего подобного. Когда первая карта проходит отправляюсь кататься на велосипеде, а вечером принимаюсь за объезд препятствий. Лобовое решение, отворачивать от препятствия расположенного в опасном угле по курсу работает плохо. Объехав первый кратер, марсоход сослепу ухает во второй. Мне подкидывают идею, предсказывать положение марсохода на несколько ходов. Решаю заняться этим завтра и отправляюсь спать.

Day 2. Doctrine: Flexibility

Со вчерашнего дня обнаружилась ещё одна проблема: перерегуляция, приводящая к том, что марсоход пролетает мимо базы. Решил сперва побороть её и ввел эвристики, запрещающие крутые повороты вдали от базы для наведения на цель. С предсказанием все плохо, марсоход едет довольно паршиво, часто падает в кратеры и стукается о валуны. Приседания с параметрами дают немного. Это продолжается до тех пор, пока я не начинаю проверять точность предсказаний в реальном времени. Сперва обнаруживается, что я забыл учесть трение и предсказания скорости не слишком точны. Добавив систему оценки трения и ускорения, получаю точность предсказания скорости до четвертого знака. Выглядит хорошо, но точность предсказания расстояния не изменилась. Проверяю расчеты калькулятором и обнаруживаю, что java.lang.Math принимает аргументы синусов и косинусов в радианах, а я считаю углы в градусах. Правлю и точность hgtlcrfpfybq достигает требуемой. Поскольку нет необходимости в играх с параметрами, устанавливаю предсказания на 5 секунд вперед. Все три тестовые карты проходятся, так что я начинаю искать, на чем бы ещё протестировать. Поскольку возможности достать и померяться прямо в процессе организаторы не предусмотрели народ во всю обсуждает результаты и выкладывает собственные карты. Пытаюсь протестировать на чужих картах и обнаруживаю два факта: а) на рандомных картах сходных с тесовыми все работает идеально; б) стенки, «рюмки», «бутылки», лабиринты и прочие непрерывности вводят марсоход в ступор. На этой прекрасной ноте отправляюсь спать.

Day 3. Doctrine: Initiative

Пенедельник — день рабочий, поэтому за марсоход удается приняться только к вечеру. Проверять на каждом шаге полноценное дерево решений чтобы выбрать оптимальное мне влом. Судя по отзывам не меньше половины участников этим не заморачивались, уповая на отсутствие в реальных тестах стенок. Так что я решаю посвятить оставшееся время отладке и доводке. На марсинан также решено забить. Мой марсоход едет быстро и непредсказуемо, так, что даже я не всегда могу предполагать куда он свернет. Перехватить его марсианином, задача гораздо менее тривиальная, чем объезд препятствий, так что с марсианином он может столкнуться только по чистой случайности. Вычисление радиуса поворота в эвристиках для определения необходимого положения руля значительно помогло. Теперь марсоход едет быстро, оптимально и опасно. Решаю оставить как есть в надежде, что он не свалится в кратер больше двух раз. Пробую ещё пару идей, но они не работают. Сперва пытаюсь объединить пересекающиеся препятствия в одно большое, но точности это не увеличивает, зато существенно замедляет работу. Затем пытаюсь настроить москитный маневр (вместо движения прямо, рулить попеременно влево-вправо для затруднения перехвата), но это ухудшает точность предсказаний, которые на него не рассчитаны. Допиливать предсказания не хочется, поэтому сабмичу, как есть. Выложат результаты, будет видно насколько мои предположения оправдались. 

Conclusions

Участвовать в этом можно, но одному не это делать не слишком приятно. Кучу побочных задач я пропустил, так, а они могли существенно улучшить результат. Если бы у меня был собственный рендерер выводящий внутренне представление, ошибка с предсказаниями была бы отловлена сразу же и хватило бы времени на более изощренный алгоритм. Генератор карт существенно облегчил бы отладку. Даже ознакомиться с достижениями конкурентов не хватило времени. В следующий раз, я планирую собрать команду и подойти к делу серьезно.