Sapka contest

Не так давно закончился контест Sapka, который проходил с 13-го по 20-е марта 2009 года. Я принимал в этом контесте участие и не могу не поделиться впечатлениями, ведь их было очень-очень-очень много.

Введение

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

Команда

Sapka и ICFPC - командные соревнования. Естественно, участвовать можно и одному, но для одного человека объем работы очень велик, да и вместе веселее. Поэтому очень важным является выбор команды, настройка средств коммуникации, распределение ролей и т.д.
Я до самого конца не был уверен, буду ли я участвовать в Sapka, поэтому команду я нашел лишь за день до соревнований, да и за день мы никак не готовились к участию. Как ни странно, но ничего страшного из-за этого не случилось, были и покрупней просчёты :) Итак, команда под названием "a" изначально состояла из трёх человек - Вашего покорного слуги, xa4a и A2K. Но у последнего участника под конец соревнования были завалы с учебой, поэтому написанием самого решения занимались всего два человека.

Начало соревнования

Оригинальное задание можно прочитать на сайте Sapka. Фан начинается уже здесь. Если кратко - то нам даётся некий сервер некой игры, в которую надо стучаться по телнету. Нужно написать клиента для этой игры. Всё! Никакого точного ТЗ, только упоминание о том, что сначала сервер нужно сконфигурировать. И вот с таким багажом знаний все участники и вступают в игру.
Лично для себя я всё время участия могу поделить на 3 этапа:

Этап 1. Хак сервера :)

То, что сервер написан на Java, и то, что защита там игрушечная, впоследствии позволило многим командам получить все нужные для конфигурации данные в течение первых 1-2х часов соревнования. Это также вызвало бурные дискуссии и недовольство тех, кто не смог сервер хакнуть. В гугл-группе даже жаловались, что из-за того, что в команде не было ни одного джависта, у них не получилось похачить сервер и поэтому они не смогли "заняться собственно программированием"(с). Для тех, кто все еще считает, что для взлома сервера обязательно нужны знания Java - следующий абзац.
Обладая минимальными знаниями Java и обладая к Java большой нелюбовью, я пересилил себя и приступил к "взлому" сервера. Вся процедура взлома заключалась вот в чём: разархивировать jar; увидеть, что там есть какой-то loader; натравить на него jad (найден в google по словам Java Decompiler); открыть Eclipse; запихать туда расшифрованный код; пройтись по коду и найти место, где происходит дешифрация; добавить запись в файл прямо там(код записи в файл был также найден в google ;));скомпилировать и использовать получившийся код для дешифрации файлов; после этого натравливать jad на дешифрованные файлы. Чтобы долго не лазить по обфусцированному коду, я взял и банально расшифровал самые большие файлы, которые были в архиве. И тут же налетел на нужные файлы - на описания логики игр. Чуть погодя(почему погодя - смотрите ниже) был написан и генератор конфигурационных токенов(простым копированием существующего кода). Вы всё еще считаете, что для взлома сервера нужно было знание Java? ;)
На самом деле, я занимался исследованием сервера намного дольше, чем это могло показаться. Во-первых, я вначале пытался достать конфигурационные токены прямо из памяти, но успеха не добился. Во-вторых, команда активно ковыряла квестовую часть Сапки, и я также принимал в этом участие.

Этап 2. Квест

Все конфигурационные токены можно было достать, пройдя текстовый квест, общаясь по telnet с сервером. Это было очень увлекательно, поэтому даже когда я уже достаточно продвинулся в процессе взлома, мы всё равно продолжали решать задачки. Так были найдены практически все токены, кроме DNA (сгенерировать токен оказалось намного проще, чем решить эту задачу). Также были подсмотрены в коде сервера секретные пароли, так что токены, которые они дают, также были получены путём хака.
В общем, описать квестовую часть практически невозможно - это было незабываемо! :) Внутри был Брейнфак, Forth-подобный язык, "шашки"(за них отдельное спасибо, я был просто поражен, когда обыграл его) + несколько задачек на преобразование текста. Я постарался не выдавать никаких секретов в описании, поэтому если вы не видели квеста - it's worth to try it out! Даже несмотря на то, что игра завершена, удовольствие вам гарантировано.

Этап 3. Программирование бота

После прохождения квеста стало ясно, что нам нужно написать клиент к bomberman-like игре. В качестве основного инструмента был выбран язык Python. Краткое описание процесса:
xa4a - написание парсера для сообщений от сервера
xa4a - создание визуализатора (на pygame)
tilarids(/me) - улучшение визуализатора
xa4a - создание keyboard controller
xa4a - рефакторинг, фикс багов, random AI
tilarids(/me) - добавлено избегание опасных мест
tilarids(/me) - добавление уничтожителя стен

---

Здесь небольшая врезка - кончился lightning раунд. На lightning раунд был отправлен бот, который не ставил бомб, а только убегал от опасностей. Причина - за убийство себя давали -1000 очков, а бот был страшен в своей наглости и часто себя убивал.
Дальнейшая разработка заключалась практически в улучшении, рефакторингом и пофиксах существующих алгоритмов.

---

xa4a - большой рефакторинг, добавлен нормальный механизм переключения состояний
tilarids(/me) - добавлен учёт времени взрыва бомб, простейшее начисление очков(в соответствии с идеей A2K), пофикс багов
xa4a - добавление охоты за бонусами, пофикс багов, рефакторинг бомб
tilarids(/me) - добавление охоты за противником
xa4a - завершение рефакторинга бомб, добавление учета подрыва бомбами друг друга, пофикс багов
tilarids(/me) - пофикс багов, пофикс учета коллапса мира, сабмит

---

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

Репозиторий с исходниками находится в публичном доступе. Также есть просмотрщик риплеев.

Благодарности

Хотелось бы выразить огромнейшую благодарность организаторам. Sapka - это было потрясающе! Такого количества фана я не получал уже очень давно. Спасибо вам за то, что вы сделали!
Также хотелось поблагодарить команду - мне показалось, что работали мы достаточно слаженно, и я очень рад, что мне довелось участвовать в Sapka в команде именно с таким составом.

Организаторам

• Всё же сервер надо защищать лучше. Чтобы взлом сервера был отдельной трудной задачей, а не заменял прохождение квеста. Например, можно было бы некоторые задания составить так, чтобы понадобилось их решать программно в момент запуска клиента
• Побольше бы заданий наподобие fifth. Задачки на преобразование текста были занятные, но по количеству фана намного менее содержательные
• Я буду очень рад поучаствовать в Sapka 2010 ;)

Себе на заметку

• Если желаешь выиграть, нужно пользоваться даже относительно нечестными методами. Если бы мы не тратили время на квест, когда уже были почти все токены, на лайтнинг можно было бы успеть отправить уже активного бота
• Количество участников в подобных соревнованиях - не главное. Но хорошо, если есть участники, которые могут потратить время на поиск и исправление багов
• Возможно, стоило попробовать переписать всё вообще без состояний, чтобы получить простого, как пробка, но зато бессмертного/безбажного бота. Но после драки кулаками не машут :)
• Pygame - отличная платформа для визуализации чего-либо