Парный постмортем: как победить Ктулху и ещё 2000 человек

Всем привет, меня зовут Оля. Две недели назад на CodinGame завершился очередной контест — соревнование по программированию ботов для игры. Я попала в топ-300 мирового лидерборда, поэтому хочу рассказать, почему контесты это круто, и поделиться своими секретами. А ещё секретами поделится Иван spaceorc, который попал в топ-100 того же соревнования.

Вы узнаете, как успешно выступать на соревнованиях по программированию игрового искусственного интеллекта.

Что такое CodinGame

codingame.com — обучающая платформа для разработчиков всех возрастов и уровней подготовки. Можно писать на 26 языках: от C# и Python до Bash и Haskell. Самое крутое, что задачки там не скучные и непонятные, а настоящие игры с неплохим GUI:

Контест — это 10-дневное соревнование, которое проводится раз в пару месяцев. Поучаствовать может любой желающий, не обязательно быть финалистом ACM ICPC. Конечно, чтобы попасть в самый топ, нужно как минимум разбираться в алгоритмах, типичных для игрового искусственного интеллекта.

Но чтобы с интересом провести пару вечеров, хватит самых начальных знаний. В каждом контесте есть готовый код для чтения входных данных. Остаётся только прочитать правила, написать простенькие if-else — и в бой!

Code Of Kutulu

«Код Ктулху» — последний контест, который проходил с 15 по 25 июня. Чтобы узнать сюжет и цель, достаточно описания:

PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Что может вечно лгать, то вовсе не мертво. И умирает Смерть в загадочный эон.

Вы с вашей командой исследователей открыли гробницу Ктулху. Это самое худшее решение в вашей жизни, так как он был не готов проснуться и теперь жаждет вашей смерти. Но склеп — настоящий лабиринт, а вы не помните, где был выход… Если он до сих пор есть!
Оу… и кажется, что Ктулху был не один, и теперь он посылает за вами Глубинных.

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

Правила

Сразу скажу, что вместо чтения текстового описания правил, можете посмотреть видеозапись разбора правил и базовых тактик от Tinsane:

Иначе читайте дальше.

Карта

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

Персонажи

• Исследователь — один из игроков. Ходит в любую сторону на одну клетку. Обладает суперспособностями, но о них позже.
• Вандерер — зелёный монстрик. Появляется на карте раз в 5 ходов, из заранее известных точек. Спавнится в течение 3–6 ходов, ищет ближайшего игрока и начинает преследование. Ходит только на одну клетку за ход. Если никого не догнал за N шагов — исчезает с карты.
• Слэшер — похож на Смерть с косой. Появляются на месте игрока, чьё здоровье упало ниже 200 единиц, и остаются на карте до конца игры. «Видит» игрока, если между ними нет стен. Если за 2 хода цель не пропала из виду, на следующем ходу прыжком перемещается на место, где в последний раз видел игрока.

Выживание

Если вандерер или слэшер попадает на клетку с игроком — игрок теряет 20 единиц здоровья. Также игроки каждый ход теряют некоторое количество здоровья просто так. Но если в радиусе двух клеток есть живые исследователи, то здоровья теряется чуть меньше.

Суперспособности исследователей

• PLAN — в течение 5 ходов повышает здоровье на 2 единицы. Если в радиус действия попали другие исследователи, то эффект распространяется и на них, а создатель эффекта получает +2 здоровья за каждого. За игру можно использовать 2 раза.
• YELL — пугает игрока в соседней клетке. Запланированное на следующий ход действие превращается в WAIT (игрок будет просто стоять на месте). Полезно, если за противником гонится вандерер, и вы хотите его подставить.
• LIGHT — освещает клетки в радиусе 5, можно использовать 3 раза за игру. Помогает отпугивать вандереров: когда они подсчитывают путь до ближайшей цели, каждая освещённая клетка считается за 4.

Конец игры

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

Разработчики контеста дают игрокам правила, но успешные игроки идут на Github и читают код арбитра.

Тактика

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

Я сдавала в университете экзамен и не попала на хаб в Екатеринбурге, но воспользовалась бонусом от организаторов — starter kit-ом. Он доступен на двух языках — C# и TypeScript, и в нём уже реализована вся инфраструктура: логика чтения состояния игры на каждом ходе, а также классы, характеризующие саму игру (типа состояния и возможных действий), и некоторые вспомогательные (например, кастомный таймер). Я смогла сразу приступить к написанию самого интересного — мозгов своего бота исследователя.

Один из лидеров хаба в Екатеринбурге — Ваня Дашкевич (spaceorc). Он сидит на CodinGame уже больше года, поучаствовал в семи контестах, а в пяти попал в мировой топ-100:

Я узнала у Вани подробности решения, которое обеспечило ему 64 место в мировом лидерборде, и сравнила его решение со своим.

[1] Приходите на хабы: там можно получить ссылки на стартер-киты, обсудить правила, придумать тактику и познакомиться с интересными людьми.

Что в начале контеста, что в конце, алгоритм выбора следующего хода выглядит одинаково:

• Сгенерировать все доступные боту действия;
• Применить их к текущему состоянию;
• Оценить результаты этих ходов;
• Выбрать наилучший.

Генерация доступных действий

Ollisteka: Уже на этом шаге я начала применять эвристики — представляла себя на месте этого исследователя, и решала, что будет хорошо, а что не очень. Могу уйти на соседнюю свободную клетку? Добавляем такой ход. У меня остался неиспользованный план, а рядом нет вандерера или слэшера, который нападёт на меня на следующем ходу? Добавляем.

По этой же схеме в список возможных действий попадали LIGHT и YELL, но их использование только опускало меня ниже в лидерборде. Поэтому из финальной реализации я их всё-таки убрала.

[2] Не бойтесь включать фантазию: для начала достаточно простых эвристик и пары условных операторов.

Применение хода

Процесс применения хода к состоянию игры называется симуляцией. Наличие симуляции позволяет использовать продвинутые техники программирования ИИ: минимакс, генетические алгоритмы, Monte Carlo Tree Search и другие.

Ollisteka: Именно этот шаг относится к моей «недосимуляции». «Недо» — потому что после того, как я сходила, должны сходить остальные игроки, сходить или зареспавниться враги. Однако мне было лень делать полную симуляцию для четырёх игроков и большого количества врагов с нетривиальной логикой. Поэтому я только меняла своё здоровье в зависимости от того, одна я или в группе, и не натолкнулась ли на этом ходу на вандерера.

spaceorc: Мой обычный подход в последнее время состоит из двух шагов:

• доходишь любым способом до этапа, когда организаторы открывают все правила и скидывают исходники «рефери» на Github;
• берёшь рефери и пишешь, глядя в него, симуляцию.

Симуляция полная, со всеми нюансами, но неэффективная. Я обычно ставлю на быстроту и глубину перебора… Но полная симуляция позволяет запускать много матчей локально и сравнивать разные стратегии. Полную симуляцию я тестировал на CodinGame — предсказывал позиции миньонов, зная как сходили соперники (то есть на следующем ходу), и разбирался с расхождениями. Когда полная симуляцию была готова, начал писать быструю — это делать просто, имея работающую.

[3] Хотите попасть в топ? Придётся разобраться с правилами и написать симуляцию.

Симуляция противников

spaceorc: Написал Monte Carlo Tree Search, но он играл хуже, так как было слишком мало времени на перебор. Вообще, этот подход у меня зашёл более менее только в Ultimate Tic-Tac-Toe. Соперники играли так же — симуляция на ход плюс оценка, мои ходы — MCTS и доигрываем до конца. Удавалось таким способом симулировать за 50 мс порядка 200 игр до конца. Это мало для MCTS, поэтому я это выпилил и вернулся к исходной идее.

В результате быстрая симуляция стала неполной:

• перестал рассматривать вандереров дальше, чем за 8 клеток от меня;
• перестал спавнить вандереров, потому что они и так спавнятся за 5 ходов, а это моя глубина перебора примерно.

За счёт этого увеличилась глубина перебора. Ещё пробовал симулировать у соперников только ходы (без YELL, LIGHT, PLAN), но получилось хуже.

Оценочная функция

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

Ollisteka: Какие параметры входили в мою оценку:

• здоровье моего исследователя;
• вандереры:
  
  • если он скорее всего придёт сюда следующим ходом, то это плохой ход;
  • если я с ним на одной прямой — то чем дальше от него, тем лучше;
  • если он ещё и охотится на меня, то расстояние ещё важнее.
• свободные клетки вокруг, чтобы не забегать в тупик;
• остальные исследователи, к которым лучше держаться поближе;
• действующий PLAN: если моё здоровье опустилось ниже 230, то полечиться — хорошая идея.

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

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

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

• количество очков (тур, на котором умер + здоровье);
• Вороной;
• расстояние до чужих исследователей.

[4] Экспериментируйте: меняйте коэффициенты у параметров оценочной функции, добавляйте новые параметры и удаляйте старые.

Выбор наилучшего хода

Сортируем ходы по убыванию оценки, берём первый, используем.

Оптимизация

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

Ollisteka: Я воспользовалась тем, что карту можно представить в виде графа — посчитала заранее длины всех путей из клетки в клетку и не тратила на это время на каждом ходу.

spaceorc: На CodinGame симуляция работала быстро, за 50 мс делала несколько десятков тысяч ходов. За счёт чего:

• Битовые маски и unsafe code.
• Explorer — int, wanderer — int, slasher — int.
• Всё изменяемое состояние укладывается в 128 байт, поэтому с ним очень быстро всё работает.
• Координата — байт, потому что у самой большой карты было 222 свободных ячейки.
• Надо очередь — var queue = stackalloc byte[255].
• Предподсчёт путей, расстояний и прочего.

Я в последнее время постоянно так делаю, получается очень хорошо. На такую симуляцию, кстати, всегда пишу очень много тестов, без этого её просто никак не отладить.

[5] Хотите соревноваться за место в топ-100 — избавляйтесь от неэффективного кода.

К чему это привело

Ollisteka: На протяжении всего контеста мой бот уверенно держался в топ-300. В какой-то момент я даже была на 84 месте в мировом лидерборде, но потом закоммитила новую версию и обратно не вернулась ?(?)/? Финишировав на 290 месте, я весьма довольна по трём причинам:

• Это первый контест, в котором я приняла полноценное участие, так как во время прошлых была слишком загружена учёбой.
• Мне понравилась сама игра — было понятно, как играть и что делать, чтобы победить.
• Мировой топ-15 % — это звучит круто :)

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

spaceorc: Результатом скорее доволен, прошел же в топ-100… Но всё же надо было больше поработать над оценочной функцией, сильный перекос в сторону симуляции получился. А ещё устал под конец немного, фантазии не хватило…

В заключение

Заходите на CodinGame и пробуйте свои силы! В июле обещают новый контест — приходите на хабы, будем кодить ботов вместе.

Полезные ссылки:

• аккаунты на CodinGame: мой и Вани Дашкевича;
• следующий контест Legends of Code and Magic (на момент написания статьи уже 1392 зарегистрировавшихся);
• блог Контура и канал в Телеграме — ждите в них анонсы новых хабов.