Небольшой отчет о том, как мы решали ICFP Contest 2015. Мы участвовали в данном соревновании впервые, однако результат получился довольно неплохой. Можно поискать нас в таблице промежуточных результатов под именем «WILD BASHKORT MAGES». Финальные результаты ожидаются в течение нескольких ближайших недель, когда организаторы протестируют все решения на полном наборе тестов.

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

Введение

Нас в команде было трое, если не считать двух кошек — Дамир, Максим и я. Мы с Дамиром — олимпиадники на пенсии, Максим имеет много опыта в написании компиляторов. В качестве предварительной подготовки мы подняли git-репозиторий, немного почитали информации о криптографии (ибо в анонсе про это зачем-то упоминалось), я проверил, что моя Ubuntu на виртуалке работает (я виндузятник, в отличие от сокомандников). Ну и, конечно же, мы хорошенько проспались перед выступлением.

Хотя соревнование длилось трое суток, в данном повествовании все будет разбито на 4 дня в связи с нашим часовым поясом. По нашему местному времени контест начинался в пятницу в 17:00, заканчивался в понедельник в 17:00. То есть, день 1 и день 4 будут слегка урезанными, что в итоге даст ровно трое суток. Время в повествовании примерное, специально его никто не записывал, оно было восстановлено из git-репозитория.

Технические детали нашего решения выделены такой рамочкой.

Если вы не хотите вникать в технические тонкости — можете смело пропускать, если же вам интересны именно детали реализации — их будет так проще найти. Это все дело не было спрятано в спойлеры по причине картинок, на которые все же имеет смысл мельком обратить внимание.

День 1. Начало

Итак, контест начался в 17:00. Ребята уже собрались, я в это время еще на работе, уже собираюсь уходить. Перед уходом пробежал глазами условие задачи. Сначала не дошло, что речь шла про тетрис, было разве что понятно, что мы имеем дело с гексакональным полем, по которому двигаются какие-то юниты. «ИИ для стратежки что-ли надо писать?» — подумал я. К команде подтянулся примерно в 18:00, заглянув по дороге в магазин за провизией и таким стратегически важным ресурсом, как кофе.

Около часа мы обсуждаем условие задачи, Дамир параллельно пишет визуализатор на Python. Понятно, что Python может быть слишком тормознутым для итогового решения, поэтому я начинаю писать базовые операции с полем и фигурками на C++.

Максим решает писать то же самое, только на OCaml. Предполагалось пойти сразу в нескольких направлениях, после чего отсеять явно неперспективные. Да и делать что-либо другое особо было нечего в начале контеста. Как утопический вариант — можно было потом объединить несколько эвристик на разных языках, запускать все на каждом тесте, а затем выбирать лучший вариант.

Около 19:30 готова первая версия визуализатора, можно посмотреть какие тесты заготовили там организаторы. На поле в некоторых из них видны странные послания, уж не power word'ы ли это?

Еще мы там нашли это:

А я тем временем ковыряюсь с выполнением базовых команд над фигурками. Сдвигать-то фигурки по гексагональной сетке может и просто, а вот поворачивать — не совсем тривиально.

В итоге после некоторого корпения над бумажкой и разбора случаев получился следующий код:

	void move_pnt( PAR & p, int dir, int d )
	{
		if (d<0)
		{
			d *= -1;
			dir += 3;
			if (dir>=6) dir -= 6;
		}
		if ((p.Y & 1)==0)
		{
			if (dir==0) { p.X -= d; }
			else if (dir==1) { p.X -= ((d+1)>>1); p.Y += d; }
			else if (dir==2) { p.X += (d>>1); p.Y += d; }
			else if (dir==3) { p.X += d; }
			else if (dir==4) { p.X += (d>>1); p.Y -= d; }
			else if (dir==5) { p.X -= ((d+1)>>1); p.Y -= d; }
		}
		else
		{
			if (dir==0) { p.X -= d; }
			else if (dir==1) { p.X -= (d>>1); p.Y += d; }
			else if (dir==2) { p.X += ((d+1)>>1); p.Y += d; }
			else if (dir==3) { p.X += d; }
			else if (dir==4) { p.X += ((d+1)>>1); p.Y -= d; }
			else if (dir==5) { p.X -= (d>>1); p.Y -= d; }
		}
	}

Это очень важная функция. Она сдвигает точку, которую ей подсунули, на d клеточек в направлении dir. После этого операции параллельного сдвига становятся совсем тривиальными, а повороты сделать очень просто. Для этого для каждой клеточки в фигурке надо вычислить ее сдвиги относительно точки вращения по двух неколлинеарным направлениям, после чего найти клеточку, сдвинутую относительно точки вращения на те же самые смещения, только по немного другим направлениям:

Код пришлось немного подебажить, к 22:00 все было протестировано, заодно была добавлена функция вставки и позиционирования новых фигурок на поле, а также проверка на пересечение со стенами и занятыми клетками. Дамир берет мой код и переписывает его на Python для вставки в визуализатор. Максим тоже переписывает мой код на OCaml для использования в своей версии решения.

Ужина, как такового, не было. Перебивались бутербродами с колбасой и чаем/кофе не отходя от рабочих мест. Максим вспомнил, что в холодильнике лежит курица и ее надо бы приготовить и съесть, пока она не испортилась. Но мы решили, что ничего с ней до утра не случится.

Полночь. Дамир прикрутил к визуализатору возможность проигрывать решения: теперь можно скармливать ему давар, после чего по ходам отслеживать что на доске происходит. Правда, пока давара у нас нет, смотреть нечего.

К 03:00 я дописал код нахождения всех позиций, куда можно приткнуть фигурку перед тем как «заморозить». Вместе с последовательностью команд, которая к данной позиции приводит. Максим реализовал все базовые операции на OCaml'е, попутно исправив пару багов в моем коде. Дамир добавил в визуализатор возможность интерактивно управлять фигурками с клавиатуры: т��перь в этот тетрис можно натурально играть! И сохранять решения.

К сожалению, на игры уже сил не хватает — пора спать. В этот день на сне мы решили не экономить.

День 2. Эпизод 1: Lightning Division

Просыпаемся в районе 11 часов утра. Утренний кофе — и опять за работу.

Дамир достает из закромов С++ библиотечку для работы с JSON, я ее прикручиваю, добавляю генератор псевдослучайных чисел, тупую эвристику выбора хода (выбираю тот, где фигурка в итоге окажется ниже всего). И вот оно — готово решение, которое делает хоть что-то! Немного тестирования, дебага и прогон по тестам квалификации — и к 14:00 у нас есть первый давар.

За это время Дамир тоже без дела не сидит — прокачивает визуализатор, фиксит баги. Теперь в нем можно прокручивать решения вперед и назад, в том числе и пошагово. Максим все это время ковыряется в своем OCaml решении.

Время обеда. На обед курицу готовить лень, поэтому заказываем две пиццы. Да и времени, на самом деле, особо нет — в 17:00 заканчивается так называемый Lightning Division. Это особая номинация, в которой принимались решения, написанные всего за сутки, которые уже что-то решают без учета power-word'ов. И очень хотелось туда что-то заслать, тем более что что-то уже было на руках.

Как только первые решения были получены, Максим начал разбираться с вопросом «А как тут вообще давар и решения отправлять?», а мы с Дамиром на визуализаторе просматриваем что там наш тупой солвер нам нарешал. В принципе, ведет себя вполне адекватно, кое-какие очки даже получает. На некоторых тестах наблюдаются забавные квантовые туннельные эффекты для фигурок, у которых точка поворота отстоит далеко от, собственно, самой фигурки:

К 15:45 параллельно с поглощением пиццы было сделано: я добавил в решение эвристику, которая дополнительно учитывает пропадающие линии, Дамир привинтил к моему решению работу с командной строкой согласно спецификации, Максим написал автоматизированную отправлялку решений пачками прямо на сервер.

Пора готовить архив для Lightning Division. Максим пишет Makefile и README, собирает тарбол. Мы с Дамиром просматриваем давар, полученный с последнего решения. Вроде бы ошибок особо нет, тарбол собран и протестирован, и в 16:47 мы отправляем архив на сервер организаторов вместе с последними решениями.

Тут Дамир находит явно неадекватный давар. Начиная с некоторого момента решение начинает вести себя очень странно — промахиваться мимо дырок и лепить фигурки на потолок. И это безобразие происходит после того, как полностью заполняются и удаляются две соседние строки! Почти сразу стало ясно, что это ничто иное как баг в моем C++ коде в том месте, где происходит удаление заполненных строк. То есть в визуализаторе оно удаляет все строки правильно, а в моей реализации одна из строк остается — отсюда и рассинхронизация.

Дальше все происходит как в голливудском кино (тайминги примерные):

16:50 я быстро, но аккуратно правлю баг, перетестирую новой версией все задачи.
16:54 коммичу изменения в git, Дамир пытается утянуть мои исправления, чтобы проверить в визуализаторе. Но он сделал некоторые изменения и по запарке забыл их закоммитить, в итоге после pull'а у него получается какая-то каша и надо разруливать страшный merge. Просто Дамир всю жизнь сидел на hg, и на git руку не набил.
16:55 Максим спешит на помощь Дамиру, понимает, что у него там какая-то жесть, спешит обратно к своему компу. Я тем временем прогоняю проблемный тест у себя — вроде больше глюков нет.
16:56 Максим утягивает мои правки и быстро собирает новый тарбол.
16:58 запускает скрипт отправки давара последнего решения на сервер.
16:59 загружает тарбол на сервер, я тем временем слежу за временем вот тут. В скрипте отправки давара у нас задержка между отдельными тестами, чтобы нас ненароком не забанили (попортила она нам нервы!), поэтому отправка тормозит. Счет уже идет на секунды: 5, 4, 3...

Ух, успели! За 3 секунды до дедлайна. Мораль: использование малознакомых инструментов может создать проблемы на ровном месте, в самый ответственный момент.

Чуть позже мы все-таки поинтересовались у организаторов, успели мы или нет. Пришел ответ:

<galois_kiniry> We see two tarballs submitted by your team, at 11:47 and 11:59. Both are well-formed.
<galois_kiniry> But is C++ really the programming language of choice for discriminating hackers? ;)

День 2. Эпизод 2: Змейки, цилиндры и конечный автомат

Ну, один из самых напряженных моментов позади, пора придумывать нормальное решение. Например, которое учитывает использование power-word'ов. На самом деле, идея уже давно витала в воздухе, чуть ли не в первые часы контеста, но мы решили развивать ее после Lightning раунда — для него использование power-word'ов было не нужно. Мы засели на часик, формализовали идею, в итоге получилось следующее:

Пусть мы каким-то образом ставим фигурку в конечную позицию и «замораживаем». К этой позиции можно прийти очень большим числом способов — мы можем изначально хоть по всему полю протаскать нашу фигурку, набивая power-word'ы перед тем, как поставить ее на нужное место. Этот оптимальный путь мы можем поискать с помощью динамического программирования.

Нам в состояние динамики надо запихнуть всю информацию о положении фигурки. А именно: положение точки поворота, текущий поворот, а также информацию о том, какие команды мы уже вводили, чтобы ловить появления новых power-word'ов в последовательности команд.

Со второй частью состояния отлично справится конечный автомат, построенный следующим образом. Пусть у нас n power-word'ов, тогда состояние автомата можно представить в виде вектора длины n, i-ый элемент которого обозначает длину префикса i-го power-word'а, который мы уже набрали. Переходы между состояниями случаются, когда мы добавляем к строке команд какую-нибудь новую букву. При этом некоторые уже набранные префиксы удлиняются на единичку, другие укорачиваются или даже сбрасываются на нулевую длину. Когда power-word набирается полностью, мы также отмечаем эту информацию в автомате, а в качестве префикса указываем самый длинный, который совпадает с суффиксом.

Пример построения автомата можно видеть на картинке чуть ниже. Тут использованы три слова: aba, acac и bc. На ребрах указаны символы, по которым мы переходим, в скобках обозначается номер слова, которое мы только что набрали.

Power-word'ов у нас мало, букв в них тоже не очень много, поэтому автомат можно строить в лоб, не особо заботясь о эффективности решения — все равно будет быстро.

С первой же частью состояния динамики пришлось попотеть. Дело в том, что когда мы двигаем фигурку до пункта ее назначения, нам нельзя приходить в одни и те же состояния. Всего у нас 6 вариантов действий с фигуркой: сдвинуть влево, сдвинуть вправо, сдвинуть вниз-и-влево, сдвинуть вниз-и-вправо, повернуть по часовой стрелке, повернуть против часовой стрелки. С «сдвинуть вниз-и-влево» и «сдвинуть вниз-и-вправо» все понятно — как только мы подвинули фигурку вниз, наверх обратно ее затащить уже не можем. Повторения могут быть когда мы двигаем фигурку влево-вправо в одной и той же строке и при этом вращаем.

Получается следующая вещь. Все положения фигурки в строке можно представить в виде прямоугольной таблицы. Ее ширина — ширина поля, а высота — количество возможных поворотов (1, 2, 3 или 6 — в зависимости от симметрии фигурки). При этом верхняя сторона таблицы склеена с нижней — получается эдакий цилиндр. И мы своими ходами перемещаемся с соседние по ребру клеточки. В итоге все ходы на одной строке игрового поля можно представить в виде змейки, которая ползает по нашему цилиндру и старается не откусить себе хвост:

К сожалению, при таком подходе нам пришлось бы хранить в состоянии динамики все посещенные клетки каждого цилиндра. При этом общее число состояний растет экспоненциально. Надо было что-то с этом делать. Мы решили ограничить перемещения змейки следующем образом: если мы ушли с какой-то строчки, то больше ее никогда не посещаем. Тогда всевозможные пути змейки вырождаются в загогулины следующего вида:

Все уже посещенные строки образуют некоторый отрезок (змейка не может телепортироваться, скажем, через строчку). Отсюда — для того, чтобы запомнить какие мы строчки посетили, надо максимум 36 состояний. Добавим сюда еще один параметр: откуда мы ��ришли — слева, справа или сверху/снизу/c-другой-строки-игрового-поля — и этого будет достаточно для того, чтобы змейка себе хвост таки не оттяпала.

Конечно, мы теперь будем перебирать далеко не все возможные последовательности команд, и не все возможные слова мы тогда сможем учесть. Но, мы нарисовали все найденные на текущий момент потенциальные power-слова и увидели, что нельзя набрать только слово watermelon. Решили, что пока обойдемся и без него.

Итого, состояние динамики:

x, y // позиция фигурки, а точнее ее точки вращения
rotation // текущий поворот
rot_seg_left, rot_seg_right // отрезок уже посещенных поворотов
from // откуда мы пришли: слева, справа или сверху/снизу/c-другой-строки-игрового-поля
node // номер вершины из конечного автомата

В каждом состоянии мы считали взвешенную оценочную функцию по трем параметрам: оценка игрового поля когда мы «замораживаем» фигурку, максимальную длину использованного power-слова и суммарную длину всех использованных слов. Второй параметр был добавлен на будущее: чтобы можно было заставлять динамику выбирать путь с ранее не использованными словами (организаторы давали 300 очков за каждое power-слово, если оно встречается хотя бы 1 раз и дополнительные очки (удвоенное количество букв в слове), за каждое повторение).

Суть динамики: для каждого состояния мы считаем максимум оценочной функции, который мы можем получить делая какие-то ходы из текущего состояния до какого-либо «замораживаемого» состояния. Мы пробуем делать всевозможные ходы, рекурсивно их обрабатываем, обновляем оценочную функцию если текущим ходом мы закончили какие-либо слова, выбираем максимум и сохраняем. Довольно тонкий момент для осмысления: казалось бы, информацию о том, какие слова закончились мы получаем из прямого прохождения по рекурсии, но на самом деле всю нужную информацию хранит в себе само состояние динамики. Ну и все найденные слова мы учитываем в обратном порядке их окончания.

Динамику можно считать лениво с использованием мемоизации (ну наконец хоть какой-то намек на функциональщину!). Просто запускаем ее из начального положения фигурки и… нахаляву просчитываем все положения фигурки, где ее можно «заморозить». Если добавить к каждому состоянию символ, по которому надо переходить для достижения оптимума, то можно легко восстановить искомую последовательность команд.

Где-то к 19:00 решение было формализировано, осталось его только написать. Дамир засел писать конечный автомат, а я пишу саму динамику (точнее, большая часть времени ушла на учет ограничений, которые дает нам состояние динамики). Максим продолжает ковырять свою реализацию на OCaml'е.

К 20:45 Дамир дописывает автомат, а я пару минутами позже дописывают динамику. Мержим код, смотрим что получилось. Получился Stack Overflow. Ну накосячил я где-то в динамике, поэтому она циклится. На поиск бага убилось довольно много времени (оказалась глупая опечатка). После этого я начал прогонять всякие тесты и проверять, что решение нигде больше не падает. Делаю commit с исправленным решением в 23:45 вместе с даваром для теста 0. Засылаем его на сервер… и выходим на первую строчку по данному тесту!

В это время мы меняем название команды. На самом деле, изначально мы назывались «Team Bashkortostan». А когда вышли на первую строчку по тесту 0 подумали, что название какое-то некреативное. Переименовались в «WILD BASHKORT MAGES». Вспомнили про курицу, думаем что с ней делать. Решили: если не выкинем ее завтра, то выкинем послезавтра.

Пока я тупил с поиском бага в динамике, Дамир без дела не сидел: немного подкрутил построение автомата, добавил поддержку power-word'ов в визуализатор, написал модуль подсчета количества очков, которые должны дать за давар (этот модуль далее использовался как в визуализаторе, так и извне для автоматического подсчета очков и генерации табличек для сравнения). Работать с визуализатором стало комфортнее некуда:

Максим продолжал возиться со своим решением на OCaml ровно до того момента, когда мы заслали давар теста 0 на сервер. После этого он принял волевое решение забить на свою разработку и сосредоточиться на тестировании решений (чтобы отслеживать не сломали ли мы решение после каких-нибудь «улучшений»), а также поиске новых power-word'ов. Не сказать, что написание решения на OCaml'е было большой потерей времени — скорее это было страховкой на случай если я затуплю со своим решением на С++.

Где-то в 00:15 я добавил в оценивающую функцию еще одну эвристику. А именно — штрафы за создание «дырок» в заполненной части поля. Суть эвристики очень проста: считаем количество таких соседних клеточек, что одна из них заполненная, а другая — пустая. Тогда одинокая «дырка», оставленная на поле, дает штраф 6. После этого решение стало работать гораздо лучше.

Хотя для теста 0 решение было хорошим, с другими тестами возникли некоторые трудности. Дело в том, что текущее решение оказалось тормознутое. Для теста 14 оно работало 3 часа. Забавный момент: я вообще-то хотел запустить решение для теста 13, который гораздо меньше по размеру и всего на 100 ходов (а 14 тест — это та пентаграмма на картинке выше с 500 ходами), но немного перепутал номера тестов. Ну и сижу жду когда оно досчитает. А оно все не досчитывает. Через полчаса работы программы уже стало делом принципа дождаться завершения. А через час после запуска наконец дошло, что я запустил 14 тест, а не 13. Видимо, уже сказывалась усталость. Досчитало оно только к 03:45.

Пока я ждал завершения злополучного 14го теста (сил на кроме как ожидать у меня больше не оставалось, но и не засыпалось), Максим прогнал корректным решением еще немного тестов и попытался заслать их на сервер. Парочку успели проверить, а последний проверяться не хочет. Точнее не понятно что там с ним — таблица результатов просто не обновляется. Кроме того, по некоторым уже засланным тестам счет в таблице результатов и наш собственный немного не совпадал. Дамир сидит ищет ошибку в модуле оценки счета. Уже вроде все перепроверил — нет ошибки. После этого таблица результатов совсем падает — оказалось, что кто-то отсылал на сервер некорректный давар (плохой давар, некачественный) и тем самым поломал проверяющую систему. Организаторы вскоре исправили баг, восстановили таблицу, а участникам сказали больше плохой давар не присылать:

Исправление бага с таблицей произошло примерно в то же время, когда у меня досчитался 14й тест. В обновленной таблице счет по каждому тесту совпал с нашим локально подсчитанным — т.е. баг был не у нас и мы его зря искали.

Заслали 14 тест и он тоже дал очень хороший результат. После этого мы до 06:00 занимались тем, что засылали свежепосчитанный давар, Максим попробовал руками проверить-поискать новые power-word'ы. Новых, к сожалению, не нашлось, зато все те слова, которые были найдены в тестах («Ei!», «Ia! Ia!», «R'lyeh» и «Yuggoth») действительно оказались power-word'ами.

Цель на завтра стала ясна: ускорить текущее решение. Благо, там был довольно большой простор для оптимизаций.

День 3. Оптимизации и улучшения

Проснулись примерно в 15:30. Максим проснулся чуть раньше и наконец приготовил курицу. С картошечкой. Как раз к тому моменту, как проснулись мы с Дамиром. Позавтракали (хотя наверно лучше сказать пообедали (или поужинали?)).

В 16:00 возвращаемся к нашему решению. Оказалось, что Дамиру вчера не спалось и он лег далеко не в 6 утра. Все это время он оптимизировал мое решение. Вынес вычисление значений оценивающий функции в отдельную процедуру и закэшировал (что сильно сократило количество вычислений одного и того же). Для ускорения сравнений структур (и поиска их в std::map) сжал все в один int64. Реализовал эвристику в динамике, чтобы она отдавала приоритет ранее не использованным power-словам. Еще он в целях оптимизации переписал мою динамику, но что-то там сломал. В итоге получилось решение, которое работает гораздо быстрее вчерашнего, но дает гораздо меньше очков.

Что именно сломалось после оптимизации динамики мы так и не поняли, решили не тратить на это время и не ломать голову. Просто взяли и аккуратно перенесли динамику из старого кода поверх всех новых оптимизаций. Исправление было закончено к 17:00. И теперь тот самый 14 тест, что я вчера считал 3 часа, считается за 5 минут!

Запускаем прогон всех тестов. Этот массовый прогон тестов фигурировал под тегом «apocalypse_1».

Примерно в это время приходит понимание, что таскать посчитанный давар через git жутко не удобно. Каждый раз надо коммитить текущие изменения, пушить, потом остальным пуллить давар с репозитория. А в это время уже имеются нестабильные изменения, которые надо стараться в репозиторий не пушить. Короче, одна морока. Поэтому мы решили перевезти хранение давара с git на Dropbox с договоренностью, которая как-то стихийно сложилась уже 2 дня назад: называть посчитанный давар в формате «solution_%PROBLEM_ID%_%TAG%_%TAG_INDEX%.json» и у всех всегда разные теги (чтобы не затирать давар друг друга). За часик все перенастроили. И все вдруг сразу стало гораздо удобнее: сидишь, спокойно пишешь код, а в это время Dropbox в уголку пишет «вот такой-то давар посчитался» и ложит его в соответствующую папочку. Никаких лишних телодвижений!

Еще одна мелочь в пользу Dropbox. Мы как-то не подумали арендовать на время контеста кластер и сидели с тремя ноутбуками. У меня с i5, у Дамира с i3, а у Максима — что-то еще древнее. И когда Максим запускал у себя решение — все остальное начинало подтормаживать. И тут Максим достает из закромов удаленный сервер. Он, конечно, не кластер, но на нем можно было организовать тестирование текущих решений без затормаживания наших собственных машин. Ну так вот, пуллить и пушить на удаленном сервере с риском нарваться на конфликты — не самая хорошая идея (придется разруливать через терминал). А Dropbox там уже стоял. Сказано — сделано. После недолгой настройки удаленный сервер начал тестировать решения на полном наборе тестов, автоматически через Dropbox закидывая на наши машины произведенный давар. Красота!

К этому моменту тестирование на полном наборе тестов завершено. Засылаем давар на сервер и попадаем в тройку лидеров. Фхтагн!

Тем временем, в нашем решении еще есть много чего, что можно улучшить. Основных направлений два: заменить std::map на хэш-таблицы и ускорить вычисление оценочной функции (она вычислялась за O(размер поля), хотя ее можно вычислять за O(количество элементов в фигурке)). Я пишу хэш-таблицу, прикручиваю к решению. Еще я добавляю к оценивающей функции четвертый параметр, так называемый «потенциал» — суммарную длину префиксов еще не законченных power-слов. Это позволяет дополнительно собирать слова между ходами. В 22:30 вроде все готово. С хэш-таблицей тест 14 считается минуты за 3.

За это время Максим написал «долбилку» сервера организаторов для определения новых power-word'ов. Ее принцип довольно незамысловатый:

Запускаем решение со списком слов, подозреваемых на свойство power.
Проверяем полученный давар, что он действительно содержит все подозрительные слова из списка.
Помечаем этот давар уникальным тегом и засылаем на сервер организаторов.
Далее раз в минуту автоматически проверяем таблицу результатов, пока там не появится нужный тег.
По итоговому счету выносится вердикт о «волшебности» использованных слов.

Дамир же изучал в визуализаторе полученный ранее давар. Как оказалось, тесты, в которых много свободного места для нас были хорошими — наша динамика во всю использовало его для набивания power-word'ов. Плохими же оказались тесты, в которых места было мало, фигурки были всяких сложных форм, а общее число фигурок, которые надо было уложить, было большим. Наша тупая оценивающая функция просто как-то их там укладывала и поле довольно быстро забивалось, поэтому на этих тестах мы получали мало очков. В частности, такими тестами были тесты с номерами 4, 9, 13 и 23. Мы решаем для маленького поля прикрутить просчет на 2 хода вперед.

В процессе засылки нового давара мы замечаем две команды в пятерке лидеров с названиями «Hack the pool» и «Hack the loop». И решаем немного пошалить… Переименовываемся в «Hack the poop». Вот он, апофеоз нашего хулиганства:

В официальном irc-чате один из админов возмущается «Ну что за безобразие?», но вроде не банит. Через пару часов переименовались обратно в «WILD BASHKORT MAGES». Посмеялись — и хватит.

03:00. Я реализовал перебор на 2 хода вперед. На самом деле он был написан гораздо раньше, но там, как всегда, возникли баги. Самый первый из них — вот вроде уже все должно работать, а не работает! Сначала думали, что вообще какая-то чертовщина. Потом поняли, что мы идиоты — надо же для второго хода новую фигурку создавать вверху поля. Когда этот баг был исправлен — вроде заработало.

Но работало оно как-то так:

Логика программы примерно следующая: «Если я поставлю одну фигурку слева, а потом еще одну справа — я соберу строчечку...». Поэтому программа ставит фигурку слева. На следующий ход программа думает: «Если я поставлю одну фигурку куда попало, а потом поставлю следующую справа — я соберу строчечку...». Ну и ставит первую фигурку куда попало. На следующих ходах происходит то же самое, п��ограмма как бы говорит нам: «Да успею я собрать эту строчку, чего привязались!». Но такое поведение нам не надо, нам выгодно как можно быстрее расчистить все поле чтобы потом набивать power-word'ы. Решили проблему по принципу «первое слово дороже второго»: даем первому ходу небольшой бонус, поэтому если к какому-то состоянию игры можно прийти несколькими способами, выбирается тот, который приносит больше очков на первом ходу.

Новое решение стало гораздо лучше справляться с 4 тестом. Но, к сожалению, все еще не идеально. Дамир, проверяя в визуализаторе разные значения начального random seed, говорит: «Вот, опять поле забилось». Я подтверждаю: «Да, поле забилось в угол и боится оттуда вылезать». Решили, что надо все-таки проверять на 3 хода вперед. К сожалению, перебор на 2 хода вперед уже очень сильно затормозил наше решение, поэтому его нужно дополнительно ускорять. Но у нас осталась еще одна идея в запасе: ускорение вычисления оценочной функции.

Пока я писал перебор на 2 хода вперед, Дамир придумывал эвристики для того, чтобы побороть тест 9. Суть этого теста сводилась к тому, чтобы накидать на уровень побольше палок, при этом стабильно собирая строки и, по возможности, не заваливаясь. Наше решение работало как-то так:

При этом оно заваливалось на 35 ходу из 400 возможных. К сожалению, ничего рабочего в тот поздний вечер Дамир не придумал.

Максим же все это время собирал подозрительные слова и тестировал их на то, что они являются power-word'ами. К 03:00 было найдено то ли 6, то ли 8 таких слов (вместе с теми 4, что мы нашли ранее). Параллельно он запускал наше решение со все большим и большим количеством найденных «волшебных» слов и засылал полученный давар на сервер. Таким образом, прошли еще 3 апокалипсиса, т.е. последний тег массового тестирования был «apocalypse_4».

После ужина в 3 часа ночи (на этот раз были какие-то замороженные овощи + грибы + покрошенные сосиски, разогретые все вместе на сковородке) Дамир ушел спать (все-таки мало спал в предыдущую ночь), Максим продолжил долбить сервер организаторов подозрительными словами, а я сел ускорять оценочную функцию.

Оценочная функция была переписана с O(размер поля) на O(количество элементов в фигурке) примерно в 5:00. Погонял — вроде стало быстрее, значит уже можно пробовать замахнуться на 3 хода. Сегодня замахивать уже нет сил, я ложусь спать на 3-4 часа.

День 4. Финальный рывок

Я просыпаюсь где-то в 9-10 утра, Дамир чуть позже.

Максим ночью не спал (и собрался не спать до самого окончания контеста). За ночь он нашел еще несколько «волшебных» слов, чуть ли не распарсивая целые статьи из Википедии, которые так или иначе связаны с Ктулху. Итого найденных power-word'ов стало 10. Вот они:

ei!
yuggoth
ia! ia!
r'lyeh
necronomicon
planet 10
monkeyboy
john bigboote
in his house at r'lyeh dead cthulhu waits dreaming.
yoyodyne

К сожалению, как выяснилось после контеста, подход для поиска этих слов был идеален не до конца. Например, слово «Yog-Sothoth» было отброшено, поскольку там содержался дефис. Оказалось, что «YogSothoth» (без дефиса!) оказалось power-word'ом! В общем, не догадался Максим просто выкидывать лишние дефисы. Еще момент: Максим проверял слово «laundry», однако силу имела строка «the laundry». Также непонятка случилась с «ph'nglui mglw'nafh cthulhu r'lyeh wgah'nagl fhtagn.». Эта фраза была «волшебной», но наша процедура этого почему-то не подтвердила.

Еще Максим ночью провел пятый апокалипсис со всеми 10 найденными «волшебными» словами.

Утром пока мы с Дамиром просыпались, Максим сбегал в магазин за энергетиками (прогулялся на свежем воздухе), чтобы у нас хватило сил для финального рывка.

Работа пошла по трем направлениям: я начал писать перебор на 3 хода вперед, Дамир продолжил играться с эвристикой для 9 теста (у него появились кое-какие новые идеи), Максим начал писать скрипт, который парсит весь наш предыдущий давар, выбирает для каждого теста/seed'а максимум и собирает это все воедино.

Примерно в 12:30 Дамир наконец написал нормальную эвристику для оценочной функции, которая гораздо лучше играет на тесте 9: затыкается на 110 ходе из 400, а не 35, как было раньше. Кроме того, Дамир написал код, который запускает поиск решения 2 раза: сначала с новой оценочной функцией, потом со старой. Для обоих случаев считает количество очков и выводит в ответ тот вариант, где очков больше. После этого Дамир с Максимом переключаются на компоновку финального тарбола и потихоньку пишут README для жюри.

Я дописываю перебор на 3 хода к 14:00. С ним пришлось повозиться: добавить еще несколько оптимизаций, чтобы ускорить процесс. Кроме того, перебор третьего хода пришлось немного обрезать (ибо иначе было совсем тормознуто), а именно: проверять третий ход только у тех веток, которые самые перспективные. То есть сначала мы запускаем перебор второго хода «вхолостую», вычисляя значения оценочных функций без запуска третьего хода. Среди полученных значений отсеиваем около 10 максимальных и запускаем перебор второго хода уже «вбоевую»: при этом пробуем делать третий ход только из тех самых около 10 оптимальных состояний.

То, что получилось, решает 4 тест очень и очень круто. Почти по всем вариантам random seed находит решения в 200 ходов из 200. При этом за полученным даваром в визуализаторе было очень интересно следить:

К 14:40 совместно с Дамиром мержим две наши модификации. Вроде все проходит без особых трудностей. Максим дописывает скрипт для компоновки оптимального давара. Сборный оптимальный давар идет под тегом «panopticum», засылаем его на сервер.

Запускаем последнее решение за полном сете. До дедлайна (17:00) остается около двух часов.

Тут у нас возникают некоторые споры: а какое решение, собственно, запаковывать в тарбол? То, которое получили сейчас или то, которое у нас было утром? Дело в том, что новое решение пока еще толком не протестировано, в отличие от утреннего + новое решение стало заметно тормознутее утреннего. То есть есть риск не успеть его нормально протестировать и итоге заслать лажу. А то, что у нас было утром — типа уже проверенный стабильный релиз. Все-таки решаем запаковать новый вариант.

Тем временем новое решение тестируется и, судя по его производительности, становится ясно, что до дедлайна есть шанс и не уложиться. В спешном порядке раскидываем расчет различных тестов на разные машины. В итоге за полтора часа до дедлайна посчитали все тесты кроме 4, 6 и 24. Дело в том, что 4 и 6 тесты имеют маленький размер поля, поэтому на них запускается перебор на 3 хода вперед. Кроме того, в каждом из них 50 подтестов (различные random seed) на 150 или 200 ходов. Наш перебор на 3 хода вперед требует около секунды на ход, поэтому становится ясно, что, скажем, на весь 4й тест надо около 3 часов времени. А у нас нет 3 часов времени! С 24 тестом ситуация немного другая: хотя там только 1 подтест, там очень большое поле и 1620 ходов для обработки — на него тоже надо около 3 часов.

В итоге мы решаем забить на 6 и 24 тесты, а 4й тест распараллелить на 5 подзадач (по 10 подтестов в каждой), посчитать на разных машинах, потом руками все склеить. Сказано — сделано. Считаем. Около 16:00 (за час до конца) у Дамира от перегрева сдыхает ноут. Ну, не совсем сдыхает, просто перезагружается, и тем самым 2 из 5 параллельных веток теряются. Ну, делать нечего — Дамир начинает считать свои ветки заново. Пока они считаются, Дамир ставит свой ноутбук на 2 стакана и затем создает вокруг него потоки воздуха для лучшего отвода тепла. К 16:20 у нас все досчиталось, причем одновременно. Ну что поделать, в нашем решении много операций с int64, у Дамира 64-битный Линукс, а у меня 32-битная Винда.

Отправляем последний давар, дооформляем тарбол, засылаем. Через несколько минут Максим находит грамматическую ошибку в README файле, правит ее, засылает исправленный тарбол за минуту до конца (все у нас как-то в последний момент).

Эпилог

Когда мы засылали последний давар — мы были на второй строчке квалификационной таблицы. Чуть поже свой давар заслали Unagi и сместили нас на третью строчку.

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

Наш репозиторий можно найти на гитхабе (во время контеста он был в другом приватном месте, на гитхаб перебросили только сейчас). Можно погонять/поизучать наши решение/визуализатор. В таблице ниже можно видеть некоторые наши решения, запущенные на всех 18 power-word'ах, которые стали известны после окончания контеста.

Спасибо всем, кто дочитал до конца!

Ктулхи в банке: как мы решали ICFPC 2015