среда, августа 12, 2015

Как не надо участвовать в ICFPC (типа отчёт об ICFPC-2015)

Мы с несколькими товарищами (широко известными в узких кругах - ForNeVer, rexim, Minoru) уже который год подряд пытаемся участвовать в ICFPC. Если кто не в курсе, это такой своеобразный ежегодный контест по программированию, приуроченный к international conference for funcional programming (ICFP). Несмотря на название, программировать можно не только на функциональных языках, а на чём бог на душу положит. Более того, во многих случаях код организаторам передавать необязательно - контест организован так, что нужно отослать ответы на какие-то задачи. Т.е. теоретически можно вообще не программировать, а решить задачи на бумажке и отослать ответы. Просто очень сложно. Контест длится трое суток — в моём часовом поясе это от вечера пятницы до вечера понедельника. Темы заданий выбираются в целом довольно разнообразные, но последние годы заметен уклон в сторону всяческих AI. Например, вот задачи тех контестов, в которых я участвовал:
  • 2014 - надо было написать AI для игры a la Pacman. Даны карты, а надо прислать программы на ассемблере выдуманных процессоров, играющие за основного персонажа и за призраков, набирая побольше очков.
  • 2013 - угадывание формул. Даны значения переменных и результат вычисления, а также некоторая общая информация о выражении. Надо прислать угаданные выражения.
  • 2012 - AI для игры наподобие Supalex.
Результаты у нашей команды обычно... э... ну, лучше чем последнее место, чо. С одной стороны, главное не победа. C другой...
Типичный «путь к успеху» таков. Команда географически сильно распределённая, покрывая несколько часовых поясов. Теоретически это могло бы даже быть преимуществом (непрерывный 24-часовой кодинг, как 24-часовая поддержка, а?). Но как-то не в нашем случае. О контесте вспоминаем за пару дней. Обсуждаем выбор языка программирования, особо не зацикливаясь на фиксации этого выбора. Типичное решение: «давайте попробуем haskell, а там если увидим что чото не то, возьмём C++». При том, что часть команды имеет очень мало опыта с Haskell, а другая часть — с C++. Во время контеста (он длится трое суток) у каждого что-нибудь случается, из разряда «зимой совершенно неожиданно выпал снег» — приезжают родственники, нужно на работу или ещё что-нибудь. Т.е. вещи, которые в принципе можно было предотвратить (отработать в другой день итд), если позаботиться об этом достаточно заранее. В этот раз соригинальничали. О контесте вспомнили аж за неделю. В качестве языка программирования выбрали Scala. При том, что двое из команды (я и Minoru) к этому моменту о ней только по наслышке знали. Я был в принципе не против, т.к. наслышан о языке был давно — почему бы и не изучить. За неделю скачал компилятор, среду разработки (hint: Idea community edition с плагинами для Scala и vim mode) и уехал на дачу. Где через напоминающий старые-добрые времена мобильный GPRS (ни дать ни взять диалап - не верещит на всю комнату, и только) стал изучать гугл на тему туториалов. Нашёл scala by example. Написав hello world, решил потренироваться на кошках и пошёл куда очень давно не ходил — на acm.timus.ru. Кстати, с удивлением обнаружил, что они теперь поддерживают и Scala, и Haskell. Тот факт, что я с институтских времён не занимался спортивным программированием, очень даже сказался — все мои программы упёрлись в time limit :) Не из-за «тормозной явы», конечно, а просто из-за плохих алгоритмов. В данном случае меня это не очень расстроило — в рамках ICFPC производительность нашего кода обычно мало важна. Общее впечатление от Scala, кстати — это скорее «пере-ява», чем «недо-хаскель» :)
У меня есть «особенность стиля разработки», по-моему, не очень удивительная. Я плохо умею придумывать алгоритмы и организацию кода отдельно от самого кода. Поэтому, приступая к чему-то новому, я обычно начинаю с написания сколь угодно плохого алгоритма на том, что под руку подвернётся (прототип в 15 строк, он может даже и вовсе не работать), а дальше уже думаю над алгоритмами и дизайном параллельно с изменением кода. Начало предыдущих ICFPC выглядело поэтому так. Пока народ в чате думает над задачей, над алгоритмами, обсуждает, лучше ли здесь Haskell или C++, я беру и начинаю что-то писать на haskell. К моменту, когда в чате появляются сообщения вида «ну ладно, давайте писать», оказывается, что в репозитории уже лежит мой код на haskell :) (хороший код или плохой — отдельный вопрос). И в итоге остальные, из соображения «экономии кода», чтобы не переписывать то же самое на другом языке, продолжают тоже на haskell. Когда опыта с ним мало, это иногда выливается в многочасовую борьбу с компилятором. Видимо как раз из-за того, что прошлые разы я таким образом «навязывал» остальным Haskell, в этот раз ForNeVer и предложил взять Scala :) Поэтому в этот раз в начале контеста я ждал, пока ForNeVer cоздаст заготовку проекта, а в это время пытался думать над задачей. Без кода думать получалось плохо.
Кстати, о задаче.
В этот раз опять нужно было написать AI для игры. Игра — нечто похожее на тетрис на гексагональной решётке. Основные отличия: вся последовательность фигур известна заранее; фигуры сами по себе вниз не падают, их надо падать отдельными командами; и их можно закреплять не только внизу, но и где-нибудь посередине, если упереть в стенку или в другую фигуру. И ещё: каждая команда может быть закодирована одной из нескольких букв. Поэтому из последовательностей команд можно составлять слова. Имеется некоторое количество «заклинаний», «phrases of power», или попросту чит-кодов. За использование их в последовательности команд дают отдельные очки. Одно заклинание (Ei!) сказали сразу, другие предложили найти «в задании, в твитах, в background leaterature и game artifacts». Бэкграундом были, видимо, произведения Лавкрафта. Организация получения задач и отправки решений такая: дано фиксированное количество «карт» — описаний игровых полей (они могут быть пустыми или на них изначально могут быть какие-то занятые клетки) и фигур, которые там могут выпадать. Надо для каждой карты прислать последовательность команд, которая наберёт по специфическим правилам этого «тетриса» как можно больше очков.
Я нарисовал одну из первых карт (они выдаются в виде json) на бумажке, и обнаружил, что там заполненными клетками написано «Ei!». Ага, значит на других картах могут быть другие заклинания. Только рисовать гексагональную решётку даже на клетчатой бумаге немного утомительно, так что явно нужна какая-то рисовалка карт, чтобы хотя бы на них посмотреть. Примерно к этому времени появилась заготовка проекта, и ForNeVer уже сделал загрузку карт из json. Тогда я написал рисовалку карт в виде ascii-art. Запустив её на имеющихся картах, узнали ещё парочку заклинаний.
В предыдущих ICFPC мы как-то умудрялись обходиться без визуализации действий наших ботов. В этот раз rexim для разнообразия взялся таки сделать визуализацию. Я в AI и родственных алгоритмах мало сведущ — в прошлом году апофигеем стало использование волнового алгоритма. Поэтому я взялся писать то, что особой изобретательности не требует, но при этом явно понадобится — эмулятор этого самого тетриса. Отдельный анекдот вышел вокруг представления игрового поля. Очевидно, нужно что-то наподобие двухмерного массива, с возможностью как-нибудь делать операции «вычёркивание строки» и «перемещение занятых клеток». При этом у меня был, с одной стороны, опыт ещё институтских игрушек, где это был сишный char[][]; с другой — опыт хаскеля предлагал использовать что-нибудь типа [[CellState]]. Опыт со scala не подсказывал пока ничего. Я спросил в чате, и мне предложили не заморачиваясь использовать Array[Array[CellState]] (если кто не в курсе — это мутабельный массив с произвольным доступом, в принципе аналогично сишному char[][]). Ну и ладно. Обернул его в класс, дополнив методами типа «проверить валидность координат», и вперёд. Таким образом, эмулятор вышел «мутабельным»: при обработке команды он изменяет своё состояние. А когда позже ForNeVer стал писать какой-никакой AI, ему понадобились методы типа «посмотреть что получится если выдать такую-то команду», не изменяющие состояния игрового поля. В результате пришлось переделывать эмулятор в частично иммутабельный. Народ потом возмущался — зачем у нас эмулятор мутабельный! в следующий раз никакой мутабельности! Я отвечал, что тогда непонятно, зачем взяли Scala — код без мутабельности естественнее писать на Haskell.
Ещё через некоторое время после начала контеста к нам присоединились grouzen и ulidtko. Ulidtko примерно одновременно с Minoru взялись решать специфическую геометрическую задачку: поворот фигур на гексагональной решётке. Причём каждый из них, кажется, пошёл своим путём. Я решил, что трёх человек на такую простую на первый взгляд задачу будет многовато, и решил этим не заниматься. В итоге большую часть времени я допиливал помаленьку эмулятор и... играл в тетрис. В наш эмулятор с визуализатором. Т.к. первый работоспособный AI у нас появился только где-то к вечеру воскресенья, до этого мы могли набирать очки только играя в наш «тетрис», набирая очки и записывая последовательности команд. А т.к. AI у нас получился бесхитростный, на некоторых задачах мои результаты так и остались лучшими. В воскресенье вечером мы залили всё что этот наш AI нарешал. В понедельник все кроме Minoru ушли на работу. Поэтому в понедельник Minoru ещё что-то допилил в AI и отправил решения по тем задачам, по которым их удалось улучшить.
Собственно, на этом и всё.
«А мораль сей басни... а не будет сегодня никакой морали, дети, идите сами думайте» (с) не помню откуда.