Команда Wintermute на ICFP Contest 2012

2012-08-13 #
Метки:

TL;DR: Это эпический пост о нашем участии в программистском конкурсе ICFP Contest 2012. В задаче мы создавали искусственный интеллект робота для игры по собиранию полезных ископаемых в шахтах. Участвовать было интересно и весело :) Мы прошли два отборочных раунда и вышли в финальный рануд!

Update: Мы заняли 19-ое место в итоговой таблице! Мы расцениваем результат как хороший.

А теперь полная версия для тех, кому интересно, как это было ;)

В 2012 году мы в четвёрый раз приняли участие в конкурсе ICFP Contest. В этот раз наша команда spb-archlinux переименовалась в Wintermute в связи с изменениями в составе команды. В команду Wintermute вошли следующие люди и компьютеры:

  • Андрей Власовских
  • Вадим Цесько
  • Вова Батыгин
  • Дима Качмар
  • Олег Шпынов
  • 4 Mac OS X и 1 Ubuntu

Из участников я был хорошо знаком со всеми, кроме Димы. Вадим, Вова и Дима были из Яндекса, а Олег и я были из JetBrains.

День 1. 2012-07-13

  • 15:40 Собрались в JetBrains вчетвером
  • 15:50 Тестовая консольная программка и скрипты запуска (Андрей)
  • 16:10 Читаем задание

В этом году спецификация задания была краткая и весьма понятная. Она занимала всего 6 страниц и в ней не было почти никаких хитростей или элементов квеста. Единственный квест состоял в том, что организаторы обещали выпустить несколько запланированных дополнений к спецификации в течение соревнования.

У задачи этого года была весёлая легенда. Поскольку функциональные языки становятся всё более известными и даже в популярных императивных языках появляются функции высшего порядка, мировые запасы лямбд оказались под угрозой. Ожидается, что лямбды закончатся к октябрю 2012 года. К счастью, в шахтах Шотландии были обнаружены большие залежи лямбд и остаётся лишь разработать технологию их добычи.

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

  • 17:10 Добавили build.xml и JUnit (Вадим)
  • 17:20 Отправились обедать в кафе
  • 19:00 Составили список идей и проблем, план ближайших действий

Это, пожалуй, был первый для нас конкурс, в котором задание было сразу понятно и можно было почти сразу приступать к основной части, то есть к изобретению алгоритма для робота. Поэтому мы решили, что после ознакомления с задачей имеет смысл пойти всем вместе посидеть в кафе и за ужином порассуждать на тему задачи.

По возвращении мы выписали идеи и проблемы на доску. Мы постарались не выписывать идеи про оптимизации, считая их преждевременными. В частности, было высказано много мыслей по поводу очень больших шахт, не влезающих в память (1GB) и даже не влезающих на диск, которые надо обрабатывать потоково. Но решили, что сначала у нас всё будет тупо: шахта на обычных структурах данных.

После составления списка идей составили список первоочередных задач. Мы решили ответить на вопрос, что нужно сделать, чтобы начать выдавать решения по сбору лямбд. Вот что примерно получилось:

  1. Робот
    1. Парсер и внутреннее представление шахт
    2. Система симуляции шахт
    3. Алгоритм поиска кратчайшего маршрута между лямбдами
    4. Способ перемещения к конкретной лямбде
  2. Визуализатор
  3. Генератор карт

Несколько идей, высказанных при начальном обсуждении, существенно повлияли на наше решение задачи. Мы начали думать о задаче сбора лямбд в шахте как о композиции двух подзадач:

  • Глобальный поиск оптимального пути между начальным положением робота, лямбдами и лифтом
  • Локальный поиск кратчайшего пути к очередной лямбде

Задача глобального поиска пути — это известная задача комивояжёра, TSP. Мы почти сразу вспомнили о приближённых способах её решения, в частности об алгоритме 2-opt TSP. Про задачу поиска локально пути мы вспомнили о не очень эффективном алгоритме поиска пути на графе в ширину, BFS. Эти алгоритмы будут описаны ниже.

Надо заметить, что мы вначале не осознавали опасность ловушек и динамических событий в шахте. Мы думали о решении как о достаточно статичном процессе, условия которого известны заранее. Скорее мы беспокоились об эффективном решении задачи на большой размерности, хотя всячески старались избавиться от этих мыслей и реализовать "для начала" простое решение.

Тем не менее, имея в виду возможность повторного использования процедур обновления шахты, мы решили вначале описывать решения не в виде функций вида Mine -> List<Turn>, а в виде объектов-акторов, реализующих интерфейс:

interface Robot {
    Turn act(Mine m);
}

Предполагалось, что мы разработаем некий симулятор, который распарсит шахту, создаст робота, и будет вызывать его в цикле, обновляя и передавая ему шахту по результатам его предыдущего хода.

  • 20:10 Начальная реализация шахты Mine (Олег, Андрей)
  • 20:40 Начальный парсер шахт (Олег)
  • 20:00 Присоединился Дима

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

  • 20:30 Заготовка визуализатора (Вадим)
  • 21:10 Начальная версия алгоритма BFS (Дима)

В качестве алгоритма для поиска пути к ближайшей лямбде нам довольно быстро пришёл в голову BFS, поиск в ширину. Он перебирает все ближайшие клетки к исходной, запоминая путь из неё к ним. Если цель достигнута, то путь найден. Иначе он итеративно повторяется для следующих ближайших клеток. Этот алгоритм очень неоптимален, поскольку для поиска кратчайшего пути длины N он обходит все возможные пути длины меньше N.

Сложно сказать, решили ли мы реализовать такой алгоритм лишь в качестве начального варианта или это был наш основной вариант. Достаточно отметить, что в течение конкурса мы делали попытки отойти от этого медленного решения, но так и не пришли к алгоритму A*, которым воспользовались многие команды, занявшие высокие места. У нас была похожая на A* идея, которую мы в ходе конкурса называли модифицированным DFS, то есть поиском в глубину с учётом направления движения, но она так и не была реализована.

  • 21:30 Клонирование шахт, заготовка для ходов (Олег)
  • 21:20 Реализация визуализатора (Вадим)
  • 22:00 Реализация обновления шахты и хода робота (Олег)
  • 22:10 Заготовка симулятора и заглушка робота (Андрей)
  • 22:30 Генератор шахт, фиксы парсера (Вова)
  • 23:10 Визуализатор на Swing (Вадим)
  • 23:25 Карта на одномерном массиве (Вадим)
  • 23:40 Входная точка и основной цикл симулятора (Андрей)
  • 23:40 Фиксы шахты (Вова)
  • 00:00 Фиксы BFS (Дима)
  • 00:10 Обновление шахты (Олег)
  • 00:10 Фиксы шахты и парсера (Вадим)
  • 00:30 Разъехались по домам

К концу первого дня у нас был начальный парсер и симулятор шахт, а также визуализатор трассы робота и генератор случайных шахт. Глядя на полученные к концу дня результаты, мы решили, что не так уж много было сделано. В частности, была не решена задача создания робота, который бы хоть как-то ходил по шахтам и пробовал собирать лямбды, а парсер и симуляция шахт не были оттестированы. Поэтому мы решили ночью позаниматься задачей из дома, но завтра всё же встретиться в 12. Хотелось поучаствовать в lightning round, который заканчивался в 16:00.

Вечером первого дня организаторы, до той поры выдавшие лишь скромную и мирную спецификацию на 6 страниц, начали осуществлять объявленный план по внесению дополнений. Оказалось, что в шахтах могут происходить наводнения! Раз в несколько ходов уровень воды в шахте, изначально нулевой, поднимается на одну клеточку. Робот может оставаться под водой не более нескольких ходов. Соответственно менялся формат шахты и способ симуляции. Требовались также коррективы алгоритма робота, поскольку лямбды на нижних уровнях шахты могли теперь оказаться затопленными и не доступными для сбора через несколько ходов. Для успешного участия в lightning round требовалось поддержать это дополнение.

  • 01:30 Фиксы парсинга шахт (Вадим)
  • 02:30 Параметризованный генератор (Вова)
  • 03:00 Скрипты сборки пакета для отправки (Андрей)
  • 03:00 Требуемый API шахты для робота, фиксы обновления шахты (Вадим)
  • 05:30 Отрефакторен BFS, переведён на API шахт (Андрей)
  • 05:30 Прототип робота-собирателя лямбд (Андрей)
  • 05:30 Опции выбора робота для симуляции (Андрей)

День 2. 2012-07-14

В результате небольшого ночного хака к утру у нас уже был прототип робота, который работал в реальной симуляции. Этот робот получал лямбды, брал первую попавшуюся, пробовал получить через BFS кратчайший путь к ней и после некоторых раздумий решал прервать миссию, то есть выдавал трассу из одной буквы A.

Попытки компьютера подумать по разработанному тобой алгоритму радуют и вдохновляют, особенно когда задействованы лишь недавно связанные куски кода, которые взаимодействуют пока не известным для тебя образом. Так что пол-секунды мыслей робота и выдача решения о прерывании миссии были встречены нами с улыбкой :)

На второй день мы собрались к 13 часам и составили план подготовки решения к lightning round, заключавшийся в следующем:

  • Убедиться в работоспособности парсера и симулятора шахт
  • Довести робота до рабочего состояния
  • Добавить поддержку наводнений в парсер и симулятор
  • Отправить пакет решения организаторам

Олег и Вова стали доводить робота, Дима стал добавлять поддержку наводнений в парсер и симулятор, Вадим занялся тестами и доработкой визуализатора, а я общался со всеми и подготавливал решение к отправке.

  • 11:10 Фиксы генератора (Вова)
  • 13:40 Начальная реализация алгоритма 2-opt для решения TSP (Олег)
  • 14:20 Рефакторинг тестов (Вадим)
  • 14:40 Скрипт для запуска генератора (Андрей)
  • 14:40 Использование TSP в роботе (Вова)
  • 15:00 Скрипт для запуска визуализатора (Андрей)
  • 15:00 Тесты парсера шахт (Вадим)
  • 15:00 Простой собиратель лямбд как робот по умолчанию (Вова)
  • 15:10 Фиксы в TSP (Олег)
  • 15:20 Номер команды Wintrmute в скриптах для отправки (Андрей)
  • 15:30 Новый парсер и новая реализация шахт на списках с поддержкой воды, не вошло в lightning (Дима)
  • 15:30 Перевод визуализатора на чистый Swing без IntelliJ (Вадим)

Олег и Вова поправили ошибки в BFS, из-за чего наш робот не мог вычислить путь к ближайшей лямбде. Также Олег решил заменить глобальную стратегию поиска пути между лямбдами со случайной (берём первую попавшуюся) на алгоритм приближённого решения задачи комивояжёра 2-opt TSP, который он вспомнил ещё вчера. Этот алгоритм заключается в том, чтобы взять начальный случайный путь, а затем для двух пар рёбер из этого пути переставить их местами из двух путей взять тот, который короче. Это можно делать итеративно, постепенно приближаясь к неплохому пути. Олег написал квадратичную от числа рёбер реализацию, перебирающую попарно все рёбра пути и повторяющую это фиксированное число раз. Алгоритм 2-opt TSP вместе с поправленным BFS вошёл в наше решение для lightning round.

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

  • 15:30 Проблема с NEwMineParser.java и NewMineParser.java в Mercurial
  • 15:40 Предел в итерациях 2-opt TSP (Вова)
  • 15:50 Подготовка версии для отправки на lightning round (Андрей)
  • 16:00 Послали решение на lightning round: 3622 очка на картах contest

Итак, до окончания lightning round остаётся полчаса, мы доделываем свою работу и готовимся к отправке, как вдруг у нас происходит беда! Пришла она оттуда, откуда её не ждали: сломалась наша система управления версиями Mercurial!

Вообще я очень хорошо знаком с Mercurial и обычно помогаю всем с ней разобраться. Но в этот раз ошибка поставила меня в тупик. Потребовалось минут 10, чтобы понять, что происходит.

При попытке обновиться на новые изменения от Вадима я получал ошибку, что файл NewMineParser.java уже существует и обновиться невозможно. При этом рабочая копия была чистой. Аналогичную ошибку вскоре заметили и остальные участники. После некоторых разбирательств стало ясно, что проблема в том, что у нас в результате переименования в истории изменений образовалось два файла: бывший NEwMineParser.java и заменивший его NewMineParser.java. А Mercurial, возможно, не без участия нечувствительности к регистру на Маке, не может обновить рабочую копию на другой, но при этом такой же файл. Проблему нормальным способом было никак не устранить и пришлось организовывать массовое стирание истории с сервера и с компьютера каждого, кто успел обновиться.

Наконец, проблема была решена, и за 2 минуты до конца lightning round мы отправили наше решение в виде пакета организаторам.

  • 16:10 Отправились прогуляться и пообедать, обсуждали задачи и парное программирование

Сдав решение, мы отправились прогуляться вдоль Чёрной речки, чтобы подышать воздухом и пообедать. До начала конкурса у нас была идея выходить каждый день погулять, чтобы иметь возможность отдохнуть и подумать о задаче немного со стороны.

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

Чтобы устранить эти проблемы, мы решили попробовать продолжить разработку в стиле парного программирования. Одну пару составили Вова и Олег. Они должны были работать над алгоритмами робота: 2-opt TSP, BFS, обходом ловушек и т. д. Вторую пару составили Вадим и Дима. Они должны были заняться доработкой парсера, симулятора и визуализатора: тестированием, исправлением багов, реализацией обещанных организаторами обновлений спецификаиции. Я оставался без пары и должен был продолжать заниматься понемногу инфраструктурой и обсуждать со всеми актуальные проблемы.

Сдав наше первое решение, мы поняли, что не представляем, куда мы двигаемся. У нас не было системы оценки нашей текущей ситуации: того, насколько хорошо ведёт себя робот. Не очень мы представляли и проблемы, из-за которых робот недостаточно хорош, и как сделать его лучше. Не все даже уже видели, как робот ведёт себя в визуализаторе или в виде отдельной программы, поскольку продолжали запускать свои отладочные примеры из IntellJ IDEA.

Поэтому общим планом на второй день стали следующие задачи:

  1. Автоматизированные тесты корректности парсера и симулятора шахт
  2. Система подсчёта очков, получаемых роботом на наборе шахт
  3. Анализ прохождения роботом шахт организаторов и сгенерированных шахт
  4. Улучшение алгоритмов робота по добыче лямбд
  5. Реализация дополнений к спецификации

Пообедав, мы приступили к работе над этими задачами.

  • 17:30 Вычисляем BFS на каждом шагу, считаем только 1000 итераций 2-opt TSP (Олег)
  • 18:00 Разделение шахт на массивах и списках (Дима)
  • 18:00 Фиксы визуализатора (Вадим)
  • 18:20 Подсчёт очков (Вова)
  • 18:40 Тесты списковой и массивной реализаций шахт (Вадим)
  • 18:40 Переход на списковую реализацию шахт в визуализаторе (Вадим)
  • 18:50 Фиксы списковой реализации шахт (Дима)
  • 19:00 Опция симулятора для вывода очков (Андрей)
  • 19:00 Фиксы перемещения камней роботом (Олег)
  • 19:00 Фиксы списковой реализации шахт (Вадим)
  • 19:20 Параллельные исключающие фиксы шахт Вадима и Димы
  • 19:30 Запуск симулятора на тестовых наборах со статистикой очков (Андрей)
  • 19:40 Переход на списковую реализацию шахт в симуляторе (Андрей)
  • 21:10 Визуализатор читает трассу со стандратного ввода (Андрей)
  • 21:20 Затопление шахты и ныряние робота (Дима)
  • 21:20 Запуск симуляции и визуализации одним скриптом (Андрей)
  • 21:30 Возможен только один лифт на карте (Вадим)

Одной из вещей, которую требовалось наладить как можно скорее, была система подсчёта очков. Мы с Вовой реализовали её, после чего в течение конкурса мы стали замерять число очков на эталонном наборе из 10 начальных шахт от организаторов. Так, например, посчитав ретроспективно число очков, набираемых нашим решением на lightning round, мы получили начальную точку отсчёта: 3622 очка. На момент внедрения системы подсчёта очков мы набирали уже 4283 очка, в основном, за счёт разных фиксов. Олег исправлял ошибки в роботе, а Вадим и Дима фиксили парсер и симуляцию шахты.

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

Ситуацию помогли улучшить сами организаторы, ибо вечером второго дня они выпустили обновление спецификации: в шахтах появились трамплины! Трамплины позволяли перепрыгнуть из одного места карты, омтеченного трамплином, в другое фиксированное место. При этом трамплин исчезает. Это дополнение потребовало от нас обновления парсера и поддержки трамплинов в симуляторе и алгоритмах робота. Дима стал реализовывать это обновление, а Вадим продолжил заниматься фиксами текущей реализации.

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

  • 21:40 Расстояние по BFS в 2-opt TSP (Вова)
  • 21:40 Отображение статуса завершения симуляции (Андрей)
  • 22:00 Отключён BFS в 2-opt TSP из-за тормозов (Андрей)
  • 22:10 Обработка и визуализация убийства (Вадим)
  • 22:40 Поддержка трамплинов (Дима)
  • 22:40 Реализация BFS с симуляцией виртуальной шахты (Вова)

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

Вова под вечер реализовал такую версию BFS, получившую название full BFS или виртуального BFS. Внедрение виртуального BFS в робота на следующий день привело к прорыву в получении очков.

  • 23:10 Фиксы в наводнении (Вадим)
  • 23:30 Учёт трамплинов в обычном BFS (Дима)
  • 00:10 Поправлен обход BFS, чтобы увеличить шансы на выживание (Олег)
  • 00:20 Оценка роботом возможных оставшихся очков (Олег)
  • 00:20 Начальная реализация стрёмности лямбд (Олег)
  • 00:20 1GB памяти для JVM (Вадим)
  • 00:30 Разъехались по домам
  • 02:20 Поддержка наводнений, кэш камней и переход на массивные шахты (Вадим)

В рамках начинающейся борьбы за выживание робота в шахте Олег решил попробовать идею о стрёмности лямбд. Она заключается в следующем: некоторые лямбды очевидно опаснее других. Например, рядом с ними есть камни или они находятся в закрытом помещении или внизу шахты с наводнением. Можно вначале пробовать собрать лямбды попроще и лишь в конце переходить к более стрёмным. Идея была интересной, но её начальная реализация снижала число получаемых очков с 4283 до 3408, поэтому мы вначале отложили её, а позже фактически исключили из алгоритма робота.

Под вечер мы стали обращать внимание на проблему производительности. После внедрения виртуального BFS робот стал решать шахты среднего размера за несколько секунд, а потребление памяти достигло сотен мегабайт за счёт постоянного копирования вируальных шахт на каждый шаг расчёта BFS.

Количество очков за вечер не возросло, поскольку виртуальный BFS ещё только тестировался и не был подключен к основному роботу. В конце второго дня соревнования мы набирали 4283 очка.

2012-07-15

На этот раз ночью хачить дома почти никто не стал, только Вадим поработал над реализацией шахт.

Ночью вышло очередное дополнение к спецификации. Оказывается, под землёй могут расти бороды! Они растут каждые несколько ходов во всех направлениях и через них не пройти. Их можно сбривать бритвами, которые можно найти в шахте. Без динамического вычисления пути по виртуальному BFS с таким справиться было тяжело. К тому же, как всегда, потребовалась модификация парсера и симулятора шахт.

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

  • 11:30 Ожидание и двигание роботом камней в виртуальном BFS (Вова)
  • 12:30 Переход к следующей лямбде только при подтверждении её сбора от шахты (Олег)
  • 12:40 Учёт стрёмности лямбд отделён от 2-opt TSP (Олег)
  • 13:00 Перерасчёт TSP, если робот случайно собрал лямбду (Олег)
  • 13:50 Фиксы в оценке роботом максимального числа очков (Олег)
  • 14:30 Не игнорировать полностью смертельно стрёмные лямбды (Олег)
  • 14:40 Ленивый расчёт BFS только при пустом текущем маршруте (Вова)

Одной из важных вещей было подключение разработанного Вовой алгоритма виртуального BFS. Это с учётом утренних фиксов позволило нам резко повысить число набираемых очков до 7918. Теперь нашему роботу были не страшны динамические события в карте при движении к очередной лямбде. Он начал выныривать из-под воды, уворачиваться от камней и вообще вести себя очень разумно. Но как только дело доходило до попадания в ловушки, заключающиеся во взятии нескольких лямбд, робот легко попадался.

Приведу пару примеров таких ловушек. Например, лямбда, на которой лежит камень и путь к которой есть только снизу. Робот прекрасно брал эту лямбду, но больше не мог никуда сходить, т. к. единственный возможный ход вниз приводил к удару камнем по голове. Или, скажем, комната, полная лямбд, войти в которую по прямой можно только один раз: за тобой заваливает вход. Робот смело шёл туда по кратчайшему пути, собирал все лямбды, после чего сдавался. Ему (и нам) не хватало мозгов, чтобы вначале разобрать ловушку, а уже потом входить в комнату. Или хотя бы собрать сначала менее опасные лямбды по всей карте.

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

  • 14:40 Олег и Андрей пробуют избежать ловушек моделированием больше чем на 1 лямбду вперёд
  • 15:00 Виртуальный BFS возвращает шахту после моделирования (Вова)
  • 15:00 Поддержка трамплинов в массивных шахтах (Вадим)
  • 15:10 Не проводить в роботе параллельную симуляцию шахты (Олег и Андрей)

Поскольку стрёмность лямбд пока себя не оправдывала, мы с Олегом решили попробовать ещё один подход к избеганию ловушек. Идея была простая: если при виртуальном BFS робот, взявший лямбду, не может вернуться на свою позицию на момент расчёта или дойти до лифта, то такая лямбда стрёмная и идти к ней надо лишь в самом конце.

Хотя идея вроде бы была неплохая, нам никак не удавалось заставить её эффективно работать. В результате наших переделок робота мы откатились назад до 6772 очков. Единственным положительным моментом нашей попытки стало приведение интерфейса алгоритма 2-opt TSP к нормальному виду. Он появился на свет при разработке робота и был тесно связан с ним внутренностями. Теперь же у нас фактически получилось два семейства алгоритмов, которые можно было воткнуть куда угодно:

  • TSP (2-opt TSP и TSP с учётом стрёмности лямбд)
  • BFS (быстрый BFS, виртуальный BFS)

Как мы ещё увидим, это дало нам возможность реализовать вечером совсем не похожий на нашего робота алгоритм, который сильно помог нам на небольших картах с ловушками.

Мы ещё не успели поддержать дополнение спецификации про бороды и лезвия, а организаторы уже выпустили ещё одно, к счастью последнее, дополнение. В шахтах, оказывается, встречаются камни высшего порядка! Стоит лишь расколоть их, уронив с высоты, и они превращаются в лямбду. Тут уже обычным виртуальным BFS не обойдёшься. Ведь для раскалывания надо ходить вовсе не по кратчайшему маршруту. Например, может потребоваться отойти в сторону и вернуться назад, чтобы расколоть камень. Мы решили, что поддержим камни высшего порядка синтаксически, а обрабатывать их будем позже, если у нас хватит времени.

  • 16:10 Реализация учёта максимального числа очков и лучшей трассы в симуляторе (Дима)
  • 16:10 Учёт камней высшего порядка в массивной шахте (Вадим)
  • 16:20 Учёт трамплинов в виртуальном BFS (Вова)
  • 16:30 Расчёт стрёмности в стрёмной версии TSP (Олег)
  • 17:00 Поехали обедать на Петроградку

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

  • 19:00 Фиксы по оптимизации в виртуальном BFS (Вова)
  • 19:20 Опциональная жадность в виртуальном BFS (Вова)
  • 19:50 Рефакторинг робота, радиус жадности BFS (Андрей и Олег)
  • 19:50 Убран подсчёт максимума очков из робота (Андрей)
  • 20:10 Жадный BFS берёт лямбду прямо на нашем пути (Андрей)
  • 20:00 Поддержка бороды и лезвий в массивных шахтах (Вадим)
  • 20:10 Удобный интерфейс вызова 2-opt TSP (Олег)
  • 20:30 Робот переведён на упрощённый интерфейс TSP (Олег)
  • 20:30 Скроллинг шахты в визуализаторе (Вадим)

Проблема ловушек была поставлена с утра и над её решением думали все, кроме Вадима. Вадим был занят важным делом по поддержке бород и камней высшего порядка в парсере шахт и симуляторе.

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

Вова и Олег, оставивший несработавшую инициативу по избеганию ловушек предрасчётом виртуального мира больше чем на одну лямбду вперёд, решили попробовать одну оптимизацию в сборе лямбд. Они заметили, что наше манхеттенское расстояние по координатам между лямбдами при расчёте TSP иногда приводит к тому, что мы проходим буквально рядом с лямбдой по пути к другой лямбде. Это происходит из-за лабиринто-подобных шахт, в которых манхеттенское расстояние может сильно не соответствовать действительности. Они стали добавлять в BFS элементы жадности, чтобы робот всё же сворачивал с пути к ближайшей по манхеттенскому расстоянию лямбде, если в его настоящем радиусе оказалась другая лямбда.

В результате фиксов виртуального BFS, добавления жадности и отслеживания максимума очков нам удалось набрать 7895 очков, то есть вернуться к утреннему уровню очков, но с более чистым отрефакторенным кодом и пофикшенными алгоритмами.

  • 20:30 Дима и Андрей пробуют метод ветвей и границ
  • 21:00 Фиксы виртуального BFS (Вова)
  • 21:20 Большая жадность в виртуальном BFS (Олег)
  • 23:00 Константы количества повторных посещений и ожиданий в BFS (Вова)
  • 23:50 Симулятор с алгоритмом ветвей и границ (Андрей и Дима)
  • 01:00 Случайное переупорядочение ветвей в алгоритме ветвей (Дима)

Вова и Олег продолжили совершенствовать нашего робота и фиксить ошибки, в результате чего мы набрали 8791 очко.

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

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

К нашей задаче мы применили этот метод следующим образом. Решениями в нашем случае являются разные последовательности обхода лямбд, обязательно заканчивающиеся лифтом. Численная оценка решения — это набираемые роботом очки, надо найти её максимум. Мы разбиваем множество вариантов обхода лямбд по тому, какую из лямбд мы посетим на очередном шаге. Соотвественно, на первом шаге у нас есть N веток решений, начинающихся с посещения одной из N лямбд. Каждая из веток делится на ветки по тому, какую лямбду посетить второй и т. д. В качестве критерия для упорядочивания веток на одном уровне мы выбрали кратчайший путь по готовому алгоритму 2-opt TSP. Если путь можно пройти и зайти в лифт, нигде не застряв, мы считаем, что это уже хорошо, и выдаём решение. Нижней оценкой является количество очков за достижение ближайшей лямбды и отмена миссии после этого. С верхней оценкой всё хуже, поскольку без расчёта пути вглубь лямбд мы часто ничего сказать не можем. Мы можем получить верхнюю оценку только в случае, если пути в лямбду очередной ветки нет вообще и нам дают 0 очков. Для расчёта очков и ходов робота до ближайшей лямбды мы использовали готовый алгоритм виртуального BFS.

В первой реализации это, фактически, получился алгоритм хождения по оптимальному пути 2-opt TSP с бэктрекингом, то есть откатами к предыдущей лямбде, если из текущей дальнейшего пути никуда нет. Понятное дело, что такой алгоритм в случае ловушек по всей длине маршрута работает ужасно долго, а именно за экспоненциальное время. Особенно обидно, когда робот забирается по уши в ловушку и перебирает варианты, уже находясь в безвыходной ситуации, когда выход заключается в том, что надо сделать другой первый ход. Посмотрев, как ведёт себя наш алгоритм ветвей и границ, мы добавили отсечение возможных вариантов по мере продвижения по маршруту. С погружением вглубь дерева мы позволяли роботу считать всё меньше вариантов.

В итоге получилось решение, которое хорошо работало для маленьких карт и находило почти идеальный путь. Работало оно не совсем долго, поскольку экспонента была не от числа клеточек, а от числа лямбд. Ведь алгоритм искал лишь маршрут между лямбдами, полагаясь на виртуальный BFS для поиска кратчайшего пути к очередной лямбде. Применив алгоритм ветвей и границ, мы получили 9890 очков!

К сожалению, даже на небольших тестовых картах алгоритм думал по несколько секунд. А на больших картах мы просто бы убивались сигналами SIGINT и SIGKILL от организаторов, не успев ничего посчитать. Стало понятно, что нужно создать соединённое решение, выбирающее робота или ветви в зависимости от размера карты.

  • 01:10 Разъехались по домам, Андрей и Вадим остались хачить

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

Мы сформировали следующий план до конца конкурса. Часть этого плана было совершенно необходимо выполнить, а часть предполагала возможность поэкспериментировать. План выглядел примерно так:

  1. Выдача текущего наилучшего решения по SIGINT и OutOfMemoryError
  2. Соединение алгоритмов робота для больших шахт и ветвей для маленьких
  3. Переход к шахтам на персистентных массивах для существенной экономии памяти
  4. Параметры алгоритмов для поддержки очень больших шахт

За последним пунктом скрывалась группа мер по тому, как заставить робота решать большие шахты за приемлемое время и не попадаться в ловушки. Напомню, что алгоритм ветвей и границ круто обходил ловушки, но работал только на маленьких картах из-за плохой производительности.

  • 03:10 Рефакторинг алгоритма ветвей и границ (Андрей)
  • 03:20 Фиксы обновления шахты (Вадим)
  • 03:30 Алгоритм ветвей и границ реализует интерфейс симулятора (Андрей)
  • 03:40 Выключены опции выбора робота (Андрей)
  • 03:40 Поддержка Scala в проекте (Вадим)
  • 04:00 Симулятор робота реализует интерфейс симулятора (Андрей)
  • 05:00 Фиксы в вызове симулятора ветвей и границ через общий интерфейс (Андрей)
  • 05:00 Опция выбора алгоритма (Андрей)
  • 05:40 Фикс ошибки индексации на единицу в симуляторе ветвей и границ (Андрей)
  • 06:40 768MB памяти для JVM (Вадим)
  • 06:50 Обработка SIGINT (Андрей)
  • 06:50 Шахта на персистентных массивах Scala (Вадим)
  • 07:00 Попытка распечатать лучшее текущее решение по OutOfMemoryError (Андрей)

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

interface Simulator {
    void simulate(Mine m);
    List<Turn> getTurns();
    int getScore();
}

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

Для того, чтобы привести алгоритм ветвей и границ к такому интерфейсу, мне пришлось потратить несколько часов. Дело в том, что код реализации алгоритма был очень страшным, хотя и коротким. В нём изобиловало изменяемое состояние, фрагменты для отладки и т. п. После выполнения рефакторинга я долго не мог восстановить работоспособность алгоритма, потому что не замечал ошибки на единицу в цикле. Ближе к утру оба симулятора, робот и ветви, были переведены на новый интерфейс.

Вадим тем временем пробовал новую реализацию шахт, которую было бы очень дёшево копировать в смысле занимаемой памяти. Поскольку в Java с неизменяемыми структурами данных всё не очень здорово (по крайней мере, отсутствует хороший источник информации по этой проблеме и нет общепринятных библиотек), Вадим решил взять коллекции языка Scala. Шахта была основана на неизменяемой scala.collection.immutable.HashMap<Int, Cell>, которая при добавлении элемента создаёт новую коллекцию, разделяющую со старой хранилище всех прежних элементов. На реализацию новой шахты поверх этой структуры данных тоже ушла большая часть ночи.

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

  • 07:40 Настройка параметров симулятора ветвей и границ (Андрей)
  • 08:20 Фиксы персистентной шахты (Вадим)
  • 08:30 Соединённый симулятор, адаптирующийся к типу карты (Андрей)
  • 10:50 Жадный TSP для кучи лямбд и опция симулятора для вывода отладочных сообщений (Андрей)
  • 11:30 Сохранение наилучшего результата в соединённом симуляторе (Андрей)
  • 11:30 Соединённый симулятор включён по умолчанию (Андрей)

После появления поддержки SIGINT, дешёвых по копированию шахт, единого интерфейса симуляторов робота и ветвей можно было заняться замечательной вещью: созданием соединённого симулятора, который действовал бы адаптивно в зависимости от параметров решаемой шахты. Вадим уже начал засыпать, а я взялся за реализацию этого united simulator.

Вначале я просто соединил симуляторы робота и ветвей, выбирая ветви только для маленьких карт. Новый UnitedSimulator имел интерфейс Simulator, поэтому он без проблем воткнулся в общую программу в качестве симулятора по умолчанию. Затем я добавил в алгоритм ветвей параметров общего числа шагов, чтобы можно было пробовать запустить его в фиксированном времени. Для не очень больших карт в соединённом симуляторе сначала пробовался симулятор ветвей и границ на небольшое число шагов, затем робот и затем опять ветви до конца времени (прихода SIGINT), после чего выдавалось лучшее найденное одним из алгоритмов решение. Поскольку на очень больших картах даже робот начинал сильно тормозить, я написал альтернативное решение TSP по жадному алгоритму (всё время ломимся к ближайшей лямбде) и вкрутил его в робота для больших размерностей карт.

Благодаря адаптивному подходу нам удалось набрать 9334 очка. Это немного меньше, чем чистым симулятором ветвей и границ, но зато соединённый симулятор мог обрабатывать и большие карты, а на маленьких вёл себя довольно быстро благодаря ограничениям на параметры алгоритмов. Вообще говоря, глядя на официальные итоги первого раунда конкурса, можно было поставить и менее экономные параметры ради получения большего числа очков.

2012-07-16

Утром мы вновь собрались и решили попробовать побороться за производительность на больших размерностях, а также ещё раз попытаться улучшить обход ловушек в роботе.

  • 11:50 Оценка допустимых ходов для лёгкого BFS (Вова)
  • 13:00 Фиксы виртуального и лёгкого BFS (Вова)
  • 13:50 Рефакторинг парсеров, окончательный переход на персистентные шахты (Вадим)
  • 14:00 Оценка одноходовой ловушки в роботе (Вова)
  • 14:20 Добавлено 20 сгенерённых карт размера до 100 на 100 (Андрей)
  • 14:20 Виртуальный BFS со случайной промежуточной точкой, алгоритм ветвей и границ на нём (Дима)
  • 14:20 Запуск тестов с прерыванием SIGINT по таймеру 5 секунд (Андрей)
  • 14:30 Учёт ловушек в виртуальном BFS (Вова)
  • 14:50 Отключён неработающий учёт ловушек в BFS для алгоритма ветвей и границ (Вова)
  • 15:00 Откладывание недоступных лямбд и случайный выбор одной из них в конце (Олег)
  • 15:10 Алгоритм ветвей и границ на BFS со случайной точкой как первый вариант для мелких карт (Андрей)
  • 15:20 Уменьшено число шагов с неизменными очками в BFS ради производительности (Андрей)
  • 15:30 Таймаут в запускалке тестов 150 секунд (Андрей)

Утром я уже очень хотел спать, поэтому сделал мало чего полезного. Правда в результате в проекте появилось немного кода на Python :) Я связался с Женей Кирпичёвым, бывшим участником нашей бывшей команды spb-archlinux, который тоже участвовал в этом году. Он скинул мне набор из 1000 тестовых шахт, сгенерированных одной командой, чтобы померяться с нами очками. На этих шахтах решение Жени набирало, насколько я помню, 6.1 млн очков, имея лимит на решение каждой шахты в 5 секунд. Для нашего united симулятора, весь смысл которого был в использовании отведённых 150 секунд по максимуму, этот лимит был слишком жёстким. Всё же я написал на Python запускалку тестов в убиванием по SIGINT с лимитом в 30 секунд и прогнал наш симулятор на этих картах. Мы набрали 1.2 млн очков, что было в 5 раз меньше конкурентов. Как показали официальные итоги конкурса, мы рано огорчались. Во-первых мы отправили неплохое и довольно адаптивное решение, в то время как команда Жени засуетилась и послала не самое сильное решение, не устоявшее уже в первом раунде. Во-вторых, эти нагенерированные шахты были совсем не той природы, что шахты от организаторов. Поведение решений на них сильно отличалось.

Остальные участники успели попробовать ещё несколько подходов. Вова попробовал дополнить лёгкий (не виртуальный) BFS избеганием ловушек, чтобы его можно было использовать в больших шахтах. Дима добавил сделал альтернативный виртуальный BFS, в котором путь разбивался на две половинки по манхеттенскому расстоянию и затем считались два BFS меньшей размерности. Олег доделывал консервативный вариант стрёмности лямбд, когда смертельные лямбды откладываются на конец обхода и затем предпринимается попытка взять одну из них. Вадим тестировал и исправлял новую реализацию шахт на Scala.

  • 15:30 Вывод очков на stderr (Андрей)
  • 15:40 Приняты последние изменения, включён анализ ловушек в роботе моделированием BFS к лифту и своей позиции (Андрей)
  • 15:50 Отключён почти весь stderr (Андрей)
  • 16:00 Фикс исключения (Олег)

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

До окончания конкурса оставалось 10 минут. Я собрал последние изменения и начал уже делать пакет для отправки, как вдруг ко мне подскочил Олег: оказалось, что в наш код было посажено исключение! Буквально за две минуты мы пофиксили его и пересобрали пакет для отправки. Как же долго компилируется Scala! Всё же мы успели отправить решение и на этом конкурс был завершён. Отправленное нами решение набирало 9463 очка.

По окончании конкурса мы посравнивали результаты на шахтах организаторов с результатами команды Kotlin из JetBrains, наших соседей по конкурсу. Мы немного уступили им в решении этих шахт. Однако наше решение могло неплохо работать на больших размерностях, в то время как их переборный алгоритм не очень хорошо справлялся с ними.

Подводя итог, я хотел бы поблагодарить нашу команду Wintermute. Все участники хорошо боролись и внесли весомый хак в наш результат. Задание тоже было хорошим: простым по формулировке, но оставляющим простор для разных подходов. Мы отлично провели время!

Окончательные результаты конкурса ещё не известны. На данный момент мы занимаем скромное 53 место, однако мы при этом прошли первые два раунда отбора и вышли в финальный раунд! :)

blog comments powered by Disqus