Как именно Google будет побеждать всех в StarCraft. Часть2

В первой статье цикла мы описали основные моменты, отличающие RTS игры, к коим относится SC:BW, от традиционных настольных игр, в которых искусственный интеллект уже победил человека. Теперь увеличим уровень абстракций и постараемся выделить задачи более высокого уровня, которые появляются при попытке построить AI для игры в StarCraft.

Продолжим рассказ о неизведанном мире ботостроения для Starcraft, об участии в котором весной 2016 года заявила компания Google (DeepMind).

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

В этой части мы увеличим уровень абстракций и постараемся выделить задачи более высокого уровня, которые появляются при попытке построить AI для игры в StarCraft. Попутно попробуем зафиксировать терминологию, которая незначительно отличается от той, которую мы привыкли слышать, смотря киберспортивные трансляции. Статья написана по мотивам материалов университета Альберта. 

Прежде всего, давайте зафиксируем, что должен представлять из себя бот? Для этого нужно описать требования, которые предъявляются к искусственному интеллекту для игры в Starcraft. Кратко их можно сформулировать так: “Бот должен играть по тем же правилам, что и игрок”. Если говорить конкретнее, то:

  • Бот не использует техники, позволяющие ему наблюдать все игровое поле (т.е. бот не пользуется мапхаком). Боту, как и живому игроку, необходимо осуществлять разведку для получения информации о деятельности противника. Стандартный ИИ из SC:BW нарушает это правило, во время первой атаки присылая войска прямиком к вам на базу, без разведки.
  • Бот добывает ресурсы с той же скоростью, что и игрок. Сильный ИИ из StarCraft 2 нарушает это правило, добывая ресурсы быстрее.
  • Бот строит здания и войска с той же скоростью, что и игрок.
  • Юниты бота обладают такими же характеристиками, что и юниты игрока.

Другими словами, бот должен быть способен полностью заменить живого игрока в стандартной игре на ладдере.

Ранние исследователи в области AI для RTS определяли следующие 6 задач:

  • Управление игровыми ресурсами (минералы/газ) и их планирование.
  • Моделирование оппонента и обучение.
  • Принятие решение в условиях неопределенности.
  • Пространственный и временной менеджмент.
  • Командное взаимодействие (между несколькими агентами в командных играх).
  • Планирование в реальном времени для противостояния текущей тактике оппонента.

Кроме всего этого, есть вполне конкретный челлендж, связанный с использованием огромного массива знаний о предметной области (страты, билды, реплеи и т д), которые накоплены за долгие годы огромным сообществом.

Вообще говоря, если вы когда-либо пытались научить кого-нибудь (друга, ребенка, девушку/жену, родителей) играть в RTS вообще и в StarCraft в частности, то скорее всего все эти элементы игры вы так или иначе объясняли своим ученикам. Оставляя разговоры о психологической стороне вопроса, связанные с тем, что мотивация нового живого игрока не всегда формулируется как “побеждать в каждом игровом матче”, перейдем к обсуждению вышеописанных задач в том виде, в котором они необходимы для построения AI.

Планирование

Как мы разбирали ранее, размер пространства состояний в игре катастрофически огромен. Стандартные практики планирования, основанные на деревьях решений, не работают. Кроме того, AI должен осуществлять планирование на нескольких уровнях: высокоуровневое планирование включает в себя планы по использованию возможностей для развития сильной экономики и армии, а низкоуровневое планирование включает в себя обеспечение правильной координации юнитов на поле боя с учетом ландшафта и действий противника. Разумеется, мы, выросшие в киберспортивной атмосфере, чаще говорим об этих видах планирования, называя их макро и микро, вкладывая в эти слова еще и реализацию этих планов.

Обучение

Из-за сильного ветвления дерева состояний игры, многие исследователи вместо моделирования техник планирования макро и микро сосредоточили усилия на техниках обучения AI планированию. Сразу выскажем некоторое замечание, что применительно к задаче построения AI: обучаться должен именно бот – программа, а не тот, кто его разрабатывает. Эта оговорка крайне важна, поскольку для человека с обширным игровым опытом может показаться очевидным, как использовать те или иные знания, но применительно к AI никаких знаний на первом этапе не существует, их AI должен выработать самостоятельно, опираясь на поток некоторых событий, которые не всегда имеют метки “полезно, делай так” и “вредно, никогда так не делай”.

Традиционно выделяют 3 проблемы обучения:

  • Доигровое обучение. Как можно использовать исторически накопленные данные, такие как реплеи или информацию о специфике карты для изучения подходящих стратегий до начала игры? Существенное количество исследовательских работ пошло именно в этом направлении. В контексте высказанного ранее замечания это значит, что, например, из архива реплеев игр, произошедших на какой-то карте, бот должен вынести какие-то элементы успешной игры (опенинги, застройки, тот факт, что рабов в начале игры нужно отправлять на минералы, а не в атаку).
  • Внутриигровое обучение: Как могут боты использовать техники обучения в реальном времени, которые позволят ему улучшить свое мастерство во время игры? Эти техники могут включать в себя как обучение с подкреплением, так и техники моделирования противника. Как это происходит у людей, неплохо описано в проверенной временем статье “Об уровнях понимания игры”, пережившей уже не одно перерождение (изначально написанная про  SC:BW, она подтвердила свою актуальность и для WC3, Dota(2), SC2 и вот теперь снова для SC:BW, но уже в контексте AI). Говоря простыми словами, если AI вдруг понял, что разложенные танки хороши против собак, то, видя у врага собак, он должен понять, что достроить танки - это хорошее решение (но что если это мута-линги?).
  • После-игровое обучение: Какие выводы можно сделать после завершения одной игры, чтобы повысить свои шансы на победу в следующей игре? Катая ладдер, вы часто пересматриваете демки только что отыгранных матчей с целью понять, какое решение было правильным, а какое нет? Как боту научиться понимать, что было хорошо, а что было плохо? Среди трех обозначенных направлений в данном успехи наименьшие.

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

 


К сожалению, даже для прохождения PvE составляющей Starсraft такие эксперименты до сих пор остаются слишком сложными и не особо привлекают внимание одиночных исследователей. В отличие от Марио, в Starcraft под нашим контролем намного больше одного юнита и намного большее количество доступных для выполнения им действий. Однако для моделирования подведения отдельных юнитов такие эксперименты показывают неплохой результат:

2 вультурки и танк против 3 ультралов:

 


Убегающая вультурка:

 


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

Борьба с неопределенностью

Боту запрещено “использовать мапхак”. Тогда, во-первых, каким образом AI необходимо делать разведку? Как интерпретировать полученную информацию и делать вывод о ненаблюдаемом? Во-вторых, неопределенность возникает из-за того, что оппонент может удивлять, а AI априори не способен предсказывать действия противника.

Пространственный и временной менеджмент

Грамотное управление пространством подразумевает максимально эффективное использование рельефа карты для решения игровых задач. Эта компетенция используется при принятии решений относительно задач строительства баз и экспандов: максимально эффективное расположение зданий с целью удобства их защиты, выстраивание стенок, а также избегание ситуаций, в которых юниты будут застревать между строениями. Кроме того, AI должен определять, какую из локаций наиболее выгодно занимать, ставя нычку. Наконец, рассуждения об использовании местности должны закладываться в основу тактических рассуждений. Так, например, AI должен грамотно перемещать войска, пытаясь поймать “на муве” оппонента или нападать на противника, когда его войска расположены в неудачном порядке.

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

Декомпозиция задач

В свете вышеизложенного мы наконец готовы попытаться описать блоки, на которые необходимо разделить игровой процесс. К сожалению, привычные киберспортивные термины макро и микро фактически являются метафорами и не достаточно конкретны для описания подсистем AI.

91484_V6s8.png

Стратегия. Это самый высокоуровневый процесс принятия решения. Задача поиска эффективной стратегии против оппонента ключевая в RTS играх. Сюда включают построение грамотного билдордера и его оперативное изменение для наиболее эффективного противодействия противнику. На стратегическом уровне работа идет с ресурсами и всем набором юнитов и зданий, подконтрольных игроку.

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

Реактивное управление (от слова реакция). Реализация конкретной тактики, включающая в себя перемещение, нацеливание, атаку (и применение способностей), дропы юнитов, техники байтинга и кайтинга в моменты битв. Реактивное управление сконцентрировано вокруг управления конкретными юнитами.

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

Сбор информации. В данном блоке предпринимаются действия для нивелирования действия тумана войны. Игроки должны регулярно разведывать оппонента и по возможности не давать ему получать ценную информацию.

Полноценный игровой AI должен обладать способностями для решения всех поставленных задач. Все эти задачи радикально отличаются друг от друга, но решение каждой из них так или иначе используется во всех оставшихся. Приятная новость заключается в том, что каждый из модулей, решающих вышеописанные задачи, может разрабатываться и тестироваться по отдельности. Кроме того, модули могут требовать для разработки достаточно различных компетенций. Что в свою очередь говорит о том, что успешный супер-AI можно построить, только координируя усилия нескольких специалистов (или усилиями одного суперграмотного). При этом, успешным этот AI будет только при условии скоординированный работы каждого из получившихся модулей. Вот уж где можно наблюдать настоящий архонт-мод.

91482_epc2.png

Промежуточные выводы

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

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

Теперь, обозначив основные задачи, мы можем поговорить о том, как они решаются сегодняшними разработчиками AI для Starcraft.

91486_gsi5.png

Но об этом в следующей части.