Всем привет, меня зовут Оля. Две недели назад на 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 зарегистрировавшихся);
- блог Контура и канал в Телеграме — ждите в них анонсы новых хабов.
Автор: Жукова Ольга
