Предыстория
Поучаствовать в самом знаменитом нестандартном ежегодном контесте по программированию ICFPC я лелеял мечту последние три года, с тех пор как узнал про его существование. К сожалению, его традиционно проводят в июне, и все прошлые годы он попадал мне аккурат на сессию — причем проблемную, к которой приходилось готовиться. Теперь же, в 2011 г., с сессией абсолютно никаких проблем у меня не наблюдалось, и я решил-таки собрать команду.
С командой вышел пробой (забегая наперед, он и определил наши результаты). Я очень хотел, чтобы все тиммейты были в Киеве, чтобы мы могли лично собраться и устроить брейнсторм с ноутами на три дня :) Среди моих знакомых умных людей с разными знаниями и умениями было дофига (а как показывает ICFPC, никогда не знаешь, кто именно тебе понадобится — физик, математик или биолог, так что я решил собрать всех). Как выяснилось в процессе поисков за 2 месяца до контеста, у одного умного человека — диплом, у другого — сессия, у третьего — работа, у четвертого — отъезд в США на интерншип на неделю раньше меня... так что в итоге осталось 5 человек, включая меня. В отчете остальные фигурируют как Саня, Сергей, Андрей и Виталик.
Буквально вечером в день перед контестом мне в аську постучался
![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
sharpc и спросил, не нужны ли нам вольные стрелки. Вольные стрелки нам, конечно же, были нужны :) Правда, на следующий день
sharpc прочел задание, сказал, что он предпочитает раскапывание и реверс-инжиниринг (а-ля ICFPC 2010), а задача этого года его как-то не прет. Так мы и остались впятером.
Названий почти никто не генерировал, так что мы остановились на предварительном
Code Cercopithecoids (это обезьяны, если что :) ). Правда, потом название вынужденно сменилось в процессе контеста на
Bastard, см. далее ;) А пока что мы создали
репозитарий на гитхабе, документ в sync.in и конференцию на jabber.ru. Было принято решение название нигде не светить, чтобы наш репозитарий не нагуглили, а то про-аккаунта на гитхабе ни у кого нет. Всеобщий язык - C#.
Задание
Вкратце, для тех, кто не читал: организаторы смешали M:tG с функциональным программированием и назвали то, что получилось, Lambda: The Gathering. Есть по 256 ячеек у каждого игрока, в каждой лежит значение (либо функция, либо число — которое, в принципе, есть нуль-арная функция) у каждой есть хп (от -1 до 65535, изначально 10000, ячейка с хп <= 0 считается мертвой). И есть набор из 15 видов карточек с функциями. За один ход можно выбрать свою ячейку, выбрать любую карту, и применить либо ячейку к карте, либо карту к ячейке, положив результат в ячейку (если действие занимает больше 1000 применений функций, оно обрывается). Выигрывает тот, кто либо вынес все ячейки противника, либо после 100000 ходов имеет больше живых. Карты можно кратко описать так:
Стандартные комбинаторы Шейнфинкеля для тьюринг-полноты:
- I x = x
- K x y = x
- S f g x =
h <- f x
y <- g x
return h yФункции работы с числами:
- zero = 0
- succ x = x + 1
- dbl x = x * 2
Функции работы с данными ячеек — своими и вражескими. Стоит заметить, что, чтобы передать индекс ячейки карте, его нужно сначала вычислить где-нибудь с помощью succ и dbl, так что ячейки с маленькими номерами становятся критично важными для жизни: вся существенная работа идет с их использованием. Чтобы жизнь малиной не казалась, организаторы сделали так, что обращение к вражеским ячейкам происходит не по номеру j, а по номеру 255-j, таким образом, чтобы добраться до жизненно важной для противника ячейки 0, нужно сначала набрать у себя число 255, а на это уходит время. На практике это ограничение мы потом хитро обошли :)
- get i = f[i] // получить данные из своей ячейки i
- put x = I // не использует аргумент. Используется для быстрой очистки своих ячеек.
- inc i =
++v[i]; // увеличить хп своей ячейки на 1
return I
- dec j =
--v'[255-j]; // уменьшить хп чужой ячейки на 1
return I
- copy j = f'[j] // получить данные из чужой ячейки j.
// Единственная карта, нарушающая правило "255-j"
- revive i =
v[i] <- 1 // оживить свою мертвую ячейку, установить хп в 1
return IФункции взаимодействия ячеек:
- help i j n = // помочь одной своей ячейкой другой
v[i] -= n;
v[j] += 11*n/10;
return I
- attack i j n = // атаковать чужую ячейку за счет своего хп
v[i] -= n;
v'[255-j] -= 9*n/10;
return I
- zombie j x = // превратить чужую мертвую ячейку в зомби
v'[255-j] <- -1
f'[255-j] <- x
return IКарта zombie стоит особняком. Семантика её работы такова: если чужая ячейка уже мертва, то мы можем превратить её в одноразового зомби, записав в неё свой код. В начале каждого хода каждого игрока движок игры проходится по всем его картам, если находит зомби — выполняет его код на аргументе I, и после этого превращает карту в обычную мертвую (хп = 0, значение = I). Самое интересное то, что во время зомби-фазы семантика функций в коде зомби меняется — они начинают вредить противнику. А именно: inc не добавляет ему хп, а отнимает, dec не отнимает у нас хп, а добавляет, help отнимает у одной карты n хп, а у второй
отнимает 11*n/10, attack отнимает у его карты n хп, а нашей
прибавляет 9*n/10. Весело, правда? :)
Полная версия задания лежит на
официальном сайте, если кому интересно. Там, кстати, умилительные картинки карт :) Организаторы постарались на славу, стиль M:tG выдержан.
Пятница, 17 июня
В период с 9 до 11 утра все, кроме Андрея, собирались у меня в квартире. Андрей мог подъехать только к часу. Впрочем, это было не очень существенно, поскольку мы все время тратили на разборки с заданием и принципами обращения с этой системой вообще. Обычно я сидел и объяснял суть карт одному человеку, потом в квартиру являлся еще один, все объяснения начинались сначала... и так до 12 дня. К полудню из чтения примеров и игр с эмулятором стало ясно следующее:
- нам нужно, чтобы кто-то сел и закодил движок-эмулятор правил игры, чтобы проигрывать в нем ходы свои и вражеские, и всегда знать, что творится на поле.
- разработать стандартные конструкции-комбинаторы в этой системе (типа "вечный цикл с непустым телом и полезными действиями", "применение слота к слоту" и пр.)
- разработать стратегию поведения бота.
Сергей с Виталиком сели за стратегию. Мы с Саней — за комбинаторы на бумажке. Движок писать никто не хотел, но он нам пока был не критичен, поэтому его отложили до приезда Андрея. Как я сейчас понимаю, это была стратегическая ошибка: из всей команды мы с Саней лучше всех понимали семантику поведения функций, а я — их ФП-подноготную, так что движок надо было сесть мне и закодить за 2 часа. Саня, как самый опытный геймер из всех, бегал периодически к Сергею, и они вместе спорили над стратегией, я, как не имеющий особого опыта в играх вообще, не вмешивался :0
Примерно два-три дня. Приезжает Андрей, мы в очередной раз объясняем ему тонкие моменты в правилах и садим за движок, предварительно согласовав типы данных. К этому моменту у нас готово следующее:
Вечный цикл, хранящийся по номеру index:
S (get) (S f I) indexf - по вызову тождественна с I
Чтобы предварительно получить данные из другой ячейки, нужно набрать ее номер и применить get — это операция копирования. Всунуть эту конструкцию в код так, чтобы она выполнялась при вызове, постоянно выбирая свежие данные ячейки, нереально: когда строится выражение, как только мы получаем закрытый терм, он тут же, собака, выполняется, и заменяется на результат. Так что обращаться к переменным "по ссылкам" мы так и не научились.
Вместо этого разработали так называемую "регистровую арифметику": ячейки 0, 1 отводятся под регистры, в них кладутся ценные данные (обычно — большие константы для help/attack, а также адреса других ячеек — двойная адресация), а потом при наборе выражения просто делается get 0 или get 1, и получаем кусочек формулы. С помощью этого подхода была разработана процедура Apply: применение слота к слоту:
APPLY i j:
* j -> #0
* get -> #0
* K -> #i
* S -> #i
* #i -> get
* #i -> zeroВообще, конструкция "окружить что-то в К, а потом в S", используемая в комбинаторном исчислении, отлично помогала при реализации отложенных вычислений в цикле.
К этому моменту Сергей с Саней, долго ругаясь по поводу того, что и когда нам выгоднее делать, поняли, что можно делать help i i, что делает прирост хп на 1.1*n. При достаточно большом n, если засунуть это в цикл, можно получить в нулевой ячейке 65535 за один ход, если подготовить константу n, например, в #1.
S(K(S(K(help(zero)(zero)))(get)))(succ) zero — одноразовый вариант
S(K(S(K(help(zero)(zero)))(get)))(get) zero — в #1 индекс ячейки с числом, формула копируется get`ом.
Они планировали использовать это в защитной стратегии (или нападающей с помощью attack), если набрать сначала 65535 в #0, а потом циклическим help распространить хп от #0 до #255. После этого за счет своего хп можно и атаковать. Весь вопрос был в том, как разработать универсальный цикл.
Универсальный цикл у нас был готов только к 6 вечера, и выглядел он стремно:
#ind: S (S (K(get)) (K(ind))) (S K f) tf — функция от одного аргумента (возможно, каррированная). Этот последний аргумент t передается циклу и запускает его на выполнение. Цикл хранится по индексу ind, и этот индекс намертво забит в теле цикла.
Мы думали пойти дальше, придумать цикл с фиксированным кол-вом итераций и еще более сложные конструкции, но потом оказалось, что это никому не нужно: решили более сложные конструкции реализовывать в шарповом коде за несколько ходов игры. Выводящий и оптимизирующий компилятор на Haskell писать мне дико не хотелось :)
Кстати, о движке. Процесс его написания выглядел следующим образом:
- Андрей что-то кодит некоторое время
- Андрей вскакивает и бежит задавать вопрос
- Андрей получает ответ, задумывается, ходит по комнате, потом замирает, орет "Бля! Я понял!" и бежит обратно за ноут :)
Андрей уехал в 7 вечера вместе со всеми, реализовав (с багами) около 80% эмулятора. Остаток я потом писал и исправлял сам в следующие 2 дня.
Стратегии и методы, которые сообща рождала фантазия Сергея, Сани и Виталика, к вечеру становились все изощреннее :) Я думаю, если бы все это реализовать в многокритериальной системе принятия решений (как одно время предлагал Сергей — все угукнули и решили оставить на фиг мечту закодить ее за трое суток), бота можно было бы выпускать на чемпионат мира по LtG.
Например, они предлагали следить за константами, которые строит противник. Если они нам нужны — копировать их через copy, если нет — грохать ячейки с константами, а то мало ли что :) Если бы написать анализатор формул противника, можно тырить и чужой код тоже. Если нет анализатора — можно грохать и зомбировать любую ячейку с длинным кодом.
Многокритериалка разрабатывалась долго и мучительно, в синке от нее остался длинный текст, описывающий разные критерии успешности и планы выполнения. Вплоть до субботы предполагалось, что мы реализуем сложное переключение с плана на план. Но основной стратегией еще с пятницы оставался zombie rush. В какой-то момент, когда мы полностью представили себе мощь зомби, Саня написал большими буквами на листе бумаги "ZOMBIE RUSH", и мы прикололи его на стену, это стало движущим моментом стратегии =) В какой-то момент предполагался zerg rush (нахеллять себе ячейки, а потом в цикле бить противника), но все-таки решили остановиться на зомби.
В 7 вечера все разъехались по домам и принялись записывать в синк все мысли по ходу. В гите валялся недописанный движок.
Суббота, 18 июня
Начинаются фейлы. Во-первых, собраться вместе уже не получается: негде. Во-вторых, Виталик и Андрей отпочковались от команды: один по причине сессии (и потере надежды разобраться в последующем коде), второй по причине работы. Движок дописывать приходится мне, но я пока трачу день субботы на то, чтобы реализовать в коде все придуманные комбинаторы и планы, в т.ч. разнообразные циклы. На данный момент (середина дня субботы) я единственный в команде, который ясно представляет, что за хрень там валяется в гитхабе :)
Мы решили-таки зарегистрироваться на неофициальном сервере дуэлей, чтобы тестить наших ботов. Проблема была в том, что истинное название команды светить не хотелось, так что регаться надо было под левым ником. Первым, что всплыло у меня в голове, оказался почему-то фильм Тарантино, так что я вбил в поле регистрации
"Bastard", и так было создано новое имя команде :)
Становилось ясно, что втроем ничего сложного в качестве плана работы мы за два дня не реализуем. Первоначальным вариантом тупой стратегии Саня предложил тупой zombie rush без лечения, который выглядел приблизительно так:
- набиваем константу 4608 в #0.
- атакуем чужую #255 этой константой с помощью какой-нибудь своей бесполезной ячейки (выбрали #8).
- увеличиваем константу вдвое до 9216.
- атакуем еще раз из другой ячейки (#9).
- теперь чужая #255 мертва. Туда
очень быстро начинают засылаться зомби, которые выполняют код типа help i j 9216. Это убивает ячейку j и сильно ослабляет ячейку i.
- повторять засылку зомби до наступления коммунизма.
(Как выяснилось после контеста, мы почти приблизились к идеалу. Единственный шаг вперед, до которого никто не додумался — сделать цикл зомби низкоуровневым, а не высокоуровневым: засунуть в код зомби цикл хелпов со счетчиком. Это была основная стратегия работы сильных команд, которая делала полный экстерминатус менее чем за 1000 ходов: кто-то за 200, кто-то за 300-500.)
Эту стратегию в самом тупом варианте я закодил к 11 вечера субботы. Дальше следовал час игрищ с установленным в виртуалке Дебианом. Организаторы в этом году оказались ленивыми, подготовить даже Live CD им оказалось впадлу, так что они отделались сообщением "Мы надеемся, что все участники в состоянии установить себе Debian squeeze x64". В общем и целом установить Дебиан не так-то и сложно, а вот собрать на Mono 2.6.7 код из нашего солюшена уже гораздо веселее, особенно учитывая, что о "Unit Test Project" монодевелоп представления не имеет, .NET 4 версия в репозитарие Дебиана еще не умеет, Generational GC в ней тоже не реализован, память эта архаика жрет что твой фаерфокс, и запускать полученный файл нужно через шелл-скрипт вида
mono Game.exe. Заскриптовать весь этот процесс мне было лень (в идеале надо было это делать до контеста, а не тратить время в нем — но до контеста никто не знал структуру сабмита решения и его вид), так что процесс подготовки пакета для сабмита каждый раз занимал 20 минут. В первом же сабмите на сервер я забыл поставить восклицательный знак в инсталл-скрипте
#!/bin/sh, так что сабмит падал с ошибкой «Невозможно установить бота, насяльника». К счастью, это быстро обнаружили и исправили.
Тупой бот, к удивлению Сергея (ратовавшего за долгое стратегическое лечение, а не rush) оказался поразительно продуктивен. За два часа он прошел 14 дуэлей, в которых победил в 11, а в остальных трех вылетел с эксепшном в стандартный вывод, после чего был забракован сервером :) Слабые команды эта стратегия выносила подчистую за 10076 или что-то около того ходов. Сильные, естественно, выносили нас.
Через два часа было принято решение поднять константы. Теперь первая атака делалась в размере 1250, а вторая — 10000, и код зомби help i j 10000 убивал как #i, так и #j. Это увеличило скорость работы в два раза: новая версия бота выносила все ячейки противника за 5495 ходов. На этом я обернул весь код бота в try с пустым catch, описал результаты в синке, и ушел спать. На часах было 3 ночи.
Воскресенье, 19 июня
Проснувшись к полудню, первым делом я бросился смотреть скорборд дуэльного сервера. Был приятно удивлен: подавляющая масса зарегистрированных команд была прощелкана нашими тупыми зомбаками как орешки :) Общий счет был 42 выигрыша из 62 партий, после чего сервер опять забраковал сабмит: какие-то три эксепшена все-таки просочились наружу. Но за счет этого тотального выноса слабых команд наш бот стабильно тусовался в топ-30, изредка опускаясь до 50го места или подымаясь до 10го. Был момент, когда мы даже занимали 7ю строчку таблицы — это был наш абсолютный рекорд за три дня контеста.
Сергей открыл код в гитхабе и ужаснулся. Там творился адовый кромешный северный пушной зверек, ибо тупую стратегию я кодил очень-очень быстро вечером субботы, а времени уже не было. Я честно попытался объяснить ему в джаббере, какая кошмарная архитектура там реализована мною поверх не менее кошмарного недописанного движка. Лог этого разговора лежит в
http://code-cercopithecoids.sync.in/documentation, Сергею он в итоге не помог, зато к работе над кодом подключился Саня. Итак, из команды осталось 2 человека.
Как показала ночь с субботы на воскресенье, у бота есть несколько проблем. Во-первых, мы никак не защищаем свои критически важные ячейки: если противник исхитрится и успеет убить нам #0, вся череда зомбостроя прервется навсегда. Во-вторых, часто обе команды что-то делали друг с другом, нарушали нормальное функционирование планов друг друга и впадали в ступор: игра в итоге заканчивалась на 100000 ходу по очкам, то есть по количеству живых ячеек. Конечно, больше их обычно было у нас, но все-таки это 2 очка за партию, а не 6 — если следовать правилам официальных дуэлей, которые будут проводиться между отправленными ботами после контеста.
Строчка
"player 1 wins by 1:252 after turn 100000" повторялась в логах дуэлей все чаще и заметно меня нервировала, хотя это, казалось бы, и была победа, но победа в заступоренном дефе :) Для решения проблемы были предложены 2 новых модуля. Копирую текст из синка.
Revival system1. В каких-то далеких номерах (мб 30, мб 170) мы держим константы с номерами нужных ячеек - emergency array.
2. В случае гибели нужной ячейки - восстанавливаем командой revive і, где і содержится в emergency array.
3. В случае повреждения (гибели ячейки) из emergency array под функционал погибшей ячейки выделяется другая. Таким образом revival system работает до уничтожения почти всех наших ячеек без замедления в работе.
Targeting system1. При отсутсвии у противника ячеек с хп >=10000 в 0ю ячейку помещается максимальное хп из его ячеек.
2. Нужно поддерживать зону высадки
а) Константу 0 нужно сделать в какой-то ячейке сразу
б) Если противник возрождает свою 255ю ячейку в ближайший свой ход убиваем её командой dec 0
3. Также можно рассмотреть противодейтсвие активному отжеру: если у противника достаточно ячеек с высоким хп - увеличиваем константу в 0
тут сложно подобрать критерии когда стоит менять константу
4. Можно подумать над обдуманным выбором целей атаки, но это в последнюю очередь.
Revival system писал уже Саня. К этому моменту, поскольку нас осталось двое, мы уже тупо сидели и общались вслух по скайпу, передавая код друг другу коммитами через гитхаб или, в некоторых случаях, тупо копируя пару строк в чат скайпа. Получался такой очень распределенный репозитарий :)
3-6 часов дня. Зомби-бот с Revival system прочно держится в топ-30, выигрывая 23 партии из 31. К вечеру мы начинаем работать над таргетингом... и обнаруживаем, что баги в движке не всегда правильно определяют состояние поля. Это был трындец: с одной стороны Саня пытается найти, какая ошибка в таргетинге заставляет партию все равно зацикливаться до 100000 хода, с другой стороны я лихорадочно исправляю движок, подгоняя его под правильную семантику тех или иных мелких моментов правил (типа "нельзя inc`ать мертвую ячейку"). Вечер воскресенья прошел в сумасшедшем режиме write-only: в общем итоге на сервер было сабмитнуто 5 разных версий бота с теми или иными версиями выбора целей для атаки зомби-хелпом. Что самое смешное, по производительности они не особо отличались: обозначилась некая стабильность, то бишь список команд, которых мы выносили регулярно (Wile E., ciklum, notogawa, Ria Mitsuru, coding_monkeys), и команды, которые регулярно выносили нас (Joho, Platinum Anger, atomic do $ save Madoka, Punch Jordan in the Face). Один раз мы даже выиграли у shinh3, но это, наверное, была какая-то ошибка :) В 6 часов вечера организаторы заморозили скорборд. Для истории остался скриншот с нашей командой на 7м месте:
К 12 ночи создалась патовая ситуация: есть две версии бота, со старой и новой targeting system. Новая теоретически работает лучше (так, слабые команды она выносит за 4900 ходов, а не за 5025), однако в ней, судя по всему, еще остались баги: когда бота запустили на сервер, он первые четыре дуэли со средними командами продул вчистую. И старая, которая работает средненько, но надежно. Саня после вечера дебага и кода сказал, что тут уже без разницы, оставил на меня выбор, и свалил спать. Дуэли проводятся раз в 10-15 минут, так что мне оставалось подобрать момент, когда сабмитнуть на сервер дуэлей старого бота и просидеть полтора часа, держа мышку на кнопке отправки в гугл-форме официального сабмита, чтобы, возможно, заменить официальный сабмит с нового на старый. В 2:45 (15 минут до конца контеста) я принял решение, что старая версия выиграла по количеству побед у новой, нажал "Отправить" и упал спать. Через четыре часа приходилось вставать и переться в универ на экзамен :)
Заключение
Официальное тестирование будет длиться всю эту неделю. В официальной форме отправке мы фигурируем как
Bastard (aka Code Cercopithecoids). Лично я рассчитываю на топ-30 и второй раунд, а дальше уже как повезет.
В 2012 году надо будет собрать надежную крепкую классную команду и всех порвать :) Киевляне, кто за?
P.S. Да, а еще я забил на раунды TCO и Russian Code Cup. Писать их все равно было бессмысленно, ибо следующий раунд TCO через неделю я должен был бы писать в самолете, а финал RCC в сентябре, в случае прохода, — в другом самолете :) А на ICFPC больше фана, чем в них двоих, вместе взятых.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
