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

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


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


    Что такое CodinGame


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


    image


    Контест — это 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:


    image


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


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

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


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

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


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


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


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

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


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


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


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


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

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


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

    image


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


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

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


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


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

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


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


    В заключение


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


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



    UPD. Спасибо dbf за комментарий: Code of Kutulu выложили в мультиплеер. Так что можно применить полученные в статье знания на практике! :)

    Контур 93,89
    Делаем веб-сервисы для бизнеса
    Поделиться публикацией
    Комментарии 15
      0

      Ну вот, а я играл по наитию, использовал тривиальную оценочную функцию и занял 241 место :) В следующем контесте попробую воспользоваться советами и напишу какой-нибудь простой симулятор.


      Не понял только, что значит, что spaceorc «использовал Вороного» в оценочной функции. Диаграммы Вороного я знаю, но как их тут применить?

        +1
        Я считал диаграмму Вороного для себя и вандереров (без слэшеров). Количество «моих» клеток входило как часть оценочной функции… Это позволяет не давать себя зажать, если перебираешь достаточно глубоко. Поскольку все расстояния были предрасчитаны заранее, расчет был очень быстрым — просто цикл по всем координатам (их 255 штук) по сравнение расстояния до меня и всех вандереров (их 8 — ближайших в моей симуляции, остальные игнорируются).

        Но, если по честному, эта фича не дала статистически значимого преимущества, в сравнении с другими моими стратегиями. В результате у меня было две примерно равных по силе стратегии. Качественно выбрать, что сабмитить как финальное решение, я не успевал уже, потому выбирал по наитию.
          +1
          Получилось уделить этому контесту где-то час времени. Реализовал алгоритм A*. Веса ребер на основе текущей ситуации на доске. Кажется, что алгоритмы на графах тоже были перспективны в данном контесте. По поводу необходимости писать симуляцию — не соглашусь, контесты CodinGame выгодно отличаются тем, что вполне допускают конкурентноспособную эвристику. В топе есть участник Khao (9 место) — он принципиально пишет эвристику на js. От себя добавлю, если есть цель попасть в топ 20, то это практически всегда бешеные трудозатраты.
            +2
            На мой взгляд, когда появляются исходники рефери, все эти игры превращаются в соревнование «перепиши рефери на свой любимый ЯП как можно быстрее» и посчитай 100500 ходов вперед.

            Вот бои или гонки автономных роботов должны быть интереснее. Там исходный код противника уже не посмотришь и не просимулируешь.
              0
              Можно и сильно усложнить игру, а условием сделать полное уничтожение типа как здесь
              Вроде на CD не посмотришь код соперников.
                +1
                Но ведь и в таких контестах нельзя посмотреть исходный код остальных игроков. Поэтому всегда остаётся интерес: постараться угадать действия противника, и сходить так, чтобы ему было похуже, а нам получше. И тут не поможет идеальная симуляция:

                Допустим, Петя думает, что вражеский исследователь следующим ходом перейдёт на соседнюю клетку. А враг бах, и делает YELL на Петю. А Петя уже 100500 ходов просимулировал в расчёте на то, что враг просто убежал. Скорее всего, ход, который он получил в итоге — не очень, и выиграть ему не поможет.
                  +1
                  когда появляются исходники рефери, все эти игры превращаются в соревнование «перепиши рефери на свой любимый ЯП как можно быстрее» и посчитай 100500 ходов вперед.

                  Нет, просто вместо борьбы эвристик начинается борьба оценочных функций и стратегий сортировки ходов и отсечения ветвей. 100500 ходов вперёд получится только у того, кто сможет оптимально отбросить 100^500 ходов вбок.

                    +2

                    На самом деле, конечно, в борьбе оценочных функций нет ничего плохого. Фичи люди придумывают самые разные. Да и в условной "сортировке ходов и отсечении ветвей" много вариантов. Можно делать альфабету, mcts, генетические алгоритмы, что-то, наверное, еще. Если соперники ходят одновременно, как, скажем, в любых гонках, то можно потратить часть времени хода и пытаться предсказывать ходы соперника разными стратегиями, и считать статистику по ходу игры, чтобы выбирать, какая лучше предсказывает.


                    Это все есть почти в любом "стандартном" игровом контесте. А бывают и нестандартные контесты, типа code4life, когда у меня была чистая эвристика, потому что не придумал, что там можно перебирать.


                    В общем, я играю год всего, и мне пока не надоело. :)

                      +1

                      Это да, мало запилить симуляцию. Надо ещё понять, что с ней делать в отягчающих обстоятельствах, как то: больше двух игроков (не работает наивная альфа-бета), недискретность (непрерывное пространство без ячеек/графов, большой фактор ветвления), одновременность ходов (нет шахматных plies), неопределённость («туман войны», «природа»).

                  0
                  Только посматриваю в сторону CD, поэтому может задам пару нубских вопросов:
                  В какой-то момент я даже была на 84 месте в мировом лидерборде, но потом закоммитила новую версию и обратно не вернулась

                  А почему нельзя было загрузить старую версию и вернуть место?

                  я так понимаю это ваша симуляция?
                  Заголовок спойлера
                  image

                  вроде нагуглил есть локальные ранеры от самого CD и энтузиастов
                  ими нельзя воспользоваться для симуляции?
                    +2
                    К тому моменту, когда откатилась обратно, другие игроки уже тоже поменяли свои стратегии, против них старая версия играла не очень хорошо.

                    Это визуализация симуляции :) Делал spaceorc, для удобства отладки.

                    Ранеры (или brutaltester-ы) — это не про симуляцию. Они только запускают матчи локально, вызывая в нужных местах методы из реализаций бота и из кода рефери. Поэтому, если у вас уже есть своя симуляция и несколько разных стратегий, то можно сохранить их, скормить brutaltester-у, и он уже покажет статистику, какая из стратегий круче.
                      +1

                      Я вижу там ShelterMe.java. Неужели spaceorc отвернулся от C# и перешёл на тёмную сторону :)

                        0
                        Я думаю, он просто импортировал карту из исходников, а они как раз таки на Java :)
                          +1
                          Это джавовские классы из рефери, описывающие лабиринты.
                          Я просто парсю их регулярками в брутал-тестере :)
                      +2
                      Если кто, прочитав статью, захочет поиграть, то вчера игру добавили в мультиплеер-режиме: www.codingame.com/ide/puzzle/code-of-kutulu

                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                      Самое читаемое