Главная » Хабрахабр » [Перевод] Разработка ИИ на примере игры Dicey Dungeons

[Перевод] Разработка ИИ на примере игры Dicey Dungeons

Примерно в течение месяца я решал одну из самых сложных технических проблем моей новой игры Dicey Dungeons — совершенствол ИИ для финального релиза игры. Это была довольно интересная работа, и многое в ней стало для меня новым, поэтому я решил немного о ней написать.

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

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

Ну, давайте начнём с объяснения задачи!

Задача

На случай, если вы не играли в Dicey Dungeons, вкратце расскажу об игре: это RPG с построением колоды (deckbuilding), в которой у каждого врага есть набор карт вооружений, выполняющих различные действия. Кроме того, они бросают кубики! Затем они помещают эти кубики на вооружение, чтобы нанести урон, или создавать различные статусные эффекты, или лечиться, или защищаться от урона, и тому подобное. Вот простой пример того, как маленькая лягушка использует большой меч и малый щит:

Более сложный пример: у этого Мастера на все руки есть гаечный ключ (spanner), позволяющий сложить два кубика вместе (то есть 3 + 2 дадут 5, а 4 + 5 дадут 6 и 3). Также у него есть молоток (Hammer), который накладывает на игрока эффект «шока», если применить к нему шестёрку, и трубка для стрельбы горохом (Pea Shooter), которая наносит мало урона, но зато у неё есть «обратный отсчёт», то есть она действует несколько ходов.

Ещё одно важное усложнение: в игре есть статусные эффекты, изменяющие возможности противников. Самые важные из них — это шок (Shock), который случайным образом отключает вооружение; шок можно снять, использовав на него дополнительный кубик, и «горение» (Burn), которое поджигает кубики. Пока кубики горят, ими можно пользоваться, но каждое использование будет стоить 2 очка здоровья. Вот, что делает умный Мастер на все руки, когда я накладываю шок и горение на всё его вооружение и кубики:

Разумеется, в игре есть и многое другое, но чтобы получить общее представление, этого достаточно.

Как ему узнать, какой из горящих кубиков потушить, какой кубик использовать для снятия шока, а какой сохранить для важного вооружения? Итак, наша задача: как заставить ИИ выбрать лучшее действие для своего хода?

Как он поступал раньше

Долгое время ИИ в Dicey Dungeons имел всего одно правило: он смотрел на всё вооружение слева направо, определял наилучший кубик, который на него можно было использовать, а затем использовал его. Это работало замечательно, но бывали и исключения. Поэтому я добавил новые правила.

С горящими кубиками я работал так: проверял, достаточно ли у меня здоровья, чтобы их потушить, и случайным образом выбирал, нужно ли это делать. Например, я справлялся с шоком, глядя на всё не подверженное шоку вооружение, и выбирая, какой бы кубик я использовал на нём, когда шок был бы снят, а потом помечал этот кубик как «зарезервированный» на будущее.

На самом деле удивительно, насколько хорошо показывало себя это переплетение разных правил — ИИ в Dicey Dungeons может быть и не всегда принимал верное решение, но оно всегда было хотя бы приемлемым. Я добавлял правило за правилом для всего, что мог вообразить, и в результате получил ИИ, который вроде бы работал! По крайней мере, для игры, всё ещё находящейся в разработке.

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

Но думаю, что таким образом я просто отодвигал истинное решение задачи. Разумеется один из способов решения заключался в добавлении новых правил, рассмотрении каждой задачи одна за одной и создании новых конструкций if для их обработки. Она никогда не заглядывала вперёд и не пыталась предположить, что может получиться из конкретной умной комбинации. Ограничение системы заключалось в том, что её волновал только один вопрос: «Каким будет мой следующий ход?».

Поэтому я решил начать заново.

Классическое решение

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

Реализация минимакса выглядит следующим образом:

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

Допустим, в шахматах доска, на которой фигуры расположены в своих исходных позициях, оценивается в 0 очков. Затем мы создаём функцию ценности, измеряющую, насколько хорошо идёт игра для конкретной конфигурации игры, то есть для конкретной доски. А доска, на которой мы поставили противнику мат, будет оцениваться в бесконечное количество очков, или что-то вроде этого! Доска, на которой вы съели пешку противника, имеет ценность 1 очков, а доска, на которой вы потеряли собственную пешку — ценность -1 очков.

Затем мы симулируем совершение всех возможных ходов на этих досках, и так далее, столько шагов, сколько вам захочется. Затем, из этой абстрактной доски мы симулируем все возможные ходы, которые можем сделать, что даёт нам новые абстрактные доски. Вот превосходная иллюстрация подобного решения с сайта freecodecamp.org:

Мы создаём граф всех возможных ходов, которые могут совершить оба игрока, и применяем к нему функцию ценности для оценки того, как идёт игра.

И в этом Dicey Dungeons отличается от минимакса: минимакс пришёл из математической теории игр, он предназначен для нахождения наилучшей серии ходов в мире, где противник стремится максимизировать свой счёт. Алгоритм называется так, потому что он занимается минимизацией потерь игрока, когда противник играет, чтобы максимизировать свой выигрыш.

На самом деле меня не волнует, что делает мой противник. Но что происходит в Dicey Dungeons? Другими словами, мне важен только «макс», без «мини». Чтобы игра была увлекательной, искусственному интеллекту достаточно делать логичные ходы — определять наилучший способ применения кубиков к вооружению, чтобы бой был честным.

То есть, чтобы ИИ Dicey Dungeons совершал хороший ход, мне достаточно создать этот граф возможных ходов и найти доску, имеющую наибольшую оценку, а затем сделать ходы, ведущие к этой точке.

Простой ход противника

Ну, перейдём к примерам! Давайте снова рассмотрим лягушку. Как ей решить, что делать дальше? Как она узнает, что выбранное действие является наилучшим?

По сути, у неё есть всего два варианта. Поместить 1 на широкий меч, а 3 на щит, или сделать наоборот. Она очевидно решает, что лучше положить на меч 3, а не 1. Но почему? Потому что она изучила все возможные результаты:

Если положить на меч 1, то мы получим 438 очков. Если положить на него 3, то получим 558 очков. Замечательно! Значит, я получаю больше очков, помещая на меч 3, задача решена.

Система оценки в Dicey Dungeons на данный момент учитывает следующие аспекты: Откуда берутся эти очки?

  • Урон: самый важный фактор — 100 очков за каждое очко наносимого урона.
  • Яд: важный статусный эффект, который ИИ считает почти столь же важным, как урон — 90 за каждый яд.
  • Создание других статусных эффектов: например шока, горения, ослабления и т.д. Каждый из них стоит 50 очков.
  • Бонусные статусные эффекты: добавление к самому игроку положительных статусных эффектов, таких как защита и тому подобное, стоит по 40 очков каждое.
  • Использование вооружения: использование любого из видов вооружений стоит 10 очков, потому что если ничего другого не удалось, ИИ просто должен пытаться использовать всё.
  • Снижение обратного отсчёта: для активации некоторых видов вооружения (например, для Pea Shooter) просто достаточно общей суммы на кубиках. Поэтому ИИ получает по 10 очков за каждое уменьшенное им очко обратного отсчёта.
  • Точки на кубиках: ИИ получает 5 очков за каждую неиспользованную точку на кубике, то есть 1 стоит 5 очков, а 6 — 30 очков. Это сделано для того, чтобы ИИ предпочитал не использовать кубики, которые использовать не нужно, благодаря чему его ходы становятся очень похожими на человеческие.
  • Длительность: ИИ теряет по 1 очку за ход, поэтому долгие ходы имеют чуть меньшую ценность, чем короткие. Это сделано для того, чтобы при наличии двух ходов, во всём остальном имеющих одинаковую ценность, ИИ выбирал самый короткий.
  • Лечение: стоит всего 1 очко за одно восстановленное очко здоровья, потому что хоть я и хочу, чтобы ИИ считал это важным, но не очень следил за здоровьем. Всегда есть дела и поважнее!
  • Бонусные очки: их можно добавлять к любому ходу, чтобы заставить ИИ делать что-то, чего бы он в противном случае никогда не совершил. Используется очень умеренно.

И наконец, есть два особых случая — если у атакуемой цели кончается здоровье, то это стоит миллион очков. Если здоровье заканчивается у ИИ, то это стоит минус миллион очков. Это значит, что ИИ никогда случайно себя не убьёт (допустим, погасив кубик при очень низком здоровье), или никогда не пропустит ход, в котором может убить игрока.

Даже приблизительно точных чисел достаточно, чтобы стимулировать ИИ поступать более-менее правильно. Эти числа неидеальны — возьмём, например, текущие открытые issues: 640, 642, 649, но это не очень важно.

Более сложные ходы врага

Случай с лягушкой настолько прост, что даже мой ужасный код может вычислить все варианты всего за 0,017 секунды. Но потом ситуация становится сложнее. Давайте снова взглянем на пример с Мастером на все руки.

Его дерево решений «немного» сложнее:

К сожалению, даже в относительно простых случаях довольно быстро происходит взрыв сложности. В данном случае в нашем графе получается 2 670 узлов, которые нужно исследовать, и это занимает намного больше времени, чем в случае с лягушкой — возможно, одну-две секунды.

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

Итак, это первая серьёзная проблема такого подхода. Но даже если мы найдём и оптимизируем подобные ненужные ветви (что я в определённой степени и делаю), всегда будет существовать точка, в которой сложность всех возможных перестановок решений ведёт к огромным, медленным деревьям решений, оценка которых займёт бесконечное количество времени. Вот ещё одна:

Отмычка. Разделяет кубик на два.

Если я помещу на него шестёрку, то могу получить пять и один, или четыре и два, а может и две тройки. Этот важный тип вооружения (и подобные ему) вызывает у ИИ проблемы, потому что результат его применения является неопределённым. Я этого не узнаю, пока не сделаю, поэтому очень сложно создать план, который будет это учитывать.

К счастью, в Dicey Dungeons используется отличное решение обеих этих проблем!

Современное решение

Метод Монте-Карло для поиска в дереве (Monte Carlo Tree Search, MCTS) — это вероятностный алгоритм принятия решений. Ниже показано немного странноватое видео, которое, тем не менее, очень хорошо объясняет принцип принятия решений на основе метода Монте-Карло:

По сути, вместо того, чтобы добавлять в граф каждый возможный ход, MCTS проверяет последовательности случайных ходов, а затем отслеживает те из них, которые лучше себя проявили. Благодаря формуле под названием Upper Confidence Bound он волшебным образом может определить, какие ветви дерева решений «наиболее перспективны»:

Кстати, эту формулу я взял из очень полезной статьи про поиск по деревьям методом Монте-Карло. Не спрашивайте меня, как она работает!

То есть мы как бы используем оба алгоритма. Удивительно в MCTS то, что для нахождения наилучшего решения нам обычно не нужно выполнять тупой перебор всего, и мы можем применить такую же абстрактную систему симуляции доски/ходов, как и в минимаксе. Сначала она пытается выполнить полное разворачивание дерева решений, что обычно не занимает много времени и приводит к наилучшему результату. Именно такую схему я и использовал в Dicey Dungeons. Но если дерево кажется слишком большим, то мы откатываемся к использованию MCTS.

У MCTS есть два очень крутых свойства, которые идеально подходят для Dicey Dungeons:

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

По сути, при работе с MCTS можно выполнять сколько угодно симуляций. Во-вторых, он может дать мне частичное решение. Однако мне важнее то, что я могу использовать MCTS для получения хорошего решения за ограниченное количество времени обдумывания. Теоретически, если его выполнять бесконечно, он сойдётся к точно таким же результатам, как и минимакс. Чем больше поисков мы выполняем, тем лучше будет найденное «решение», но в случае Dicey Dungeons часто достаточно всего нескольких сотен поисков, которые занимают малую долю секунды.

Интересные близкие темы

Итак, вот как враги в Dicey Dungeons решают, как вас убить! Я хочу добавить эту систему в ближайшую версию v0.15 игры!

Откуда взялись графы, которые я показывал, в том числе и в twitter:

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

В результате я реализовал систему скриптинга действий. Часть решения этой задачи заключалась в том, чтобы позволить ИИ симулировать ходы, что само по себе является интересной головоломкой. они выполняют вот такие небольшие скрипты: Теперь когда противники используют разные типы вооружений.

Эти небольшие скрипты выполняются hscript — парсером и интерпретатором выражений на основе haxe. Эту часть реализовать было сложно, но усилия себя оправдали: она сделала игру сверхудобной для создания модов. Надеюсь, что после выхода игры люди могут использовать эту систему для разработки собственного вооружения, то есть они смогут добавить в игру практически всё, что способны вообразить. Кроме того, так как ИИ достаточно умён, чтобы оценивать любое передаваемое ему действие, враги смогут разбираться, как пользоваться любым модифицированным вооружением, которое создадут игроки!


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

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

*

x

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

[Перевод] CG-моделинг 80 уровня: фотореалистичные персонажи real-time в Unreal

На днях тестировали новую графику в War Robots и получили уйму положительного фидбека от игроков. И хотя речь о мобильной графике, места для роста там очень много. С десктопом еще интереснее. Если раньше на рендер качественной сцены с фотореалистичными моделями ...

[Перевод] IntelliCode теперь и в TypeScript/JavaScript

На Build 2018 мы анонсировали Visual Studio IntelliCode: набор AI-инструментов, которые способствуют более качественной разработке. В сотрудничестве с командой IntelliCode мы рады сообщить, что теперь IntelliCode доступен пользователям TypeScript/JavaScript через расширение IntelliCode для VS Code. Что такое IntelliCode? IntelliCode дополняет ...