Тексты

  Тексты:

Пхова 2004
ICFPC 2007
ICFPC 2008
Sapka 2009
ICFPC 2009
ICFPC 2010
Защита от взлома

  Переводы:

Природа Будды
Махамудра



Если обнаружите в тексте ошибку, выделите ее мышкой и нажмите Ctrl-Enter.

Sapka 2009

С 13 по 20 марта 2009 года проходило соревнование для программистов Sapka, приуроченное к конференции CodeCamp'09 в Киеве. Ниже описывается мой опыт участия в нем.

Анонсируя конкурс, организаторы сказали, что являются большими поклонниками ICFPC и постараются сделать свое соревнование в его духе. У них это полностью получилось. Исходная постановка задачи содержала историю загадочного появления черной коробочки с сетевым интерфейсом, исследование которой дало понять, что это сервер сетевой игры. Был выложен сам сервер (который, к счастью, запускался под любой ОС, а не только под Linux, как это было в прошлом ICFPC) и описание параметров его запуска. Участникам предлагалось написать программу, которая будет играть в эту игру, соревнуясь с другими решениями. В чем именно состоит игра, каковы ее правила, и как именно клиент должен общаться с сервером сказано не было.

Запустив сервер, к нему можно было подсоединиться на указанный порт. Если зайти туда телнетом, был виден англоязычный текстовый интерфейс, предлагавший запустить игру или сначала сконфигурировать сервер.

Оказалось, что в зависимости от того, как сервер настроен, он выдает клиенту разную информацию об игре и по-разному себя ведет. Не включив двигатель, нельзя заставить своего игрока двигаться. Не включив распознавание объектов, не сможешь их друг от друга отличать. Не починив систему пеленгации, не узнаешь координат противников. И так далее. Разные функции сервера включаются специальными командами-токенами, а чтобы их узнать необходимо решить ряд задачек. По мере решения одних задачек открываются новые. Вход в подсистему настройки был закрыт паролем, который предлагалось угадать. Это несколько обескуражило, ибо готовясь к решению задачек, не ожидаешь задачи на угадывание. Но благодаря коллективному разуму IRC-чата контеста пароль был подобран очень быстро. Кроме этого основного пароля сервер реагировал на несколько других, отвечая на каждый по-своему. Например, он знал слово iddqd - чит-код бессмертия из культовой игры Doom, давая в ответ код настройки, включающий защиту игрока от въезжания в огонь. Подсистема настройки содержала несколько разделов-модулей, в каждом из которых скрывались одна-две задачи.

Модуль лексического интерпретатора содержал зашифрованный текст, конец которого содержал подсказку по его расшифровке.

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

Второй раздел - двигатель - тоже содержал зашифрованный текст, подсказка к которому давалась при входе в модуль. Кроме того, он реагировал на команду help, причем если ввести ее много раз, в ответ выдавалось все больше подсказок.

Расшифрованный текст содержал уже больше информации об игре: как управлять движением и как считаются очки.

Третьим модулем была лаборатория ДНК. В ней предлагалось путем воздействия аминокислотами привести ДНК к некой абсолютной форме, суть которой была совершенно неочевидна.

В каждый момент времени можно видеть конфигурацию 2х2 буквы, и ввод каждой команды-аминокислоты меняет до двух букв. Некоторые команды противоположны - их последовательное применение возвращает в исходное положение. Если одну команду применить 4 раза подряд, тоже оказываешься в начальном положении. Выписывание эффектов команд на бумажке помогло понять, что перед нами что-то вроде кубика Рубика 2х2х2. Более пристальное исследование поведения показало, что это не совсем кубик Рубика - при повороте вокруг оси перпендикулярная ей плоскость не поворачивалась. Как рассказали уже после конкурса организаторы, они вплоть до второго дня соревнования были уверены, что сделали кубик Рубика. Отличие же от него оказалось просто ошибкой в их реализации. Как бы то ни было, получилась вполне самобытная задача, которую надо было решать. Раз она напоминала кубик Рубика, предположили, что абсолютная форма ДНК - это собранный кубик. Я сделал простенький графический его симулятор, в котором моя жена довольно быстро привела псевдокубик к нужной форме. Осталось лишь ввести ту же последовательность команд в сервер и получить положительный ответ с новой информацией. Днем позже, когда оказалось, что из-за пробела в имени команды мне нужно было получить токены настройки еще раз (они привязаны к имени команды), собрать кубик в ручную уже не получилось, поэтому пришлось написать программу для честного поиска решения. Она оказалась намного умнее меня и нашла решение в 7 ходов за 0,4 секунды.

В лаборатории ДНК был также спрятан и второй токен, найти который было сложнее. Если внимательно посмотреть на текст справки, его испорченную часть, то отдельно стоящие буквы как бы намекают нам на писателя Ивана Франко. И каждый, кто учился в украинской школе, должен был вспомнить его рассказ про мальчика и гуся, где произносилась заветная фраза (или слово), обозначающая алфавит. Это же слово можно было увидеть в пятом модуле, о котором позже:

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

Четвертый модуль, почему-то названный спутником, содержал в себе интерактивную игру с наглым вирусом в шашки.

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

Пятый модуль так и назывался - пятый (fifth). Внутри он содержал интепретатор языка программирования FIFTH, пародирующего семейство языков Форт (Forth), название которого происходит от слова fourth (четвертый, имелся в виду номер поколения языков). На этом стековом языке с постфиксной нотацией и отсутствием циклов нужно было реализовать пару функций - физический рассчет равноускоренного движения двух тел и определения расстояния между ними и чтение числа в произвольной системе счисления.

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

Шестой модуль содержал испорченную вирусом программу на языке Brainfuck. Для незнакомых с языком даже давалась ссылка на его описание в интернете.

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

Последний модуль - часы - содержал еще один зашифрованный текст и подсказки к нему.

Применив к тексту циклически операцию, на которую намекают большие буквы из фразы вверху с именем автора фразы внизу, можно получить расшифрованный текст. Помимо готового конфигурационного токена он содержал еще одну последовательность байт, применив ту же операцию к которой и первому токену, можно было получить еще один токен.

Решив все имеющиеся задачи и сравнив число полученных токенов с тем, что обсуждалось в IRC-чате среди участников, я понял, что есть еще один заветный пароль, который может дать недостающий токен. Угадать его не получалось, пришлось прибегнуть ко взлому. Сервер был написан на Java и состоял из небольшого загрузчика и кучи зашифрованных частей программы. Опыта работы с Java и ее декомпиляции у меня не было, поэтому идти по этому пути я не стал, хотя другие участники сообщали, что им это удавалось очень легко. Вместо этого я просто в диспетчере задач сбросил содержимое памяти процесса на диск и в нем нашел угаданные пароли. Рядом с ними в открытом виде оказались неугаданные.

Оказалось, что недостающий пароль я уже встречал по мере прохождения задач и даже вводил как пароль, но не вовремя - он начинал действовать после решения каких-то других задач. Введя же его теперь, я получил недостающую часть грамматики и последний токен.

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

Через некоторое время после начала соревнования организаторы выложили новую версию сервера с режимом графического отображения хода игры. В сочетании с той информацией, что удалось выведать у сервера, стало ясно, что игра эта - Bomberman. В ней есть прямоугольное поле из клеток. В каждой клетке может быть либо неразрушимая стена, либо стена, которую можно взорвать, либо пустое место, либо один из бонусов. Игроки могут передвигаться по карте и ставить бомбы. Координаты и скорости игроков задаются в точках, каждая клетка имеет размер в несколько точек, поэтому на пересечение клетки нужно обычно несколько ходов. Поставленная бомба тикает некоторое количество ходов (оно сообщается сервером при установке бомбы, как и радиус поражения), а потом взрывается. Взрыв распространяется крестом вертикально и горизонтально на указанное число клеток. Если на его пути окзывается стена или бонус, они уничтожаются, а взрыв дальше в этом направлении не идет. Крестообразный пожар продолжается несколько ходов, число которых также сообщается сервером. Если игрок окажется внутри горящей зоны, он погибает. Если он подорвался на своей же бомбе, с него снимают 1000 очков. Если подорвал врага - прибавляют 1000. За разрушение стен дают по 10. Бонусы бывают хорошие и плохие. Хорошие дают дополнительные бомбы, увеличивают радиус поражения, увеличивают скорость передвижения, они действуют до конца игры. Плохие бонусы могут лишить игрока возможности ставить бомбы, снизить радиус поражения или скорость до минимума, а могут инвертировать управление. Действие плохого бонуса временно и называется инфекцией, потому что она заразна - если зараженный игрок окажется на одной клетке с другим, второй тоже заболеет.

Есть также бонусы-сюрпризы, их действие экивалентно одному из вышеперечисленных бонусов, просто заранее неизвестно какому (выбирается случайно). Игра состоит из нескольких раундов. Раунд заканчивается, когда в живых остается только один игрок. Если живых более одного слишком долго, то мир начинает коллапсировать: сначала по периметру мира появляются неразрушимые стены, потом второй слой внутри их кольца, потом третий и т.д. Каждый шаг коллапса заранее предваряется сообщением от сервера, так что если игрок настроил сервер на посылку таких сообщений и принял к сведению, то может убежать от коллапса ближе к центру карты. Но, разумеется, как говорил Тайлер Дерден из Fight Club, "на достаточно большом промежутке времени наши шансы на выживание равны нулю". Игра идет в реальном времени, сервер сообщает обо всех событиях N раз в секунду. В документации говорилось про 20 раз в секунду, но практика показала лишь 10. Игроки посылают свои сообщения в любое время, но из нескольких сообщений, присланных в течение одного хода (1/10 секунды), принимается к исполнению только последнее (вроде бы).

После получения всех конфигурационных токенов пришло время садиться за написание своего бота (программы-игрока). Энтузиазм несколько поугас, т.к. на фоне только что решенных интересных и разнообразных задачек большая задача с такими частями как общение по сети и тщательный разбор сообщений сервера выглядела не столь увлекательной. К счастью, код для сетевого обмена с сервером у меня уже был готовый - остался от ICFPC'08, а задачу парсинга сообщений мне удалось сделать интересной путем написания специально для нее маленькой библиотечки монадных парсер-комбинаторов, позволяющих код разбора сообщения сделать очень похожим на саму формулировку грамматики.

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

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

Для каждой такой достижимой клетки определяется ее интересность: в зависимости от того, есть ли на ней бонус, сколько вокруг взрываемых объектов и нет ли неподалеку от нее врага. Плохие и неизвестные бонусы имеют отрицательный интерес, поэтому в такие клетки он пойдет в последнюю очередь. Из взрываемых объектов интереснее те, что ближе к врагам - так он будет продвигаться в их сторону. При определении интересности для взрывания, также рассматривается, есть ли из этой клетки пути отхода. Ведь если он поставит бомбу, от которой сам не сможет убежать, то умрет. Если путей отхода не найдено, интересность клетки для взрывания нулевая.

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

Зная для каждой потенциальной цели привлекательность и временные затраты, бот выбирает ту, что имеет лучшее отношение первого ко второму, таким образом максимизируя количество очков, набираемое в минуту. Если для каких-то целей это соотношение примерно одинаковое, выбирается ближайшая из них. Так определяется лучшая цель, причем это делается отдельно для каждой из 4 зон, соответствующих направлениям движения. Также для каждой зоны определяется, есть ли в ней совершенно безопасные клетки - где в обозримом будущем точно не будет взрывов. Если в какой-то зоне таких совершенно безопасных клеток нет, то в этом направлении двигаться нельзя, даже если там есть временно безопасные клетки с интересными целями; такие зоны считаются опасными. Из 4 зон, соответствующих направлениям, выбираются безопасные, а из найденных для них лучших целей выбирается самая лучшая по тем же принципам. Если это текущая клетка, и интересна она не своим бонусом, то отдается команда на установку бомбы. Если лучшая цель не в текущей клетке, то отдается команда двигаться в ее направлении, благо первый шаг пути к любой цели боту известен.

При отслеживании изменений мира помимо прочего бот следит какие бонусы он съел. Если это бонус временного разоружения, это влияет на оценку интересности взрывания клеток (обнуляет). Если бот съел бонус инвертирования управления, то он инвертирует собственные команды, пока не закончится инфицированность. К сожалению, в коде определения того, что он съел, у меня оказалась ошибка (сравнивались координаты в точках и в клетках), поэтому вся эта логика не работала. Ошибку обнаружил уже после окончания соревнования. Из-за другой ошибки, на этот раз чисто логической, мой бот боится ставить бомбы в длинных узких коридорах - думает, что не сможет убежать.

Как и программы для решения задачек, своего бота я писал на языке OCaml. Получилось около 600 строк, включая пустые и комментарии. Пока писал, то и дело ловил себя на мысли о неоптимальности кода, потом измерил время - на обдумывание хода на карте 11х11 тратит в среднем 150 микросекунд. Оптимизировать не понадобилось, и это приятно. :) Помимо кода на Окамле была одна процедура на С в три строчки, устанавливающая нужный флаг у сетевого соединения. Разработка велась под Windows, а сдавать программу надо было под Linux. При перекомпиляции в нем единственная часть, которую пришлось редактировать, была часть на С - отличались пути к заголовочным файлам. Код на Окамле оказался полностью переносимым, и это тоже приятно. Архив с моим решением (исходники и исполняемый файл под Linux): contest.zip.

Кое-кто из участников выложил свои решения, например команда А: два с половиной программиста, 1800 строк на Питоне. Вот видео сражения моего бота (синий) с их ботом (зеленый):

Красный бот - наблюдатель, управляемый с клавиатуры. В данном случае красный заработал 42 очка (за введенные коды), зеленый 724, синий 6884.

Всего в основном раунде участовала 41 команда, и мой бот занял 5-е место (счет ведется с 0-ого). Дошел до полуфинала, где описанные выше ошибки проявили себя, не позволив пройти в финал.
Результаты:


© Dee Mon, 2004-2010.