Eugene Kirpichov (antilamer) wrote,
Eugene Kirpichov
antilamer

ICFPC 2012

Мы участвовали с _navi_ (географически вместе - у Вани или у меня дома, Palo Alto / Mountain View) и _adept_ (Лондон). Даже неудобно как-то, что у меня юзернейм без подчеркиваний.

Команду назвали Λ*.

_adept_ написал такой офигительный отчёт, что мне его всё равно не переплюнуть, так что полноценный отчёт писать не буду. Читайте: (там есть видео того, как играет наш робот, и многое другое).

http://users.livejournal.com/_adept_/123989.html

Кратко об алгоритмах засабмиченной версии. Все из упомянутых оптимизаций и эвристик дают в среднем 2х-3х прирост очков, так мы и добрались от 50к утром второго дня до 6млн ночью третьего.

  • Глобальной маршрутизации нет, только жадная
  • Маршрутизация к ближайшей лямбде - с помощью A* над графом состояний карты (позиция робота + позиции камней)
    • В качестве оценочной функции - расстояние "как если бы камни не двигались" (с помощью A* тоже, оценочная функция - манхеттенское). Т.о., робот по возможности идет по оптимальному статическому пути, не перебирая все возможные ненужные действия.
  • Избегать попыток дойти до тупиковых лямбд
    • Тупик = "все пути от лямбды на глубину 4 ведут к смерти либо ничего нового не находят по сравнению с глубиной 1,2,3"
  • Маршрутизация к лямбде делается с таймаутом 0.5с. Если не получилось, немедленно переходим к следующей.
  • Если все лямбды сейчас статически недостижимы, то попытаться достигнуть динамически:
    • Найти граничные точки floodfill области вокруг робота
    • Отсортировать их по эвристике "манхеттенское до точки + манхеттенское от точки до ближайшей лямбды"
    • Пройти до точки и от точки до лямбды A* с манхеттенской эвристикой
  • Оптимизации обновления и хранения карты:
    • Карта хранится в одноуровневом IntMap, индексируемом 32-битным словом (x,y)
    • IDA*: ищем путь длины не более 1, не более 2, не более 4 и т.п. При этом, когда ищем путь длины не более k, то обновляем карту только в окне k вокруг робота. Когда путь нашли - проигрываем его заново, обновляя уже всю карту.
    • Храним список камней, которые могут подвинуться, список бород, и правильно их апдейтим
    • Для сравнения положений камней у двух узлов в графе поиска A* сравниваем только хеши (хеш = сумма Jenkins Hash от положений каждого камня). Хеши кешируем и обновляем за O(1) при движении камней. Это приближение good enough и дико разгоняет.


И все-таки немного мыслей:
  • Команда получилась охрененная. Никто никого не тянул вниз, не генерил бесполезные идеи, не писал бесполезный код или код, который заведомо не получилось бы вовремя отладить, и т.п., communication/negotiation overhead почти отсутствовал. Круче было бы только если бы мы все трое были в одной комнате.
  • Haskell ацки рулит. Очень компактный код, очень быстро пишется, реально сложные вещи практически всегда работают с первой попытки, с точностью до опечаток. Trace для отладки было более чем достаточно. Проблем с ленивостью не было. Профайлинг производительности в GHC 7.4 работает замечательно - небо и земля по сравнению с предыдущими.
  • Нам не хватило смелости попробовать написать общую теорию всего бектрекинга, чтобы пореже загонять себя в сложную ситуацию (например, в лямбду, из которой трудно дойти до следующей). Не знаю, правильно мы или неправильно поступили, что не стали пытаться этого делать - может, стало бы легко комбинировать разные стратегии (например, описанную в посте _adept_ combo - перемежать вышеописанный поиск лямбд и итеративное улучшение если не получается) - а может, стало бы невозможно отлаживать существующие.
  • Алексей Щепин написал на OCaml безумно быструю и безумно тупую программу безо всяких вот этих вот эвристик, которая набирает больше очков чем мы. Ну, то Алексей Щепин, а то мы. Но какой-нибудь урок надо из этого извлечь.
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 12 comments