Поделиться через

Июль 2016

ТОМ 31 НОМЕР 8

C# - Применение искусственного интеллекта к игре в мини-баскетбол с несколькими агентами

Арнальдо Перес Перес

Продукты и технологии:

C#, Windows Forms, Microsoft .NET Framework, применение искусственного интеллекта (AI)

В статье рассматриваются:

  • AI, агенты и система с несколькими агентами в среде игры в баскетбол;
  • реализация конечных автоматов и деревьев поведения (behavior trees) в таких средах;
  • разработка многопоточного C#-приложения для симуляции игры в баскетбол;

Искусственный интеллект (artificial intelligence, AI) сегодня является самой интересной и самой активно исследуемой областью компьютерной науки, и многие его подобласти оказывают большое влияние на нашу повседневную жизнь. AI используется едва ли не повсюду и в самых неожиданных сферах, например когда страховая компания применяет алгоритмы анализа данных для нахождения отношений между индивидуальными лицами (чтобы убедиться, что клиент не затевает мошенничество), когда вы получаете список предлагаемых друзей в Facebook, когда вы играете в видеоигры и т. д. Сферы применения AI колоссальны и включают, в частности, экономику, коммерцию, астрономию, медицину и оборону.

Желание автоматизировать различные задачи, выполняемые человеком, и создать искусственное сознание со временем привело к появлению этой популярной области науки, известной как AI. Его определение, как бы просто оно ни звучало, регулярно вызывает сомнения, поскольку AI представляет, по-видимому, самую широкую сферу в компьютерной науке. С точки зрения эксперта, AI — это автоматизация деятельности, которую мы связываем с человеческим мышлением и действиями, такими как принятие решений, решение задач, обучение и многое другое (см. книгу Ричарда Беллмана [Richard E. Bellman] «Artificial Intelligence: Can Computers Think?», 1978). Предыдущее определение заявляет то, как AI относится к автоматизации человеческой деятельности. Таким образом, возникает вопрос: почему для автоматизации задач, выполняемых человеком, нужно создавать именно AI? Действительно ли это необходимо? Ответ — да.

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

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

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

Желание автоматизировать различные задачи, выполняемые человеком, и создать искусственное сознание со временем привело к появлению этой популярной области науки, известной как искусственный интеллект.

В следующих разделах я опишу некоторые традиционные сущности, системы, связанные с AI, и их взаимодействие. Я покажу, как разработать AI для игры в баскетбол с несколькими агентами (multi-agent basketball game), где возможно наличие двух баскетбольных команд (Bulls и Knicks), играющих друг против друга.

Агенты

В 1990-е годы в компьютерной науке появилась концепция агентов, и теперь этот термин является столь же современным и модным, как и объектно-ориентированный подход в 1980-е или AI в 1970-е. Агент — это некая сущность, способная распознавать свою среду и выполнять действия над ней (Стюарт Рассел [Stuart Russell] и Питер Норвиг [Peter Norvig] «Artificial Intelligence: A Modern Approach», 1997). Главное различие между агентом и обычной программой состоит в том, что первый должен быть автономным, т. е. он должен работать без прямого вмешательства человека или других сущностей. Дополнительное отличие — агент выполняет специфические задачи в интересах кого-то другого (обычно пользователя или программиста), отсюда и слово «агент», поскольку оно как раз и обозначает кого-либо, действующего в интересах других.

Рациональный агент (rational agent) действует так, чтобы добиться лучшего результата или — при наличии неопределенности — лучшего ожидаемого результата (см. уже упомянутую книгу «Artificial Intelligence: A Modern Approach»). Рациональность в этом смысле относится к нахождению правильных выводов и выбор (по мере возможности) такого действия, которое приведет к достижению поставленной цели. Люди являются рациональными агентами; они воспринимают окружающую их среду органами чувств (глазами, ушами, языком и носом) и в конечном счете действуют, двигая ногами, руками и т. д., как правило, после каких-то логических рассуждений и выбора действий, ведущих к желаемой цели.

Объект восприятия (percept) относится к приему ввода агентом в любой момент времени. Последовательность восприятия (percept sequence) представляет полную последовательность объектов восприятия, которые агент распознал или воспринял в течение срока своей жизни. Функция агента (agent function) представляет поведение агента, сопоставляя любую последовательность восприятия с каким-либо действием. Эта функция является чисто абстрактным описанием; настоящая реализация этой абстракции заключена в программе агента. В табл. 1 показана частичная функция агента для игрока в баскетбол. В столбце «Последовательность восприятия» перечислены состояния игрока, а в столбце «Действие» указывается действие, которое должно быть выполнено после соответствующей последовательности восприятия.

Табл. 1. Частичная функция агента для игрока в баскетбол

Последовательность восприятия Действие
Близость к корзине, не блокирован Бросок
Близость к сопернику, соперник бросает мяч Блок
Соперник теряет мяч Перехват
Блокирован, товарищ по команде не блокирован Передача
Товарищ по команде близок к корзине, не блокирован, умеет добивать мяч в прыжке (good slammer), визуальный контакт (eye connection) Наброс на кольцо

Вы могли бы разбить агенты на следующие категории согласно их архитектуре.

  • Реактивный агент (reactive agent) Способен поддерживать постоянное взаимодействие с окружающей средой и своевременно реагировать на изменения в ней. Этот термин теперь широко используется для обозначения системы, которая не включает поддержки символьного представления (symbolic representation) или построения логического вывода (reasoning); такой агент не размышляет о долгосрочных эффектах своего действия и не координирует деятельность с другими агентами. Таким образом, реактивный агент всегда своевременно реагирует на внешний раздражитель и управляется событиями. Это можно реализовать с помощью простых правил if-then. Цели агента лишь неявно представляются правилами, и трудно гарантировать его желательное поведение. Абсолютно все ситуации следует продумать заранее, а значит, в сложных средах реактивные системы обычно содержат сотни правил. Реактивные агенты не имеют никакой внутренней модели мира и поэтому неспособны к построению логического вывода о нем каким-либо абстрактным способом. Еще раз подчеркну, что агент лишь принимает ввод и реагирует на него по простым правилам.
  • Упреждающий агент (pro-active agent) Способен проявлять инициативу, не управляется только событиями, может генерировать цели и рационально действовать для их реализации. Некоторые считают его реактивным агентом, управляемым целями (goal-driven reactive agent).
  • Делиберативный агент (deliberative agent) Представляет знания в символьном виде и использует такие ментальные понятия, как принципы, намерения, желания, предпочтения и т. д. Он пытается моделировать человеческую логику, децентрализованную активность (distributed activities) и поведение через логические представления. Обычно реализуется посредством архитектуры BDI (believe, desire, intention). Он может строить логические заключения о прошлом и планы на будущее; планирование является важным в этом типе архитектуры.
  • Гибридный агент (hybrid agent) Сочетает в себе смесь некоторых или всех архитектур.

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

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

Система с несколькими агентами

Когда агент сосуществует в какой-то среде с другими агентами (возможно, действуя совместно или конкурируя с ними), такой вариант считается системой с несколькими агентами (multi-agent system, MAS). В MAS-средах у каждого агента свое понимание мира и нет никаких знаний о внутренних состояниях других агентов или о том, как они видят эту среду. Таким образом, MAS представляет тип распределенной системы со следующими особенностями:

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

Коалиция (coalition) — любое подмножество агентов в среде. Для игры в баскетбол используются две коалиции — команды A и B, область пересечения (intersection) которых пуста, и обе имеют одинаковое количество элементов множества (кардинальность) (cardinality), большее нуля.

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

В MAS взаимодействие осуществляется посредством коммуникации, и существуют разные формы коммуникации агентов; обычные сигналы, подходящие для фиксированных интерпретаций, по-видимому, являются наивной формой коммуникации между агентами. Структура с доской объявлений (blackboard structure) — это форма коммуникации через общий ресурс, поделенный на разные области окружающей среды, где агенты могут считывать или записывать любую важную информацию для их действий. Передача сообщений между агентами — другая форма коммуникации. В этом случае агенты обмениваются сообщениями с заданным синтаксисом и по определенному протоколу, но семантика отсутствует; таким образом, принимающему агенту нужно логически определить предназначение сообщения. Наконец, теория речевых актов (speech act theory), в развитие которой внес большой вклад американский философ Джон Роджерс Сёрл (John R. Searle) в 1969 году («Speech Acts: An Essay in the Philosophy of Language») и канадский специалист по логике Дэниэль Вандервекен (Daniel Vanderveken) в 1994 году («Foundations of Speech Act Theory»), позволяет преодолеть недостатки передачи сообщений, выводя взаимодействие между агентами на два уровня: информационного содержания и предназначения сообщения. При этом подходе проводится различие между локутивным актом (locution act) (слова, фразы), локутивным намерением (locution intention) (информирование, просьба, приказ и т. д.) и желаемым результатом локуции (оскорбление, убеждение и др.).

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

Кооперация необходима как результат дополняющих навыков и взаимозависимости между действиями агентов и неизбежностью удовлетворения какому-то критерию успеха. В кооперативной модели агенты имеют коллективную мотивацию или интерес; следовательно, они работают на достижение некоей общей цели. Другая возможная модель — агенты являются инициативными (self-motivated) или движимые собственными интересами (self-interested). Каждый агент имеет свои цели и может вступать в соперничество с другими агентами в системе для достижения этих целей. В этом смысле соперничество может относиться к выполнению или распределению определенных задач. В таких моделях агентам нужно координировать свои действия с другими агентами, чтобы гарантировать согласованное поведение. В процессе координации как в кооперативной, так и в конкурентной среде могут возникать конфликты, которые разрешаются посредством согласования (negotiation). Согласование можно рассматривать как процесс идентификации взаимодействий на основе коммуникации и построения логических выводов о состоянии и намерениях других агентов.

В следующем разделе я опишу необычную и интересную структуру данных, которая присутствует во многих современных видеоиграх: дерево поведения (behavior tree).

Конечные автоматы и деревья поведения

Традиционный подход к моделированию принятий решений, выбору действий и поведению агента в играх основан на конечных автоматах (finite state machines, FSM). FSM представляет математическую модель, состоящую из конечного набора состояний и функции перехода. FSM обеспечивает простой, интуитивно понятный механизм для реактивного поведения, обработки и реагирования на постоянные потоки событий или ввода.

Рис. 1иллюстрирует простое моделирование поведения агента на основе FSM, когда он оказывается на расстоянии до корзины, которое считается близким (close). В этот момент он переключается на поведение Shoot (бросок). В этом сценарии состояния соответствуют поведениям и переходам. Главный недостаток FSM проявляется, когда возникает необходимость в расширении его функциональности или реализации более сложного поведения. В таких случаях количество переходов между состояниями может расти по экспоненте, делая FSM чрезвычайно трудным для понимания и обработки.

Простая модель на основе конечного автомата
Рис. 1. Простая модель на основе конечного автомата

Moving Переход
Close to Basket Близко к корзине
Shoot Бросок

Деревья поведения (behavior trees, BT) — простое, масштабируемое, модульное решение, представляющее сложные AI-поведения и обеспечивающее удобную в сопровождении и настройке логику. Их применение в игровой индустрии значительно расширилось в последние несколько лет, в частности такие игры, как Halo 3, Spore, BioShock и SWAT 4, включают BT как средства моделирования поведения. BT являются ориентированными на цели, и каждое дерево относится к отдельной высокоуровневой цели. BT можно связывать вместе, что делает возможной реализацию сложных поведений, где сначала определяются меньшие по функционалу подчиненные поведения (sub-behaviors).

Каждый узел в BT — это либо элементарная конструкция (primitive construct), либо составная (composite construct). Первый тип образует листья дерева, а второй — представляет способ описания взаимосвязей между дочерними узлами.

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

На рис. 2 показано BT с двумя дочерними узлами: условием C и действием A.

Дерево поведения с двумя дочерними узлами
Рис. 2. Дерево поведения с двумя дочерними узлами

Sequence Последовательность
Counter 10 Счетчик 10
Is OpponentReachable Доступна ли корзина сопернику
Block Path Путь блокировки

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

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

Наконец, декораторы, взятые из проектировочных шаблонов, предоставляют способ, который позволяет упростить процесс программирования и расширять поведение добавлением функциональности к узлу. Timer Decorator мог бы быть разновидностью декоратора, который, как и предполагает его название, выполнял свои дочерние узлы через определенные интервалы времени. С другой стороны, Counter Decorator, мог бы выполнять дочерний узел или поведение несколько раз в соответствии со счетчиком. На рис. 2 счетчик-декоратор D будет выполнять узел Sequence 10 раз.

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

Игра в баскетбол и реализация AI

Поскольку баскетбол — это большая и сложная игра, которая потребовала бы сложного FSM или по-настоящему крупного BT, в этой статье обсуждается только упрощенная версия данной игры, включающая некоторые базовые стратегии атаки и защиты. В этой игре будут два игрока (A1->черный, B1->серый), каждый со свойствами Speed (скорость) и Shooting Accuracy (точность броска). Первое свойство определяет, насколько быстро или часто игрок реагирует на изменения в среде, а второе — вероятность того, что игрок забьет гол при попытке броска. Изначально игроки находятся в центре, как показано на рис. 3. Счет — 0:0, а время — 0 секунд. Если игрок не забил гол в течение 15 секунд, инициируется превышение лимита времени на атаку (shot-clock violation) и этот игрок теряет мяч. GUI игры состоит из приложения Windows Forms, которое вы потом сможете просмотреть, чтобы понять интересующие вас детали графики. Кнопка Start, как и следовало ожидать, запускает игру, а кнопка Stop — останавливает.

Игра в баскетбол с реализацией AI
Рис. 3. Игра в баскетбол с реализацией AI

Темные квадраты обозначают корзины, а белый кружок представляет мяч. Давайте начнем с анализа класса Court, который соответствует баскетбольной площадке; он содержит поля, перечисленные на рис. 4.

Рис. 4. Класс Court

public class Court
{
public int Height { get; set; }
public int Width { get; set; }
public Point BallPos { get; set; }
public int ScoreTeamA { get; set; }
public int ScoreTeamB { get; set; }
private readonly string[,] _grid;
public Court(int h, int w)
  {
Height = h;
Width = w;
_grid = new string[h,w];
  }
...
}

Поля Height и Width понятны и без объяснений. BallPos указывает позицию мяча на площадке. ScoreTeamA и ScoreTeamB сообщают счет для каждого игрока, а _grid является строковой матрицей, содержащей логику площадки. Если игрок A1 находится в ячейке (0,0) и владеет мячом, то значение _grid [0, 0] = A1,B. То же самое относится к игроку B1, следовательно, возможные значения любой ячейки в сетке равны A1, B1, A1,B и B1,B. Методы-индексаторы, реализованные в этом классе, показаны ниже (индексатор обеспечивает индексацию элементов сетки; кроме того, он обновляет позицию мяча на площадке):

public string this[int i, int j]
{
get { return _grid[i, j]; }
set
  {
    _grid[i, j] = System.String.Format("{0}", value);
if (IsBall(value))
    BallPos = newPoint(i, j);
}
}

Метод IsBall определяет, содержится ли мяч в данной строке:

private bool IsBall(string s)
{
 return s.Split(',').Contains("B");
}

Метод IsEmpty определяет, пуста ли ячейка сетки:

public bool IsEmpty(int i, int j)
{
 return string.IsNullOrEmpty(_grid[i, j]);
}

Наконец, метод ToWallGrid возвращает матрицу PathNode (рис. 5); она будет использоваться в алгоритме нахождения пути, который я вскоре поясню.

Рис. 5. Метод ToWallGrid

public PathNode[,] ToWallGrid()
{
var wallGrid = newPathNode[Height, Width];

for (var i = 0; i < Height; i++)
  {
for (var j = 0; j < Width; j++)
 {
wallGrid[i, j] = newPathNode
  {
    IsWall = !string.IsNullOrEmpty(_grid[i,j]),
    X = i,
    Y = j,
  };
}
}
return wallGrid;
}

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

Класс BehaviorTree и все его потомки структурируются согласно схеме на рис. 6.

Структура класса BehaviorTree
Рис. 6. Структура класса BehaviorTree

Код для каждого класса, относящегося к BehaviorTree, приведен на рис. 7.

Рис. 7. Код для каждого класса, относящегося к BehaviorTree

public abstract class BehaviorTree
  {
public List<BehaviorTree> Children { get; set; }
public BehaviorTree Value { get; set; }
public Court Court { get; set; }

protected BehaviorTree(Court court)
{
  Court = court;
}

public abstract bool Exec();
  }

public abstract class Primitive : BehaviorTree
  {
protected Primitive(Court court) : base(court)
{
}
  }

public class Action: Primitive
  {
public delegate bool Act();
public Act Function { get; set; }

public Action(Court court):base(court)
{
}

public override bool Exec()
{
return Function();
}
  }

public class Conditional : Primitive
  {
public delegate bool Pred();
public Pred Predicate { get; set; }

public Conditional(Court court)
  : base(court)
{
}

public override bool Exec()
{
return Predicate();
}
  }

public abstract class Composite : BehaviorTree
  {
protected Composite(Court court):base(court)
{
}
  }

public class Sequence: Composite
  {
public Sequence(Court court)
  : base(court)
 {

}

public List<int> Order { get; set; }

public override bool Exec()
{
if (Order.Count != Children.Count)
throw new Exception(
  "Order and children count must be the same");

foreach (var i in Order)
{
if (!Children[i].Exec())
return false;
}

return true;
}
  }

public class Selector : Composite
  {
public Selector(Court court)
  : base(court)
{

}

public int Selection { get; set; }

public override bool Exec()
{
return Children[Selection].Exec();
}
  }

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

Самый важный класс в приложении — Player; он представляет сам агент и инкапсулирует его поведение и весь код AI. Это поведение делится на атакующее и защитное; первое моделируется через FSM, а второе — с использованием простого BT вроде показанного на рис. 2. Player содержит поля, перечисленные на рис. 8.

Рис. 8. Поля класса Player

public class Player
{
public Point Position { get; set; }
public string Name { get; set; }
public int Number { get; set; }
public int Speed { get; set; }
public double ShootingAccuracy { get; set; }
public bool BallPossession { get; set; }
public Point ScoringBasket { get; set; }
public LinkedList<PathNode> Path;
private readonly Court _court;
private readonly Random _random;
public Player(Court court, Point basket)
  {
    ScoringBasket = newPoint(basket.X, basket.Y);
    _court = court;
    Path = newLinkedList<PathNode>();
    _random = newRandom();
  }
}

Position определяет позицию игрока на площадке. ScoringBasket — это место, где он должен забивать голы на площадке. Path — список PathNode, используемых для нахождения кратчайшего пути от одной начальной точки до другой с учетом препятствий на пути, а _random — объект Random, используемый для получения вероятности совершения броска. Остальные поля понятны без пояснений.

Этот класс использует следующие перечисления:

public enum Percept
{
  Guarded,
  CloseToBasket,
  BallLoose,
  BallInPossession,
  OnDefense,
  None
}

public enum Direction
{
  Up, Down, Left, Right
}

Класс Player содержит методы-предикаты и Action. Предикатов три:

private bool IsBallLoose()
{
return _court[_court.BallPos.X, _court.BallPos.Y] == "B";
}

private bool IsCloseToBasket()
{
return Math.Abs(Position.X - ScoringBasket.X) <= 1 &&Math.Abs(
  Position.Y - ScoringBasket.Y) <= 1;
}

Метод IsBallLoose просто определяет, свободен ли мяч на площадке, а метод IsCloseToBasket — близок ли игрок к корзине:

private bool IsOpponentReachable()
{
var opponents = FindOpponents();
var factor = ScoringBasket.Y == 0 ? 1 : -1;

foreach (var opponent in opponents)
  {
if ((Position.Y - opponent.Y) * factor >= 0)
return true;
  }

return false;
}

IsOpponentReachable указывает вероятность досягаемости одного из соперников на площадке; переменная factor помогает решить, находится ли соперник в досягаемой позиции.

Прежде чем рассматривать код блока Actions, давайте проанализируем два метода, которые вызываются сразу после выполнения агентом какого-либо действия:

public void Action()
{
var percepts = GetPercepts();

if (percepts.Contains(Percept.CloseToBasket))
Shoot();
else if (percepts.Contains(Percept.BallLoose))
MoveToBall();
else if (percepts.Contains(Percept.BallInPossession))
MoveToBasket();
else if (percepts.Contains(Percept.OnDefense))
Defend();
}

Этот метод представляет функцию агента; он получает набор percepts и реагирует или решает, какое действие следует предпринять на основе анализа percepts (рис. 9).

Рис. 9. Функция агента

private IEnumerable<Percept> GetPercepts()
{
var result = newList<Percept>();

if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (IsBallLoose())
result.Add(Percept.BallLoose);
if (IsCloseToBasket())
result.Add(Percept.CloseToBasket);
if (BallPossession)
result.Add(Percept.BallInPossession);
else
result.Add(Percept.OnDefense);

return result;
}

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

Метод FeasibleMoves действует как фильтр: как только агент решает совершить перемещение в определенном направлении, он проверяет список направлений от FeasibleMoves и смотрит, является ли направление, куда он собирается переместиться, действительно возможным; если оно невозможно, никакое действие не выполняется. Метод Move, включающий вызов метода FeasibleMoves, показан на рис. 10.

Рис. 10. Метод Move

private void Move(Direction direction)
{
if (!FeasibleMoves().Contains(direction))
return;

  _court[Position.X, Position.Y] = "";

switch (direction)
  {
case Direction.Left:
Position = newPoint(Position.X, Position.Y - 1);
break;
case Direction.Right:
Position = newPoint(Position.X, Position.Y + 1);
break;
case Direction.Up:
Position = newPoint(Position.X - 1, Position.Y);
break;
case Direction.Down:
Position = newPoint(Position.X + 1, Position.Y);
break;
  }

// Записываем его корректное значение в сетку
_court[Position.X, Position.Y] = (_court.BallPos.X ==
  Position.X && court.BallPos.Y == Position.Y) ||
  BallPossession
? Name + ",B"
: Name;

if (_court[Position.X, Position.Y].Split(',').Contains("B"))
BallPossession = true;
}

Метод MoveToBall перемещает игрока к мячу в случае, если тот свободен на площадке:

private void MoveToBall()
{
var ballPos = _court.BallPos;

if (ballPos.X == Position.X)
Move(ballPos.Y>Position.Y ? Direction.Right : Direction.Left);
else if (ballPos.Y == Position.Y)
Move(ballPos.X>Position.X ? Direction.Up : Direction.Down);
}

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

Рис. 11. Метод MovetoBasket

private void MoveToBasket()
{
if (Path.Count == 0)
  {
    Path = new LinkedList<PathNode>(PathFinding(
      Position, ScoringBasket));
    Path.RemoveFirst();
  }

// Стратегия уже есть
if (Path.Count > 0)
  {
var nextMove = Path.First();
  Path.RemoveFirst();

// Проверяем, по-прежнему ли доступно перемещение
if (string.IsNullOrEmpty(_court[nextMove.X, nextMove.Y]))
MoveDecision(nextMove);
else
Path.Clear();
  }
}

MoveToBasket формирует путь от позиции игрока до корзины; если план проваливается или становится неосуществимым, данный путь стирается и вычисляется заново. PathFinding относится к алгоритмам поиска; в данном случае это алгоритм A*. Алгоритмы поиска пути часто реализуются в искусственном интеллекте и чрезвычайно распространены в играх.

Самый важный класс в приложении — Player; он представляет сам агент и инкапсулирует его поведение и весь код AI.

Как упоминалось ранее, поведение в защите вырабатывается с использование BT (рис. 12).

Рис. 12. Поведение в защите на основе дерева поведения

private void Defend()
{
DefensiveBehavior(_court).Exec();
}
private BehaviorTree DefensiveBehavior(Court court)
{
var isReachableNode = new Conditional(court)
{
  Predicate = IsOpponentReachable
};

var blockNode = new Action(court)
{
  Function = BlockPath
};

var defenseBehavior = new Sequence(court)
{
  Order = new List<int> {0,1},
  Children = new List<BehaviorTree>
    {
isReachableNode,
blockNode
    }
};

return defenseBehavior;
}

Метод BlockPath представляет стратегию, по которой игрок пытается блокировать ближайший путь соперника к корзине. Он полагается на метод Closest, который использует манхэттенское расстояние (Manhattan Distance) для нахождения ближайшего соперника (рис. 13).

Рис. 13. Метод BlockPath

private bool BlockPath()
{
var closestOppPos = Closest(FindOpponents());

// Перемещаемся в ту же строку
if (closestOppPos.X > Position.X)
Move(Direction.Down);
else if (closestOppPos.X < Position.X)
Move(Direction.Up);
// Перемещаемся в тот же столбец
else if (closestOppPos.Y > Position.Y)
Move(Direction.Right);
else if (closestOppPos.Y < Position.Y)
Move(Direction.Left);

return true;
}

Заключение

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

{Для верстки: в следующем абзаце есть испанские буквы с диакритическими знаками}

Арнальдо Перес Кастаньо (Arnaldo Pérez Castaño) — ученый в области компьютерных наук, живет на Кубе. Автор серии книг по программированию: «JavaScript Fácil», «HTML y CSS Fácil» и «Python Fácil» (Marcombo S.A.). Пишет для VisualStudioMagazine.com и Smashing Magazine. Эксперт в области Visual Basic, C#, .NET Framework и искусственного интеллекта. Предлагает свои услуги как фрилансер через сайт nubelo.com. Увлекается, в том числе, кино и музыкой. С ним можно связаться по адресу arnaldo.skywalker@gmail.com.

Выражаю благодарность за рецензирование статьи эксперту Microsoft Джеймсу Маккафри (James McCaffrey).

Discuss this article in the MSDN Magazine forum