^{В ситуации полной и беспросветной задницы власть в AI сразу забирали военные, и это иногда спасало партию.}

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

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

Давным-давно мой преподаватель профессор Сербин рассказывал байку с сыроваром из Европы. К этому обаятельному толстяку приезжали автоматизаторы и спрашивали, как он делает такой вкусный сыр. Им нужны были эвристики для температуры, густоты и так далее. Сыровар опускал палец в мягкий сыр, медленно и кайфно чертил там дугу, улыбался во всё хитрое лицо и говорил: «Ну как вы не чувствуете!».

Алгоритмизировать процесс гости так и не смогли. Так вот, разработка шла так: мы чертили дуги и хитро улыбались, а парни проигрывали нам в настольный Шакал. И мечтали, что за них отомстит AI.

Что надо знать про игру, чтобы понять, в чём засада с AI

Ядро AI писал разработчик idyury, который уже имел опыт создания машинного интеллекта, но не для таких стратегий. Ситуацию несколько осложняло то, что играть в «Шакала» он поначалу не умел, поэтому тесты первые полгода были просто волшебными.

Принцип «Шакала» достаточно прост – вы играете за трёх пиратов, разведывающих остров и собирающих там клады. Вот так выглядит поле во время партии:



Каждая клетка – это какое-то приключение, например, сундук с золотом, крокодил, пушка, табун диких коней или стрелка, по которой пират немедленно следует дальше. Совокупность стрелок и других элементов рождает сложный навигационный граф, который в каждой новой партии определяет рельеф острова и «узкие места», за которые идёт война.


<sup>Настольные клетки


Для экрана пришлось менять «интерфейс» клеток</sup>

Собственно, «Шакал» изначально был создан в достаточно простой форме преподавателями и студентами МГУ ещё в 70-х. До 2008 он успешно игрался с помощью двух листов бумаги, карандаша и знания теории графов, а после мы существенно переработали его и издали в виде коробки настольной игры. Чертовская простота освоения рождала казусы вроде занявшей на турнире II место 12-летней девочки и родителей, пишущих нам, как их четырёхлетние-пятилетние дети режутся в «остров».

Когда количество проданных коробок в России перевалило за 100.000 штук, мы решили делать приложение. И тут понадобился AI.

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

Одной из ключевых сложностей был достаточно большой набор возможных ячеек на игровом поле с различным действием. Действие некоторых ячеек вообще было уникальным (например, «самолет» или «аборигенка»). Тем не менее, изначально стояла задача построить такую систему, которая позволила бы структурировать всю игровую информацию и унифицировать все подсистемы. Не хотелось заниматься «подгонкой данных» и микронастройками на базе стратегий — нужна была схема, которая позволяет расширять игру любыми типами клеток.

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

Модель данных

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


^{Вид сбоку на игровое поле реальной игры (это старая версия, где монеты были без рельефа). Здесь чёрные пираты хорошо укрепились, и белый не может взять золото, не рискуя оказаться побитым. Но и чёрные также не могут взять монету.}

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


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

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

Для каждого узла графа задается список флажков, характеризующих его текущее состояние с точки зрения активного игрока (например, есть флаг, сигнализирующий о том, что текущий узел находится под атакой вражеского пирата):

enum eLocks
	{
		eLock_Prohibited = 1 << 0, 
		eLock_LandAttack = 1 << 1, 
		eLock_SeaAttack  = 1 << 2, 
		eLock_TrapLock   = 1 << 3, 
		eLock_Unexplored = 1 << 4, 
		eLock_Fortress   = 1 << 5, 
		eLock_ExcludeTrap = eLock_Prohibited | eLock_LandAttack,
		eLock_AllDanger = eLock_Prohibited | eLock_LandAttack | eLock_TrapLock,
	};

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


^{Пример графа для неразведанных ячеек}

Оценочная функция

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

• Разведка, то есть оценка необходимости открытия новых ячеек.
• «Жадная» система, то есть непосредственное взятие монет с разведанных ячеек и доставка их на корабль.
• Система восстановления пиратов – когда один из наших пиратов попадает в беду, часто рациональнее спасать его, чем хвататься за пиастры или бить врага.
• И система атаки вражеских пиратов. Это единственная агрессивная подсистема, задача которой – снизить риски для остальных трёх систем. Забегая вперёд, скажу, что она включается как аварийная, если риски для оптимальных действий в первых трёх подсистемах слишком велики.

Надо сказать, что парни уже делали шахматы и ААА-шутеры со сложными врагами, но у них всегда под рукой была хорошая оценочная функция. Здесь же реализовали симуляцию чужих ходов исходя из своей логики оптимальных действий, а затем оценку к каждой из 4 подсистем. Пришли к набору эвристик для каждого варианта. Затем 4 подсистемы «голосуют» за свои ходы (вес голоса меняется в зависимости от ситуации на доске: например, при одном дееспособном пирате из трёх мы, скорее всего, бросим всё и пойдём спасать друзей). В итоге подобного нормирования получалась одна оценочная функция, которая потом долго балансировалась. Кстати, именно так делаются разные «характеры» ботов – для жадины мы просто можем повысить вес голоса системы взятия монет, а для острожного игрока – системы восстановления. В текущей версии баланс подобран на глаз после примерно двух сотен тестовых партий с опытными игроками. Позже будем использовать результаты реальных игр для обучения AI.

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

AI разведки

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

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


^{Веса ячеек при открывании с точки зрения игрока белого цвета на первом ходу.}

Естественно, если между нами и сундуком на 5 золотых монет лежит одна неразведанная ячейка, ценность её открытия резко повышается. С точки зрения других подсистем, напоминаю, она до открытия рассматривается как пустая. Клетка с врагом и клетки под его атакой резко теряют в весе.

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

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

Система сбора монет

Система сбора монет – самая сложная по нагрузке на процессор. Полный перебор на клиентских устройствах невозможен, поэтому, упрощая, используется метод ветвей и границ, основанный на выборочных просчётах в глубину.

При этом расчеты строятся не на отдельном ходе, а на действии, которое может включать в себя последовательности ходов различной длины. Например, когда надо плыть кораблем в любую возможную точку, или идти пиратом на клетку с монетой. Действия могут объединяться в более сложные действия, например, отнести корабль на монету можно напрямую кратчайшим путем (не обязательно пешком, пушка, воздушный шар или лошадь также учитываются), а можно доставить ее на побережье, куда может быть подогнан корабль другим пиратом. Поиск в глубину перебирает доступные ходы на несколько шагов вперед и выбирает оптимальный. В текущей версии для iPad 2 и iPhone 4 используется глубина в 2-3 хода в зависимости от ситуации, на топовых устройствах можно считать в 4 хода с ожиданием менее секунды. Есть куда оптимизировать по логике работы алгоритма, но пока глубины хватает, чтобы боты хорошо играли на тактическом уровне.

При этом пират всё также избегает нежелательной встречи с врагами. И считает, куда они могут пойти на заданной глубине прогноза.

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


^{Пиастррры!}

Подсистема спасения

Пират может упасть в воду (тогда нужно подогнать корабль с другим пиратом для его спасения), может провалиться в ловушку (нужен второй друг, чтобы его вытащить), может быть съеден людоедом (придётся воскрешать его в крепости с аборигенкой) или попасть в бесконечный цикл (например, стрелка на крокодила), что приведёт к тому, что он сойдёт с ума и погибнет. Для воскрешения тоже нужна крепость и аборигенка.

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

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

Упрощая, если наш друг провалился в ловушку в соседней клетке, оценочная функция назначает 10 очков сложности восстановлению. А если в двух клетках – сложность растёт нелинейно, например, становится уже 30 очков. Далее на основе первичной возможности восстановления отбрасываются гипотезы, которые не нужны в текущей игровой ситуации (чтобы не считать весь комплекс каждый ход, когда нужно заниматься другими вещами). Важность восстановления растёт в зависимости от игровой ситуации, количества наших активных пиратов и лёгкости восстановления.

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

Подсистема атаки

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

Несмотря на просчет в глубину и наличие выполняемых действий, каждый ход делается новая оценка. В результате пират может оперативно изменить свое действие в зависимости от изменения ситуации на игровом поле. Для просчёта выбираются пары пиратов по схеме «я один и противники» на 2 хода вглубь минимум.

В тактическом блоке учитывается влияние игроков на клетки поля и их влияние на золото на поле — это вопрос безопасности наших операций и потенциальной выгоды от того, что мы ворвёмся в чужие. Главный вопрос — сколько пират контролирует золота в перспективе нескольких ходов. Опять же, если наши пираты напрямую контролируют золото или виртуально контролируют золото через 2 хода – приоритет в голосе будет отдан в систему таскания монет, скорее всего. Потому что AI знает, что лучше синица в руках. Также целесообразность включения этой системы напрямую зависит от необходимости расчистки пространства для безопасности – если врагов нет близко, она даже не включается по факту.

Итого

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

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


^{Скриншот режима отладки. Голубой – текущая позиция, желтый — выбранный наилучший ход. Формат вывода: количество пиратов (минус означает противников) | разница атакующих клетку своих и защищающих её чужих | перспективность клетки для сбора золота | итоговый счет клетки. На скрине видно, что желтый решил сходить по диагонали и занять клетку, с которой можно атаковать другую клетку с вражескими пиратами и с запасом золота. Позиция улучшилась при этом с -20.61 до -12.37.}

Реализация и тесты

Здесь я процитирую:

В первую очередь была реализована навигационная система. Эта задача на многих проектах решается приблизительно одинаковым способом, необходимо было только учесть специфику Шакала (пришлось, к примеру, дорабатывать алгоритмы после того, как выяснилось, что упавшие монеты лежат в подслотах «длинных» клеток, а не на ячейке в целом).

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

Первоначальное тестирование проводилось в автоматическом режиме еще на этапе разработки. Сама система управления игрой построена таким образом, что работает универсально. Это изначально было заложено для возможностей мультиплеерной игры. Любой игрок может управляться одним из трех типов контроллеров: человеком, компьютером или удаленным игроком (удаленный игрок также может быть человеком или компьютером). В любой момент игры контроллер одного типа может быть заменен на контроллер другого типа (например, компьютер может занять место игрока, «отвалившегося» от сети, но впоследствии игрок может подключиться заново и вернуться в игру). Для тестирования Шакала в целом и ИИ, в частности, это сыграло очень хорошую службу. Игра запускалась с игроками-компьютерами, и они играли сами с собой. Оставалось только следить за их поведением и собирать статистику. В игре сейчас используется SFMT-генератор случайных чисел, что позволяло по ходам воспроизвести ее заново, если в ней на каком-то этапе возникал момент, требующий отладки или доработки. Подобная методика очень удобно позволяла определять и локализовывать многие проблемы, например, вечные циклы в навигации пиратов, нелогичные или неправильные действия и прочее. Вторым этапом тестирования было тестирование в игре с реальными людьми, которое строилось на похожих принципах, однако для воспроизведения игровой сессии использовалась специально разработанная система протоколирования игровых событий, записывающая и сохраняющая на диске все сыгранные партии. Впоследствии игровая сессия просто воспроизводилась по ходам.

Есть идеи и планы о создании, например, разных поведенческих типов пиратов – трусливый, агрессивный, исследователь и прочие. Хотелось бы реализовать различные уровни сложности для игроков с разным уровнем подготовки.

Собственно, в комментарии можно задавать вопросы idyury по коду и математике. Реализация всего этого вот тут в Аппсторе, только для iPad пока.

И да, AI очень живо не хватает тактик опытных игроков вроде ситуаций, когда сундук с 5 монетами в двух клетках от корабля. Опытный игрок проходит мимо и оставляет таскание на конец партии, но в нашем AI «жадина» получает больше голосов и начинает таскать, залипая на 20 ходов минимум, которые могли бы дать огромное стратегическое преимущество. Но, конечно, если мы увеличим глубину просчёта ситуации на поле – игра пойдёт медленнее, но веселее в плане сложности.

В общем, я просто хотел сказать, что шизофрения — это круто. Иногда.