ICFP 2014 micro-report
Собственно, уже отоспавшись, можно подвести краткие итоги прошедшего конкурса: ICFPC торт (c) :)
Нам удалось хоть с чем-то поучавствовать в lightning division, и собрать не самое плохое финальное решение.
В первые сутки мы у нас получилось собрать компилятор некой упрощённой схемы в gcc (мы назвали его "intermediate lisp"), на котором я, в последние несколько минут до окончания lightning round что-то сумел изобразить: пакман бодро оббегал примерно четверть карты и циклился на большом круге :) Тем не менее, это решение было существенно лучше, чем ничего, поэтому оно и ушло.
Вторые сутки прошли в битве с багами компилятора, которые не давали нормально спрограммировать AI. Я чёто там окончательно запутался с этими environment frame'ами в варианте LDF + AP / LD + AP, и ситуация казалась уже почти безвыходной, но её спас sectoid, когда сообразил, что первый вариант создаёт кадр, а второй восстанавливает environment на момент сохранения замыкания. Так что, благодаря ему, у нас в воскресенье, наконец-то, появился нормальный intermediate lisp.
На третьи сутки мы, наконец-то, приступили к делу. Я начал писать AI, turtle и grep_z занялись привидениями, а sectoid сначала дофиксил ilisp, а потом, с моей подачи, мы вообще решили упразднить этот ilisp нафиг и транслировать уже напрямую из CL. Нахрена я вообще изначально придумал эту цепочку CL -> ilisp -> gcc, я уже не могу понять, очевидно же, что середина здесь лишняя. Ну, бывает.
Итого, к ночи воскресенья пакман уже умел проходить уровень из эмулятора оргов, но классические blinky, pinky, inky и clyde из hall of fame его жрали без шансов. На утро понедельника я переделал pathfinding на гибрид волны + тупого перебора направлений, и пакман уже стал намного бодрее выполнять поручения, вроде: догнать синее привидение, побежать к power-pill (если рядом гоуст), собрать фрукт и тд. Но, разумеется, вылезла проблема cycles limit на ход, которую я решил уменьшением длины волны, хотя, конечно, надо было просто закешировать по-максимуму всё что можно на этапе инициализации.
Тем не менее, в итоге, буквально за 15 минут до окончания контеста наш пакман впервые одолел классическую карту из scoreboard со счётом в 10000 очков! При этом, правда, результат на proton-pack у него несколько просел, но не суть. А на ghostbusters я в тот раз решение не сабмитил.
Вот с последним, кстати, любопытная история. Солюшн, набравший почти 30к очков (5-я место), походу, там был достаточно старый, а вот финальный, насколько мы потом поняли из прогонов в эмуляторе, чуть ли не первое место бы взял :)
Ну как-то так :) Какое-то высокое место в финальном чемпионате у нас вряд ли будет (хотя у меня есть надежда на наших приведений, они почти всех пакманов сжирают из тех, что я видел в доступных репортах), но фана мы получили море, всем понравилось, все мы молодцы!
А теперь выводы:
Самые царские моменты в нашем решении:
- Common Lisp =)
- Транслятор CL -> GCC. Код для пакмана можно писать на хост-языке, для которого есть подсветка, REPL, slime, break, inspect и тп :)
- Две программы привидений с разными тактиками: один преследует, второй идёт на опережение -- зачастую получается эффективно окружать и сжирать покемона.
TODO, который просто не успели по времени:
- Использовать этап инициализации для кеширования всего, что только можно, а не считать в рантайме. Например, всех доступных соседей ячейки.
- Использовать в стратегии время, оставшееся до окончания срока действия таблетки или фрукта. В финальном сабмишне они просто игнорируются.
- Прогнозировать будущую позицию гоустов по их направлению движения и учитывать это при пасфайндинге.
- Поддержать хвостовую рекурсию в GCC.
Основные провалы, по моему мнению:
- Надо было сразу транслировать CL, без всяких промежуточных языков, это же так очевидно :(
- Надо было с первого же дня написать симулятор игры.
- Надо было не начинать со сложных алгоритмов для привидений, а сначала поэкспериментировать с очевидными: "страж таблеток", "патруль", "тупой преследователь + перехватчик", комбинации их, опять же.
- Плохой "общий кругозор", никто ничего не знал про SECD-машины :)
- Научиться пользоваться инструкцией SТ. Мы про неё какое-то время думали, но я так и не смог допереть, начерта она там вообще нужна в виде SETQ, а не RPLACA / RPLACD. Идея-то на поверхности была, и у меня были все шансы догадаться: переписать консы через замыкания! Я же, блин, собственноручно статью давным-давно писал про AVL-деревья на замыканиях. Короче, с деструктивным консом можно было бы логично и реально граф карты с циклами построить, как это сделал Frictionless Bananas.
- Надо больше спать, периодически делать перерывы и, вообще, брать полный отпуск на время контеста :)