Это пятая часть моей серии отчётов об ICFPC 2020. Остальные части ищите здесь:

1. предисловие;
2. день первый;
3. день второй;
4. день третий;
5. день четвёртый (это то, что вы сейчас читаете);
6. итоги и выводы.

20-е июля, понедельник, Z-15:30. Гоняемся за багами в модуляторе

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

Весь этот код был покрыт какими-никакими, но тестами: закодировали всё, что упоминалось в сообщениях инопланетян, дополнив проверками \(mod(dem(x)) \equiv x\) и \(dem(mod(x)) \equiv x\) для нескольких известных нам \(x\). На самом деле, модуляция списков — дело несложное. Там всего два правила:

ap cons x y  ==  11 (mod x) (mod y)
nil          ==  00

К примеру (числа не модулированы для читабельности):

[]  ==  00
[42]  ==  11 42 00
[42, 13]  ==  11 42 11 13 00
(42, 13)  ==  11 42 13

Именно с последними двумя примерами у нас и возникли проблемы. Дело в том, что Python-код вместо честного cons использовал встроенные списки. Следовательно, он не делал различий между списком двух элементов и парой двух элементов — а ведь они должны модулироваться по-разному! Этот баг частично маскировался демодулятором, который «срезал углы», игнорируя nil-ы.

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

Теперь у Codingteam есть пушки!

Стратегия пока что простая: на каждом ходу наш корабль стреляет в первого попавшегося противника. Всё. Этот подход будет держать нас в районе 25-го места лидерборда в течение всего следующего раунда.

Тем временем в чате появился pink-snow и, вдохновившись нашей с IngvarJackal-ом активностью, тоже включился в работу над ботом: IngvarJackal поручил ему завести корабль в угол защищаемой области и висеть там. unclechu смотрел на визуализации боёв и пытался вникнуть в механики игры. У меня было далеко за полночь, до конца очередного этапа оценивания оставалось всего полчаса, и я встал перед выбором: лечь спать и проснуться только к концу контеста, либо попытаться дотянуть до появления «восточных» сокомандников и помочь им поскорее влиться в разработку бота. Второй вариант показался мне более разумным вложением усилий, и я принялся выделять стрельбу в отдельный модуль, чтобы проще было экспериментировать.

Z-13:00. Только бы нам ночь простоять да день продержаться

Пока я возился, IngvarJackal успел выставить «стреляющего» бота против соперников, дать ему сыграть пару десятков игр, и откатиться обратно к не-стреляющему боту: похоже, из-за выстрелов корабль сильно перегревался, что увеличивало расход топлива и приводило к падениям на планету. Закончив с рефакторингом, я принялся смотреть чужие игры, чтобы понять, что происходит с температурой и топливом. А тем временем…

<xxx> конец стейджа
<xxx> мы на нулевом месте
<xxx> выше первого!

Мы ничего не знали про начальные параметры кораблей, были только догадки: первый параметр — количество топлива, второй — количество пушек, третий неизвестно, четвёртый — тоже неизвестно, но обязательно больше нуля. Я принялся выяснять, сколько пушек можно взять при 150-и единицах топлива. Для этого я делал сабмишен, в котором просил, например, 64 пушки. Ждал 5 минут, пока это сбилдится и пройдёт тесты. Когда тесты падали, я уменьшал количество пушек вдвое и снова отправлял сабмишен. Спустя пять минут опять корректировал количество, и так далее… Понадобилось полчаса, чтобы выяснить: при 150-и единицах топлива можно взять 44 пушки.

Следующей задачей было выяснить, как пушки вообще влияют на бой. Я принялся смотреть все игры подряд и скоро сформировал теорию:

1. пушки греют корпус, причём и у стреляющего (обязательно), и у цели (только при попадании с небольшой дистанции и, похоже, ещё каких-то условиях);

2. как только корпус достигает критической температуры (которая в параметрах корабля значилась как x6), топливо начинает буквально испаряться.

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

А эти самые противники тем временем научились создавать целый флот и подрывать корабли, нанося нам дополнительный урон. Я тоже так хочу!

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

Z-09:00. Конец очередного этапа оценивания

Под конец раунда у нас начинается полный бардак: у меня вроде как работает ограничение радиуса, а у IngvarJackal-а работают новые орбиты, но при этом его версия не стреляет (чтобы не раскалять корабль), а моя не содержит последних наработок по орбитам. Сабмитим мою, но в целом это, конечно, фейл.

Оставив мне коротенький список TODO, IngvarJackal уходит вздремнуть, а я добавляю простенькую защиту от перегрева и берусь выяснять, как создавать больше кораблей. pink-snow тем временем научился загонять корабль в угол карты и удерживать его там; IngvarJackal надеялся использовать эту стратегию для корабля-защитника, чтобы соперникам сложнее было нас доставать.

Тут просыпаются ForNeVeR и portnov, и я быстренько пересказываю им всё то, что успел узнать про игровые механики. ForNeVeR решительно отказывается лезть в Python. Вместо этого он берётся доводить наш Haskell-код до состояния, пригодного к сабмиту; в этом ему помогают unclechu и portnov. Настроение подавленное: суббота была потрачена впустую, прогресс за воскресенье неутешительный, и теперь, похоже, придётся делать финальный сабмишен на Python.

Тем временем моя работа над дополнительными кораблями даёт первые плоды: мне удаётся «отпочковать» четыре новых, но они тут же падают, т.к. у них нет ни топлива, ни времени на коррекцию орбиты. Следующая задача: «отпочковывать» корабли только после выхода на стабильную орбиту. Модуль IngvarJackal-а содержит все необходимые вычисления, нужно только немного порефакторить (famous last words).

До окончания контеста остаётся всего пять часов, поэтому всем, кто подаёт голос в чате, я тут же выдаю задание: форкнуть мою ветку и экспериментировать с «роями» кораблей, пытаясь понять, как заставить их стрелять — пока что все мои попытки выдать «отпочковавшимся» кораблям оружие заканчивались провалом. IngvarJackal, проснувшись, тоже берётся за эту задачу. Не падать мы научились, теперь нужно научиться топить противника в море огня!

Просыпается Akon32 и берётся выяснять, как с помощью самоподрыва наносить противникам максимальный урон. Кажется, он даже успеет что-то написать, но мы это так и не смержим ☹

Незаметно подкрадывается Z-4:00, то есть начало предпоследнего раунда оценивания.

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

К Z-2:00 у нас не готово ничего нового, и мы сабмитим тот же код, что и в Z-9:00. Вся команда в мыле, все пытаются заставить «отпочковавшиеся» корабли хотя бы разок пальнуть по противнику. Лидерборд замерзает, мы на 37-м месте. Возможности сравнить своего бота с чужими больше нет; дальше придётся нащупывать прогресс вслепую.

В Z-00:26 выясняется, что в моей ветке баг: в перечне кораблей нет «отпочковавшихся». Не удивительно, что они не стреляют! В срочном порядке делаю cherry-pick исправления от IngvarJackal и пушу. Секунду спустя IngvarJackal пишет, что переименовал одну из переменных класса с состоянием игры. Аргх! Снова git cherry-pick, опять git push, скрещиваю пальцы.

Не дожидаясь результатов, в Z-00:11 делаю очередной сабмишен, в котором «отпочковавшиеся» корабли палят по ближайшему противнику. IngvarJackal мержит мои изменения и сабмитит свою собственную реализацию «роя кораблей». Впрочем, его «осы» не умеют «жалить», так что финальным сабмишеном будет либо тот, что я сделал только что, либо тот, что мы отправляли в Z-9:00. До конца соревнования остаются считанные минуты, поэтому я в спешном порядке запускаю бои между всеми парами сабмишенов: нашим старым и двумя новыми.

Наступает час Z, мы делаем F5, и сайт организаторов генерирует уже знакомый нам мемасик (выделение моё):

ICFP Programming Contest 2020 has started 3 days ago, will end a few seconds ago

А дальше я просто цитирую чат:

[Z+00:02] <xxx> капец
[Z+00:02] <xxx> я в одном месте distance не поменял
[Z+00:02] <xxx> то есть все последующие сабмиты тоже багованные

Из-за банальной опечатки последние 9 часов работы улетают коту под хвост.

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