В прошлом году мне настолько понравилось играть, что на этот раз я попросился в команду заранее, аж за неделю до начала. Тогда же решили, что писать в этом году будем на Scala. Но если у ForNeVeR и rexim практики с этим языком хоть отбавляй, то мы с portnov за него взялись впервые. Не знаю толком, что там читал и писал portnov, но я после фальстарта с написанием одной мелкой штуковины засел за «Scala by Example», по итогам прочтения написав пост для хаскелистов, желающих быстренько перекатиться.

Инфраструктурой занимался ForNeVeR, поэтому чтобы попасть в XMPP-конференцию, нужно было открыть письмо, проследовать к приватной репе на GitHub и там прочитать Readme. В ответ на мои подколки об отсутствии загадок обещал для следующего раза подготовить. Чую, на следующий год мы это дело кому-то другому поручим ☺

Пятница

Контест начинался в три часа дня по моему локальному времени и часов в пять-шесть по часам моих коллег. Стартонули без rexim’а — у того были дела.

Суть задания этого года сводилась к написанию ИИ для игры в вариацию тетриса с шестиугольными ячейками и полной информацией (т.е. мы знали, в каком порядке выпадают фигурки). В дополнение к этому каждая из возможных команд кодируется одним из набора символов, благодаря чему последовательности команд можно записывать как слова и фразы. Нам предлагалось найти в твиттере оргов и в трудах Лавкрафта «слова силы», которые давали бы дополнительные баллы.

Быстренько прочитав условие, разбежались кто куда: ForNeVeR занялся сетапом проекта, portnov ушёл в размышления, а я взялся выяснять, как на гексагональной решётке выполнять поворот фигуры. Тут случился фейл №1: вместо того, чтобы нагуглить страничку, которую нашли все остальные команды, я нашёл двадцатилетней давности публикацию, которую тут же отложил в сторону, чтобы пообедать и подумать про общий подход к решению. Впрочем, кого я обманываю? Общий подход я в этот момент уже представлял:

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

Я предполагал, что оба уровня будут использовать A*, в который я с детства студенчества влюблён, но который мне ни разу не доводилось использовать всерьёз. Оставалось только продумать детали, но это как-то не получалось, поэтому я взял задачу попроще — реализовать генератор псевдослучайных чисел. ForNeVeR тем временем возился с чтением карт, а portnov нарисовал-таки одну от руки, после чего принялся пилить ASCII-рисовалку.

Тут к нам присоединился ещё один цодингтимовец, grouzen, но он ещё не читал задания и был не совсем готов в техническом плане, так что в работу влился не сразу.

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

grouzen тем временем пригласил в команду ещё одного чувака, ulidtko. Тот уже начал пилить PRNG на Haskell; я попробовал перетянуть его на Светлую сторону на Scala, кинув ссылку на свой пост, но не вышло ☹ В итоге grouzen взялся за эмулятор (тоже на Haskell), ulidtko решил писать к нему визуализатор, а я, отчаявшись придумать что-то новое в плане ИИ, кинул им ссылку на вышеупомянутую публикацию и отправился спать.

Суббота

Проснувшись, я обнаружил, что:

• portnov пилит эмулятор;
• rexim пилит визуализатор;
• ForNeVeR пилит (де)сериализатор и нашёл багу в scalac;
• grouzen с ulidtko занимаются неизвестно чем, т.к. не отчитываются в конфочке.

Тут до нас начала доходить странность ситуации: grouzen и ulidtko как бы с нами, но при этом пишут на другом языке то, что у нас уже написано, и не делятся идеями, хотя обещали чего-то подумать на тему ИИ. После непродолжительных пинков с нашей стороны ulidtko сказал, что они там мусолили теорию, а потом взялись писать базовые тулзы (т.е. то, что мы уже почти сделали). Я попытался вытянуть из него какие-то подробности по теории, но он испугал меня страшными словами вроде «флуд-филл», и я забил (зря — время, потраченное в итоге на пустые раздумья, можно было бы потратить на чтение Википедии).

Завтракая, пытался наверстать по чтению #icfp-contest на Freenode, но там за ночь нафлудили столько, что пришлось потратить лишние полчаса. Это тоже зря, ибо ни из упомянутой комнаты, ни из icfpc@conference.jabber.ru мы за всё время ничего критически важного не узнали.

Так как в плане ИИ мне ничего нового не приснилось, взялся за более приземлённую задачу — повороты (grouzen с ulidtko тоже должны были работать в этом направлении, но я с ними мало знаком и полагаться не мог). И к четырём вечера я таки раскурил всю-всю-всю математику, понял пейпер и вывел формулы, позволяющие конвертировать наши координаты в те, в которых удобно поворачивать, и обратно. Ура! Ведь ура же?

Не ура. Вывести-то вывел, а вот догадаться схлопнуть это всё в одну формулу — не догадался. Поэтому пока я возился с реализацией всех этих конвертаций и поворотов, ulidtko закончил свой прототип функции поворота на JS, и мой труд стал не нужен. Тут произошёл мой личный фейл №2: вместо того чтобы взять готовый код, портировать на Scala и пойти заниматься другими задачами, я почему-то упорно продолжал пилить своё. В итоге угробил час времени.

ForNeVeR тем временем портировал-таки повороты на Scala и занялся глобальным поиском. Когда я оторвался-таки от своего ненаглядного, но все равно неработающего кода для поворотов, мне тут же выдали поручение заняться поиском локальным. Посовещавшись с ulidtko на тему применения A* для локального поиска, я получил новый набор кейвордов для гугла и опять загрустил. Спать ушёл с тяжёлыми мыслями о том, с какого конца мне вообще за всё это браться.

Воскресенье

Видать, правду говорят о том, что утро вечера мудренее: наутро локальный поиск перестал казаться такой уж сложной задачей. Всего-то нужно было совершить волевой поступок и выбросить из задачи все детали, мешавшие написать первый прототип. Карты проходимости? У меня нет на это времени, я буду запускать поиск пересечений на каждом шагу! В итоге, кстати, сработало — локальный поиск не тормозил.

rexim тем временем продолжал трудиться над визуализатором, portnov дописывал эмулятор, а ForNeVeR корпел над глобальным поиском. К полдвенадцатого был готов и локальный поиск, пока что представлявший из себя A* без каких-либо изменений. Потом ещё оказалось, что я возвращаю найденный путь в обратном порядке, чем, гм, ломаю глобальный поиск. Быстренько это починив, ушёл обедать.

После обеда мне стало понятно, что команда в унынии: ForNeVeR погруз в багах и странностях глобального солвера, у portnov закончились задачи, grouzen и ulidtko всё так же не отзывались, а rexim заканчивал мелочи в визуализаторе. Я уже придумал, как впилить в локальный поиск критерий для использования слов силы, но меня гораздо больше волновало другое: завтра понедельник, из первоначального состава команды смогу что-то делать только я (у остальных работа), а опыт сабмита и даже запуска солвера есть только у portnov и ForNeVeR. Поэтому я принялся пинать их на тему написания скриптов, чтобы я мог просто запустить одну командочку, которая пересчитает решения и засабмитит все те, что лучше существующих. В итоге portnov взялся допиливать вывод солвера так, чтобы тот выводил только улучшенные решения, а ForNeVeR написал-таки на Powershell какие-то скрипты для автоматизации рутины.

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

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

Понедельник

Проснувшись за шесть часов до окончания контеста, я быстренько позавтракал и сел смотреть, что там сделал portnov. Чудо, произошедшее в воскресенье, не повторилось: наутро принцип и, главное, ошибки в работе глобального поиска понятней не стали. Поэтому я на это дело плюнул и взялся за добавление слов силы в локальный поиск.

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

Закончив с этим, принялся запускать солвер на всех задачах подряд и смотреть, даёт ли он хоть какой-то прирост к результатам. Действительно, на ряде задач удалось получить результаты лучше прежних, но на остальных, к сожалению, либо нули, либо и вовсе падения. Очередные мои попытки поковыряться в глобальном поиске ни к чему не привели, поэтому в итоге я написал скриптик, который собрал мне все самые лучшие решения, и сабмитнул то, что получилось. Другие команды в это же время принялись сабмитить свои, гораздо более крутые, результаты, поэтому в целом мы все равно съезжали вниз по списку. Эх…

В итоге финишировали вяло и с результатом гораздо хуже, чем в прошлом году — на этот раз в мы 151-е. Позиция, конечно, может поменяться, если судьи решат запустить наш код и посмотреть на результаты, но это вряд ли — мы попросту слишком низко.

Тем не менее, свою долю фана я получил, и в следующем году непременно буду участвовать вновь.

portnov и ForNeVeR, кстати говоря, тоже поделились впечатлениями от контеста, обязательно почитайте.

На следующий год

Вещи, которые нужно учесть:

• вне зависимости от того, какой язык мы возьмём, его нужно достаточно хорошо изучить, иначе вместо тонкостей задачи снова буду воевать с ошибками компиляции и тратить время на чтение документации по вещам, которые у опытных программистов в кеше;
• пора, пора углубить знания в области ИИ! Ибо это похвально, конечно, что я сразу смог с умным видом сказать, что «это не тетрис, потому что это задача с полной информацией», вот только это не должно быть пределом моих познаний. Да и с новыми алгоритмами познакомиться было бы неплохо (и не только теоретически!);
• я должен был сообразить, что поворот на гексагональной решётке — не настолько необычная проблема, что по ней есть только научные публикации. Если в будущем передо мной встанет задача сравнимой сложности, нужно просто повнимательней погуглить;
• возможно, сто́ит более доверчиво относится к незапланированным пополнениям в команде. Не следует забывать, что я сам в прошлом году был незапланированным пополнением, и, в отличие от пополнения нынешнего, не оправдал надежд!