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

Не так давно, после победы над человеком в Го, представители Google (DeepMind) заявили о своих намерениях создать искусственный интеллект, способный победить человека в StarCraft. 
В данной серии статей хотелось бы раскрыть тему создания ИИ для StarCraft более подробно.

Заметки, посвященные этому заявлению, выходили и ранее.

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

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

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

Мы постараемся ответить на следующие вопросы:

  • В чем сложность моделирования игрового процесса в StarCraft?
  • Где боты мерятся силами и каких успехов они достигли?
  • Каким образом сегодня подходят к решению задачи обучения искусственного интеллекта игре во что-либо (поговорим о тех самых нейронных сетях и многом другом)?

А первую часть это цикла мы начнем с ответа на главный вопрос:

Почему везде пишут StarCraft, а не StarCraft 2?

Если до этого момента вы что-то подозревали, то чутье вас не обмануло. В челендже речь действительно шла о победе над человеком не в StarCraft 2, а в SC:BW.

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

Вопрос о выборе игры, как правило, упирается в вопрос о программном интерфейсе, через который бот будет манипулировать объектами в игре. В настоящий момент на всех соревнованиях искусственного интеллекта по Starcraft используется BWAPI – полученный реверс инженерингом интерфейс для чтения и записи данных в память процесса SC:BW. Поскольку любая программа, которая осуществляет такие действия, по сути ничем не отличается от МапХака, в определенный момент официальные лица Blizzard обратились к сообществу с заявлением о том, что они не хотят, чтобы что-то подобное было сделано для каких-либо других их игр, включая StarCraft2.
При этом, Blizzard разрешает проведение турниров по SC:BW среди искусственных интеллектуальных агентов, иной раз предоставляя призы для победителей. Есть мнение, что попытки организовать подобные соревнования по LoL или Dota 2 в конечном счете натолкнутся на аналогичные аргументы со стороны разработчиков и издателей.

Дабы закрыть разговор об основном инструменте (BWAPI), приведем ссылку на него.

По ссылке можно почитать о том, как все это работает на низком уровне подробнее, а также изучить тут ориалы и примеры в wiki. Осторожно, С++!

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

Чем же так сложен StarCraft?

Человечеству уже удалось создать достаточно большое количество программ, обыгрывающих человека в классические настольные игры:  Шашки, Шахматы и Го. Давайте попробуем опустить SC:BW на уровень шахмат и пронаблюдать различия между ними (для матерого игрока эти отличия могут показаться смешными, но для разработчиков AI они принципиальны). C теоретической точки зрения (с точки зрения архитектуры по) основные различия между RTS и традиционными настольными стратегиями, такими как шахматы, заключаются в следующем:

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

Буквы R и T в аббревиатуре RTS означают “real-time”, что с практической точки зрения означает, что каждый игрок обладает крайне малым количеством времени для принятия решения относительно следующего своего действия. По сравнению с Шахматами или Го, где в распоряжении каждого из игроков есть несколько минут для выполнения следующего хода, в StarCraft игра обновляется 24 раза в секунду, что в теории означает, что игрок мог бы принимать решение каждые 42 ms, прежде чем игровое состояние снова изменится. Это кажется немного диким: хочется думать, что не нужно так часто реагировать на изменение игровой ситуации. Но все мы помним эксперимент по разведению лингов во время атаки на сидж танки:

 


Cплит мариков от бейлингов:

 


И не менее очаровывающие результаты при меньшей скорости реакции – видео с 3 мариками, убивающими 2 люров в SC:BW, – золотая классика жанра.

 


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

В StartCraft, как и в большинстве других RTS/MOBA игр, игроки могут наблюдать только часть карты, на которой есть их (или дружественные им) юниты. Капитан подсказывает, что это называется туманом войны. С теоретической точки зрения это накладывает на игру условия неполноты информации. Представьте, как изменились бы шахматы, если бы игроки наблюдали вражеские фигуры только в непосредственной близости от своих.

В большинстве игр существует элемент недетерменированности (непредсказуемости). Некоторые действия имеют только некоторый шанс на успех. Применительно к SC:BW с ходу на ум приходят разве что подтупливающие мины и скарабеи риверов, хотя их подтупливание, как правило, связанно с особенностями рельефа и положения юнитов на поле боя. Для сравнения, в том же WC3 различных механик критов/станов/эвейдов, срабатывающих через раз, хоть отбавляй. В WC3 все является механикой игры, а не сайд эффектом.

И самое главное – сложность игры с точки зрения размера пространства состояний – в каждой игре количество действий, доступных для принятия решения, ужасно велико. Истинное мастерство заключается в том, чтобы уметь сразу отсекать большую часть гарантированно невыгодных решений. Именно эту технику и демонстрировал  AlphaGo. Но он играл в Го – игру, в которой количество возможных состояний оценивается как 10 в 170 степени (для сравнения, в шахматах 10 в 50, в Техасском Холдеме - 10 в 85). Количество состояний в StartCraft несоизмеримо больше, грубую оценку этого числа мы дадим чуть позже.

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

Насколько сложен StarCraft для ботов?

Нынешние успехи можно описать следующим образом. В ладдере ICCup редкий бот доходит до ранка D+, в то время как основная масса живых игроков располагается в диапазоне ранков от С до B. Топовые игроки, как и следовало ожидать, располагаются между А и А+. До победы машины над человеком на ICCUp еще очень далеко.

Одна из проблем заключается в том, что для выполнения операций с игровым полем игроку надо понимать, что на нем происходит и что может происходить. Попытка описывать игру на низком уровне (уровень фигур или юнитов/зданий) быстро упрется в астрономическое число возможных игровых ситуаций. А никаких высокоуровневых абстракций в самом начале пути у вас нет.

Для примера, представим, что на карте 128х128 мы хотим расставить 400 юнитов по 1 юниту в клетку (предположим, что все клетки поля проходимы для юнитов). Количество способов, которыми это можно сделать, огромно – 16384 в 400 степени. "Зачем нам это знать?" - спросит кто-то из толпы. Затем, чтобы показать бессмысленность создания ботов, работающих по правилам в духе “если ситуация такая-то, то совершай такие-то действия”. Точнее, бессмысленны описания, опирающиеся на низкоуровневые абстракции, такие как отдельные юниты сами по себе в контексте всей игровой карты. С другой стороны, попробуйте дать описание игровой ситуации, не перечисляя юниты и их положение на карте.

Другой способ показать сложность игры с математической точки зрения - это оценить фактор ветвления в игре  b (branching) и глубину этого ветвления d (depth). Итоговая сложность определяется как b в степени d. Для шахмат эти параметры оцениваются как b≈35 и d≈80. Для го эти параметры оценивают следующим образом: b находится в диапазоне от 30 до 300, d находится в  диапазоне от 150 до 200.

Оценим теперь эти параметры для игры в SC:BW, где ИИ может управлять каждым из юнитов непосредственно (как автоматон в роликах выше). В обычной игре количество юнитов, подконтрольных игроку, может варьироваться от 50 до 200. Соответственно, фактор ветвления b может находиться в диапазоне между u в 50 степени и u в 200 степени, где u среднее количество операций, которое может выполнять каждый юнит. Оценить это значение u непросто. Давайте зададимся некоторыми ограничениями, чтобы дать эту оценку:

  • Рядом с нашим юнитом находится не более 16 вражеских юнитов, которых он может атаковать. Соответственно, приказ атаковать мы можем дать только в отношении этих 16 юнитов.
  • Команда перемещения осуществляется на 1 клетку по 8 главным направлениям: север, юг, запад, восток, северо-запад, северо-восток, юго-запад, юго-восток, а не в произвольную точку карты.
  • Команды “строить” для рабочих, разбиваются на несколько команд движения до точки строительства и последующего выполнения в конечной точке команды “строить”.
  • Мы рассматриваем только расу Теранов.

С учетом таких ограничений можно оценить возможное количество команд для всех юнитов и построек. Так, саплай (Supply depot), который в SC:BW не умеет закапываться, будет всю игру неподвижно стоять на месте (пока его не снесут) – т.е. количество выполнимых для него команд равно 1. В противовес этому выступает призрак (Ghost), для которого число возможных команд равно 43 (по утверждению авторов оригинальной статьи, видимо, действия в инвизе и без него рассматриваются по отдельности). В среднем же юниты могут поддерживать до 20-30 различных операций. С учетом наличия кулдаунов способностей (либо доступной маны) можно ограничиться оценкой в 10 действий (в среднем для расы Теранов). Соединим этот результат с ранее описанным фактором ветвления, получим b ∈ [10 в 50 , 10 в 200]. Чтобы оценить глубину ветвления, предположим, что партия в среднем длится 25 минут, тогда получим d ≈ 25 минут х 60 секунд х 24 fps = 36000.


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