- PVSM.RU - https://www.pvsm.ru -
Всем привет, меня зовут Оля. Две недели назад на CodinGame завершился очередной контест — соревнование по программированию ботов для игры. Я попала в топ-300 мирового лидерборда, поэтому хочу рассказать, почему контесты это круто, и поделиться своими секретами. А ещё секретами поделится Иван spaceorc [1], который попал в топ-100 того же соревнования.
Вы узнаете, как успешно выступать на соревнованиях по программированию игрового искусственного интеллекта.
codingame.com [2] — обучающая платформа для разработчиков всех возрастов и уровней подготовки. Можно писать на 26 языках [3]: от C# и Python до Bash и Haskell. Самое крутое, что задачки там не скучные и непонятные, а настоящие игры с неплохим GUI:
Контест — это 10-дневное соревнование, которое проводится раз в пару месяцев. Поучаствовать может любой желающий, не обязательно быть финалистом ACM ICPC. Конечно, чтобы попасть в самый топ, нужно как минимум разбираться в алгоритмах, типичных для игрового искусственного интеллекта.
Но чтобы с интересом провести пару вечеров, хватит самых начальных знаний. В каждом контесте есть готовый код для чтения входных данных. Остаётся только прочитать правила, написать простенькие if-else — и в бой!
«Код Ктулху» — последний контест, который проходил с 15 по 25 июня. Чтобы узнать сюжет и цель, достаточно описания:
PH'NGLUI MGLW'NAFH CTHULHU R'LYEH WGAH'NAGL FHTAGN
Что может вечно лгать, то вовсе не мертво. И умирает Смерть в загадочный эон.Вы с вашей командой исследователей открыли гробницу Ктулху. Это самое худшее решение в вашей жизни, так как он был не готов проснуться и теперь жаждет вашей смерти. Но склеп — настоящий лабиринт, а вы не помните, где был выход… Если он до сих пор есть!
Оу… и кажется, что Ктулху был не один, и теперь он посылает за вами Глубинных.Постарайтесь дольше всех оставаться в живых, но помните, что в одиночку вы долго не протянете…
Сразу скажу, что вместо чтения текстового описания правил, можете посмотреть видеозапись разбора правил и базовых тактик от Tinsane [4]:
Иначе читайте дальше.
В игре четыре игрока ходят по сгенерированной карте — точнее, графу связанных друг с другом клеток. Ещё по карте бегают вражеские миньоны, чья цель — догнать и напугать игроков.
Если вандерер или слэшер попадает на клетку с игроком — игрок теряет 20 единиц здоровья. Также игроки каждый ход теряют некоторое количество здоровья просто так. Но если в радиусе двух клеток есть живые исследователи, то здоровья теряется чуть меньше.
Игрок умирает, если здоровье падает до нуля. После 200 ходов оставшиеся в живых игроки начинают терять здоровье быстрее, и игра практически сразу заканчивается.
Разработчики контеста дают игрокам правила, но успешные игроки идут на Github и читают код арбитра [5].
Сразу скажу, что я начинала не с нуля. 16 июня Контур проводил coding hub-ы в семи городах [6] — встречи для желающих обсудить контест и покодить в приятной обстановке (фото [7]).
Я сдавала в университете экзамен и не попала на хаб в Екатеринбурге, но воспользовалась бонусом от организаторов — starter kit-ом. Он доступен на двух языках — C# [8] и TypeScript [9], и в нём уже реализована вся инфраструктура: логика чтения состояния игры на каждом ходе, а также классы, характеризующие саму игру (типа состояния и возможных действий), и некоторые вспомогательные (например, кастомный таймер). Я смогла сразу приступить к написанию самого интересного — мозгов своего бота исследователя.
Один из лидеров хаба в Екатеринбурге — Ваня Дашкевич (spaceorc [1]). Он сидит на CodinGame уже больше года, поучаствовал в семи контестах, а в пяти попал в мировой топ-100:
Я узнала у Вани подробности решения, которое обеспечило ему 64 место в мировом лидерборде, и сравнила его решение со своим.
[1] Приходите на хабы: там можно получить ссылки на стартер-киты, обсудить правила, придумать тактику и познакомиться с интересными людьми.
Что в начале контеста, что в конце, алгоритм выбора следующего хода выглядит одинаково:
Ollisteka [10]: Уже на этом шаге я начала применять эвристики — представляла себя на месте этого исследователя, и решала, что будет хорошо, а что не очень. Могу уйти на соседнюю свободную клетку? Добавляем такой ход. У меня остался неиспользованный план, а рядом нет вандерера или слэшера, который нападёт на меня на следующем ходу? Добавляем.
По этой же схеме в список возможных действий попадали LIGHT и YELL, но их использование только опускало меня ниже в лидерборде. Поэтому из финальной реализации я их всё-таки убрала.
[2] Не бойтесь включать фантазию: для начала достаточно простых эвристик и пары условных операторов.
Процесс применения хода к состоянию игры называется симуляцией. Наличие симуляции позволяет использовать продвинутые техники программирования ИИ: минимакс [11], генетические алгоритмы [12], Monte Carlo Tree Search [13] и другие.
Ollisteka [10]: Именно этот шаг относится к моей «недосимуляции». «Недо» — потому что после того, как я сходила, должны сходить остальные игроки, сходить или зареспавниться враги. Однако мне было лень делать полную симуляцию для четырёх игроков и большого количества врагов с нетривиальной логикой. Поэтому я только меняла своё здоровье в зависимости от того, одна я или в группе, и не натолкнулась ли на этом ходу на вандерера.
spaceorc [1]: Мой обычный подход в последнее время состоит из двух шагов:
Симуляция полная, со всеми нюансами, но неэффективная. Я обычно ставлю на быстроту и глубину перебора… Но полная симуляция позволяет запускать много матчей локально и сравнивать разные стратегии. Полную симуляцию я тестировал на CodinGame — предсказывал позиции миньонов, зная как сходили соперники (то есть на следующем ходу), и разбирался с расхождениями. Когда полная симуляцию была готова, начал писать быструю — это делать просто, имея работающую.
[3] Хотите попасть в топ? Придётся разобраться с правилами и написать симуляцию.
spaceorc [1]: Написал Monte Carlo Tree Search, но он играл хуже, так как было слишком мало времени на перебор. Вообще, этот подход у меня зашёл более менее только в Ultimate Tic-Tac-Toe [14]. Соперники играли так же — симуляция на ход плюс оценка, мои ходы — MCTS и доигрываем до конца. Удавалось таким способом симулировать за 50 мс порядка 200 игр до конца. Это мало для MCTS, поэтому я это выпилил и вернулся к исходной идее.
В результате быстрая симуляция стала неполной:
За счёт этого увеличилась глубина перебора. Ещё пробовал симулировать у соперников только ходы (без YELL, LIGHT, PLAN), но получилось хуже.
Оценочная функция помогает выбрать из всех доступных ходов самый лучший. Она берёт состояние игры на вход, а на выход даёт число с оценкой — чем она больше, тем лучше состояние игры для текущего игрока.
Ollisteka [10]: Какие параметры входили в мою оценку:
В какой-то момент я пыталась оценивать и слэшеров, но, когда убрала их, меня подняло на пару десятков мест в лидерборде. Если бы я проработала их логику получше, то, возможно, они бы принесли больше пользы.
В итоге моя оценочная могла быть и поменьше, но, как говорится, работает — не трогай.
spaceorc [1]: Попробовал поиграться с оценочными функциями, но вот тут получилось не очень… В целом, некоторые из тех, кто оказался существенно выше меня в лидерборде, перебирали вообще не так много, но придумывали хорошие фичи для оценки. Я с этим не справился. В мою финальную оценочную функцию вошли:
[4] Экспериментируйте: меняйте коэффициенты у параметров оценочной функции, добавляйте новые параметры и удаляйте старые.
Сортируем ходы по убыванию оценки, берём первый, используем.
Чтобы бороться за место в сотне лучших — недостаточно иметь хорошую оценочную функцию и полную симуляцию. Чем быстрее работает бот, тем больше игр будет просимулировано за квант времени. Чем больше игр, тем больше шансов, что текущий ход — самый оптимальный. Чем оптимальнее ход, тем выше место в лидерборде.
Ollisteka [10]: Я воспользовалась тем, что карту можно представить в виде графа — посчитала заранее длины всех путей из клетки в клетку и не тратила на это время на каждом ходу.
spaceorc [1]: На CodinGame симуляция работала быстро, за 50 мс делала несколько десятков тысяч ходов. За счёт чего:
Я в последнее время постоянно так делаю, получается очень хорошо. На такую симуляцию, кстати, всегда пишу очень много тестов, без этого её просто никак не отладить.
[5] Хотите соревноваться за место в топ-100 — избавляйтесь от неэффективного кода.
Ollisteka [10]: На протяжении всего контеста мой бот уверенно держался в топ-300. В какой-то момент я даже была на 84 месте в мировом лидерборде, но потом закоммитила новую версию и обратно не вернулась ¯(ツ)/¯ Финишировав на 290 месте, я весьма довольна по трём причинам:
Было очевидно, что для попадания в топ нужно сделать полную и быструю симуляцию. Но делать этого не хотелось, поэтому я просто добавляла параметры в оценочную функцию и меняла магические константы.
spaceorc [1]: Результатом скорее доволен, прошел же в топ-100… Но всё же надо было больше поработать над оценочной функцией, сильный перекос в сторону симуляции получился. А ещё устал под конец немного, фантазии не хватило…
Заходите на CodinGame и пробуйте свои силы! В июле обещают новый контест — приходите на хабы, будем кодить ботов вместе.
Полезные ссылки:
Автор: Жукова Ольга
Источник [21]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/285589
Ссылки в тексте:
[1] spaceorc: https://habr.com/users/spaceorc/
[2] codingame.com: https://www.codingame.com/
[3] 26 языках: https://www.codingame.com/faq
[4] Tinsane: https://habr.com/users/tinsane/
[5] код арбитра: https://www.google.com/url?q=https://github.com/JohnnyGuye/code-of-kutulu/
[6] в семи городах: https://habr.com/company/skbkontur/blog/413577/
[7] фото: https://twitter.com/igorlukanin/status/1007926730403741696
[8] C#: https://github.com/kontur-contests/codingame-kutulu-starterkit-cs
[9] TypeScript: https://github.com/kontur-contests/codingame-kutulu-starterkit-ts
[10] Ollisteka: https://habr.com/users/ollisteka/
[11] минимакс: https://www.youtube.com/watch?v=J1GoI5WHBto
[12] генетические алгоритмы: https://tech.io/playgrounds/334/genetic-algorithms
[13] Monte Carlo Tree Search: http://mcts.ai/about/
[14] Ultimate Tic-Tac-Toe: https://www.codingame.com/multiplayer/bot-programming/tic-tac-toe
[15] Вороной: https://ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0_%D0%92%D0%BE%D1%80%D0%BE%D0%BD%D0%BE%D0%B3%D0%BE
[16] мой: https://www.codingame.com/profile/ca4733dea5c284c3cf10b6fa4c4d4b172663742
[17] Вани Дашкевича: https://www.codingame.com/profile/2e0a3c013b91c554d4a8ebf14ad1633e0904491
[18] Legends of Code and Magic: https://www.codingame.com/contests/legends-of-code-and-magic
[19] блог Контура: https://habr.com/company/skbkontur/
[20] канал в Телеграме: https://t.me/KonturTech
[21] Источник: https://habr.com/post/416607/?utm_source=habrahabr&utm_medium=rss&utm_campaign=416607
Нажмите здесь для печати.