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

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

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

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

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

image

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

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

Чтобы узнать сюжет и цель, достаточно описания: «Код Ктулху» — последний контест, который проходил с 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-ы в семи городах — встречи для желающих обсудить контест и покодить в приятной обстановке (фото). Сразу скажу, что я начинала не с нуля.

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

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

image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image

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

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

Оптимизация

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

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

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

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

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

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

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

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Вышла Oracle Database 18c XE

Можно открывать шампанское и закатывать вечеринку — спустя более, чем 7 лет с момента выпуска предыдущего релиза, для скачивания наконец доступна свежайшая Oracle Database 18c XE. Свершилось! Пока только для Linux x64, но версии для других платформ, также как и ...

Palm возрождается из пепла с новым гаджетом

Ее разработки служили примером для других компаний, в свое время поклонников продукции Palm было не счесть. Компания Palm навсегда вписана в историю современного «железа». Но устройства компании и ее программное обеспечение до сих пор популярны у гиков. Как и многим ...