Корсар++ (kopcap_plusplus) wrote,
Корсар++
kopcap_plusplus

Мааленький отчёт об ICFPC2015

Всем привет из лузервиля. 133 место из 316 это не то что бы очень плохо, но целью было войти хотя бы в сотню.

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

Задание. Заданием в этом году было написать ИИ для игры в тетрис на произвольном гексагональном поле с произвольными фигурами, кроме того, каждое движение можно был закодировать несколькими способами и результирующая кодировка может использоваться чтобы составлять т.н. power words (будем называть их заклинаниями), за которые дают доп очки. Помимо этого программе ещё передаётся инфа об ограничениях по времени и памяти, но на них я вообще забил болт (как и, я подозреваю, большинство участников).

Схема, которую я набросал в первое же утро после прочтения задания, выглядела так: для каждой фигуры анализируем наилучшую позицию, в которую её надо в конце поместить, а потом с помощью разновидности BestFS её туда помещаем, rinse and repeat. BestFS в итоге заменился на A* (строго говоря, A* это частный случай BestFS), но то решение, которое начало у меня работать аж только на третий день, работает именно так. Т.е. я придумал всю концепцию  в первый же час, а потом три дня не мог её нормально реализовать.

Развитие этой идеи тоже достаточно хорошо понятно - поиск наилучшего места можно развить до поиска наилучшего места с учётом следующей фигуры (не сильно большое изменение), а в A* встроить работу с фразами из списка заклинаний, которую потом можно доработать пост-процессингом. Эти изменения я сделать уже не успел.
Помимо решалки нужно было сделать:


  • Загрузку-выгрузку данных в JSON

  • Визуализатор (ибо искать ошибки в алгоритме без него нереально)

  • Собственно симулятор происходящих на поле безобразий

Почему же фейл? Помимо незнакомых средств разработки (от F# я, кстати, в диком восторге. строго типизированные парсинг и запись json'a, на реализацию которых у меня ушло примерно 5 минут на незнакомом языке - это рекорд, мать вашу) и неровного графика участия (3 дня без сна решил не сидеть), больше всего сказались всякие мелочи:


  • Работа с гексагональной сеткой это боль, хоть и выглядит просто. Готовых библиотек я не нашёл, в своих реализациях вылавливал баги все три дня. Спасибо вот этой страничке http://www.redblobgames.com/grids/hexagons/#conversions, человек, который это сделал, ты - бог.

  • Позиционирование начального юнита я тоже правил все три дня, хотя это элементарная функция из 3 строчек.

  • Неправильный подход к порядку того, что нужно сделать - я с самого начала пытался привести решение к цепочке файл -> <магия> -> визуализатор, вместо того, чтобы попытаться хоть что-то сабмитить. В результате мой первый успешный сабмит произошёл в середине третьего дня, хотя картинки бегали и прыгали уже в начале второго. Несколько часов я не мог понять, почему их сервер даёт мне только нули и спека тут вообще не помогала. Кстати, моё итоговое решение так и получает 0 на двух примерах, хотя в моём симуляторе всё работает.

  • Нули дают за то, что посылаешь команды после смерти, или за то, что возвращаешься на место, на котором уже был. Например, для фигуры из одного гекса любой поворот - это instant death. В результате я достаточно уверен, что ни того, ни другого в моих решениях нет. Сервер же считает иначе.

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

Из смешного:


  • Помня приключения лямбда-лифтёра, начал писать сетку на основе персистентных структур данных и безбожно гонять их туда-сюда в функциональном стиле. В конце второго дня вдруг понял, что нигде этим свойством НА САМОМ ДЕЛЕ не пользуюсь и, помня всё того же лифтера, где переход от List<List<enum>> в byte[][] давал прирост в 40 раз, переписал всё на обычный массив булей, выкинул все свои свёртки и заменил циклами. И получил пару часов потерянного времени, новые баги и падение в скорости. Ничему идиотов жизнь не учит.

  • В итоге я на функцию начальной позиции (3 строчки) потратил суммарно раз в 10 больше времени, чем на поиск лучшей позиции и A*, вместе взятые.

Итог: нужно лучше готовиться + играть без команды по-своему интересно, но большая доля фана и мотивации уходит. Особенно если ты плох))

Репо с ужасным кодом: https://bitbucket.org/belyaev.mikhail/icfpc2015

P.S. Для оценки того, насколько данный вариант тетриса является больным на всю голову, видео:

Tags: c#, f#, icfpc
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

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